Форум Flasher.ru - Процентый шанс ответа.

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Процентый шанс ответа. (http://www.flasher.ru/forum/showthread.php?t=156420)

У меня тоже самое, только с блек-джеком и стюардессами. :3

wvxvw, меня смущает обилие числа "10". Сбивает с толку, где это длина вектора, а где вес(?).
Не мог бы ты заменить это на прямое обращение к свойству или на человекопонятную константу? :)

Цитата:

Сообщение от GBee (Сообщение 997771)

Я не понял, если честно? Поясните как? Пока вариант ИО элегантней :о))

Код AS3:

    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;

        }

 

    }

P.S. Граждане, будьте проще.

Все-таки i.o. победил в моей голове. Но спасибо за ликбез.

Еще, кстати, вот так можно:

Код AS3:

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;

                }

 

        }

 

}

ShadowsInRain:
Ага, я просто не видел ответов, когда писал.

i.o.:
10 - там всегда длина массива, и не важно какого, т.как они должны быть одной длины (если они не будут одинаковыми, то работать не будет).

crazy:

Код:

var upperIndex:uint = weights.length - 1;

А зачем единицу отнимать? :) Если длина = 10, то нужные индексы 0..9, т.е. последний нужный индекс = 9, а 9 < 10, если мы отнимем 1, то получится 9 < 9.

mikhailk:
Если уж оптимизировать / нормализировать, то есть смысл начинать искать подходящий вариант не с начала, а пытаться предугадать его позицию, но это может сработать только если распределение более-менее однородное.
Другой вариант, при изменении веса - записывать общую суму (это будет дешевле, чем каждый раз ее пересчитывать).
Опять же, на практике все будет зависеть от того, как часто и какая именно часть алгоритма используется, и какие реальные значения могут быть у весов.

Цитата:

Если уж оптимизировать / нормализировать, то есть смысл начинать искать подходящий вариант не с начала, а пытаться предугадать его позицию, но это может сработать только если распределение более-менее однородное.

Мне мой вариант нравится тем, что там всего ничего кода. Если веса нормализовать в момент их изменения - остается вообще 5 строк фактически.

Относительно попыток предугадать позицию - не уверен. Хотя, если уже совсем лезть в бутылку, можно двоичное дерево построить. :)

Код AS3:

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

*/

Суммируем всё = это будет 100% (т.е. еденица);
делаем рандом
перебираем всё в цикле и плюсуем в переменную пока переменная не достигнет рандома. то что будет достигнуто рандомом и будет индексом в массиве чисел по шансу

А еще, конечно, не мозговыносящий алгоритм, но уже интереснее... :p

Код AS3:

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;

                }

        }

}

Добавлено через 4 минуты
ЗЫ. Не обязательно двоичное дерево, но тоже вариант. Можно предугадать позицию, если, например, мы знаем, что на каждый "шанс" у нас приходится по, скажем, 2 деления, то, тогда, если рандом выдал 8, то это значит, что это должно быть где-то в районе 4-го элемента. Ну или хотябы просто считать не с начала, а с середины, в таком случае наш самый худший случай будет в 2 раза меньше, чем если мы всегда будем считать от начала.

EDIT: Да, а еще можно было бы находить предполагаемый участок, куда упал рандомальный выбор по типу как в quicksort, т.е. делить оставшийся диапазон на 2 все время... хм... ну, вечером наверн сделаю :)

Цитата:

Сообщение от wvxvw (Сообщение 997810)

А зачем единицу отнимать? :) Если длина = 10, то нужные индексы 0..9

Если длина = 10, то проверять имеет смысл только индексы 0..8. Поскольку если ни в одном из их нашего числа нет, то оно однозначно в 9-м. Проверять то, что мы и без того знаем -- бессмыслено.