Полезная информация

Mozilla Россия — свежие версии программ Mozilla, а также масса полезной информации по каждому продукту.
  • Форумы
  •  » Разработка
  •  » Как выбрать из массива с заданным распределением вероятностей?

№119-03-2009 05:41:27

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Как выбрать из массива с заданным распределением вероятностей?

Извините, если это оффтоп. У меня вопрос не столько по конкретному коду, сколько по алгоритму.
Не могу целый день допереть, как это можно сделать просто и эффективно.
Помогите, пожалуйста, кто сталкивался.

Задача такая: есть массив из n элементов. Мне нужно из него выбрать случайный элемент. Но не с равной вероятностью. Например, чтобы чем ближе к хвосту массива, тем реже (или чаще, неважно) элемент выбирался. Скажем, чтобы последние элементы выбирались в k раз чаще первых. Распределение вероятностей между этими двумя точками (первым и последним эл-тами) может быть любым (в идеале - линейным, т.е., чтобы вероятность выбора конкретного эл-та росла линейно от его индекса), погрешности k тоже допустимы... лишь бы алгоритм был шустрым, чтобы всё можно было сделать на интерпретируемом языке вроде JavaScript.

Отредактировано alex_past (19-03-2009 05:48:17)

Отсутствует

 

№219-03-2009 05:52:09

ПротопопулуS
2,4716 THz на каждое из 64-х ядер...
 
Группа: Members
Откуда: Местное я
Зарегистрирован: 16-12-2008
Сообщений: 1515
UA: Firefox 3.1

Re: Как выбрать из массива с заданным распределением вероятностей?

i = n * Math.round(1/Math.random()); //i - индекс элемента массива.
Гарантирует гиперболическую зависимость между распределением вероятности.
Элементы с большим номером будут выбираться чаще. Математика 8-го класса блин! :lol:
Чтобы избежать исключения, надо в дроби к random() добавить хоть чуть-чуть, т.е. 1/(Math.random()+0.0000001) :cool:

Отредактировано ПротопопулуS (19-03-2009 06:00:56)


Продам: совесть, ответственность, вежливость, воспитанность. Недорого.

Отсутствует

 

№319-03-2009 06:00:37

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Спасибо огромное!
Я тоже сразу об этом подумал :) Но сижу третьи сутки в глубокой отладке, башка не варит совершенно, так что никак не могу сообразить: как мне при этом получить требуемое k (отношение вероятностей выбора первого и последнего эл-тов задано и должно быть фиксировано независимо от числа элементов, которое может меняться)

Отредактировано alex_past (19-03-2009 06:01:50)

Отсутствует

 

№419-03-2009 09:56:35

Forest
Участник
 
Группа: Members
Откуда: Обнинск
Зарегистрирован: 05-04-2005
Сообщений: 1778
UA: Firefox 3.0

Re: Как выбрать из массива с заданным распределением вероятностей?

ПротопопулуS
Только наверное округлять надо не так, а i = Math.round(n/Math.random()); ;)


---  ---

Отсутствует

 

№519-03-2009 10:09:09

ПротопопулуS
2,4716 THz на каждое из 64-х ядер...
 
Группа: Members
Откуда: Местное я
Зарегистрирован: 16-12-2008
Сообщений: 1515
UA: Firefox 3.1

Re: Как выбрать из массива с заданным распределением вероятностей?

Forest, а верное однако замечание!!! :cool:


Продам: совесть, ответственность, вежливость, воспитанность. Недорого.

Отсутствует

 

№619-03-2009 10:28:51

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Спасибо вам обоим.
Принцип понятен. Но так я получаю отношение вероятностей выбора первого и последнего эл-тов, зависящее от размера массива. А мне нужно, чтобы оно было фиксированным. Этот параметр задаётся извне - самим условием задачи :)

Отсутствует

 

№719-03-2009 10:35:15

ПротопопулуS
2,4716 THz на каждое из 64-х ядер...
 
Группа: Members
Откуда: Местное я
Зарегистрирован: 16-12-2008
Сообщений: 1515
UA: Firefox 3.1

Re: Как выбрать из массива с заданным распределением вероятностей?

Но так я получаю отношение вероятностей выбора первого и последнего эл-тов, зависящее от размера массива.

Тут от числа n зависит только номер индекса элемента, а не распределение вероятности,
т.е. чем больше элементов в массиве, тем соответственно больше индекс.


Продам: совесть, ответственность, вежливость, воспитанность. Недорого.

Отсутствует

 

№819-03-2009 11:15:05

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Увы, нет :(
Такая штука, конечно, не сработает:

Выделить код

Код:

i = Math.round(n/Math.random());

- она ведь будет давать индексы i не от 0 до n, а от n до бесконечности. А вот если попробовать её переписать правильно (нормировать как угодно), то сразу будет видно, что отношение вероятностей выбора первого эл-та к последнему задать не выйдет.

Отсутствует

 

№919-03-2009 11:25:16

ПротопопулуS
2,4716 THz на каждое из 64-х ядер...
 
Группа: Members
Откуда: Местное я
Зарегистрирован: 16-12-2008
Сообщений: 1515
UA: Firefox 3.1

Re: Как выбрать из массива с заданным распределением вероятностей?

В таком случае можно попробовать:

i = Math.round( n * x^2) или i = Math.round( n * x^(1/2)), где x = Math.random();

Вроде должно сработать. В первом случае чаще будут выбираться первые элементы массива.
Надо ещё добавить, что чем выше степень, тем больше разница между вероятностями.

Отредактировано ПротопопулуS (19-03-2009 11:29:17)


Продам: совесть, ответственность, вежливость, воспитанность. Недорого.

Отсутствует

 

№1019-03-2009 11:50:37

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Вот оно, спасибище!
Я Ваш погробжизненный должник :)
Вот так примерно оно должно выглядеть:

Выделить код

Код:

i=Math.round(Math.random()*Math.random()*n);

Или как у Вас - просто один рандом взять и его в какую-то степень возвести, не обязательно в квадрат.
Теперь осталось понять, как это дело нормировать. Чтобы вышло что-то вроде функции, куда можно передать n и k и получить случайное i.
Отосплюсь - соображу :)

Отредактировано alex_past (19-03-2009 12:02:09)

Отсутствует

 

№1120-03-2009 09:29:01

Forest
Участник
 
Группа: Members
Откуда: Обнинск
Зарегистрирован: 05-04-2005
Сообщений: 1778
UA: Firefox 3.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Но это всё конечно подгонки :(
И по-хорошему надо злобно ботать тервер на эту тему (хотя мб это можно и найти) ;)

Но можно попробовать сделать так (но не то, чтобы это совсем просто):
Дано:
1. Равномерное распределение на [0.,1.) (Math.random());
2. Интервал получения нужной случайной величины [a,b];
3. Распределение этой случайной величины в виде массива F(a:b), где в каждом элементе содержится вероятность получения этого значения (и сумма по всем должна быть == 1.).
Подготовка:
4. По F сделаем правильную функцию распределения P: уже на [a,b-1] (так как  (P(b)==1.) - не принципиально - вопрос построения поиска), но в i-ом элементе содержится вероятность всех значение <= i.
Замечание:
5. Равномерное распределение на [a,b] получается как a+Math.round((b-a+1)*Math.random()).
Решение:
а) Получаем r=Math.random();
б) Ищем r в P (бинарным поиском должно быть очень быстро);
в) Найденный индекс и будет нашей случайной величиной.

Вроде нигде не ошибся:)

Отредактировано Forest (20-03-2009 09:31:44)


---  ---

Отсутствует

 

№1220-03-2009 10:28:22

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Спасибо большое!
А я отоспался и за час всё сделал :)
Чтобы закрыть тему - соберу все советы в кучу: авось, кому-то ещё пригодится.
Итак, мне надо было получить линейно нарастающее распределение вероятностей выбора элементов:

pic2.gif

Отличный совет дал ПротопопулуS для нелинейных распределений, причем степенью (a) можно регулировать изгиб. На псевдокоде:

Выделить код

Код:

i=round((random()^a)*n);

Совет для произвольных распределений Forest еще лучше:

pic1.gif

Аппроксимируем распределение такой ступенчатой функцией. Заводим массив размером M, хранящий значения "ступенек" (в сумме - единицу), а еще лучше - нарастающую сумму с нулевого эл-та и по текущий. Чем больше погрешность допустима, тем меньше можно сделать массив.
Кидаем кости - получаем рандомное число от 0 до 1, циклом по массиву (или бинарным поиском) находим индекс эл-та, хранящего эту нарастающую сумму.
Но число наших исходных эл-тов (из которых в результате нам и надо выбрать случайный) равно N. То есть, каждый эл-т массива вероятностей представляет N/M эл-тов исходного набора. Поэтому, получив индекс, кидаем кости ещё раз, и полученное число в диапазоне 0...1 добавляем к индексу. Потом остается только умножить на N/M и округлить, и получаем индекс эл-та исходного набора.

Но мне нужен был частный случай - линейно нарастающая вероятность. И этот случай можно реализовать гораздо проще.
Гляньте на верхнюю картинку. По х там индексы, по y - нормированная вероятность (т.е., последний эл-т выпадает в K раз чаще первого)
Кидая кости, получаем случайное число. Просто будем считать, что случайное число соответствует отношению площадей, а не индексу напрямую, вот и всё :)
Нам нужно кинуть кости, получить число R в диапазоне 0...1, а потом найти, для какого индекса отношение площади фигуры - ограниченной осями, красной линией и вертикалью от этого индекса - к площади всей фигуры (т.е., ограниченной вертикалью от максимального индекса) равно R. Наша программа всего лишь должна уметь решать простейшее квадратное уравнение :)

Отредактировано alex_past (20-03-2009 11:02:11)

Отсутствует

 

№1320-03-2009 19:29:44

Forest
Участник
 
Группа: Members
Откуда: Обнинск
Зарегистрирован: 05-04-2005
Сообщений: 1778
UA: Firefox 3.0

Re: Как выбрать из массива с заданным распределением вероятностей?

alex_past

Чем больше погрешность допустима, тем меньше можно сделать массив.

При чём тут это? Ведь диапазон целых у нас ограничен, так что регулировать точность таким образом нельзя :(
Если нужна точность - надо просто интегрировать функцию распределения по каждому интервалу и делить на интеграл от всего интервала (ну или потом нормировать) ;)
Причём если интеграл берётся, то точность получается машинная, а если нет - тогда брать его численно и оценки точности тоже есть (вот там как раз разбиение и можно измельчать для достижения точности).

Аппроксимируем распределение такой ступенчатой функцией.

Но в случае линейной функции это всё не нужно - достаточно взять значения функции в середине ячеек (собственно это будет метод прямоугольников для интегрирования) и пронормировать.

Наша программа всего лишь должна уметь решать простейшее квадратное уравнение

Минус такого подхода - он работает только для такой прямой - изменение угла потребует переделки программы.
И при этом ещё неизвестно, какая реализация проще и быстрее.
Но для учебного примера наверное правильнее реализовывать то, что придумал сам:)


---  ---

Отсутствует

 

№1422-03-2009 00:02:25

alex_past
Чайник
 
Группа: Members
Откуда: 14-ый рукав Млечного Пути
Зарегистрирован: 02-03-2009
Сообщений: 33
UA: Foxware 0.0

Re: Как выбрать из массива с заданным распределением вероятностей?

Forest пишет

alex_past

Чем больше погрешность допустима, тем меньше можно сделать массив.

При чём тут это? Ведь диапазон целых у нас ограничен, так что регулировать точность таким образом нельзя :(

Просто чем меньше ступенек (т.е., чем протяжённей по х каждая ступенька), тем дальше уйдут "углы" от исходной функции.
Вы просто немного неправильно задачу ставите. Нам ведь нужно получить вероятности выпадения эл-тов конечного набора. То есть, функция сама по себе дискретна (ступенчатая). Мы вводим "аппроксимирующий" массив, каждый элемент которого соответствует M/N элементам реального набора. Понятно, что чем ближе M/N к 1 (чем больше эл-тов у нас будет в M), тем погрешность будет меньше.

Аппроксимируем распределение такой ступенчатой функцией.

Но в случае линейной функции это всё не нужно - достаточно взять значения функции в середине ячеек (собственно это будет метод прямоугольников для интегрирования) и пронормировать.

Мы говорим об одном и том же :) Значения в серединах ячеек - они и хранятся в "аппроксимирующем" массиве :) Действительно, это метод прямоугольников.

Наша программа всего лишь должна уметь решать простейшее квадратное уравнение

Минус такого подхода - он работает только для такой прямой - изменение угла потребует переделки программы.
И при этом ещё неизвестно, какая реализация проще и быстрее.
Но для учебного примера наверное правильнее реализовывать то, что придумал сам:)

Согласен. Но есть для меня принципиальный плюс в таком решении: оно будет куда меньше грузить сервер. Дело в том, что пример это не учебный, но и не слишком серьёзный. Мне понадобилось для сайта (на PHP) сделать что-то вроде локальной баннерокрутилки, которая будет показывать в подвале страницы несколько случайных авторских статей. И при этом нужно, чтобы, чем выше оценка статьи, тем чаще она крутилась. Вот, собственно, и всё :)
Сами понимаете, что особая точность мне не нужна, просто сначала до того отупел, сидя в отладке, что сходу не сообразил, как это на коленке сделать, а потом заинтересовала сама задачка :)

Спасибо и Вам, и ПротопопулуS, вы мне в самом деле здорово помогли. Тем более, что я уже вижу, куда не помешает присобачить более серьезный вариант - вроде предложенного вами.

Отредактировано alex_past (22-03-2009 10:00:14)

Отсутствует

 
  • Форумы
  •  » Разработка
  •  » Как выбрать из массива с заданным распределением вероятностей?

Board footer

Powered by PunBB
Modified by Mozilla Russia
Copyright © 2004–2020 Mozilla Russia GitHub mark
Язык отображения форума: [Русский] [English]