Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flasher.ru > Флейм

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 11.06.2017, 16:31
ZackMercury вне форума Посмотреть профиль Отправить личное сообщение для ZackMercury Найти все сообщения от ZackMercury
  № 1  
Ответить с цитированием
ZackMercury
 
Аватар для ZackMercury

блогер
Регистрация: Jul 2013
Адрес: Север
Сообщений: 1,918
Записей в блоге: 23
Отправить сообщение для ZackMercury с помощью ICQ Отправить сообщение для ZackMercury с помощью Skype™
По умолчанию Взвешенный рандом

Есть массив с любым кол-вом элементов, хранящих числа от 0 до 99, обозначающих вес текущего элемента при выпадении в рандоме.
Код AS3:
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).
Написать наиболее эффективный алгоритм, возвращающий рандомный элемент с частотой, зависящей от его веса.(я уже)
__________________
There is no thing in this world that is not simple.

Старый 11.06.2017, 19:39
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 2  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,281
-нормируем массив чтоб сумма всех элементов была равна 1
-кидаем рандомом число от 0 до 1
-считаем в какой интервал угодил рандом
-...
-profit
Код писать лень.

Старый 11.06.2017, 19:39
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 3  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
Код AS3:
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;
		}
	}
 
}
Конечно, навернякая это не самый эффективный способ - хренние массива с заполненными числами, но рабочий. Интересно посмотреть на другие решения
__________________
Ко мне можно и нужно обращаться на ты)

Старый 12.06.2017, 09:12
ZackMercury вне форума Посмотреть профиль Отправить личное сообщение для ZackMercury Найти все сообщения от ZackMercury
  № 4  
Ответить с цитированием
ZackMercury
 
Аватар для ZackMercury

блогер
Регистрация: Jul 2013
Адрес: Север
Сообщений: 1,918
Записей в блоге: 23
Отправить сообщение для ZackMercury с помощью ICQ Отправить сообщение для ZackMercury с помощью Skype™
caseyryan, твой в 5 раз быстрее моего
Код AS3:
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 минут
Вот он:
Код AS3:
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) невозможность присваивания весам дробных значений.
__________________
There is no thing in this world that is not simple.


Последний раз редактировалось ZackMercury; 12.06.2017 в 15:51.
Старый 12.06.2017, 18:33
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 5  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
Цитата:
невозможность присваивания весам дробных значений.
А зачем?
Если веса сильно маленькие, то можно, например, заранее умножить все на 100 или 1000
Цитата:
слабость к частым пересозданиям;
Ну, если веса часто меняются, то да.
__________________
Ко мне можно и нужно обращаться на ты)

Старый 12.06.2017, 18:34
ZackMercury вне форума Посмотреть профиль Отправить личное сообщение для ZackMercury Найти все сообщения от ZackMercury
  № 6  
Ответить с цитированием
ZackMercury
 
Аватар для ZackMercury

блогер
Регистрация: Jul 2013
Адрес: Север
Сообщений: 1,918
Записей в блоге: 23
Отправить сообщение для ZackMercury с помощью ICQ Отправить сообщение для ZackMercury с помощью Skype™
Цитата:
Если веса сильно маленькие, то можно, например, заранее умножить все на 100 или 1000
Представь, во сколько раз увеличится твой массив И соответственно, время на обращение.
__________________
There is no thing in this world that is not simple.

Старый 12.06.2017, 19:04
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 7  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
Ну да)
Но в твоем алгоритме тоже нельзя задать дробные числа. Вернее задать то можно, только смысла в этом нет. Все равно при переборе циклом используются целые индексы. То есть моим способом можно сделать так же, просто округляя по Math.round() каждое число, при первоначальном расчете количества ячеек
__________________
Ко мне можно и нужно обращаться на ты)

Старый 12.06.2017, 19:13
ZackMercury вне форума Посмотреть профиль Отправить личное сообщение для ZackMercury Найти все сообщения от ZackMercury
  № 8  
Ответить с цитированием
ZackMercury
 
Аватар для ZackMercury

блогер
Регистрация: Jul 2013
Адрес: Север
Сообщений: 1,918
Записей в блоге: 23
Отправить сообщение для ZackMercury с помощью ICQ Отправить сообщение для ZackMercury с помощью Skype™
Индексы то целые, а веса - дробные, вот чудеса!
__________________
There is no thing in this world that is not simple.

Старый 12.06.2017, 19:44
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 9  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
А да, все верно, я не правильно представил его работу.
Слабое место твоего алгоритма в том, что происходит перебор всего массива, пока не будет удовлетворено условие, и отсутствует типизация переменных.
__________________
Ко мне можно и нужно обращаться на ты)

Старый 12.06.2017, 19:48
ZackMercury вне форума Посмотреть профиль Отправить личное сообщение для ZackMercury Найти все сообщения от ZackMercury
  № 10  
Ответить с цитированием
ZackMercury
 
Аватар для ZackMercury

блогер
Регистрация: Jul 2013
Адрес: Север
Сообщений: 1,918
Записей в блоге: 23
Отправить сообщение для ZackMercury с помощью ICQ Отправить сообщение для ZackMercury с помощью Skype™
Злая привычка из JS. Ща поправлю и сравню результаты.
Да, действительно, мой стал намного быстрее. поставил на 10 миллионов итераций и вот такие результаты
Цитата:
#1
c: 2875
z: 4470
?: 3559
#2
c: 2871
z: 4493
?: 3605
__________________
There is no thing in this world that is not simple.


Последний раз редактировалось ZackMercury; 12.06.2017 в 20:12.
Создать новую тему Ответ Часовой пояс GMT +4, время: 18:21.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 18:21.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.