Быстрая выборка и обновление взвешенных элементов (структура данных, например, красно-черные деревья?)

Question

Какая структура данных подходит для этой задачи?

У меня есть набор из N предметов. N большое. Каждый элемент имеет положительное значение веса, связанное с ним.

Я бы хотел быстро сделать следующее:

внутренний цикл:

Пример товара, по весу.

[процесс ...]

Обновление веса K предметов, где K << N. </p>

Когда я говорю выборка по весу, это отличается от равномерной выборки. Вероятность предмета пропорциональна его весу. Так что, если есть два предмета, и у одного есть вес .8, а у другого - вес .2, то они имеют вероятность 80% и 20% соответственно.

Количество предметов N остается неизменным. Веса находятся в ограниченном диапазоне, скажем, [0, 1]. Веса не всегда равны единице.

Наивный подход использует O (n) временных шагов к выборке. Есть ли алгоритм O (log (n))?

Какая структура данных подходит для этой задачи? Я считаю, что красно-черные деревья неуместны, так как они относятся к каждому предмету как к равному весу.

Answer 1

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

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

Когда вы обновляете (т.е. вставляете / удаляете) дерево, вы следуете алгоритму для вашего любимого дерева. Когда вы меняете структуру, вы просто пересчитываете суммы узлов (что является операцией O (1), например, для поворотов, расщепления и соединения B-дерева). Когда вы меняете вес предмета, вы обновляете суммы предков узла.

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

Это описание немного хаотично, но я надеюсь, что оно поможет.

Answer 2

Это проблема, которую мне пришлось решить для некоторых симуляций Монте-Карло. Вы можете увидеть мое текущее `двоичное дерево 'по ссылке ниже. Я попытался сделать это довольно STL-как. Мое дерево имеет фиксированную емкость, которую вы можете обойти с помощью красно-черного дерева, о котором я говорил, пытаясь. По сути, это реализация идей, описанных jpacelek.

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

http://mopssuite.svn.sourceforge.net/viewvc/mopssuite/utils/trunk/include/binary_tree.hpp?view=markup

Answer 3

Поскольку N фиксировано, вы можете решить эту проблему, используя массив, скажем, v, где v [i + 1] = v [i] + weight [i], v [1] = weight [0], v [ 0] = 0 и сэмплируйте его с помощью бинарного поиска, который является log (N), для нижней границы случайного числа, равномерно распределенного между 0 и суммой весов.

Наивное обновление K элементов - O (KN), более вдумчивое - O (N).

Испортил еще один вопрос собеседования кружком самодовольных :)

Answer 4

Мне нравится ответ jpalecek. Я хотел бы добавить, что самый простой способ получить ваше случайное число будет (1) генерировать U из равномерного (0,1) распределения (2) Умножим u на сумму всех весов в дереве.