From: Tanaka Akira <akr@...17n.org>
Date: 2001-05-13T19:04:17+09:00
Subject: [ruby-list:29640] string joining with O(n)

$B:G6a!"(BArray $BCf$K$"$kBgNL$N(B String $B$r(B join $B$9$k5!2q$,$"$C$?$N$G$9$,!"$d(B
$B$1$KCY$$$3$H$K5$$,$D$-$^$7$?!#(B

$B<!$N$h$&$K$7$FD4$Y$F$_$k$H!"MWAG?t$KBP$7$FHs@~7A$K=hM};~4V$,A}2C$7$F$$(B
$B$k$3$H$,$o$+$j$^$7$?!#(B

def time
  a = Process.times
  yield
  b = Process.times
  return b.utime - a.utime
end

a = []
while true
  t = time {a.join}
  print "#{a.length} #{t}\n"
  a << ('x' * 10240)
  STDOUT.flush
end

$B$H$j$"$($:(B

def joinstrings(ss)
  l = 0
  ss.each {|s|
    l += s.length
  }
  result = ' ' * l
  i = 0
  ss.each {|s|
    result[i, s.length] = s
    i += s.length
  }
  return result
end

$B$H$$$&4X?t$r:n$C$F@~7A$K2!$($k$3$H$K$O@.8y$7$?$N$G$9$,!"$J$K$+$b$C$H$&(B
$B$^$$J}K!$O$J$$$b$N$G$7$g$&$+(B?
-- 
[$BEDCf(B $BE/(B][$B$?$J$+(B $B$"$-$i(B][Tanaka Akira]
$B!V$U$($m(B! $B$o$+$a$A$c$s:n@o$G$9$(C"=$B!W(B(Little Worker, $B7KM7@84](B)