частотный (весовой) коэффициент

Добрый день.

Есть динамический список неких объектов, у каждого из которых определён свой частотный (весовой) коэффициент. Коэффициент описывается, например, шкалой 1,2...n, со смыслом "чем больше номер, тем чаще должен появлятся объект при выборе". Сейчас выбор идёт простым рандомайзером, но нужно как-то задействовать этот коэффициент. Вопрос в том, как это сделать?

Буду очень благодарна за конкретные формулы или ссылки на любые документы, могущие оказаться полезными для решения этой задачи.

Можно так использовать.
Рандомайзером выбираете N объектов, среди них берете объект с наибольшим коэффициентом.
Можно варьировить N

Одним проходом можно выбрать с правильной вероятностью (Первоначальная идея этого алгоритма, для одинаковой вероятности, была подсмотрена в "Perl Cookbook"):

$sum = 0;
$result = null;
while (имеются данные) {
   $line = <считать строку данных>;
   $n = $line[n];         // получаем из текущей записи вероятность
   $sum += $n;            // сумма всех вероятностей
   if (rand($sum) < $n) { // самый интересный момент :)
      $result = $line;
   }
}
return $result;

Смысл таков, что проверка rand($sum) < $n возвращет правильную вероятность в зависимости от веса текущего и суммы всех встреченных ранее записей.

Алексей В. Иванов[досье]
Это если функция rand() дешёвая, а цикл по всем вероятностям дорогой — вы выполняете rand() для каждого элемента. Достаточно вызвать rand() один раз, но тогда будет два прохода по массиву вероятностей (первый, для подсчета суммы вероятностей, достаточно выполнить только один раз, если нужно выбрать несколько записей подряд не меняя вероятностей). Выглядит это так:

$sum = sum($probability);
$rand = rand($sum);
$result = -1;
while ($rand >= 0)
{
  $result++;
  $rand -= $probability[$result];
}
return $result;

Спору нет, все так :)
Но обычно в этом мире проход по записям несравним по времени с генерацией random, поэтому я и предложил свой вариант, который, как мне кажется намного оптимальнее :)

Всё зависит от того, насколько сложно посчитать сумму вероятностей — это и в этом мире может оказаться намного проще генерации сотни случайных чисел :)

Если n << общего количества записей, то может быть лучше сгруппировать все элементы по значению веса. Затем выбрать группу с помощью алгоритма(ниже, либо которые уже выше описаны). Потом выбрать любой элемент из группы, элементы в группе равновероятны.

Если значения весов равномерно распределенны от 1 до n, и все группы содержат хотя бы один элемент, то сумма вероятностей при выборе группы считается как сумма арифметической прогрессии от 1 до n с шагом 1, а именно sum = (n+1)*n/2;. Выбираем случайное число(rand) от 1 до sum. Искомая группа выбирается из выражения n = ceil((sqrt(1+8*rand) - 1)/2).

По-моему это самый трудо- и ресурсоемкий алгоримт, причем с неправильным распределением вероятности.

Алексей В. Иванов[досье] ИМХО ваш кусочек кода совсем неверный. Он всегда выбирает первую запись, так как на первой итерации $sum = $n(вероятности первой записи), далее вы выбираете случайное число от 0 до $sum и делаете проверку $rand < $n, так как $n = $sum, то эта проверка провалится только в одном случае, когда $rand равно максимальному значению($sum).

Мой код правильный, смотрите глубже. Первая запись действительно всегда выбирается, потому что из цикла нельзя выйти с пустым результатом.

То есть вы предлагаете перебрать все данные, независимо от выпавшего значения. Ха-ха-ха. И вы говорите об оптимальности.

Мы ничего не знаем о способе хранения данных и о цене операций.

Да, я говорю об оптимальности, ибо любой вариант решения данной задачи предусматривает проход по массиву, чтобы узнать общую вероятность. В моем решении проход используется только один, а расчет случайного числа всегда черезвычайно быстрая операция. Более того, мой вариант предусматривает минимальное использование памяти. Так что зря Вы смеетесь. Оптимальнее вряд ли существует. Не хочется умничать Но, поверьте, я знаю о чем говорю :).
Более того, если кого-то смущает N генераций rand(), то открою страшную тайну — в приведенном мной алгоритме сгенерировать rand() можно только 1 раз, до цикла, потом это значение использовать в сравнении ($rand * $current < $sum). Получится тоже самое.

Алексей В. Иванов, я попробовала воспользоваться вашим алгоритмом так:

int[,] list = new int[11,2]; // [порядковый номер][весовой коэффициент]
list[0,0]=1; list[0,1]=1;
list[1,0]=2; list[1,1]=1;
list[2,0]=3; list[2,1]=1;
list[3,0]=4; list[3,1]=2;
list[4,0]=5; list[4,1]=1;
list[5,0]=6; list[5,1]=1;
list[6,0]=7; list[6,1]=1;
list[7,0]=8; list[7,1]=3;
list[8,0]=9; list[8,1]=1;
list[9,0]=10; list[9,1]=1;
list[10,0]=11; list[10,1]=1;
int sum = 0;
int result = 0;
Random randObj = new Random();
for (int i = 0; i < 11; i++)
{
   sum += list[i,1];
   if (randObj.Next(sum) < list[i,0]) result = list[i,0]; // randObj.Next возвращает случайное число, меньшее sum
}

Но в результате распределение получается каким-то странным, и чаще показываются не элементы с большим весовой коэффициент, а какие-то другие. К тому же, при последовательном вызове вообще часто показываются одни и те же элементы. Подозреваю, что я что-то сделала неверно, но вот что именно?

Если randObj.Next(sum) возвращает псевдослучайное число в диапазоне [0;sum), то все правильно, за исключением того, что сравнивать надо с list[i,1], а не [i,0]:

if (randObj.Next(sum) < list[i,1])

Алексей В. Иванов
Теперь всё время выбирается элемент с максимальным коэффициентом. Всегда. Что делать?

Что за функция randObj.Next(sum)? Что она возвращает?

Алексей, вот описание этого метода:
http://msdn.microsoft.com/libr......ystemRandomClassNextTopic2.asp

Тогда Вам надо randObj.Next(sum) <= list[i,1], т.к. функция дает целое число от 0 до sum включительно

Хотя нет, это неправильно. (sum > 0) && (randObj.Next(sum - 1) < list[i,1]) видимо.

Всё равно странно. Я оборачиваю весь этот код в цикл на 100 повторов и вывожу результаты - и практически каждый раз все 100 результатов совпадают.

Разбирайтесь с Random. Я проверил свой код (на Perl), работает хорошо:

@a = (
   [1, 1],
   [2, 1],
   [3, 1],
   [4, 1],
   [5, 2],
   [6, 1],
   [7, 1],
   [8, 1],
   [9, 1],
   [10, 3]
);

for ($t = 0; $t < 130000; ++$t) {
   my $sum = 0;
   my $res = undef;
   for (@a) {
      $sum += $_->[1];
      if (rand($sum) < $_->[1]) {
         $res = $_->[0];
      }
   }
   $a[$res - 1]->[2]++;
}
for (@a) {
   print "$_->[0] > $_->[2]\n";
}

Выводит следующие цифры (кол-во выпадений):

1 > 10050
2 > 10132
3 > 9956
4 > 10057
5 > 20004
6 > 10014
7 > 10048
8 > 10104
9 > 9987
10 > 29648

>Разбирайтесь с Random. Я проверил свой код (на Perl), работает хорошо

Да вроде бы мой Random ничем особым от любого другого не отличается...

Я вот не понимаю: мы идём по списку и на каждом шаге сравниваем случайное число, полученное в диапазоне 0..sum с весовым коэффициентом. При этом sum всё время увеличивается, а весовые коэффициенты остаются маленькими, значит, чем ближе к концу списка, тем меньше вероятность того, что случайное число окажется меньше коэффициента. Разве не так?

Все почти так. По крайней мере, так кажется на первый взгляд.
Мне немного лень описывать это, было бы лучше, если бы Вы поверили :), но я постараюсь...

Мы читаем записи построчно, если мы заметим, каждая строка выбирается с той вероятностью, каков шанс был бы, если бы следющей записи не было.
Для примера возьмем массив, где вес всех записей одинаков, тогда получается, что читая первую строку мы имеем 100% шанс ее запомнить (rand(0,1) < 1), выбирая вторую - 50%, третью 33.(3)%, четвертую - 25% и т.д.
Выборка с разными весами отличается лишь тем, что вес заносится в общую "копилку весов" (сумму) и сравнивается с этой суммой.

P.S. если генератор случ. чисел, который Вы используете выдает одинаковые последовательности, то надо сбросить счетчик. Чтобы получить достоверные результаты используйте хотябы несколько тысяч выпадений. Сотни будет явно мало.

Алексей, всё поняла и наконец-то у меня всё заработало как надо. И проверять нужно всё-таки randObj.Next(sum), а не randObj.Next(sum - 1). Спасибо Вам огромное за помощь!

Если randObj.Next(sum) выдает число от 0 до sum включительно, то надо все же отнимать одиничку. Это точно.

Согласна, но мой randObj.Next(sum), после внимательного чтения документации, таки выдает числа, строго меньшие sum. Точно, точно. :)

Чтобы реально посчитать вероятность появления вашего элемента нужно сложить все веса, а потом вес каждого элемента разделить на эту сумму, получим вероятность выбора каждого элемента. После таких действий сумма всех полученных вероятностей будет равна 1.

Если вы посмотрите алгоритм Алексея на последней итерации, то увидите, что вероятность выбора последнего элемента соответствует реальной, то есть вес последнего элемента разделить на сумму всех весов, но даже эта малая вероятность уменьшает вероятности выбора предыдущих элементов.
Пример: три элемента с весами 1, 5, 4.
Первая итерация sum = 1, вес = 1, вероятность выбора 1, выбрали.
Вторая: sum = 6, вес = 5, вероятность выбора 5/6, но вероятность первого элемента остаться выбраным уменьшилась на 5/6, итого вероятности для двух элементов 1/6 и 5/6.
Третья: sum = 10, вес = 4, вероятноссть выбора 2/5, а у каждого предыдущего элемента уменьшилась вероятность остаться выбраным, но так как вероятности выбора предыдущих элементов распределенны неравномерно, то и ууменьшаются они пропорционально предыдущим значениям, а точнее новые вероятности всех элементов будут равны: 1/6 - 1/6*2/5, 5/6 - 5/6*2/5, 2/5. После подсчета получаем: 1/10, 5/10, 4/10. Я привел все значения, к общему знаменателю дабы было видно, что это вес элемента деленный сумму весов всех элементов.

ПС: пока писал уже разобрались :)