m2

重みをつけて乱択する (バイナリサーチ版)

programming

せっかく書いたのでバイナリサーチ版のっけときます。

http://jsfiddle.net/t58Vv/6/

// algorithm - 重みをつけて乱択する http://blog.livedoor.jp/dankogai/archives/51761113.html
// バイナリサーチ版
var make_random_picker = function(picks){
    var i, l = picks.length, t = 0, choices = picks.concat();
    for (i = 0; i < l; ++i) { choices[i][1] = (t += choices[i][1]); }
    for (i = 0; i < l; ++i) { choices[i][1] /= t; }
    return function() {
        var r = Math.random(), head = 0, tail = l - 1;
        while (head <= tail) {
            var sum = head + tail;
            var mid = (sum <= 0x7fffffff) ? (sum >> 1) : Math.floor(sum / 2); 
            if (r < choices[mid][1]) {
                if (mid == 0 || r >= choices[mid-1][1]) {
                    return choices[mid][0];
                }
                tail = mid - 1;
            }
            else {
                head = mid + 1;
            }
        }
        return null; // never.
    };
};
algorithm - 重みをつけて乱択する
http://blog.livedoor.jp/dankogai/archives/51761113.html
アルゴリズム百選 - 二分探索(binary search)
http://blog.livedoor.jp/dankogai/archives/50961989.html