|
|
|||||
Взвешенный рандом
Есть массив с любым кол-вом элементов, хранящих числа от 0 до 99, обозначающих вес текущего элемента при выпадении в рандоме.
Тоесть, если в массиве будет 2 элемента, и у одного будет вес 4, у другого - 6, то вероятность выпадения первого должна быть 0.4, а вероятность выпадения 2 - 0.6 Если в массиве будет 3 элемента: 42, 7, 29, то вероятность выпадения первого элемента должна быть 42/(42+7+29), второго 7/(42+7+29), третьего 29/(42+7+29). Написать наиболее эффективный алгоритм, возвращающий рандомный элемент с частотой, зависящей от его веса.(я уже)
__________________
There is no thing in this world that is not simple. |
|
|||||
Регистрация: Oct 2006
Сообщений: 2,281
|
-нормируем массив чтоб сумма всех элементов была равна 1
-кидаем рандомом число от 0 до 1 -считаем в какой интервал угодил рандом -... -profit Код писать лень. |
|
|||||
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; } } }
__________________
Ко мне можно и нужно обращаться на ты) |
|
|||||
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; } Цитата:
1) слабость к частым пересозданиям; 2) невозможность присваивания весам дробных значений.
__________________
There is no thing in this world that is not simple. Последний раз редактировалось ZackMercury; 12.06.2017 в 15:51. |
|
|||||
Цитата:
Если веса сильно маленькие, то можно, например, заранее умножить все на 100 или 1000 Цитата:
__________________
Ко мне можно и нужно обращаться на ты) |
|
|||||
Цитата:
__________________
There is no thing in this world that is not simple. |
|
|||||
Ну да)
Но в твоем алгоритме тоже нельзя задать дробные числа. Вернее задать то можно, только смысла в этом нет. Все равно при переборе циклом используются целые индексы. То есть моим способом можно сделать так же, просто округляя по Math.round() каждое число, при первоначальном расчете количества ячеек
__________________
Ко мне можно и нужно обращаться на ты) |
|
|||||
А да, все верно, я не правильно представил его работу.
Слабое место твоего алгоритма в том, что происходит перебор всего массива, пока не будет удовлетворено условие, и отсутствует типизация переменных.
__________________
Ко мне можно и нужно обращаться на ты) |
|
|||||
Злая привычка из JS. Ща поправлю и сравню результаты.
Да, действительно, мой стал намного быстрее. поставил на 10 миллионов итераций и вот такие результаты Цитата:
__________________
There is no thing in this world that is not simple. Последний раз редактировалось ZackMercury; 12.06.2017 в 20:12. |
Часовой пояс GMT +4, время: 18:21. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|