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

アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法がさり気なく流行っているようですが、awk としてもやってみます。 ここでは冪乗の下位桁から計算する方式を選んでいます。

ある程度愚直ではあるのですが、2 進数に直して下位から計算するために逆順にしてから解いて分かりやすくしたつもりですが、かえって分かりにくくなっているかもしれません。

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

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

# repeat_str():     文字列 str を num 回連接する
#   in:     str:    文字列
#   in:     num:    繰り返し回数
#   out:    文字列 str を num 回連接した文字列
function repeat_str(str, num,   rep_str, num_bin, arr_bin, memo_rep) {

    # 初期化
    rep_str = "";

    # 以下を分かりやすくするために一旦 2 進数を逆順で記述
    num_bin = split(reverse_str(dec2bin(num)), arr_bin, "");

    # 2^0 のところは str のまま
    memo_rep[0] = str;
    # 2^i に対して繰り返しを求める
    for (i = 1; i <= num_bin - 1; i++) {
        memo_rep[i] = memo_rep[i - 1] memo_rep[i - 1];
    }

    # 2 進数表記で 1 になっている部分だけを連接させる
    for (i = 0; i <= num_bin; i++) {
        if (arr_bin[i] == 1) {
            rep_str = rep_str memo_rep[i - 1];
        }
    }

    return rep_str;
}

# dec2bin():    10 進数を 2 進数で返す
#   in:     num:    10 進数
#   out:    2 進数
function dec2bin(num,    rem, str) {
    while (num > 0) {
        rem = int(num % 2);
        if (rem == 1) {
            str = "1" str;
        } else {
            str = "0" str;
        }
        num = int(num / 2);
    }
    return str;
}

# reverse_str():    文字列を逆順で返す
#   in:     str:    文字列
#   out:    逆順の文字列
function reverse_str(str,   rev_str) {
    for (i = length(str); i > 0; i--) {
        rev_str = rev_str substr(str, i, 1);
    }
    return rev_str;
}

前回の同じ文字列のn回繰り返しを作る方法よりも桁を 1 つ上げて 10 万回を計算し、しかも差が顕著に出るように nawk で実行してみます。

$ time nawk -f repeat_str_3.awk | wc -c
400001
nawk -f repeat_str_3.awk  0.01s user 0.01s system 90% cpu 0.021 total
wc -c  0.00s user 0.00s system 14% cpu 0.020 total

速度を比較するため、前の 2 つのものを並べておきます。

$ time nawk -f repeat_str_1.awk | wc -c
400001
nawk -f repeat_str_1.awk  44.79s user 5.50s system 99% cpu 50.605 total
wc -c  0.00s user 0.00s system 0% cpu 50.605 total
$ time nawk -f repeat_str_2.awk | wc -c
400001
nawk -f repeat_str_2.awk  45.21s user 3.83s system 97% cpu 50.140 total
wc -c  0.00s user 0.00s system 0% cpu 50.139 total

いかがでしょうか。 差としては 4000 倍くらいを示していますが、実際にはもっと顕著な差があると考えられます。

文字列の繰り返しと計算量で odz さんが問題を出されていますので、いろいろ試してみてはいかがでしょうか。

少し話はずれるのですが、Twitter で Busybox の awk が優れているのではないかという話を少ししています。 確かに nawk と比較すると倍程度高速に動作し、gawk の拡張機能も取り込んでいますが、awk で一般的に許されていない関数名と変数名に同じ名前を付けることが許されていることに気が付きました。 これはこれでいいのですが、やはり汎用性を考えると nawk で組んでテストするのが良さそうです。

修正しました (2009/02/26)

LL Golf Hole 6 - 10進数を2進数に基数変換するで行った修正と同様の修正を行いました。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png