アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found

2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf

[teddy-g]

べき乗で繰り返すと速い

[hagayu]

べき乗を使った文字列の連結。

[lesamoureuses]

べき乗を使った文字列の連結。同じ文字列限定だから使う機会があれば。

[Cutter]

ビット演算を使用しているのはjavascriptに整数型が無いからであって、高速化のためじゃないよ。Cなら「n >>= 1」は「n /= 2」、「n & 1」は「n % 2」って書けるんだけどね、みたいな。

[hiratake55]

ビット演算を使うので高速

[fumokmm]

べき乗

[xmx3]

こういうときビット演算が出てこないんだよな

[mongrelP]

何故てってってー？

[snaka72]

すばらしい

[edvakf]

コメント欄「あああ」氏に同意せずにはいられない。

[ezil]

何故てってってー？

[seiunsky]

JavaScriptで文字列の連結

[TakiTake]

予めまとめてから連結する。

[sankaseki]

404 Blog Not Found:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法

[emergent]

べき乗のアルゴリズムを文字列の連結にも

[SiroKuro]

Haskell すげー

[ryomiyo]

同じ文字列のn回繰り返しをlog n回で作る

[maraigue]

「てってってー」がこんなところで出てくるとはｗｗ アルゴリズム自体ももちろん参考になりますよ。

[miya2000]

「n *= 1」を入れて「str += ''」を入れないのは片手落ちでしょう。

[at_yasu]

ビット演算で "aaa" x n を実装した話

[raimon49]

べき乗

[jar2]

爆速！！

[maangie]

冪乗。

[pokutuna]

ほー

[murky-satyr]

n が負の時におかしくなるから「for(n *= n > 0; n; n >>= 1, str += str) if(n & 1) result += str;」かなぁ

[Yuichirou]

「n回繰り返しをlog n回で」ってのはアルゴリズムの問題でよく見かけますね。

[dankogai]

べき乗のアルゴリズムの応用; for(n *= 1; n > 0; n >>>= 1, str += str) ... としました＞id:murky-satyr