高速な同一の文字列結合

クソではないと言ったが、同一の文字列連結に関してはもっと高速なアルゴリズムがある。

たとえばxからxxxxxxxxという文字列を生成するなら

x + x

xx + xx 

xxxx + xxxx

普通にループすると8回の結合が必要だが3回で済む。このアルゴリズムを適用したパディングのコードを書くと以下のようになる。

'use strict';

function leftpad4(str, len, ch) {
    str = String(str);

    if (!ch && ch !== 0) ch = ' ';
    ch = String(ch);

    var max = len - str.length;
    for (var i = ch.length; i < max; i = i << 1) {
        ch += ch;
    }
    return ch.slice(0, max) + str;
}

では速度を比較してみよう。

結果

node v4.3.1, MacOSX 10.9.5, 2.5GHz Core i7, Memory 16GB DDR3

padding len 4 8 16 32 64 128
leftpag1 concat with + 12 77 166 294 544 1005
leftpad2 repeat and substring 68 92 179 210 276 401
leftpad4 fast concat algorism 31 56 165 202 251 395

パディングする桁が大きくなるほどleftpad1と比較してleftpad4がより高速になり、String.prototype.repeatを使ったバージョンと似た傾向を示した。実はrepeatはこのアルゴリズムを使っているので同じような処理速度となる。

ところで、パディングについてはさらに高速な手法もあったりするのだが…。ま、ヒマな人は考えてみてください。