<?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);
}
preferences:
26.87 ms | 414 KiB | 5 Q