Re: 文字列の繰り返しと計算量

ref: http://blog.livedoor.jp/dankogai/archives/51172176.html
ref: http://d.hatena.ne.jp/odz/20090203/1233676468

問題1
C で Dan さんが挙げられた 2 つのアルゴリズムと同様のものを実装せよ。
問題2
n を変化させながら、計算時間がどのように変化するか観察せよ。
問題3
2 つのアルゴリズムについて計算量はどうなるか。
文字列の繰り返しと計算量 - odz buffer

これはなかなか難問ですね。JavaScript の文字列の実装で使われているデータ構造と、加算の最適化の有無によって変わってくると思います。軟弱なので実装や実験はしませんが、問題 3 だけ考えてみます。

フラットなメモリ＋最適化なし

文字列を malloc で確保したようなベタなメモリで実装していて *1 、かつ str1 += str2; というコードを単純に str1 = str1 + str2; と解釈する *2 場合。
「Naive」版だと長さ 1 〜 n の文字列を確保することになるので、O(n^2) 。
「log n」版だと長さ 1 の文字列、2 の文字列、4 の文字列、8 の文字列、……だけ確保することになるので、O(n log n) O(n)。

フラットなメモリ＋最適化あり

データ構造は同じですが、str1 += str2; を「str1 のメモリを多めに確保しておいて、終端に余裕があれば memcpy するだけ。足りなくなったら倍の長さに realloc する」という風に実行した場合 (詳細) 。倍に伸ばしていくため、realloc するコストは無視できます。
「Naive」版だと長さ n の文字列分だけ memcpy をする必要があるので、O(n) 。
「log n」版でも同様で O(n) 。ただし、memcpy を call するオーバーヘッドが n 回から log n 回に減るので、オーダは変わらないけれど係数が小さくなって、実用的には結構効くという噂です。
Firefox の JavaScript エンジンである SpiderMonkey はたぶんここなんじゃないかと思います。関係ないけど Ruby の String#* もこの log n 版のアルゴリズムです (ruby-core:16005) 。

Rope

文字列を Rope で実現する場合。これだと、結合演算が O(1) でできます。
「Naive」版だと n 回の結合があるので、O(n) 。
「log n」版だと log n 回の結合でいいので、O(log n) 。
Chrome はたぶんここです。いちおう Chrome の JavaScript エンジンである v8 のソースを読んでみたら、ConsString とかいうクラスがありました。objects.h より:

// The ConsString class describes string values built by using the
// addition operator on strings.  A ConsString is a pair where the
// first and second components are pointers to other string values.
// One or both components of a ConsString can be pointers to other
// ConsStrings, creating a binary tree of ConsStrings where the leaves
// are non-ConsString string values.  The string value represented by
// a ConsString can be obtained by concatenating the leaf string
// values in a left-to-right depth-first traversal of the tree.

これはたぶん Rope です。*3

まとめ

Naive 版 log n 版 実装例
フラットなメモリ＋最適化なし O(n^2) O(n log n) O(n)
フラットなメモリ＋最適化あり O(n) O(n) Firefox
Rope O(n) O(log n) Chrome

だと思います。間違ってたら教えてください。

追記: コメントをいただいて修正。簡単に実験してみましたが、実際 O(n) になるようでした。

*1:実際に malloc するかはどうでもよくて、連続したメモリ領域 (char * みたいなの) を使って実装するということ。

*2:str1 + str2 を表すメモリを新たに確保して、str1 に代入する、ということ。

*3:確認したのは ConsString が定義されているということだけで、JavaScript レベルの文字列が本当に ConsString で実現されているかどうかは確認してないです。が、まあ多分使ってると思います。