迭代器产生独特的随机顺序？ [英] 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).
什么是程序为迭代器遵循以便每次调用迭代器时产生
项的随机顺序。 一个唯一的
随机订单意味着最终所有商品只会以
的价格遍历，但会以随机顺序返回。
如果商品数量相对较少，可以按如下方式解决此问题：
if the number of items is relatively small, one can solve this problem as follows:
- 存储商品在内存（或辅助内存）列表中
- 随机播放列表
- 遍历随机列表。
- Store the items in a list in memory (or secondary memory)
- Shuffle the list
- Traverse the shuffled list.
为此问题一可以假设迭代器可以索引项目（或排名/取消它们）。所以迭代器可以为项目范围内的所有索引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 cypher）将减少未命中数。
A cypher with variable block-size (like the Hasty Pudding cypher) will reduce the number of misses.
这篇关于迭代器产生独特的随机顺序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
