Процентый шанс ответа. - Страница 4

i.o. · 22.05.2011, 19:35

дык я не про сумму, а про вот это:

Код AS3:

 
		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;
		}

Crazy · [+1 23.05.11]

Цитата:

Сообщение от i.o.

Насколько вижу, все равно требуется поиск, будь то цикл, дерево или еще что-то..
Т.е. тупо по индексу / хэшу не получится взять. Ну или хотябы просто применить какую то мат. функцию (без циклов и поиска).

Итак, у нас два варианта: дублирование и веса. Первый вариант дает нам рост стоимости при увеличении диапазона весов, второй -- при увеличении количества вариантов. Но вот если первое дает нам рост O(n), то второй O(log(m)) при использовании дерева, где n и m соответственно диапазон и количество вариантов. Что вовсе не одно и то же.

При малых n и m выбор между этими алгоритмами эквипенисуален.

Помним также о том, что при необходимости сделать соотношения весов, к примеру, 1:1.25 в первом варианте нужно сразу идти и убивать себя об стену.

wvxvw · 22.05.2011, 22:29

i.o.:
дык ничего же не прибавляется, просто проверяем элементы массива

Dukobpa3 · 23.05.2011, 00:23

Написал вот.....

Оно конечно комбайн, но универсально. И есть пару бонусов в виде "пересчет только тогда когда меняется состав вектора или веса, а в остальные моменты просто выбор и сравнение". Ввел такое понятие как "чекПоинт" Элемента. И да, для элемента сделал свой класс. Хотя наверное можно было обойтись и обжектом.

Собственно вот:
Код класса элемента:

Код AS3:

package weights_array 
{
	import flash.events.EventDispatcher;
 
	/**
	 * ...
	 * @author Dukobpa3
	 */
	public class Element extends EventDispatcher 
	{
		//*********************************************************************
		//
		//                                         PARAMETERS
		//
		//*********************************************************************
		//-----------------------------
		//		PRIVATE
		//-----------------------------
		private var _weightIndex:int = 1;
		private var _checkPoint:int;
		private var _data:Object;
 
		//*********************************************************************
		//
		//                                         FUNCTIONS
		//
		//*********************************************************************
		//-----------------------------
		//		CONSTRUCTOR, INIT
		//-----------------------------
		public function Element(data:Object, weight:int) 
		{
			super();
 
			this._data = data;
			_weightIndex = weight
		}
 
		//-----------------------------
		//		GETTERS/SETTERS
		//-----------------------------
		public function get weight():int 
		{
			return _weightIndex;
		}
 
		public function set weight(value:int):void 
		{
			_weightIndex = value;
		}
 
		public function get data():Object 
		{
			return _data;
		}
 
		public function get checkPoint():int 
		{
			return _checkPoint;
		}
 
		public function set checkPoint(value:int):void 
		{
			if (_checkPoint != value)
			{
				_checkPoint = value;
			}
		}
	}
 
}

Код класса Вектора:

Код AS3:

package weights_array 
{
	import flash.events.Event;
	import flash.events.EventDispatcher;
	/**
	 * ...
	 * @author Dukobpa3
	 */
	public class WeightsArray extends EventDispatcher
	{
		//*********************************************************************
		//
		//      PARAMETERS
		//
		//*********************************************************************
		//-----------------------------
		//		PRIVATE
		//-----------------------------
		/**
		 * Vector of elements
		 */
		private var _elements:Vector.<Element> = new Vector.<Element>();
 
		/**
		 * глобальный вес элементов
		 */
		private var _totalWeight:int = 0;
 
		/**
		 * Дефолтный вес элементов
		 */
		private var _defaultWeight:int;
		//*********************************************************************
		//
		//    	FUNCTIONS
		//
		//*********************************************************************
		//-----------------------------
		//		CONSTRUCTOR, INIT
		//-----------------------------
		/**
		 * Конструктор, принимает в качестве параметра дефолтный вес элемента
		 * @param	defWeight
		 */
		public function WeightsArray(defWeight:int = 1) 
		{
			super();
 
			defaultWeight = defWeight;
		}
 
		//-----------------------------
		//		PUBLIC
		//-----------------------------
		/**
		 * добавляет указанный элемент в массив элементов
		 * @param	element
		 */
		public function push(data:Object):void
		{
			_elements.push(new Element(data, _defaultWeight));
			_totalWeight += _defaultWeight;
 
			_elements.sort(compare);
			calcCheckPoints();
		}
 
		/**
		 * Достает из массива элемент с указанным индексом
		 * @param	index
		 * @return
		 */
		public function distoreIndex(index:int):void
		{
			_totalWeight -= _elements[index].weight;
 
			_elements.splice(index, 1);
			_totalWeight -= _elements[index].weight;
			_elements.sort(compare);
			calcCheckPoints();
		}
 
		/**
		 * Достает рандомный элемент из массива с учетом веса
		 * @return
		 */
		public function getRandom():Object
		{
			var rnd:int = Math.random() * _totalWeight;
			var fIndex:int = 0;
			var lIndex:int = _elements.length - 1;
 
			trace("rnd: ", rnd);
			trace("start index: ", fIndex, lIndex);
 
			/**
			 * тут проверяем с какого края нам ближе к указанному элементу
			 */
			if (rnd < _elements.length * 0.5)
			{
				/**
				 * тут проходим с начала вектора к концу
				 */
				while (_elements[fIndex + 1].checkPoint <= rnd && fIndex < _elements.length - 1)
				{
					fIndex ++;
				}
 
				trace("last index: ", fIndex, lIndex);
				return _elements[fIndex].data;
			}
			else
			{
				/**
				 * а тут с конца к началу
				 */
				while (_elements[lIndex - 1].checkPoint >= rnd)
				{
					lIndex --;
				}
 
				trace("last index: ", fIndex, lIndex);
				return _elements[lIndex].data;
			}
 
		}
 
		/**
		 * устанавливаем мануально вес для элемента по указанному индексу
		 * @param	index
		 * @param	weight
		 */
		public function setWeight(index:int, weight:int):void
		{
			_totalWeight -= _elements[index].weight
			_elements[index].weight = weight;
			_totalWeight += _elements[index].weight
 
			_elements.sort(compare);
			calcCheckPoints();
		}
 
		//-----------------------------
		//		GETTERS/SETTERS
		//-----------------------------
		public function set defaultWeight(value:int):void 
		{
			if (_defaultWeight != value)
			{
				_defaultWeight = value;
			}
		}
 
		public function get defaultWeight():int 
		{
			return _defaultWeight;
		}
 
		//-----------------------------
		//		UTILLS
		//-----------------------------
		/**
		 * функция сравнения для сортировки вектора
		 * @param	first
		 * @param	second
		 * @return
		 */
		private function compare(first:Element, second:Element):Number
		{
			var result:Number;
			result = first.weight < second.weight ? -1 : first.weight > second.weight ? 1 : 0;
			return result;
		}
 
		/**
		 * расчитывает чекПоинты для каждого элемента
		 */
		private function calcCheckPoints():void 
		{
			var currPoint:int = _elements[0].weight;
 
			for (var i:int = 0 ; i < _elements.length ; i ++ )
			{
				_elements[i].checkPoint = currPoint;
				currPoint += _elements[i].weight;
			}
		}
	}
 
}

Crazy · [+1 23.05.11]

(потираю потные ладошки и жду, когда же в коде появятся следы паттернов Observer, Visitor и, к примеру, AbstractFactory

)

wvxvw · 23.05.2011, 00:30

Ну и обещаный аутистический вариант:

Код AS3:

package tests 
{
	import flash.display.Sprite;
 
	/**
	 * ...
	 * @author wvxvw
	 */
	public class ProbablityTester 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 ProbablityTester() 
		{
			super();
			//position: 0 total: 102
			//position: 1 total: 95
			//position: 2 total: 99
			//position: 3 total: 106
			//position: 4 total: 105
			//position: 5 total: 102
			//position: 6 total: 106
			//position: 7 total: 88
			//position: 8 total: 99
			//position: 9 total: 98
			this.testDistribution();
			// exclude 5 from the pool completely
			this.setChance(5, 0);
			//position: 0 total: 118
			//position: 1 total: 108
			//position: 2 total: 102
			//position: 3 total: 115
			//position: 4 total: 100
			//position: 5 total: 0
			//position: 6 total: 113
			//position: 7 total: 126
			//position: 8 total: 108
			//position: 9 total: 110
			this.testDistribution();
			// double the chaces for 6
			this.setChance(6, 2);
			//position: 0 total: 101
			//position: 1 total: 110
			//position: 2 total: 107
			//position: 3 total: 94
			//position: 4 total: 101
			//position: 5 total: 0
			//position: 6 total: 197
			//position: 7 total: 89
			//position: 8 total: 104
			//position: 9 total: 97
			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 len:uint = this._weights.length;
			var index:uint = len >> 1;
			var step:uint = index;
 
			do
			{
				step = (step >> 1) + (step & 1);
				if (this._weights[index] > random)
				{
					if (!index || this._weights[index - 1] <= random) break;
					else index -= step;
				}
				else
				{
					index += step;
					if (index >= len) index = len - 1;
				}
			}
			while (true);
			return index;
		}
	}
}

Dukobpa3 · 23.05.2011, 00:32

Цитата:

Сообщение от i.o.

Насколько вижу, все равно требуется поиск, будь то цикл, дерево или еще что-то..
Т.е. тупо по индексу / хэшу не получится взять. Ну или хотябы просто применить какую то мат. функцию (без циклов и поиска).

Если для элемента завести отдельный класс к примеру то вполне получится так сделать. Например в моем варианте вместо while с перебором можно сделать просто фильтр по чек-поинту.

Над мат-функцией сейчас думаю, но в любом случае где-то нужно хранить веса, поэтому ничего особо сэкономить не получится

Crazy · [+1 23.05.11]

Цитата:

Сообщение от Dukobpa3

Код AS3:

/**
 * расчитывает чекПоинты для каждого элемента
 */
private function calcCheckPoints():void 
{
  var currPoint:int = _elements[0].weight;
 
  for (var i:int = 0 ; i < _elements.length ; i ++ )
  {
    _elements[i].checkPoint = currPoint;
    currPoint += _elements[i].weight;
  }
}

Очевидно, если изменился вес элемента с индексом k, то пересчет достаточно делать не с 0, а с k.

Dukobpa3 · 23.05.2011, 00:35

ну это да, это за 15 минут написано только что, оптимизации там место найдется

Crazy · [+1 23.05.11]

Цитата:

Сообщение от Dukobpa3

ну это да, это за 15 минут написано только что, оптимизации там место найдется

Это я, собственно, стебусь. Степень оптимизации уже предложенных решений представляется мне избыточной.