ruby - 我怎样才能随机遍历一个大范围？

Question

我想随机遍历一个范围。每个值只会被访问一次，所有值最终都会被访问。例如:

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..99**99) 替换 (0..9)。这也是以下代码不起作用的原因:

tried = {} # store previous attempts
bigint = 99**99
bigint.times {
    x = rand(bigint)
    redo if tried[x]
    tried[x] = true
    f(x) # some function
}

此代码非常幼稚，并且随着尝试 获取更多条目而很快耗尽内存。

什么样的算法可以完成我想做的事情？

[Edit1]:我为什么要这样做？我正在尝试用尽哈希算法的搜索空间来查找部分冲突的 N 长度输入字符串。我生成的每个数字都相当于一个唯一的输入字符串、熵和所有。基本上，我使用 custom alphabet 来“计数” .

[Edit2]:这意味着上面示例中的f(x)是一种生成哈希并将其与常量进行比较的方法，目标哈希为部分碰撞。在调用 f(x) 后，我不需要存储 x 的值，因此内存应该随时间保持不变。

[Edit3/4/5/6]:进一步澄清/修复。

[解决方案]:以下代码基于@bta的解决方案。为了简洁起见，未显示next_prime。它产生可接受的随机性并且只访问每个数字一次。有关详细信息，请参阅实际帖子。

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

Answer 1

我刚刚想起几年前上过的一门课的类似问题；也就是说，在给定极其严格的内存限制的情况下，(相对)随机地迭代一个集合(完全耗尽它)。如果我没记错的话，我们的解决算法是这样的:

1. 将范围定义为从 0 到 一些数字 N
2. 在 N 内生成一个随机起点 x[0]
3. 生成小于N的迭代器Q
4. 通过添加 Q 生成连续的点 x[n] 前一点并在需要时环绕。那 是，x[n+1] = (x[n] + Q) % N
5. 重复，直到生成一个与起点相等的新点。

诀窍是找到一个迭代器，它可以让您遍历整个范围而不会两次生成相同的值。如果我没记错的话，任何相对素数的 N 和 Q 都可以使用(数字越接近范围的边界，输入的“随机性”就越小)。在这种情况下，一个不是 N 因数的质数应该有效。您还可以交换结果数字中的字节/半字节，以更改生成的点在 N 中“跳来跳去”的模式。

该算法只需要起点(x[0])、当前点(x[n])、迭代器值(Q)，以及要存储的范围限制(N)。

也许其他人记得这个算法并可以验证我是否记得正确？