我谈到一个API,给我一个
java.util.Iterator的集合.这意味着我可以迭代它,但是我不能直接/
随机访问这些元素.
现在我的问题:我想从这个集合中获得一个随机元素.我怎么做?我想我可以建立一个允许直接访问的新集合,但是这不是一点点内存消耗吗?我也可以遍历整个集合,并为每个元素“滚动一个骰子”,看看我是否应该采取该元素并退出迭代或继续.但是,我需要的集合的大小,我不能从迭代器得到.
提前致谢.
有一种
方法可以在一次通过集合中执行,不会使用大量额外的内存(只是集合中的一个元素的大小
加上一个float).伪码:
通过收集迭代.
>对于每个项目,生成随机浮点数.
>如果浮动是迄今为止看到的最低(或最高,没关系),则将集合中的当前项目存储在临时变量中. (还存储新的最低随机值.)
>一旦到达集合的末尾,你在temp变量中有一个随机项.
显然,每次调用它时,都会遍历整个集合的缺点,但是您所面临的限制您没有太多的选择.
更新:这种类型的问题的名字终于回到了我身上.这叫做Reservoir sampling.