重みを付けて乱択する

404 Blog Not Found:algorithm - 重みをつけて乱択するPerlで生でrand関数をごちゃごちゃ使うコードはもう嫌だ | hirobanex.net にインスパイヤされて、awk でも作ってみます。

確かに if 文の中で rand() 関数を使って比率分けをするのは (私自身も良く使う手法ではありますが) イマイチな感じがします。 awk では Perl や JavaScript のようにスマートな実装はできませんが、ほぼ同様のアルゴリズムで組んでみます。

最初のソートを楽にするために gawk4 以降で実装されたソートを使っています。

PROCINFO["sorted_in"] = "@val_num_desc";

このようにすることで for 文の中で数値の大きいものからソートされることを利用して、ソートされた配列を作っています。

#! /usr/local/bin/gawk4 -f
## make_random_picker.awk

BEGIN {
    pick["foo"]  = 20;
    pick["bar"]  = 10;
    pick["baz"]  = 10;
    pick["hoge"] = 30;
    pick["moge"] = 30;

    make_random_picker(pick);

    for (i = 1; i <= 20; i++) {
        print random(pick);
    }
}

## make_random_picker():    配列をランダムに選ぶための前準備
##  in:     配列 pick
##  out:    選択用にコピーされた配列 choices と配列 choice
function make_random_picker(pick,    i, total) {
    PROCINFO["sorted_in"] = "@val_num_desc";

    for (i in pick) {
        total += pick[i];
        num++;

        choices[num] = pick[i];
        choice[num] = i;
    }

    for (i = 1; i <= num; i++) {
        choices[i] /= total;
    }

    srand();
}

## random():    配列をランダムに出力
##  in:     配列 pick
##  out:    ランダムに選択された配列 choices
function random(pick,    i, p) {
    p = 0;

    for (i = 1; i <= num; i++) {
        p += choices[i];

        if (rand() < p) {
            return choice[i];
        }
    }
    return choices[1];
}

実行してみます。

$ gawk4 -f make_random_picker.awk
hoge
foo
hoge
baz
foo
baz
moge
moge
hoge
hoge
moge
foo
moge
moge
foo
foo
moge
hoge
hoge
hoge

awk では問題があって一部の配列はグローバル配列として扱わないと配列をうまく渡すことができませんので、Perl や JavaScript のようにスマートには記述できないことが分かります。

ただし、rand() 関数に任せていると、「で、実際の比率は?」とか、数が少ないと「たまたま特定の値に偏っているのではないか?」という疑問があるので、最初に配列を作成して、それをシャッフルするものを作成してみました。 こちらは awk の基本機能だけで作っています。

#! /usr/local/bin/nawk -f
## make_random_picker_2.awk

BEGIN {
    pick["foo"]  = 20;
    pick["bar"]  = 10;
    pick["baz"]  = 10;
    pick["hoge"] = 30;
    pick["moge"] = 30;

    print_choice(pick, 20);
}

## print_choice():  配列を決まった数だけ選ぶ
##  in:     配列 pick
##          数値 num
##  out:    配列を決まった数だけ選んで画面に表示
function print_choice(pick, num,  i, j, total, n, choices) {
    for (i in pick) {
        total += pick[i];
    }

    for (i in pick) {
        for (j = 1; j <= int(pick[i] / total * num); j++) {
            choices[++n] = i;
        }
    }

    ## 上の for 文で int しているので num に対して不足分を追加
    while (num > n) {
        for (i in pick) {
            choices[++n] = pick[i];
        }
    }

    shuffle_array(choices);

    for (i = 1; i <= num; i++) {
        print choices[i];
    }
}

## shuffle_array(): 配列のシャッフル
##  in:     配列 arr
##  out:    シャッフルされた配列 arr
function shuffle_array(arr,    a, num_arr, i, tmp) {
    srand();

    for (a in arr) {
        num_arr++;
    }

    for (i = num_arr; i >= 1; i--) {
        j = int((i + 1) * rand());

        if (j == 0) {
            j = 1;
        }

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

実行してみます。

$ gawk -f make_random_picker_2.awk
baz
hoge
baz
hoge
hoge
foo
moge
bar
foo
hoge
moge
moge
bar
foo
moge
hoge
foo
moge
moge
hoge

最初に決まった個数の配列を生成しているため、メリットとして、必ず比率が保たれることが挙げられます。 もっとも、不足分を補っている部分はスマートじゃないですが・・・。

もちろんシャッフルの度合いは rand() 関数を使っているため、その都度変わってしまいますが、比率は毎回一定になります。

ちなみに、シャッフルの代わりに for 文 (for (a in arr)) で連想配列を呼び出しても (それなりに) ランダムになりますね。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png