问题描述如下,我们有大量的项目,通过迭代器模式(动态构造或获取)所请求的项目来遍历。
由于项目数量很大,因此无法保存在内存中(例如作为列表)。
What is a procedure for the iterator to follow in order to produce a random order of the items each time the iterator is called. A unique random order means that eventually all items are traversed only once but returned in a random order.
如果item数量比较少,可以这样解决这个问题:
- 将列表中的项目存储在内存(或辅助内存)中
- Shuffle列表
- 遍历打乱顺序的列表。
对于这个问题,我们可以假设迭代器可以对项目进行索引(或对它们进行排名/取消排名)。因此迭代器可以为项目范围内的所有索引 i 获取第 i 个项目。
注意随机顺序应该均匀分布在所有项目排序的集合中,或者换句话说无偏。这种情况遗漏了以逐 block 方案随机化项目列表的解决方案(例如,为了将某些项目存储在内存中,并且仅随机化它们,然后随机化下一个项目 block ,依此类推)
最佳答案
加密是可逆的,因此加密是从一组到其自身的一对一映射。
选择一个 block 大小足够大的 block 密码来覆盖您拥有的项目数量。
加密数字 0, 1, 2, 3, 4, ... 这将为您提供一个最多 2^( block 大小)的非重复有序数字列表。
如果加密数字太大,请忽略。如果加密的数字在您的项目列表的大小之内,则选择该项目。对您需要的任意数量的项目重复此操作。
具有可变 block 大小的密码(如 Hasty Pudding 密码)将减少丢失的次数。
关于language-agnostic - 迭代器产生唯一的随机顺序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28990820/