Как реализовать взвешенное перемешивание

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

1. Список X объектов, каждому из которых присваивается «вес»
2. Подвести итоги
3. Генерация случайного числа от 0 до суммы
4. Перебирайте объекты, вычитая их вес из суммы, пока сумма не будет положительной
5. Удалить объект из списка, а затем добавить его в конец нового списка

Пункты 2,4 и 5 все занимают nвремя, и поэтому это O(n^2)алгоритм.

Можно ли это улучшить?

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

Пример (я сгенерирую случайные числа, чтобы сделать это реальным):

6 предметов с весом 6,5,4,3,2,1; Сумма 21

Я выбрал 19: 19-6-5-4-3-2 = -1таким образом, 2 идет в первую позицию, веса теперь 6,5,4,3,1; Сумма 19

Я выбрал 16: 16-6-5-4-3 = -2таким образом, 3 идет на вторую позицию, веса теперь 6,5,4,1; Сумма 16

Я выбрал 3:, 3-6 = -3таким образом, 6 идет на третью позицию, веса теперь 5,4,1; Сумма 10

Я выбрал 8: 8-5-4 = -1таким образом, 4 идет на четвертой позиции, веса теперь 5,1; Сумма 6

Я выбрал 5: 5-5=0таким образом, 5 идет в пятую позицию, веса теперь 1; Сумма 1

Я выбрал 1:, 1-1=0таким образом, 1 идет в последней позиции, у меня больше нет весов, я заканчиваю

Это может быть реализовано с O(n log(n))использованием дерева.

Сначала создайте дерево, сохраняя в каждом узле кумулятивную сумму всех дочерних узлов справа и слева от каждого узла.

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

Это моя реализация в Python:

import random

def weigthed_shuffle(items, weights):
    if len(items) != len(weights):
        raise ValueError("Unequal lengths")

    n = len(items)
    nodes = [None for _ in range(n)]

    def left_index(i):
        return 2 * i + 1

    def right_index(i):
        return 2 * i + 2

    def total_weight(i=0):
        if i >= n:
            return 0
        this_weigth = weights[i]
        if this_weigth <= 0:
            raise ValueError("Weigth can't be zero or negative")
        left_weigth = total_weight(left_index(i))
        right_weigth = total_weight(right_index(i))
        nodes[i] = [this_weigth, left_weigth, right_weigth]
        return this_weigth + left_weigth + right_weigth

    def sample(i=0):
        this_w, left_w, right_w = nodes[i]
        total = this_w + left_w + right_w
        r = total * random.random()
        if r < this_w:
            nodes[i][0] = 0
            return i
        elif r < this_w + left_w:
            chosen = sample(left_index(i))
            nodes[i][1] -= weights[chosen]
            return chosen
        else:
            chosen = sample(right_index(i))
            nodes[i][2] -= weights[chosen]
            return chosen

    total_weight() # build nodes tree

    return (items[sample()] for _ in range(n - 1))

Использование:

In [2]: items = list(range(10))
   ...: weights = list(range(10, 0, -1))
   ...:

In [3]: for _ in range(10):
   ...:     print(list(weigthed_shuffle(items, weights)))
   ...:
[5, 0, 8, 6, 7, 2, 3, 1, 4]
[1, 2, 5, 7, 3, 6, 9, 0, 4]
[1, 0, 2, 6, 8, 3, 7, 5, 4]
[4, 6, 8, 1, 2, 0, 3, 9, 7]
[3, 5, 1, 0, 4, 7, 2, 6, 8]
[3, 7, 1, 2, 0, 5, 6, 4, 8]
[1, 4, 8, 2, 6, 3, 0, 9, 5]
[3, 5, 0, 4, 2, 6, 1, 8, 9]
[6, 3, 5, 0, 1, 2, 4, 8, 7]
[4, 1, 2, 0, 3, 8, 6, 5, 7]

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

ОБНОВИТЬ:

Взвешенная случайная выборка (2005; Efraimidis, Spirakis) предоставляет очень элегантный алгоритм для этого. Реализация очень проста, и также работает в O(n log(n)):

def weigthed_shuffle(items, weights):
    order = sorted(range(len(items)), key=lambda i: -random.random() ** (1.0 / weights[i]))
    return [items[i] for i in order]

РЕДАКТИРОВАТЬ: Этот ответ не интерпретирует веса в том виде, как это ожидалось. Т.е. предмет с весом 2 не в два раза чаще будет первым, чем предмет с весом 1.

Один из способов перемешать список - назначить случайные числа каждому элементу в списке и отсортировать их по этим номерам. Мы можем расширить эту идею, нам просто нужно выбрать взвешенные случайные числа. Например, вы могли бы использовать random() * weight. Различные варианты будут давать разные распределения.

В чем-то вроде Python это должно быть так просто:

items.sort(key = lambda item: random.random() * item.weight)

Будьте осторожны, чтобы не оценивать ключи более одного раза, так как они будут иметь разные значения.

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

Для иллюстрации давайте используем колоду карт, где мы хотим взвесить лицевые карты вперед. weight(card) = card.rank, Суммируя их, если мы не знаем, распределение весов действительно O (n) один раз.

Эти элементы хранятся в отсортированной структуре, такой как модификация в индексируемом списке пропуска , так что все индексы уровней могут быть доступны из данного узла:

   1 10
 o ---> o -------------------------------------------- -------------> o Верхний уровень
   1 3 2 5
 о ---> о ---------------> о ---------> о ---------------- -----------> o Уровень 3
   1 2 1 2 5
 о ---> о ---------> о ---> о ---------> о ----------------- ----------> o Уровень 2
   1 1 1 1 1 1 1 1 1 1 1 
 о ---> о ---> о ---> о ---> о ---> о ---> о ---> о ---> о ---> о ---> о ---> о нижний уровень

Глава 1-й 2-й 3-й 4-й 5-й 6-й 7-й 8-й 9-й 10-й ноль
      Узел Узел Узел Узел Узел Узел Узел Узел Узел Узел Узел

Однако в этом случае каждый узел также «занимает» столько же места, сколько и его вес.

Теперь при поиске карты в этом списке можно получить доступ к ее положению в списке за O (log n) и удалить ее из связанных списков за O (1). Хорошо, это может быть не O (1), это может быть O (log log n) время (я бы подумал об этом гораздо больше). Удаление 6-го узла в вышеприведенном примере потребует обновления всех четырех уровней - и эти четыре уровня не зависят от количества элементов в списке (в зависимости от того, как вы реализуете уровни).

Поскольку вес элемента постоянен, можно просто обойтись sum -= weight(removed)без повторного обхода структуры.

И, таким образом, у вас есть одноразовая стоимость O (n) и значение поиска O (log n), а также стоимость удаления из списка O (1). Это становится O (n) + n * O (log n) + n * O (1), что дает вам общую производительность O (n log n).

Давайте посмотрим на это с картами, потому что это то, что я использовал выше.

      10
топ 3 -----------------------> 4d
                                ,
       3 7.
    2 ---------> 2d ---------> 4d
                  , ,
       1 2. 3 4.
бот 1 -> реклама -> 2d -> 3d -> 4d

Это действительно маленькая колода, в которой всего 4 карты. Должно быть легко увидеть, как это можно расширить. С 52 картами идеальная структура будет иметь 6 уровней (log ₂ (52) ~ = 6), хотя, если копаться в пропущенных списках, даже это можно уменьшить до меньшего числа.

Сумма всех весов равна 10. Таким образом, вы получаете случайное число из [1 ... 10) и его 4. Вы проходите список пропусков, чтобы найти предмет, находящийся на потолке (4). Поскольку 4 меньше 10, вы переходите с верхнего уровня на второй уровень. Четыре больше, чем 3, так что теперь мы находимся на 2 алмазов. 4 меньше 3 + 7, поэтому мы переходим на нижний уровень, а 4 меньше 3 + 3, поэтому у нас есть 3 бриллианта.

После удаления 3 алмазов из структуры, структура теперь выглядит следующим образом:

       7
топ 3 ----------------> 4d
                         ,
       3 4.
    2 ---------> 2d -> 4d
                  , ,
       1 2. 4
бот 1 -> реклама -> 2d -> 4d

Вы заметите, что узлы занимают количество «пространства», пропорциональное их весу в структуре. Это учитывает взвешенный выбор.

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

Многое из этого можно было бы сделать с каким-то сбалансированным деревом. Проблема, связанная с перебалансировкой структуры при удалении узла, становится запутанной, поскольку это не классическая древовидная структура, и домашнее хозяйство должно помнить, что 4 алмаза теперь перемещены из позиций [6 7 8 9] в [3 4 5 6] может стоить дороже, чем преимущества древовидной структуры.

Однако, хотя список пропуска аппроксимирует двоичное дерево в своей способности пропустить список за O (log n), он имеет простоту работы со связанным списком.

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