从顺序集合中获取随机元素

Question

我谈到了一个API,它给了我java.util.Iterator一个集合.这意味着我可以迭代它,但我不能直接/随机访问元素.

现在我的问题:我想从这个集合中获得一个随机元素.我怎么做？我想我可以构建一个允许直接访问的新集合,但这不是一点消耗内存吗？我也可以迭代整个集合,并为每个元素"掷骰子",看看我是否应该采用该元素并退出迭代或继续.但后来我需要集合的大小,我无法从迭代器中获得.

提前致谢.

Answer 1

有一种方法可以在一次通过集合时执行它,该集合不使用大量额外内存(只是集合中一个元素的大小加上一个浮点数).在伪代码中:

• 迭代整个集合.
• 对于每个项目,生成随机浮动.
• 如果浮动是目前为止看到的最低(或最高,无关紧要),则将集合中的当前项存储在临时变量中.(还存储新的最低随机值.)
• 到达集合的末尾后,temp变量中会有一个随机项.

显然,这有一个缺点,就是每次调用它时都要遍历整个集合,但是你没有很多选择,而是面对你所面临的限制.

更新:此类问题的名称终于回到了我的面前.这称为水库采样.

Answer 2

迭代时,您知道已经迭代了多少个对象,因此您知道当前元素是随机选择的对象的概率.所以你只需要保持一个计数和当前随机选择的项目.

public static <T> T selectRandom(final Iterator<T> iter, final Random random) {
    if (!iter.hasNext()) {
        throw new IllegalArgumentException();
    }
    if (random == null) {
        throw new NullPointerException();
    }
    T selected = iter.next();
    int count = 1;
    while (iter.hasNext()) {
        final T current = iter.next();
        ++count;
        if (random.nextInt(count) == 0) {
            selected = current;
        }
    }
    return selected;
}

(Stack Overflow免责声明:未编译,当然未经过测试.)

另请参阅Collections.shuffleJava Puzzlers中的部分.