【PHP】選択可能要素が多くても遅くなりにくい重みづけランダム選択の作り方

　時折、分布を任意の形に定めたランダムな要素の選択を作りたくなります。そういった要素毎の重みをつけたランダム選択の作り方を紹介します。

　ベースの考えは重みの累積で数直線を用意し、重みの累積の範囲で生成したランダムな値がどの範囲に属するかをチェックするという考えです。例えば、重み1、2、3の三要素がある場合は次図の数直線の様になり、

0から6までの範囲のランダム値で 1.4 が出れば2番目の範囲である重み2の要素を選ぶ、といった具合です。これを愚直にプログラムに落とし込むと次の様になります。

<?php

/**
 * @param  array  $items ランダム対象とその重みを格納した配列。キーに対象、値に重み
 * @return int|string|null 選ばれた対象。配列のキー
 */
function weighted_random_pick(array $items): int|string|null
{
    // 最初に数直線全体の範囲からどこを選ぶかを決める
    $total = array_sum($items);
    $num = mt_rand() / mt_getrandmax() * $total;
    // 数直線を←から構築しつつ、↑で選んだ場所に到達したらその時点での対象を返す
    $n = 0.0;
    foreach ($items as $item => $weight) {
        $n += $weight; // 重みを累積させる
        if ($n >= $num) {
            // 初めて重みの累積が選んだ場所を超えたら、そこが選ばれた範囲であり対象
            return $item;
        }
    }
    return $item ?? null;
}

$items = [
    "item1" => 0.1,
    "item2" => 0.2,
    "item3" => 0.7,
];
$result = weighted_random_pick($items);
echo $result . "\n"; // item1 or item2 or item3

　やっていることはコメントの通りです。先ほど述べた内容をコード上で行っているのみです。

　このコードですが、実は速度面で問題があります。というのも常に選ぶ対象の配列を先頭から順番に見ているため配列の奥の方が選ばれた時に大分計算量が増えます。コードに落とし込んだこれは線形探索であり、計算量O(n)です。選択対象の総数である n が増えても計算量が増えすぎない様に別の探索アルゴリズムを用いることも考慮したいです。また複数回実行する場合、配列に対して毎回合計や累積を計算するのも無駄です。キャッシュすることでより高速化できます。こういった高速化の余地をある程度埋めたのが次のコードです。

<?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"] = random_int(1, 1e5);
    $results[$i]     = 0;
}
// アイテムをシャッフル
shuffle($items);
// 実行するランダム選択回数
$num_trials = 1e5;
foreach([null, 'linear_search', 'binary_search',] as $algo) {
    // 処理開始時間を記録 & ランダムなアイテムの選択を繰り返す
    $start   = microtime(true);
    $results = some_weighted_random_pick($items, $num_trials, $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]\trate:\t" . ($count / $num_trials) . "\n";
    }
}

Online PHP editor ｜ output for PLjcH#↑のコードのデモ

　高速化のためのキャッシュと二分探索を盛り込んだランダム選択です。これにより大量の対象を相手に何度もランダム選択を実行しても遅くなりにくいです。もちろん詰める余地はありますし、こういった素朴な機能で真に最速を目指すならそもそもPHP以外を使った方がいいですが、ざっくりそれなりの速さで重みづけランダム選択をする目的ならこれで十分です。