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で一個一個まわすよりも早いですね。
勉強になりました。

参照

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