algorithm - 实现随机删除和插入的数据结构，其中元素在 [a,b] 中加权

Question

我想设计一个数据结构和算法，这样，给定一个元素数组，其中每个元素都有一个根据 [a,b] 的权重，我可以实现恒定时间的插入和删除。删除是随机执行的，其中元素被删除的概率与其权重成正比。

我不相信有一种确定性算法可以在恒定时间内实现这两种操作，但我认为应该有随机算法可以做到这一点？

Answer 1

我不知道 O(1) 最坏情况时间是否是不可能的；我看不出有什么特别的原因。但是绝对有可能拥有一个简单的数据结构来实现 O(1) 的预期时间。

这个想法是存储成对的动态数组（或两个并行数组），其中每个项目与其权重配对；插入是通过在 O(1) 摊销时间内追加完成的，并且可以通过将元素与最后一个元素交换来通过索引删除它，以便可以在 O(1) 时间内从数组末尾删除它。要从加权分布中采样一个随机元素，选择一个随机索引并在半开区间 [0, 2) 中生成一个随机数；如果它小于元素的权重，则选择该索引处的元素，否则重复此过程直到选择一个元素。这个想法是每个索引都有同样的可能被选择，并且它被保留而不是被拒绝的概率与其权重成正比。

这是一个拉斯维加斯算法，这意味着它预计在有限的时间内完成，但极低的概率可能需要任意长的时间才能完成。当每个权重恰好为 1 时，对元素进行采样所需的迭代次数最高，在这种情况下，它遵循参数 p = 1/2 的几何分布，因此其期望值为 2，这是一个与数量无关的常数数据结构中的元素。

一般来说，如果对于实数 0 < a <= b ，所有权重都在区间 [ a , b ] 中，那么预期的迭代次数最多为b/a。这始终是一个常数，但如果下限a相对于b较小，则它可能是一个大常数（即，选择单个样本需要多次迭代） 。

Answer 2

这本身不是一个答案，而只是一个小例子来说明@kaya3 设计的算法

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

总重量为 7.0。通过将其存储在一些内存中并在每次插入/删除时增加/减少，在 O(1) 中很容易维护。

每个元素的概率只是它的权重除以总权重。

| 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...

使用@kaya3的算法，如果我们画一个随机索引，那么每个值的概率是1/size（这里是1/5）。

v1 被拒绝的几率为 50%，v2 为 25%，v4 为 0%。所以在第一轮，被选中的概率是：

| 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%)

那么第二轮的概率是30%，每个指标的概率是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%)

第三轮的概率是 9%，即每个指数的 9/500

| 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%)

所以我们看到这个系列正在收敛到正确的概率。分子是权重的倍数，因此很明显每个元素的相对权重都受到尊重。

Answer 3

这是一个答案的草图。

权重只有 1，我们可以保持输入的随机排列。每次插入一个元素时，将其放在数组的末尾，然后在i数组中随机选择一个位置，并将最后一个元素与 position 处的元素交换i。（如果随机位置是最后一个，则很可能是无操作。）删除时，只需删除最后一个元素。

假设我们可以使用具有 O(1)（最坏情况或摊销）插入和删除的动态数组，这会在 O(1) 中进行插入和删除。

---

对于权重 1 和 2，可以使用类似的结构。也许每个重量为 2 的元素应该放置两次而不是一次。也许当一个权重为 2 的元素被删除时，它的另一个副本也应该被删除。所以我们实际上应该存储索引而不是元素，以及另一个数组 ，locations它存储和跟踪每个元素的两个索引。交换应该使这个locations数组保持最新。

删除任意元素可以在 O(1) 中完成，类​​似于插入：与最后一个交换，删除最后一个。