如何随机迭代一个大范围？
我想随机迭代一个范围。 每个值只访问一次，最终将访问所有值。 例如：
class Array def shuffle ret = dup j = length i = 0 while j > 1 r = i + rand(j) ret[i], ret[r] = ret[r], ret[i] i += 1 j -= 1 end ret end end (0..9).to_a.shuffle.each{|x| f(x)} 其中f(x)是对每个值进行操作的某个函数。 Fisher-Yates shuffle用于有效地提供随机排序。
我的问题是shuffle需要在数组上运行，这并不酷，因为我正在使用天文数字大的数字。 Ruby会快速消耗大量的RAM，试图创建一个怪异的数组。 想象一下用(0..9) (0..99**99)替换(0..9) (0..99**99) 。 这也是以下代码不起作用的原因：
tried = {} # store previous attempts bigint = 99**99 bigint.times { x = rand(bigint) redo if tried[x] tried[x] = true f(x) # some function }
这段代码非常幼稚，并且在tried获取更多条目时很快耗尽内存。
什么样的算法可以完成我想要做的事情？
[Edit1] ：我为什么要这样做？ 我试图耗尽哈希算法的搜索空间，寻找N长度输入字符串，寻找部分冲突。 我生成的每个数字等同于唯一的输入字符串，熵和全部。 基本上，我正在使用自定义字母 “计数”。
[Edit2] ：这意味着上面示例中的f(x)是一种生成散列并将其与常量目标散列进行比较的方法，用于部分冲突。 在调用f(x)之后，我不需要存储x的值，因此内存应该随时间保持不变。
[Edit3 / 4/5/6] ：进一步澄清/修正。
[解决方案] ：以下代码基于@ bta的解决方案。 为简明起见，未显示next_prime 。 它产生可接受的随机性，并且只访问每个数字一次。 有关详细信息，请参阅实际post。
N = size_of_range Q = ( 2 * N / (1 + Math.sqrt(5)) ).to_i.next_prime START = rand(N) x = START nil until f( x = (x + Q) % N ) == START # assuming f(x) returns x
我只记得几年前我上过的一个类似的问题; 也就是说，在给定非常严格的内存约束的情况下，通过集合（相对）随机迭代（完全耗尽它）。 如果我正确记住这一点，我们的解决方案算法是这样的：
- 将范围定义为0到某个数字
N - 在
N内生成随机起点x[0] - 生成小于
N的迭代器Q - 通过将
Q添加到前一点并在需要时环绕来生成连续点x[n]。 即，x[n+1] = (x[n] + Q) % N - 重复，直到生成一个等于起点的新点。
诀窍是找到一个迭代器，它可以让你遍历整个范围而不会产生两次相同的值。 如果我正确记住，任何相对素数N和Q都会起作用（数字越接近范围边界，输入越少’随机’。 在这种情况下，不是N因子的素数应该起作用。 您还可以在结果数字中交换字节/半字节，以更改生成的点在N “跳转”的模式。
该算法仅需要存储起始点（ x[0] ），当前点（ x[n] ），迭代器值（ Q ）和范围限制（ N ）。
也许其他人记得这个算法，可以validation我是否正确记住它？
正如@Turtle回答的那样，你的问题没有解决方案。 @KandadaBoggu和@bta解决方案为您提供随机数，是某些范围是随机的还是非随机的。 你得到了数字集群。
但我不知道为什么你关心同一个数字的双重出现。 如果(0..99**99)是你的范围，那么如果你每秒可以产生10 ^ 10个随机数（如果你有一个3 GHz处理器和大约4个核心，你在每个CPU周期产生一个随机数 -是不可能的，ruby甚至会减慢它的速度，然后耗费大约10 ^ 180年来耗尽所有的数字。 您还有大约10 ^ -180的概率，即在一整年内将生成两个相同的数字。 我们的宇宙可能大约有10 ^ 9年，所以如果你的计算机可以在时间开始时开始计算，那么你将有大约10 ^ -170的概率生成两个相同的数字。 换句话说 – 实际上它是不可能的，你不必关心它。
即使您只使用Jaguar（来自www.top500.org超级计算机的前1 名 ）只执行这一项任务，您仍需要10 ^ 174年才能获得所有数字。
如果你不相信我，试试吧
tried = {} # store previous attempts bigint = 99**99 bigint.times { x = rand(bigint) puts "Oh, no!" if tried[x] tried[x] = true }
如果你甚至会看到“哦，不！”我会给你买啤酒。 你生命中的屏幕上:)
我可能是错的，但我认为如果没有存储某些状态，这是可行的。 至少，你需要一些状态。
即使您每个值只使用一位（此值已尝试是或否），您将需要X / 8字节的内存来存储结果（其中X是最大的数字）。 假设您有2GB的可用内存，这将为您留下超过1600万个数字。
将范围分为可管理的批次，如下所示：
def range_walker range, batch_size = 100 size = (range.end - range.begin) + 1 n = size/batch_size n.times do |i| x = i * batch_size + range.begin y = x + batch_size (x...y).sort_by{rand}.each{|z| pz} end d = (range.end - size%batch_size + 1) (d..range.end).sort_by{rand}.each{|z| pz } end
您可以通过随机选择要处理的批次来进一步随机化解决方案。
PS：这是map-reduce的一个很好的问题。 每个批处理可由独立节点处理。
参考：
Ruby中的Map-reduce
你可以用shuffle方法随机迭代一个数组
a = [1,2,3,4,5,6,7,8,9] a.shuffle! => [5, 2, 8, 7, 3, 1, 6, 4, 9]
你想要一个所谓的“完整循环迭代器”……
这是最简单版本的psudocode，非常适合大多数用途……
function fullCycleStep(sample_size, last_value, random_seed = 31337, prime_number = 32452843) { if last_value = null then last_value = random_seed % sample_size return (last_value + prime_number) % sample_size }
如果你这样称呼：
sample = 10 For i = 1 to sample last_value = fullCycleStep(sample, last_value) print last_value next
它将生成随机数，循环遍历所有10，永不重复如果你改变random_seed，可以是任何东西，或者prime_number，它必须大于，并且不能被sample_size整除，你将获得一个新的随机顺序，但是你仍然永远不会重复。
数据库系统和其他大型系统通过将递归排序的中间结果写入临时数据库文件来实现此目的。 这样，他们可以对大量记录进行排序，同时在任何时候只在内存中保留有限数量的记录。 这在实践中往往很复杂。
您的订单必须“随机”吗？ 如果您不需要特定的输入分配，可以尝试这样的递归方案以最小化内存使用：
def gen_random_indices # Assume your input range is (0..(10**3)) (0..3).sort_by{rand}.each do |a| (0..3).sort_by{rand}.each do |b| (0..3).sort_by{rand}.each do |c| yield "#{a}#{b}#{c}".to_i end end end end gen_random_indices do |idx| run_test_with_index(idx) end
基本上，您通过一次随机生成一个数字来构建索引。 在最坏的情况下，这将需要足够的内存来存储10 *（位数）。 您将遇到范围内的每个数字(0..(10**3))恰好一次，但顺序只是伪随机。 也就是说，如果第一个循环设置a=1 ，那么在看到百位数变化之前，您将遇到1xxforms的所有三位数字。
另一个缺点是需要手动将函数构造到指定的深度。 在你的(0..(99**99))情况下，这可能是一个问题（虽然我想你可以编写一个脚本来为你生成代码）。 我确信可能有一种方法可以用一种有条理的，递归的方式重写它，但我不能把它想到头脑中（想法，任何人？）。
[编辑] ：考虑到@klew和@Turtle的答案，我能想到的最好的是随机（或接近随机）数字的批次。
这是类似于KandadaBoggu解决方案的递归实现。 基本上，搜索空间（作为范围）被划分为包含N个相等大小范围的数组。 每个范围以随机顺序反馈为新的搜索空间。 这一直持续到范围的大小达到下限。 此时，范围足够小，可以转换为数组，洗牌和检查。
即使它是递归的，我还没有炸掉堆栈。 相反，当尝试对大于约10^19密钥的搜索空间进行分区时，它会出错。 我必须处理数字太大而无法转换为long 。 它可能是固定的：
# partition a range into an array of N equal-sized ranges def partition(range, n) ranges = [] first = range.first last = range.last length = last - first + 1 step = length / n # integer division ((first + step - 1)..last).step(step) { |i| ranges << (first..i) first = i + 1 } # append any extra onto the last element ranges[-1] = (ranges[-1].first)..last if last > step * ranges.length ranges end
我希望代码评论有助于阐明我原来的问题。
pastebin：完整的来源
注意： PW_LEN下的PW_LEN可以更改为较低的数字，以便获得更快的结果。
对于一个非常大的空间，如
space = -10..1000000000000000000000
您可以将此方法添加到Range 。
class Range M127 = 170_141_183_460_469_231_731_687_303_715_884_105_727 def each_random(seed = 0) return to_enum(__method__) { size } unless block_given? unless first.kind_of? Integer raise TypeError, "can't randomly iterate from #{first.class}" end sample_size = self.end - first + 1 sample_size -= 1 if exclude_end? j = coprime sample_size v = seed % sample_size each do v = (v + j) % sample_size yield first + v end end protected def gcd(a,b) b == 0 ? a : gcd(b, a % b) end def coprime(a, z = M127) gcd(a, z) == 1 ? z : coprime(a, z + 1) end end
那你可以
space.each_random { |i| puts i } 729815750697818944176 459631501395637888351 189447252093456832526 919263002791275776712 649078753489094720887 378894504186913665062 108710254884732609237 838526005582551553423 568341756280370497598 298157506978189441773 27973257676008385948 757789008373827330134 487604759071646274309 217420509769465218484 947236260467284162670 677052011165103106845 406867761862922051020 136683512560740995195 866499263258559939381 596315013956378883556 326130764654197827731 55946515352016771906 785762266049835716092 515578016747654660267 ...
只要您的空间比M127小几个订单，就具有良好的随机性。
感谢@ nick-steele和@bta的方法。