2

我需要能够将元素从包含只能访问迭代器的元素m的地图中逐出。n我可以简单地迭代字典一次并删除所有具有概率的元素m/n，但是这可能会驱逐更多或更少的m项目（尽管删除的项目的预期数量是正确的m）。

int m = 10;
int n = map.size();

Iterator<K> keys = map.keySet().iterator();
while (keys.hasNext()) {
    keys.next();
    if (random.nextDouble() < m / (double) n) {
        keys.remove();
    }
}

我一直在考虑的解决方案是在元素被驱逐后简单地停止驱逐元素m，并在迭代结束时，如果evicted < m元素已被驱逐，则m - evicted在第二次迭代中驱逐剩余的元素。我担心这第二遍在概率上是不正确的。

int m = 10;
int n = size();
int evicted = 0;

outer: while (evicted < m) {

Iterator<K> keys = keySet().iterator();
while (keys.hasNext()) {
    keys.next();
    if (random.nextDouble() < m / (double) n) {
        keys.remove();

        if (++evicted == m) {
            break outer;
        }
    }
}

或者，我可以保留一个键列表并通过一次迭代对列表进行存储采样，并删除键列表中的所有m键，但是我不想被迫使用一些内存开销。此外，使用迭代器删除比通过键删除元素更快（它需要找到存储键的存储桶，然后找到它在列表中的位置）。是否有另一种在线算法我可以使用仅访问迭代器（不创建单独的列表）？

编辑：对于那些感兴趣的人，我找到了一篇论文，详细介绍了如何生成随机分布，以便不需要单独的排序步骤。代码是这样的（截断为整数时可能包含重复项）：

int curmax = 1.0;
int[] indices = new int[m];
for (int i = indices.length; i >= 0; i--) {
    curmax = curmax * Math.pow(random.nextDouble(), 1 / (double) (i+1));
    indices[i] = (int) curmax;
}
4

2 回答 2

3

为什么不直接驱逐前M个元素然后停止迭代器？迭代器中是否反映了一些排序，这会对被驱逐的元素产生不必要的偏见？

如果是，那么您的两遍方法将不会在统计上完美无缺。如果第一次通过提前终止，因为您在到达迭代结束之前到达M ，则永远不会考虑驱逐后面的元素。

如果您在没有驱逐M个元素的情况下到达迭代结束，则迭代的第一个元素将“冒险”驱逐两次，而接近迭代结束的元素将仅冒着驱逐一次的风险。

如果您事先知道N，您可以构建一个包含M个介于 0 和 N 之间的随机、非重复数字的列表。迭代一次，记下您在迭代中所处的位置。如果迭代号在您的“驱逐列表”上，请驱逐该元素。

按照这种方法，您只能为迭代过程临时为M 个索引位置（可能是整数）分配内存。

于 2012-11-12T00:00:22.893 回答
1

这样做的正确方法是以概率 m/n 删除每个元素，但根据结果重新归一化概率（如果我们删除一个元素，则递减 m，并且当前概率需要按剩余元素的数量进行缩放以选择从）。我的 java 有点生疏，我无法访问编译器，所以如果这不能正常工作，请原谅（但我希望你应该能够轻松修复它）：

int seen = 0

Iterator<K> keys = map.keySet().iterator();
while (keys.hasNext()) {
    if (m==0)
      break;

    keys.next();
    prob = m / (double)(n-seen)  //renormalise the prob so that the total available is 1 across all remaining instances
    if (random.nextDouble() < prob) {
        keys.remove();
        m--;
    }
    seen++;
}

我希望这里的逻辑很清楚——这是对如何以 1/n 的概率从集合中采样一个元素的概括，一旦你拒绝了一个元素，你可以忽略它并考虑所有剩余元素的分布。这应该确保您以正确的概率准确返回 m 个元素。

编辑：

修正了几个错别字并删除了多余的变量。

于 2012-11-12T17:11:04.823 回答