2013年01月20日

【PHP】重み付き乱数を取得するロジック

仕事をしている合間にちょっとした事を検索して、
将来的に使えそうなプログラムロジックなんかを探しては、
会社で自作しているライブラリに組み込んだり、スクラップブックで保存していたりします。

前回は重み付きランダム結果を取得出来るというロジックがヒットしたので、
「前に一度使用した事があるし、とりあえず保存」
と保存して動かしてみると、
どうもでてくる結果がおかしい。
で、ロジックを調査してみたら、処理ロジックが間違っているようだったので、

(たぶん)正しく動作するように作り直してみました。


$wlist = array(1,2,3,4,5,6,7,8,9,10);
shuffle($wlist);
// 1〜10の合計は55なのでn*1000に収束させるため55000回ループさせる
$result = array();
for($i=0; $i<55000; $i++){
$key = weighted_random($wlist);
$result[$key]++;
}
// view
ksort($result);
foreach($result as $key => $count){
echo "[$wlist[$key]] $count" . BR;
}


//---------------------------------------------------------------
// functions
//---------------------------------------------------------------
function weighted_random($weights){
list($lookup, $total_weight) = calc_lookups($weights);
$r = mt_rand(0, $total_weight);
return binary_search($r, $lookup);
}

// $lookup:$weights を加算していった配列
// たとえば$weights={5,2,8,10}だったら、$lookup={5,7,15,25}となる
// こうすることで、weghts 配列をソートすることなく、昇順の配列が得られる
function calc_lookups($weights){
$lookup = array();
$total_weight = 0;
$pos = 0;

foreach($weights as $val){
$total_weight += $val;
$lookup[$pos++] = $total_weight;
}
return array($lookup, $total_weight-1);
}

// 二分探索法
// なので、オーダーがO(n)からO(log2(n))になる
function binary_search($needle, $haystack){
$right = count($haystack)-1;
$left = 0;

// 左を示すポインタ($left)が右を示すポインタ($high)と同じ値か、
// 大きい値となったとき、配列に対する$needleの相対位置が特定される
while ( $left < $right ){
// (int)をつけることで$midを整数値にする
$mid = (int)(($right + $left ) / 2);
if ($needle >= $haystack[$mid]){
// 右半分へ
$left = $mid + 1;
} else if ($needle >= $haystack[$mid-1]) {
// ぴったり
return $mid;
} else {
// 左半分へ
$right = $mid - 1;
}
// $haystackの中に$needleがない場合は、
// この時点で$left > $rightになるのでループから抜ける
}
return $left;
}

参照先:http://blog.image-lab.net/2012/07/php_20.html


参照先のコードと自分のコードは細かいところで汎用性が減っていたり、コーディング規則が違ったり、処理ロジックで違うものを使っていますが、
元コードは2箇所ほど決定的に間違っているようです。
どこがどう違うのか読んで見るのも面白いです。
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

この記事へのトラックバックURL
http://blog.seesaa.jp/tb/314502911
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。