java - 随机逐出 map 值

我需要能够仅通过迭代器从包含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;
}

最佳答案

正确的方法是删除概率为m / n的每个元素，但是要根据结果对概率重新进行归一化（如果我们删除一个元素，则将m降为10，而当前概率需要根据剩余的元素数量进行缩放从）。我的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个元素。

编辑：

修复了一些错字并删除了冗余变量。