迭代器产生唯一的随机顺序? [英] Iterator to produce unique random order?
问题描述
问题如下，我们有大量的项目通过迭代器模式(动态构造或获取)所请求的项目进行遍历.
The problem is stated as follows, we have a very large number of items which are traversed through an iterator pattern (which dynamicaly constructs or fetches) the requested item.
由于项目的数量很大，因此无法保存在内存中(例如列表).
Due to the number of items being large and thus cannot be kept in memory (as a list for example).
迭代器为了产生一个每次调用迭代器时项目的随机顺序.独一无二的随机顺序意味着最终所有项目只遍历一次但以随机顺序返回.
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.
如果项目的数量比较少，可以这样解决这个问题:
if the number of items is relatively small, one can solve this problem as follows:
- 将项目存储在内存(或辅助内存)中的列表中
- 随机播放列表
- 遍历打乱的列表.
对于这个问题，可以假设迭代器可以索引项目(或对它们进行排名/取消排名).因此迭代器可以获取项目范围内所有索引 i 的第 i 个项目.
For this question one can assume that the iterator can index the items (or rank/unrank them). So the iterator can fetch the ith item for all indices i in the range of items.
注意随机顺序应均匀分布在项目的所有排序集合中，即无偏.这种情况排除了在逐块方案中随机化项目列表的解决方案(例如，为了让一些项目在内存中并仅随机化它们，然后是下一个项目块等等)
Note the random order should be uniformly distributed in the set of all orderings of the items or in other words be unbiased. This condition leaves out solutions which randomise the list of items in a block-by-block scheme (in order to have some of the items in memory for example and randomise only them, then the next block of items and so on)
推荐答案
加密是可逆的，因此加密是从集合到自身的一对一映射.
Encryption is reversible, hence an encryption is a one-to-one mapping from a set onto itself.
选择一个块大小足够大的块密码，以涵盖您拥有的项目数量.
Pick a block cypher with a large enough block size to cover the number of items you have.
加密数字 0, 1, 2, 3, 4, ... 这将为您提供不重复的有序数字列表，最大为 2^(块大小).
Encrypt the numbers 0, 1, 2, 3, 4, ... This will give you a non-repeating ordered list of numbers up to 2^(block size).
如果加密数字太大，忽略它.如果加密数字在您的项目列表的大小范围内，则选择该项目.重复所需的任意数量的项目.
If the encrypted number is too large, ignore it. If the encrypted number is within the size of your item list, then pick that item. Repeat for however many items you need.
具有可变块大小的密码(如 Hasty Pudding 密码)将减少未命中的次数.
A cypher with variable block-size (like the Hasty Pudding cypher) will reduce the number of misses.
这篇关于迭代器产生唯一的随机顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
