среда, января 25, 2012

Простой алгоритм случайной выборки с учетом веса

Часто необходимо обращаться к одной и той же задаче:
"случайная выборка с учетом веса".

Чтобы не забыть вот кратное описание взятое отсюда:

Простой алгоритм случайной выборки с учетом веса


В общем виде этот алгоритм можно описать так:

  1. Выбрать случайное число между еденицей и суммой “весов” всех элементов
  2. Спускаться по списку элементов добавляя к счетчику вес текущего элемента
  3. Проверить, если счетчик (шаг №2) больше или равен случайному числу (шаг №1), то закончить
  4. цикл и вернуть текущий элемент. В противном случае перейдите к шагу №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 комментария:

kulikov.dm комментирует...

создать массив типа: [A, A, A, B, B, B, B, B, B, B, C, C, C, C, C, C, C, C, C, C,],
перемешать, брать по одному элементу

Kirill Danilov комментирует...

К сожалению, такой подход имеет ограничение по памяти и процессорному времени(создание массива).