Online PHP editor | rfc for PLjcH

<?php /** * 与えられたアイテムの累積重みを計算します。 * * @param array<int|float> $items アイテムとその重みを格納した配列。キーにアイテム、値に重み * @return array{0: array<int|float>, 1: int|float} 累積重みの配列と総重み。累積重みの配列はキーにアイテム、値に累積重み */ function prepare_cumulative_weights(array $items): array { // 累積重みの配列を初期化 $cumulative_weights = []; // 重みの総和を初期化 $total = 0.0; // 各アイテムに対して累積重みを計算 foreach ($items as $item => $weight) { $total += $weight; $cumulative_weights[$item] = $total; } // 累積重みの配列と総重みを返す return [$cumulative_weights, $total]; } /** * 累積重みを基にランダムにアイテムを選択します。 * * @param array<int|float> $cumulative_weights 累積重みの配列 * @param float|int $total 総重み * @param string $algo アルゴリズム名。binary_search, linear_search * @return float|int|string 選択されたアイテムのキー */ function weighted_random_pick(array $cumulative_weights, float|int $total, string $algo = 'binary_search'): float|int|string { // ランダムな数を生成 $num = mt_rand() / mt_getrandmax() * $total; // 生成された数に基づいてアイテムを探索して選択 return $algo($cumulative_weights, $num); } // 何度も参照する値のキャッシュ置き場 class WeightRandomCacheStorage { public static array|null $arrayValues; public static array|null $arrayKeys; public static function clear(): void { self::$arrayValues = null; self::$arrayKeys = null; } } /** * 二分探索を行い、指定した値以上の最初の要素を見つけます。 * * @param array<float|int> $array 検索対象の配列。昇順で累積重みが値に入っている値 * @param float|int|string $value 検索する値 * @return float|int|string 指定した値以上の最初の要素 */ function binary_search(array $array, float|int|string $value): float|int|string { WeightRandomCacheStorage::$arrayValues ??= array_values($array); WeightRandomCacheStorage::$arrayKeys ??= array_keys($array); $left = 0; $right = count(WeightRandomCacheStorage::$arrayValues) - 1; // 二分探索 while ($left <= $right) { $middle = floor(($left + $right) / 2); if (WeightRandomCacheStorage::$arrayValues[$middle] == $value) { return $middle; } if (WeightRandomCacheStorage::$arrayValues[$middle] < $value) { $left = $middle + 1; } else { $right = $middle - 1; } } // $valueを超える最初の要素の値を返す return WeightRandomCacheStorage::$arrayKeys[$left]; } /** * 線形探索を行い、指定した値以上の最初の要素を見つけます。 * * @param array<float|int> $array 検索対象の配列。昇順で累積重みが値に入っている値 * @param float|int|string $value 検索する値 * @return float|int|string 指定した値以上の最初の要素 */ function linear_search(array $array, float|int|string $value): float|int|string { global $arrayV, $arrayK; $arrayV ??= array_values($array); $arrayK ??= array_keys($array); // 線形探索 for ($i = 0; $i < count($arrayV); ++$i) { if ($arrayV[$i] >= $value) { return $arrayK[$i]; // $value以上の最初の要素のキーを返す } } return $arrayK[$i]; // 指定された値以上の要素が見つからない場合 } /** * 与えられた回数だけアイテムをランダムに選択します。 * * @param array<int|float> $items アイテムとその重みを格納した配列。キーにアイテム、値に重み * @param int $count ランダムに選択する回数 * @param string|null $algo アルゴリズム名。binary_search, linear_search * @return array<int> 選択された各アイテムの数を格納した配列。キーにアイテム、値に選択された回数 */ function some_weighted_random_pick(array $items, int $count, string|null $algo = null): array { if(!isset($algo)){ // 要素が少ないなら線形探索、多いなら二分探索 $algo = count($items) < 50 ? 'linear_search' : 'binary_search'; } // 累積重みと総重みを計算 list($cumulative_weights, $total) = prepare_cumulative_weights($items); // 結果を格納する配列を初期化 $results = array_combine(array_keys($items), array_fill(0, count($items), 0)); // 指定された回数だけランダムにアイテムを選択 for ($i = 0; $i < $count; ++$i) { $result = weighted_random_pick($cumulative_weights, $total, $algo); ++$results[$result]; } WeightRandomCacheStorage::clear(); // 選択結果を返す return $results; } /** * 一度だけアイテムをランダムに選択します。 * * @param array<int|float> $items アイテムとその重みを格納した配列。キーにアイテム、値に重み * @param string $algo アルゴリズム名。binary_search, linear_search * @return float|int|string 選択されたアイテムのキー */ function single_weighted_random_pick(array $items, string $algo = 'binary_search'): float|int|string { // 累積重みと総重みを計算 list($cumulative_weights, $total) = prepare_cumulative_weights($items); // ランダムにアイテムを選択 $ret = weighted_random_pick($cumulative_weights, $total, $algo); WeightRandomCacheStorage::clear(); return $ret; } /** 使用例 **/ // ランダム対象 $items = []; // どれが選ばれたのか集計する配列 $results = []; for ($i = 0; $i < 10; ++$i) { $items["item$i"] = [ 'name' => "item$i", 'weight' => random_int(1, 1e5), ]; $results[$i] = 0; } // アイテムをシャッフル shuffle($items); // 実行するランダム選択回数 $num_trials = 1e5; foreach([null, 'linear_search', 'binary_search',] as $algo) { // 処理開始時間を記録 & ランダムなアイテムの選択を繰り返す $start = microtime(true); $results = any_item_some_weighted_random_pick($items, $num_trials, static fn($item)=>$item['weight'], $algo); $end = microtime(true); // 処理時間を表示 $algo ??= 'auto_algo_select'; echo $algo . ' Time: ' . ($end - $start) . "\n"; // 選択結果を表示 foreach($results as $item => $count) { echo "key:\t$item\tweight:\t{$items[$item]['weight']}\trate:\t" . ($count / $num_trials) . "\n"; } } function any_item_some_weighted_random_pick(array $items, int $count, callable|null $weightGetter = null, string|null $algo = null) { $_items = []; if(isset($weightGetter)) { foreach($items as $key => $item) { $_items[$key] = $weightGetter($item); } } else { $_items = $items; } return some_weighted_random_pick($_items, $count, $algo); }

3v4l.org

Active branches

Archived branches