如何随机迭代一个大范围? [英] How can I randomly iterate through a large Range?

问题描述

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

类数组洗牌ret = 重复j = 长度我 = 0而 j >1r = i + rand(j)ret[i], ret[r] = ret[r], ret[i]我 += 1j -= 1结尾ret结尾结尾(0..9).to_a.shuffle.each{|x|f(x)}

其中 f(x) 是一些对每个值进行操作的函数.Fisher-Yates shuffle 用于有效地提供随机排序.p>

我的问题是 shuffle 需要对数组进行操作，这并不酷，因为我正在处理 天文数 大数字.Ruby 会很快消耗大量 RAM 来尝试创建一个巨大的数组.想象一下用 (0..99**99) 替换 (0..9).这也是以下代码不起作用的原因:

tried = {} # 存储之前的尝试大整数 = 99**99bigint.times {x = 兰德(大整数)如果尝试重做[x]试过[x] = truef(x) # 一些函数}

这段代码非常幼稚，随着尝试获得更多条目，很快就会耗尽内存.

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

[Edit1]:我为什么要这样做?我试图用尽哈希算法的搜索空间来寻找 N 长度的输入字符串以寻找部分冲突.我生成的每个数字都相当于一个唯一的输入字符串、熵等等.基本上，我正在使用 自定义字母表.

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

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

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

N = size_of_rangeQ = ( 2 * N/(1 + Math.sqrt(5)) ).to_i.next_prime开始 = 兰德(N)x = 开始nil until f( x = (x + Q) % N ) == START # 假设 f(x) 返回 x

解决方案

我只记得我几年前上过的一门课有一个类似的问题；也就是说，在给定非常严格的内存限制的情况下，随机地(相对地)迭代一组(完全耗尽它).如果我没记错的话，我们的解决方案算法是这样的:

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).

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

I would like to randomly iterate through a range. Each value will be visited only once and all values will eventually be visited. For example:

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)}

where f(x) is some function that operates on each value. A Fisher-Yates shuffle is used to efficiently provide random ordering.

My problem is that shuffle needs to operate on an array, which is not cool because I am working with astronomically large numbers. Ruby will quickly consume a large amount of RAM trying to create a monstrous array. Imagine replacing (0..9) with (0..99**99). This is also why the following code will not work:

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

This code is very naive and quickly runs out of memory as tried obtains more entries.

What sort of algorithm can accomplish what I am trying to do?

[Edit1]: Why do I want to do this? I'm trying to exhaust the search space of a hash algorithm for a N-length input string looking for partial collisions. Each number I generate is equivalent to a unique input string, entropy and all. Basically, I'm "counting" using a custom alphabet.

[Edit2]: This means that f(x) in the above examples is a method that generates a hash and compares it to a constant, target hash for partial collisions. I do not need to store the value of x after I call f(x) so memory should remain constant over time.

[Edit3/4/5/6]: Further clarification/fixes.

[Solution]: The following code is based on @bta's solution. For the sake of conciseness, next_prime is not shown. It produces acceptable randomness and only visits each number once. See the actual post for more details.

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

解决方案

I just remembered a similar problem from a class I took years ago; that is, iterating (relatively) randomly through a set (completely exhausting it) given extremely tight memory constraints. If I'm remembering this correctly, our solution algorithm was something like this:

1. Define the range to be from 0 to some number N
2. Generate a random starting point x[0] inside N
3. Generate an iterator Q less than N
4. Generate successive points x[n] by adding Q to the previous point and wrapping around if needed. That is, x[n+1] = (x[n] + Q) % N
5. Repeat until you generate a new point equal to the starting point.

The trick is to find an iterator that will let you traverse the entire range without generating the same value twice. If I'm remembering correctly, any relatively prime N and Q will work (the closer the number to the bounds of the range the less 'random' the input). In that case, a prime number that is not a factor of N should work. You can also swap bytes/nibbles in the resulting number to change the pattern with which the generated points "jump around" in N.

This algorithm only requires the starting point (x[0]), the current point (x[n]), the iterator value (Q), and the range limit (N) to be stored.

Perhaps someone else remembers this algorithm and can verify if I'm remembering it correctly?

这篇关于如何随机迭代一个大范围?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！