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

Question

我与一个 API 交谈，该 API 为我提供了一个集合的 java.util.Iterator。这意味着我可以对其进行迭代，但无法直接/随机访问元素。

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

提前致谢。

Answer 1

有一种方法可以在一次遍历集合时完成，它不会使用大量额外内存(只是集合中一个元素的大小加上一个 float )。在伪代码中:

• 遍历集合。
• 为每个项目生成一个随机 float 。
• 如果 float 是您目前看到的最低(或最高，这无关紧要)，则将集合中的当前项目存储在一个临时变量中。 (同时存储新的最低随机值。)
• 一旦到达集合的末尾，临时变量中就会有一个随机项。

显然，这有一个缺点，即每次调用它时都会遍历整个集合，但由于面临的限制条件，您没有太多选择。

更新: 我终于想起了这类问题的名字。这叫做 Reservoir sampling .