Подскажите, как реализовать алгоритм случайного выбора из массива на основании веса каждого эл-та.
Поясняю, есть массив: строка(string), - вес(int). Вес в данном случае это относительное число которое устанавливает частоту выбора строки соответсвующей весу. Т.е. строка с весом 20 должна выбираться в 2 раза чаще чем строка с весом 10.

Схожий принцип реализует AdRotator из ASP.Net, там вес записываетя в impressions, на основании которого показываются банеры.

Ну а мне нужно на вход подать массив, на выходе получить строку. 

Подскажите как реализовать, или где копать что ли? Буду признателен за пример.

сделай например 
struct S
{
string str;
int w;

public S(string s)
{
str = s;
w = 0;
}

public int W
{
get
{
return w;
}
}

public string GetString()
{
w++;
return str;
}
}

в проге - массив 
S[] strings = new S[100];
for(int i = 0; i<strings.Length; i++)
{
strings[i] = new S("string " + i.ToString());
}

доступ к строке возможен только через GetString(), при запросе строки ее вес увеличивается.
Ну а потом - цикл по всему массиву S[] и смотришь, у кого  W круче, того и вызывают чаще 

ну а Random :
поставь 2 потока, поставь 2 порога, например выбрать все с весом не меньше чем 50 в один массив, остальные - в другой
один поток с таймером 10 сек, второй - 30 сек.
тот, что чаще фигачит - пусть с большим весом строки печатает, а медленный - "легковесные" 
Вот и получится, что весовые строки в три раза чаще вылетают.

Это сообщение отредактировал(а) tol05 - 12.5.2007, 20:09

мне в голову приходит только такое решение, надеюсь верное:

1. отсортировать данные так, чтобы меньшие веса шли в начале.
2. сгруппировать элемменты в новом массиве по значению веса. т.е., грубо говоря, создать массив массивов.
3. сгенерировать случайное значение в диапазоне от 0 до суммы весов всех групп.
4. последовательно перебирая все группы сравнивать вес гурппы с полученным случайным числом.
5. если случайное число больше веса группы, вычесть вес группы из этого числа и перейти к следующей группе.
6. иначе, искомая группа найдена. внутри группы элементы равновероятны, т.е. обычный рандом, как при бросании игральной кости.

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

tol05, что-то какие-то пляски с бубном    

Имитационное моделирование СВ

tol05, Чесно говоря, не совсем въехал про потоки... Принцип понятен, но..... а если у меня 50 строк в массиве, мне 50 потоков создавать?

cully,  Спасибо большое за совет. Честно говоря, интерестно было бы посмотреть на ваш алгоритм без гурппировки в массив, ради интереса. Но  нашел алгоритм по проще: без сортировки, без доп. массива, позволяет использовать в качестве весов одинаковые числа, как раз, то что надо.  

Если кому понадобится, это дело называется: weighted random selection.

Большое всем спасибо.

      


Уважаемый cully.
Прежде всего хочу со всей откровенностью заявить, что Ваш пост нисколько меня не оскорбил.   
Я с Вами согласен, стиль ковбойский.   
Просто я не занимаюсь математическими алгоритмами уже несколько лет, фиксание же разнообразных мелких багов откровенно испортило меня и привило вредные привычки. Может быть, отсюда "танцы с бубнами" и все остальные мои беды.

Однако, после внимательного повторного чтений своего и Вашего постов, у меня сложилось мнение, что я недостаточно ясно изложил свою мысль и она была понята превратно.
Так вот. В моем посте я намечал 3 пункта:
- организация хранения строк
- определение весов строк
- реализация поставленной задачи (приоритетное использование)

Во-первых, нужно было добиться того, что имеет AdRotator, т.е. хранения веса. Как?
Xml аттрибуты - вещь хорошая, когда она есть. А я не увидел, что вес каждой строки 
где-нибудь хранится. Вот я и предложил объект-элемент (кстати, XmlElement тоже ведь
хранит данные аттрибутов в коллекциях?) - структура. И не более того.

Определение весов строк. Вы раскрыли алгоритм учета весов.

 А кто и как их будет создавать и модернизировать? 
Моя структура это пытается обеспечить.

Реализация. Да, потоки, как вариант. Но я не настаиваю 

Ну вот, теперь я уверен, что изложил свою мысль полностью.

А впрочем... Может и зря я постился.

Это сообщение отредактировал(а) tol05 - 12.5.2007, 23:55

Вы не верно меня поняли. Задача была получить функционал AdRotator. Т.е. на основании веса выбирать из списка строку (для AdRotatorа - банер) случайным образом. А как веса хранить, это дело десятое.



Я же написал:




Ну с массивами вроде работать не сложно 


Честно говоря, в первые увидел решение вероятностной задачи за счет потоков!!!
Как наберу 100 постов - вам +1 за неординарное решение!!!

Значит перенапрягся я где-то...
А жаль ...

Я делал так:

1)
сумма всех весов -> 100% 
На основании этого вырешиваем проценты для каждого элемента.
создаём массив из 100 элементов, инициализируем его нашими значениями, количество берём процентуальное, вырешанное выше.
Например 30% -> 30 элементов итд. 
Это всё делается один раз.

2)
Сам алгоритм:
Выбираем случайное число из 100, берём элемент из массива по этому индексу.

По теории вероятноси всё работает весьма неплохо. для улучшения точности, увеличиваем массив например в 10 раз.
ну и конечно взятие элемента - это схематично. Достаточно определить границы отдельных элементов, сложить их в дерево и по дереву находить нужный элемент.

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

про идею с потоками. очень напоминает байку про программера-индуса, его спросили как узнать какая дата будет завтра, в ответ услышали: надо сделать Sleep(1000 * 60 * 60 * 24), а потом взять текущую дату.

Позволю не согласится на счет сортиовки. 

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

идея в бинарном поиске, а не в последовательном просмотре. для этого надо: иметь сортированный массив и, как писал sergejzr, "определить границы отдельных элементов".


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

если скорость работы устраивает, оптимизировать нет смысла; как говориться, проблемы надо решать по мере их поступления.

Выскажу свою идею

Нужно преобразовать в массив строка(string), - вес_относ(double) следующим образом:
определить относительный вес каждого из элементов:
вес_относ()=вес(int)/сумму_весов(int).
Далее составить интервалы частот с.о.:
вес_относ[0]=вес[0]/сумму_весов(int);

вес_относит[i]=вес_относ[i-1]+вес[i]/сумму_весов(int);

получим массиву строк соответсвует отсортированный массив относительных частот.
Далее вызываем Random.NextDouble() который выдает, равномернораспределенную СВ на отрезке 
[0;1]. И бинарным поиском ищем i такое, что вес_относит[i-1]<=Random.NextDouble()<вес_относит[i]

Вес элемента определяет вероятность его выбора. Пусть для каждого элемента назначен диапазон значений, размер которого определяется его весом. Тогда случайное значение, которое выбранное в промежутке от "0" до "сумма всех весов (диапазонов)" попадает в каждый из диапазонов с вероятностью равной отношению веса элемента, которому принадлежит этот диапазон, к весу всех элементов, что и требовалось получить.



Элементы хранятся в


Это сообщение отредактировал(а) adLucem - 15.5.2007, 15:50

Если кого интересует, вот как эта функция реализована в самом AdRotator