"случайная выборка с учетом веса".
Чтобы не забыть вот кратное описание взятое отсюда:
Простой алгоритм случайной выборки с учетом веса
В общем виде этот алгоритм можно описать так:
- Выбрать случайное число между еденицей и суммой “весов” всех элементов
- Спускаться по списку элементов добавляя к счетчику вес текущего элемента
- Проверить, если счетчик (шаг №2) больше или равен случайному числу (шаг №1), то закончить
- цикл и вернуть текущий элемент. В противном случае перейдите к шагу №2.
/** * Выборка случайного элемента с учетом веса * * @param array $values индексный массив элементов * @param array $weights индексный массив соответствующих весов * @return mixed выбранный элемент */ function weighted_random_simple ( $values, $weights ) { $total = array_sum( $weights ); $n = 0; $num = mt_rand( 1, $total ); foreach ( $values as $i => $value ) { $n += $weights[$i]; if ( $n >= $num ) { return $values[$i]; } } } $values = array('A', 'B', 'C'); $weights = array(3, 7, 10); echo weighted_random_simple($values, $weights);
Алгоритм случайной выборки из тысяч элементов
Алгоритм может быть расширен, чтобы сделать его значительно быстрее. Вместо вычисления общего веса (шаг №1) и счетчика (шаг №2) каждый раз, можно сделать это один раз и сохранить значения счетчиков в массиве. Тогда мы сможем использовать бинарный поиск, чтобы быстро выбрать правильный элемент. Ниже приведен модифицированный вариант скрипта:/** * Случайно выбирает один из элементов на основе их веса. * Оптимизирован для большого числа элементов. * * @param array $values индексный массив элементов * @param array $weights индексный массив соответствующих весов * @param array $lookup отсортированный массив для поиска * @param int $total_weight сумма всех весов * @return mixed выбранный элемент */ function weighted_random($values, $weights, $lookup = null, $total_weight = null) { if ($lookup == null OR $total_weight == null) { list($lookup, $total_weight) = calc_lookups($values, $weights); } $r = mt_rand(1, $total_weight); return $values[binary_search($r, $lookup)]; } /** * Создание массива используемого в бинарном поиске * * @param array $values * @param array $weights * @return array */ function calc_lookups($values, $weights) { $lookup = array(); $total_weight = 0; for ($i=0; $i < count($weights); $i++) { $total_weight += $weights[$i]; $lookup[$i] = $total_weight; } return array($lookup, $total_weight); } /** * Ищет в массиве элемент по номеру и возвращает элемент если он найден. * В противном случае возвращает позицию, где он должен быть вставлен, * или count($haystack)-1, если $needle больше чем любой элемент в массиве. * * @param int $needle * @param array $haystack * @return int */ function binary_search($needle, $haystack) { $high = count($haystack) - 1; $low = 0; while ( $low < $high ) { $probe = (int)(($high + $low) / 2); if ($haystack[$probe] < $needle) { $low = $probe + 1; } elseif ($haystack[$probe] > $needle) { $high = $probe - 1; } else { return $probe; } } if ( $low != $high ) { return $probe; } else { return ($haystack[$low] >= $needle) ? $low : $low + 1; } } // Рассчет массивов (1 раз) list($lookup, $total_weight) = calc_lookups($values, $weights); //.... // Каждый раз когда вам необходимо выбрать случайный элемент: $val = weighted_random($values, $weights, $lookup, $total_weight);
2 комментария:
создать массив типа: [A, A, A, B, B, B, B, B, B, B, C, C, C, C, C, C, C, C, C, C,],
перемешать, брать по одному элементу
К сожалению, такой подход имеет ограничение по памяти и процессорному времени(создание массива).
Отправить комментарий