Взвешенный рандом

[ZackMercury]

Есть массив с любым кол-вом элементов, хранящих числа от 0 до 99, обозначающих вес текущего элемента при выпадении в рандоме.
var arr = [];
for(var i = 0; i < N; i ++)
arr.push(Math.floor(Math.random()*100));
Тоесть, если в массиве будет 2 элемента, и у одного будет вес 4, у другого - 6, то вероятность выпадения первого должна быть 0.4, а вероятность выпадения 2 - 0.6
Если в массиве будет 3 элемента: 42, 7, 29, то вероятность выпадения первого элемента должна быть 42/(42+7+29), второго 7/(42+7+29), третьего 29/(42+7+29).
Написать наиболее эффективный алгоритм, возвращающий рандомный элемент с частотой, зависящей от его веса.(я уже)

[undefined]

-нормируем массив чтоб сумма всех элементов была равна 1
-кидаем рандомом число от 0 до 1
-считаем в какой интервал угодил рандом
-...
-profit
Код писать лень.

[caseyryan]

package {
import flash.display.Sprite;

public class ProbabilityByWeight extends Sprite {

private var _weights: Array = [53, 25, 18, 199];
private var _values: Array = [];
private var _totalCells: int = 0;

public function ProbabilityByWeight() {
trace(getRandomValue());
}

private function fillValuesArray():void {
if (_totalCells < 1) {
_totalCells = getTotalNumberOfCells();
var numWeights:int = _weights.length;
for (var i:int = 0; i < numWeights; i++) {
for (var j:int = 0; j < _weights[i]; j++) {
_values.push(_weights[i]);
}
}
}
}


private function getRandomValue():int {
if (!_values.length) {
fillValuesArray();
}
if (_totalCells > 0) {
return _values[int(Math.random() * _totalCells)];
}

return 0;
}


/**
* получить максимальное количество ячеек-вероятности
* @return
*/
private function getTotalNumberOfCells():int {
var result:int = 0;
for each (var value:int in _weights) {
result += value;
}
return result;
}
}

}
Конечно, навернякая это не самый эффективный способ - хренние массива с заполненными числами, но рабочий. Интересно посмотреть на другие решения

[ZackMercury]

caseyryan, твой в 5 раз быстрее моего
private function rand():int
{
var rand = Math.random() * _totalCells;
var sum = 0;
var l = _weights.length;
for(var i = 0; i < l; i ++)
{
sum += _weights[i];
if(sum > rand) return i;
}
return -1;
}
Но... если нужно часто создавать и уничтожать массивы весов с новыми значениями, думаю, твой проиграет.

Однако существует алгоритм, который в два раза быстрее моего, но не зависит от доп массивов.

Добавлено через 6 часов 18 минут
Вот он:
private function pickOne():int
{
var i = 0;
var r = Math.random();
while (r > 0)
r -= _weights[i++]/_totalCells;
return --i;
}

Результаты:

Попытка один:
caseyryan: 791
Zackmercury: 3571
???: 1745
Попытка два:
caseyryan: 780
Zackmercury: 3615
???: 1720


Минус твоего алгоритма в
1) слабость к частым пересозданиям;
2) невозможность присваивания весам дробных значений.

[caseyryan]

невозможность присваивания весам дробных значений.
А зачем?
Если веса сильно маленькие, то можно, например, заранее умножить все на 100 или 1000
слабость к частым пересозданиям;
Ну, если веса часто меняются, то да.

[ZackMercury]

Если веса сильно маленькие, то можно, например, заранее умножить все на 100 или 1000
Представь, во сколько раз увеличится твой массив :D И соответственно, время на обращение.

[caseyryan]

Ну да)
Но в твоем алгоритме тоже нельзя задать дробные числа. Вернее задать то можно, только смысла в этом нет. Все равно при переборе циклом используются целые индексы. То есть моим способом можно сделать так же, просто округляя по Math.round() каждое число, при первоначальном расчете количества ячеек

[ZackMercury]

Индексы то целые, а веса - дробные, вот чудеса!

[caseyryan]

А да, все верно, я не правильно представил его работу.
Слабое место твоего алгоритма в том, что происходит перебор всего массива, пока не будет удовлетворено условие, и отсутствует типизация переменных.

[ZackMercury]

Злая привычка из JS. Ща поправлю и сравню результаты.
Да, действительно, мой стал намного быстрее. поставил на 10 миллионов итераций и вот такие результаты

#1
c: 2875
z: 4470
?: 3559
#2
c: 2871
z: 4493
?: 3605

[caseyryan]

Еще попробуй сделать предварительную сортировку массива

_weights.sort(Array.NUMERIC);

Должно тоже в некоторых случаях ускорить выполнение

[ZackMercury]

Разве что по убыванию.

[dark256]

нифига не понял :)))

[Psycho Tiger]

Голосую за вариант от undefined