読者です 読者をやめる 読者になる 読者になる

No Programming, No Life

新しいNPNLです。http://d.hatena.ne.jp/fumokmm/ から引っ越してきました。

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

プログラミング

404 Blog Not Found:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法
で面白いアルゴリズムがあった。

「ある文字列のn回繰り返しを作る関数」を高速化したいらしい。
Groovyとかだと 「"..." * n」 みたいな感じで実現できるやつですね。

ちょっとコードを拝借(JavaScript)

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

なるほど! str += str で一気に足していくわけですね。

アルゴリズムのイメージ


1回目: str = 'a'
2回目: str = 'a' + 'a' => 'aa'
3回目: str = 'aa' + 'aa' => 'aaaa'
4回目: str = 'aaaa' + 'aaaa' => 'aaaaaaaa'




これならforで一個一個まわすよりも早いですね。
勉強になりました。