|
|
|||||
Регистрация: Mar 2011
Сообщений: 35
|
У меня тоже самое, только с блек-джеком и стюардессами. :3
|
|
|||||
Регистрация: Apr 2010
Адрес: Earth
Сообщений: 1,897
|
wvxvw, меня смущает обилие числа "10". Сбивает с толку, где это длина вектора, а где вес(?).
Не мог бы ты заменить это на прямое обращение к свойству или на человекопонятную константу?
__________________
Загружаем картинки, минуя ошибки безопасности |
|
|||||
[+1 23.05.11]
Регистрация: Dec 2001
Сообщений: 4,159
|
public class Selector { public static function selectRandom(values:Array, weights:Array):uint { var rnd:uint = uint(calculateTotalWeight(weights) * Math.random()); return values[findIndex(weights, rnd)]; } private static function calculateTotalWeight(weights:Array /* uint */):uint { var total:uint = 0; for each (var weight:uint in weights) { total += weight; } return total; } private static function findIndex(weights:Array, target:uint):uint { var accumulated:uint = 0; var upperIndex:uint = weights.length - 1; for (var i:uint = 0; i < upperIndex; ++i) { accumulated += weights[i]; if (accumulated > target) { return i; } } return upperIndex; } }
__________________
GIT d++ s++:++ a C++$ UB++ P++ L+ E+ W+++ N++ w++ O+ M V- t-- 5-- X+ R+++ tv- b+++ D++ |
|
|||||
Регистрация: Nov 2009
Адрес: СПб
Сообщений: 2,236
|
Еще, кстати, вот так можно:
package { public class RandomVariant { public static function getVariant(variants:Vector.<int>, weights:Vector.<int>) : int { // Нормируем сумму весов к единице var weightsNormalized:Vector.<Number> = getWeightsNormalized(weights); // Получаем индекс варианта и возвращаем его значение var variantIndex:int = getVariantIndex(Math.random(), 0, weightsNormalized); return variants[variantIndex]; } private static function getVariantIndex(randomValue:Number,index:int,weightsNormalized:Vector.<Number>) : int { // Если randomValue меньше текущего элемента - значит нашли, иначе уменьшаем randomValue на его значение // и смотрим следующий элемент if (randomValue < weightsNormalized[index]) return index; else return(getVariantIndex(randomValue-weightsNormalized[index], index + 1, weightsNormalized)); } private static function getWeightsNormalized(weights:Vector.<int>) : Vector.<Number> { var weightsSum:int = 0; var weightsNormalized:Vector.<Number> = new Vector.<Number>; for (var i:int = 0; i < weights.length; i++) weightsSum += weights[i]; for (i = 0; i < weights.length; i++) weightsNormalized[i] = weights[i] / weightsSum; return weightsNormalized; } } } Последний раз редактировалось mikhailk; 22.05.2011 в 10:26. |
|
|||||
Modus ponens
|
ShadowsInRain:
Ага, я просто не видел ответов, когда писал. i.o.: 10 - там всегда длина массива, и не важно какого, т.как они должны быть одной длины (если они не будут одинаковыми, то работать не будет). crazy: А зачем единицу отнимать? Если длина = 10, то нужные индексы 0..9, т.е. последний нужный индекс = 9, а 9 < 10, если мы отнимем 1, то получится 9 < 9. mikhailk: Если уж оптимизировать / нормализировать, то есть смысл начинать искать подходящий вариант не с начала, а пытаться предугадать его позицию, но это может сработать только если распределение более-менее однородное. Другой вариант, при изменении веса - записывать общую суму (это будет дешевле, чем каждый раз ее пересчитывать). Опять же, на практике все будет зависеть от того, как часто и какая именно часть алгоритма используется, и какие реальные значения могут быть у весов.
__________________
Hell is the possibility of sanity |
|
|||||
Регистрация: Nov 2009
Адрес: СПб
Сообщений: 2,236
|
Цитата:
Относительно попыток предугадать позицию - не уверен. Хотя, если уже совсем лезть в бутылку, можно двоичное дерево построить. |
|
|||||
Регистрация: Oct 2010
Адрес: Новосиб
Сообщений: 122
|
var mass:Array = [10,10,20,10,10,10,100,10,10,10]; var variant:Array = [1,2,3,4,5,6,7,8,9,0]; function Chance(arr:Array):int { var len:uint = arr.length; var sum:Number = 0; for (var i:uint = 0; i<len; i++) { sum += arr[i]; } var rand:Number = Math.random(); var sum2:Number = 0; var num:int = 0; for (var k:uint = 0; k<len; k++) { sum2 += arr[k] / sum; if (rand<=sum2) { num = k; break; } } return num; } //test var test:Object = {} for (var n = 0; n<10000; n++){ var num:int = Chance(mass) if(!test[num]){ test[num] = 0; } test[num]++; } for (var names in test){ trace(variant[names]+" "+test[names]); } /* 1 562 2 552 3 977 4 532 5 466 6 514 7 4937 8 511 9 502 0 447 */ делаем рандом перебираем всё в цикле и плюсуем в переменную пока переменная не достигнет рандома. то что будет достигнуто рандомом и будет индексом в массиве чисел по шансу Последний раз редактировалось kseniya; 22.05.2011 в 14:53. |
|
|||||
Modus ponens
|
А еще, конечно, не мозговыносящий алгоритм, но уже интереснее...
package tests { import flash.display.Sprite; /** * ... * @author wvxvw */ public class ProbabilityTest extends Sprite { private const _variants:Vector.<uint> = new <uint>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; private const _weights:Vector.<uint> = new <uint>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; private var _sum:uint = 10; public function ProbabilityTest() { super(); // position: 0 total: 67 // position: 1 total: 107 // position: 2 total: 105 // position: 3 total: 113 // position: 4 total: 108 // position: 5 total: 88 // position: 6 total: 91 // position: 7 total: 107 // position: 8 total: 115 // position: 9 total: 99 this.testDistribution(); // exclude 5 from the pool completely this.setChance(5, 0); // 1,2,3,4,5,5,6,7,8,9 // position: 0 total: 110 // position: 1 total: 120 // position: 2 total: 107 // position: 3 total: 117 // position: 4 total: 117 // position: 5 total: 0 // position: 6 total: 97 // position: 7 total: 115 // position: 8 total: 108 // position: 9 total: 109 this.testDistribution(); // double the chaces for 6 this.setChance(6, 2); // 1,2,3,4,5,5,7,8,9,10 // position: 0 total: 110 // position: 1 total: 107 // position: 2 total: 106 // position: 3 total: 105 // position: 4 total: 88 // position: 5 total: 0 // position: 6 total: 205 // position: 7 total: 85 // position: 8 total: 93 // position: 9 total: 101 this.testDistribution(); } public function setChance(of:uint, to:uint):void { of = of % 10; this._sum = this.updateIndices(of, to - this.weightAt(of)); } private function weightAt(index:uint):uint { var previous:uint; if (index) previous = this._weights[index - 1]; return this._weights[index] - previous; } private function updateIndices(from:uint, by:int):uint { while (from < 10) this._weights[from++] += by; return this._sum + by; } private function testDistribution():void { var results:Vector.<uint> = new Vector.<uint>(10); var i:int; for (i = 0; i < 1e3; i++) { results[this.selectRandom()]++; } for (i = 0; i < 10; i++) { trace("position:", i, "total:", results[i]); } } private function selectRandom():uint { var random:uint = this._sum * Math.random(); var index:uint = 4; if (this._weights[index] <= random) { while (index < 10) { if (this._weights[index++] > random) { index--; break; } } } else { while (index) { if (this._weights[--index] <= random) { index++; break; } } } return index; } } } ЗЫ. Не обязательно двоичное дерево, но тоже вариант. Можно предугадать позицию, если, например, мы знаем, что на каждый "шанс" у нас приходится по, скажем, 2 деления, то, тогда, если рандом выдал 8, то это значит, что это должно быть где-то в районе 4-го элемента. Ну или хотябы просто считать не с начала, а с середины, в таком случае наш самый худший случай будет в 2 раза меньше, чем если мы всегда будем считать от начала. EDIT: Да, а еще можно было бы находить предполагаемый участок, куда упал рандомальный выбор по типу как в quicksort, т.е. делить оставшийся диапазон на 2 все время... хм... ну, вечером наверн сделаю
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 22.05.2011 в 14:12. |
|
|||||
[+1 23.05.11]
Регистрация: Dec 2001
Сообщений: 4,159
|
Если длина = 10, то проверять имеет смысл только индексы 0..8. Поскольку если ни в одном из их нашего числа нет, то оно однозначно в 9-м. Проверять то, что мы и без того знаем -- бессмыслено.
__________________
GIT d++ s++:++ a C++$ UB++ P++ L+ E+ W+++ N++ w++ O+ M V- t-- 5-- X+ R+++ tv- b+++ D++ |
Часовой пояс GMT +4, время: 18:51. |
|
« Предыдущая тема | Следующая тема » |
Теги |
выпад , массив , Рандом , шанс |
Опции темы | |
Опции просмотра | |
|
|