random (с определенной вероятностью)

как бы это сделать правильно ... вот на примере алфавита:

Код (Text):

1. ;========================================================================; data
2. objects     db      'abcdefghijklmnopqrstuvwxyz'
3. objects$    =       $-objects
4. freq        db      7,1,2,1,1,1,1,1,4,9,4,2,1,3,1,1,1,1,2,1,1,1,1,1,1,1
5. ;========================================================================; code
6.         stdcall random,objects$        ; генерация числа от 0 до 25
7.         ...
8.         movzx   eax,byte[objects+eax]
9. ;==============================================================================

необходимо генерировать случайное число (по кол-ву объектов), но так, чтобы числа выпадали в соответствии с заданой частотой, т.е. буква "a" выпадала в 7 раз чаще буквы "b"

здесь это можно сделать просто изменив objects на db 'aaaaaaabccd.....', но в реальности размер objects измеряется мегабайтами и frequency одних объектов может отличаться от других в тысячи раз

 

Давно делал так (в аттаче исходник с генерацией распределения):

Делил отрезок [0,1] на части, пропорциональные требуемой частоте и получал случайное число из [0,1], соответственно искал номер отрезка - он и был требуемым числом:

Пусть требуется получать событие A с частотой (вероятностью выпадения) вдвое меньше события B. Делим отрезок [0,1] на [0,0.333..] и (0,333...,1.00] Если число из [0,1] выпало на первый интервал...

 

Можешь сделать примерно так:

Код (Text):

1. byte ver[26] = {7/*A=7%*/, 1/*B=1%/, ...}
2.  
3. z = 0
4. for (i = 0; i<26; i++)
5.   z += ver[i]
6.  
7. x = random(0..z)
8.  
9. z = 0
10.  
11. for (i=0; i<26; i++)
12. {
13.   z+=ver[i]
14.   if (z>ver[i])
15.     return 'a'+i-1
16. }

Chingachguk

опередил

 

я думал так, т.е. сделать freq на пропорциональные отрезки

freq db 7,8,10,11,12,13,14,15,19,28,32,34,35,38,39,40,41,42,44,45,46,47,48,49,50,51

затем stdcall random,51 и обходить весь freq в поисках выпавшего числа для взятия индекса? freq хранится в той же базе как свойство каждого из object, перечитывать всю базу накладно, разве только выносить freq в отдельную (хотя тоже перебирать сотни тысяч freq'ов долго)

 

bogrus
Количество элементов массива в самом минимальном случае (моем неотлаженном) будет равно числу элементов, для которых заданы вероятности их появления

 

Folk Acid

Ага

Возможно, если надо сделать идеальна, то надо оптимизировать поиск (методом деления пополам или типа того).