2009年01月31日 01:00 [Edit]

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

これなのですが....

同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang
ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。

なぜかもっとシンプルな奴がなかったので。


以下、比較。初期値はIEにあわせてあります。Firefox/Safari/Opera/Chromeでは桁を2つほど増やしてみてください。

str =  n =

Naive

function (str, n){
    var result = '';
    for (var i = 0; i < n; i++) result += str;
    return result;
};

log n

function (str, n){
    var result = '';
    for(n *= 1; n > 0; n >>>= 1, str += str) if (n & 1) result += str;
    return result;
}

アルゴリズムは、実は

と同様です。

どのブラウザでもご利益がありますが、特にIEだと多大なご利益があります。"てってってー" x 10000 程度でも60倍近い速度差が出ました。驚異的なのがChromeで、1000000、すなわち100万回でも log n アルゴリズムは 0 msでした。

Enjoy!

Dan the Algorithmic JavaScripter


この記事へのトラックバックURL

この記事へのトラックバック
ref: http://blog.livedoor.jp/dankogai/archives/51172176.html ref: http://d.hatena.ne.jp/odz/20090203/1233676468 問題1 C で Dan さんが挙げられた 2 つのアルゴリズムと同様のものを実装せよ。 問題2 n を変化させながら、計算時間がどのように変化するか観察せよ。
Re: 文字列の繰り返しと計算量【まめめも】at 2009年02月04日 04:06
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法  http://blog.livedoor.jp/dankogai/archives/51172176.html function (str, n){ var result = ’’; for(n *= 1; n > 0; n >>>= 1, str += str) if (n & 1) result += str; return result...
巨大回数の繰り返し - JavaScript【c4se記】at 2009年02月04日 00:55
404 Blog Not Found:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 で面白いアルゴリズムがあった。 「ある文字列のn回繰り返しを作る関数」を高速化したいらしい。 Groovyとかだと 「”...” * n」 みたいな感じで実現できるやつですね。 ちょっとコード(Jav...
[プログラミング]Re:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法【No Programming, No Life】at 2009年02月03日 00:14
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 - 404 Blog Not Found function (str, n){ var result = ''; for(n *= 1; n > 0; n >>>= 1, str += str) if (n ...
べき乗アルゴリズム - 下位桁編【読断と変見】at 2009年02月02日 02:53
404 Blog Not Foundで同じ文字を高速に繰り返し入力する際のアルゴリズムが公開されています。 コードは以下となります。 function (str, n){ var result = ''; for(n *= 1; n &gt; 0; n &gt;...
高速に同じ文字を繰り返し入力するときのアルゴリズム【STEEL-PLATE - 鉄板管理人のWeb事情】at 2009年02月01日 09:08
久しぶりにプログラミングのことで、反省しなければならないことを読んだ。確かに反省しなければならないけれど、まずは感動した。404 Blog Not Foundアルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法単純な繰り返しのループなんて、for(i=0; i&lt;n; i++){ ... }...
アルゴリズムへの感動【止まらずに走れ!】at 2009年01月31日 08:52
この記事へのコメント
凄い!美しい!素直に感動しました。
リンク先のWikipediaも見てみたんですが、バイナリ法知ってるだけではこのコードは書けないですね。
「str += str」が指数関数的に増えていくのと、数値の2進数表現をこんな風に応用するとは・・・感服いたしました。
Posted by tetz at 2009年02月09日 23:29
successive squaring ですね。SICP にもありました。
n のビット演算で繰返しを制御するなんて巧妙。。
でも与えられてみると実に自然ですね。
Posted by いけ田 at 2009年02月01日 14:39
黄金のガイドブックで初めて拝読し、ブログを拝見致しました。
本文が大文字のレイアウトってとても見やすいですね。
C言語やPerlの本も技術者ではありませんが読んで見たいです!
Posted by ボサノバ at 2009年02月01日 11:20
スターリングだった。まあどっちでも良いか。
Posted by すたーりんぐ at 2009年01月31日 16:36
スターリンの公式
Posted by すたーりん at 2009年01月31日 16:34
「同じ文字列のn回繰り返しを解く」という問題なら、このアルゴリズムはあり。
 
ただ、+とjoinの速度の違いを知るという目的なら
あまり意味は無いかな。これは単に連結回数を減らしているだけだし。
それに文字列の連結はあっても、同じ文字列の連結ってあまりしないし。

元記事の人は+とjoinの速度の違いを調べているんだと思う。
連結するのが同じ文字列であるのはたまたま。
Posted by あああ at 2009年01月31日 15:14
str += strがlog nで
result += strがlog n以下
でlog nなんですよね。
Posted by order_no_nazo at 2009年01月31日 13:04
log n版、IE8RC1で100000000でも2msでした。報告まで。
Posted by matarillo at 2009年01月31日 06:16
LiosKさん、
n *= 1は、nがnumberであることを強制するためのおまじないです。
なくても動きます。
Dan the JavaScripter
Posted by at 2009年01月31日 01:45
n *= 1
って何ですか?
Posted by LiosK at 2009年01月31日 01:29