Структура данных для случайного удаления и вставки, где элементы взвешиваются в [a,b]

Question

Я хотел бы разработать структуру данных и алгоритм таким образом, чтобы, учитывая массив элементов, где каждый элемент имеет вес в соответствии с [a,b], я мог добиться постоянного времени вставки и удаления. Удаление выполняется случайным образом, при этом вероятность удаления элемента пропорциональна его весу.

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

Answer 1

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

Идея состоит в том, чтобы сохранить динамический массив пар (или два параллельных массива ), где каждому элементу соответствует его вес; вставка выполняется путем добавления в амортизированное время O(1), и элемент может быть удален по индексу, заменив его последним элементом, чтобы его можно было удалить из конца массива за время O(1). Чтобы выбрать случайный элемент из взвешенного распределения, выберите случайный индекс и сгенерируйте случайное число в полуоткрытом интервале [0, 2); если он меньше веса элемента, выберите элемент по этому индексу, в противном случае повторяйте этот процесс, пока не будет выбран элемент. Идея состоит в том, что каждый индекс с равной вероятностью будет выбран, и вероятность того, что он будет сохранен, а не отклонен, пропорциональна его весу.

Это алгоритм Лас-Вегаса , то есть ожидается, что он будет завершен за конечное время, но с очень низкой вероятностью это может занять сколь угодно много времени. Количество итераций, необходимых для выборки элемента, будет наибольшим, когда каждый вес равен 1, и в этом случае он следует геометрическому распределению с параметром p = 1/2, поэтому его ожидаемое значение равно 2, константе, которая не зависит от числа. элементов в структуре данных.

В общем, если все веса находятся в интервале [ a , b ] для действительных чисел 0 < a <= b , то ожидаемое количество итераций не превышает b / a . Это всегда константа, но потенциально это большая константа (т. Е. Для выбора одной выборки требуется много итераций), если нижняя граница a мала по сравнению с b .

Answer 2

Это набросок ответа.

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

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

---

С весами 1 и 2 можно использовать аналогичную конструкцию. Возможно, каждый элемент веса 2 следует ставить дважды, а не один раз. Возможно, при удалении элемента веса 2 следует удалить и другую его копию. Таким образом, мы должны фактически хранить индексы вместо элементов и другой массив, в котором хранятся и отслеживаются два индекса для каждого элемента. Свопы должны сохранить это актуальный массив.

Удаление произвольного элемента может быть выполнено в O(1) аналогично вставке: поменять местами с последним, удалить последний.

Answer 3

This is not an answer per se, but just a tiny example to illustrate the algorithm devised by @kaya3

      | value | weight |
| v1    | 1.0    |
| v2    | 1.5    |
| v3    | 1.5    |
| v4    | 2.0    |
| v5    | 1.0    |
| total | 7.0    |

The total weight is 7.0. It's easy to maintain in O(1) by storing it in some memory and increasing/decreasing at each insertion/removal.

The probability of each element is simply it's weight divided by total weight.

      | value | proba |
| v1    | 1.0/7 | 0.1428...
| v2    | 1.5/7 | 0.2142...
| v3    | 1.5/7 | 0.2142...
| v4    | 2.0/7 | 0.2857...
| v5    | 1.0/7 | 0.1428...

Using the algorithm of @kaya3, if we draw a random index, then the probability of each value is 1/size (1/5 here).

The chance of being rejected is 50% for v1, 25% for v2 and 0% for v4. So at first round, the probability to be selected are:

      | value | proba  |
| v1    |  2/20  | 0.10
| v2    |  3/20  | 0.15
| v3    |  3/20  | 0.15
| v4    |  4/20  | 0.20
| v5    |  2/20  | 0.10
| total | 14/20  | (70%)

Then the proba of having a 2nd round is 30%, and the proba of each index is 6/20/5 = 3/50

      | value | proba 2 rounds |
| v1    |  2/20 +  6/200 | 0.130
| v2    |  3/20 +  9/200 | 0.195
| v3    |  3/20 +  9/200 | 0.195
| v4    |  4/20 + 12/200 | 0.260
| v5    |  2/20 +  6/200 | 0.130
| total | 14/20 + 42/200 | (91%)

The proba to have a 3rd round is 9%, that is 9/500 for each index

      | value | proba 3 rounds            |
| v1    |  2/20 +  6/200 +  18/2000 | 0.1390
| v2    |  3/20 +  9/200 +  27/2000 | 0.2085
| v3    |  3/20 +  9/200 +  27/2000 | 0.2085
| v4    |  4/20 + 12/200 +  36/2000 | 0.2780
| v5    |  2/20 +  6/200 +  18/2000 | 0.1390
| total | 14/20 + 42/200 + 126/2000 | (97,3%)

So we see that the serie is converging to the correct probabilities. The numerators are multiple of the weight, so it's clear that the relative weight of each element is respected.