получить взвешенный случайный предмет

51

У меня есть, например, эта таблица

+ ----------------- +
| фрукты | вес |
+ ----------------- +
| яблоко | 4 |
| апельсин | 2 |
| лимон | 1 |
+ ----------------- +

Мне нужно вернуть случайный фрукт. Но яблоко следует собирать в 4 раза чаще, чем лимон, и в 2 раза чаще, чем апельсин .

В более общем случае это должно быть f(weight)часто.

Что такое хороший общий алгоритм для реализации этого поведения?

Или, может быть, на Ruby есть несколько готовых камней? :)

PS
Я реализовал текущий алгоритм в Ruby https://github.com/fl00r/pickup

fl00r
источник
11
это должна быть та же самая формула для получения случайного лута в Diablo :-)
Jalayn
1
@Jalayn: На самом деле, идея для интервального решения в моем ответе ниже основана на том, что я помню о боевых таблицах в World of Warcraft. :-D
Бенджамин Клостер
Смотрите также
BlueRaja - Дэнни Пфлугхофт
Я реализовал несколько простых взвешенных случайных алгоритмов . Дайте мне знать, если у вас есть вопросы.
Леонид Ганелайн

Ответы:

50

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

fruits = [apple, apple, apple, apple, orange, orange, lemon]

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


Другой, немного более сложный подход будет выглядеть так:

  1. Рассчитать кумулятивные суммы весов:

    intervals = [4, 6, 7]

    Где индекс ниже 4 представляет яблоко , от 4 до 6 ниже апельсин и от 6 до 7 ниже лимон .

  2. Генерация случайного числа nв диапазоне 0до sum(weights).

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

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

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

Бенджамин Клостер
источник
2
Интервальное решение кажется хорошим
Jalayn
1
Это была моя первая мысль :). Но что, если у меня есть стол со 100 фруктами, а вес может быть около 10к? Это будет очень большой массив, и это будет не так эффективно, как я хочу. Это о первом решении. Второе решение выглядит хорошо
fl00r
1
Я реализовал этот алгоритм в Ruby github.com/fl00r/pickup
fl00r
1
Метод псевдонимов - это дефактный способ справиться с этим. Я, честно говоря, удивлен количеством постов, которые повторяют один и тот же код снова и снова, игнорируя метод псевдонимов . ради бога, вы получаете постоянную производительность по времени!
оп
30

Вот алгоритм (в C #), который может выбирать случайный взвешенный элемент из любой последовательности, повторяя его только один раз:

public static T Random<T>(this IEnumerable<T> enumerable, Func<T, int> weightFunc)
{
    int totalWeight = 0; // this stores sum of weights of all elements before current
    T selected = default(T); // currently selected element
    foreach (var data in enumerable)
    {
        int weight = weightFunc(data); // weight of current element
        int r = Random.Next(totalWeight + weight); // random value
        if (r >= totalWeight) // probability of this is weight/(totalWeight+weight)
            selected = data; // it is the probability of discarding last selected element and selecting current one instead
        totalWeight += weight; // increase weight sum
    }

    return selected; // when iterations end, selected is some element of sequence. 
}

Это основано на следующих соображениях: давайте выберем первый элемент нашей последовательности как «текущий результат»; затем на каждой итерации либо сохраняйте ее, либо отбрасывайте и выбирайте новый элемент в качестве текущего. Мы можем вычислить вероятность того, что любой данный элемент будет выбран в конце, как произведение всех вероятностей того, что он не будет отброшен на последующих этапах, в зависимости от вероятности того, что он будет выбран в первую очередь. Если вы сделаете математику, вы увидите, что этот продукт упрощается до (вес элемента) / (сумма всех весов), что именно то, что нам нужно!

Так как этот метод выполняет итерации по входной последовательности только один раз, он работает даже с неприлично большими последовательностями, при условии, что сумма весов вписывается в int(или вы можете выбрать больший тип для этого счетчика)

Неважно
источник
2
Я бы оценил это, прежде чем предположить, что это лучше, потому что он повторяется один раз. Генерировать столько же случайных значений тоже не очень быстро.
Жан-Бернар Пеллерен
1
@ Жан-Бернар Пеллерен: Я сделал это, и в больших списках это действительно быстрее. Если вы не используете криптографически сильный генератор случайных чисел (-8
Nevermind
Должен быть принятый ответ IMO. Мне нравится это лучше, чем подход «интервал» и «повторный вход».
Вивин Палиат
2
Я просто хотел сказать, что я возвращался к этой теме 3 или 4 раза за последние пару лет, чтобы использовать этот метод. Этот метод неоднократно успешно давал ответы, которые мне нужны достаточно быстро для моих целей. Хотелось бы, чтобы я высказывал этот ответ каждый раз, когда возвращался, чтобы использовать его.
Джим Ярбро
1
Хорошее решение, если вы действительно должны выбрать только один раз. В противном случае выполнение подготовительной работы к решению в первом ответе будет гораздо более эффективным.
дедупликатор
22

Уже представленные ответы хороши, и я их немного расширю.

Как предположил Бенджамин, кумулятивные суммы обычно используются в такой проблеме:

+------------------------+
| fruit  | weight | csum |
+------------------------+
| apple  |   4    |   4  |
| orange |   2    |   6  |
| lemon  |   1    |   7  |
+------------------------+

Чтобы найти элемент в этой структуре, вы можете использовать что-то вроде фрагмента кода Nevermind. Этот кусок кода C #, который я обычно использую:

double r = Random.Next() * totalSum;
for(int i = 0; i < fruit.Count; i++)
{
    if (csum[i] > r)
        return fruit[i];
}

Теперь к интересной части. Насколько эффективен этот подход и какое решение наиболее эффективно? Мой кусок кода требует O (n) памяти и запускается за O (n) времени. Я не думаю, что это может быть сделано с меньшим, чем O (n) пространством, но временная сложность может быть намного ниже, O (log n) на самом деле. Хитрость заключается в том, чтобы использовать бинарный поиск вместо обычного цикла for.

double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;

while (highGuess >= lowGuess)
{
    int guess = (lowGuess + highGuess) / 2;
    if ( csum[guess] < r)
        lowGuess = guess + 1;
    else if ( csum[guess] - weight[guess] > r)
        highGuess = guess - 1;
    else
        return fruit[guess];
}

Также есть история об обновлении весов. В худшем случае обновление веса для одного элемента вызывает обновление кумулятивных сумм для всех элементов, увеличивая сложность обновления до O (n) . Это тоже можно сократить до O (log n), используя двоичное индексированное дерево .

Император Орионий
источник
Хороший вопрос о бинарном поиске
fl00r
Ответ Nevermind не требует дополнительного места, поэтому он равен O (1), но добавляет сложности во время выполнения, многократно генерируя случайные числа и оценивая весовую функцию (которая, в зависимости от основной проблемы, может быть дорогостоящей).
Бенджамин Клостер
1
То, что вы называете «более читаемой версией» моего кода, на самом деле не так. Ваш код должен заранее знать общую сумму весов и кумулятивные суммы; мой нет.
Nevermind
@Benjamin Kloster Мой код вызывает весовую функцию только один раз для каждого элемента - вы не можете сделать это лучше, чем это. Вы правы насчет случайных чисел.
Nevermind
@Nevermind: Вы вызываете его только один раз за вызов функции pick, поэтому, если пользователь вызывает его дважды, функция веса вызывается снова для каждого элемента. Конечно, вы можете кэшировать его, но тогда вы больше не O (1) для сложности пространства.
Бенджамин Клостер
8

Это простая реализация Python:

from random import random

def select(container, weights):
    total_weight = float(sum(weights))
    rel_weight = [w / total_weight for w in weights]

    # Probability for each element
    probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))]

    slot = random()
    for (i, element) in enumerate(container):
        if slot <= probs[i]:
            break

    return element

а также

population = ['apple','orange','lemon']
weights = [4, 2, 1]

print select(population, weights)

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

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

Выбор колеса рулетки

Типичные алгоритмы имеют сложность O (N) или O (log N), но вы также можете выполнить O (1) (например, выбор колеса рулетки посредством стохастического принятия ).

Manlio
источник
Вы знаете, каков исходный источник этого изображения? Я хочу использовать это для бумаги, но должен удостовериться в атрибуции.
Малкольм МакЛауд
@MalcolmMacLeod Извините, он используется во многих статьях / сайтах GA, но я не знаю, кто автор.
Манлио
0

Эта суть делает именно то, что вы просите.

public static Random random = new Random(DateTime.Now.Millisecond);
public int chooseWithChance(params int[] args)
    {
        /*
         * This method takes number of chances and randomly chooses
         * one of them considering their chance to be choosen.    
         * e.g. 
         *   chooseWithChance(0,99) will most probably (%99) return 1
         *   chooseWithChance(99,1) will most probably (%99) return 0
         *   chooseWithChance(0,100) will always return 1.
         *   chooseWithChance(100,0) will always return 0.
         *   chooseWithChance(67,0) will always return 0.
         */
        int argCount = args.Length;
        int sumOfChances = 0;

        for (int i = 0; i < argCount; i++) {
            sumOfChances += args[i];
        }

        double randomDouble = random.NextDouble() * sumOfChances;

        while (sumOfChances > randomDouble)
        {
            sumOfChances -= args[argCount -1];
            argCount--;
        }

        return argCount-1;
    }

Вы можете использовать это так:

string[] fruits = new string[] { "apple", "orange", "lemon" };
int choosenOne = chooseWithChance(98,1,1);
Console.WriteLine(fruits[choosenOne]);

Приведенный выше код, скорее всего, (% 98) вернет 0, что является индексом для «яблока» для данного массива.

Кроме того, этот код проверяет метод, представленный выше:

Console.WriteLine("Start...");
int flipCount = 100;
int headCount = 0;
int tailsCount = 0;

for (int i=0; i< flipCount; i++) {
    if (chooseWithChance(50,50) == 0)
        headCount++;
    else
        tailsCount++;
}

Console.WriteLine("Head count:"+ headCount);
Console.WriteLine("Tails count:"+ tailsCount);

Это дает вывод что-то вроде этого:

Start...
Head count:52
Tails count:48
оборота Рамазан ПОЛАТ
источник
2
Программисты о концептуальных вопросах, и ответы должны объяснить вещи. Создание дампов кода вместо объяснения похоже на копирование кода из IDE на доску: это может показаться знакомым и даже иногда понятным, но это кажется странным ... просто странным. У доски нет компилятора
комнат
Вы правы, я сосредоточился на коде, поэтому забыл рассказать, как он работает. Я добавлю объяснение о том, как это работает.
Рамазан Полат