Online PHP editor | perf 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); }

Version	System time (s)	User time (s)	Memory (MiB)
8.2.7	0.007	0.114	79.33
8.2.6	0.017	0.106	79.33
8.2.5	0.016	0.109	79.33
8.2.4	0.016	0.109	79.33
8.2.3	0.014	0.112	79.33
8.2.2	0.024	0.100	79.33
8.2.1	0.014	0.108	79.33
8.2.0	0.017	0.109	79.33
8.1.20	0.017	0.113	79.33
8.1.19	0.014	0.109	79.33
8.1.18	0.013	0.114	79.33
8.1.17	0.011	0.113	79.33
8.1.16	0.007	0.119	79.33
8.1.15	0.007	0.116	79.33
8.1.14	0.007	0.121	79.33
8.1.13	0.016	0.108	79.33
8.1.12	0.013	0.109	79.33
8.1.11	0.004	0.120	79.33
8.1.10	0.017	0.104	79.33
8.1.9	0.013	0.113	79.33
8.1.8	0.022	0.106	79.33
8.1.7	0.013	0.112	79.33
8.1.6	0.017	0.111	79.33
8.1.5	0.016	0.112	79.33
8.1.4	0.023	0.103	79.33
8.1.3	0.013	0.117	79.33
8.1.2	0.013	0.113	79.33
8.1.1	0.014	0.121	79.33
8.1.0	0.013	0.107	79.33
8.0.29	0.014	0.111	79.33
8.0.28	0.010	0.114	79.33
8.0.27	0.014	0.110	79.33
8.0.26	0.007	0.122	79.33
8.0.25	0.020	0.107	79.33
8.0.24	0.010	0.118	79.33
8.0.23	0.010	0.118	79.33
8.0.22	0.010	0.115	79.33
8.0.21	0.019	0.105	79.33
8.0.20	0.007	0.126	79.33
8.0.19	0.010	0.120	79.33
8.0.18	0.016	0.114	79.33
8.0.17	0.013	0.118	79.33
8.0.16	0.013	0.107	79.33
8.0.15	0.017	0.106	79.33
8.0.14	0.013	0.114	79.33
8.0.13	0.017	0.112	79.33
8.0.12	0.010	0.117	79.33
8.0.11	0.019	0.114	79.33
8.0.10	0.007	0.117	79.33
8.0.9	0.010	0.119	79.33
8.0.8	0.013	0.116	79.33
8.0.7	0.000	0.128	79.33
8.0.6	0.004	0.123	79.33
8.0.5	0.010	0.117	79.33
8.0.3	0.010	0.118	79.33
8.0.2	0.014	0.113	79.33
8.0.1	0.007	0.120	79.33