同じ文字列のn回繰り返しを作る方法

同じ文字列のn回繰り返しを作る最速の方法を探求してみたというところからですが、最短で O(log n) で記述できるそうですが、ここでは比較的オーソドックスな方法で記述します。

例えば以下のような方法があります。 これは連接にて文字列を接続していく方法です。

#! /usr/bin/gawk -f
# repeat_str_1.awk

BEGIN {
    print repeat_str("test", 10000);
}

function repeat_str(str, num) {
    for (i = 1; i <= num; i++) {
        result = result str;
    }
    return result;
}

awk には連接という便利なものがありますが、sprintf() でも記述することができます。

#! /usr/bin/gawk -f
# repeat_str_2.awk

BEGIN {
    print repeat_str("test", 10000);
}

function repeat_str(str, num) {
    for (i = 1; i <= num; i++) {
        result = sprintf("%s%s", result, str);
    }
    return result;
}

単に連接を sprintf() に変更しただけのものです。 gawk は途中まで連接が遅く、sprintf() の方が高速に動作する時代がありましたが、途中からほぼ同じ速度で動作するようになっています。

ところが、手元の CVS 版 gawk では予期しない結果がでました。

$ time gawk -f repeat_str_1.awk > /dev/null
gawk -f repeat_str_1.awk > /dev/null  0.00s user 0.00s system 87% cpu 0.007 total
$ time gawk -f repeat_str_2.awk > /dev/null
gawk -f repeat_str_2.awk > /dev/null  10.15s user 0.01s system 97% cpu 10.428 total

多少の差が出ることは予想していましたが、100 倍を越える差になると問題です。 gawk と同じ処理と思われる CVS 版の xgawk も同じような結果になりました。

単純に nawk を用いてみます。

$ time nawk -f repeat_str_1.awk > /dev/null
nawk -f repeat_str_1.awk > /dev/null  0.45s user 0.00s system 87% cpu 0.520 total
$ time nawk -f repeat_str_2.awk > /dev/null
nawk -f repeat_str_2.awk > /dev/null  0.48s user 0.00s system 99% cpu 0.486 total

また、Fedora10 に含まれる gawk では連接と sprintf() にほとんど差が見られないことから CVS 版で修正されたところでの問題だと思われます。 他に同様の結果が出た人がいましたら、ご連絡ください。

原因

どうも CVS 版 gawk の問題のようです。 Re: sprintf() of gawk in cvs works very slow under ja_JP.UTF8 に gawk のメンテナーの Arnold Robbins からパッチが提供されています。 速度は改善されているようですが、他に影響がないかどうかを現在検証しています。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png