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会很快消耗大量内存来创建一个巨大的数组,例如将(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
获取更多条目时会很快耗尽内存。
有什么算法可以完成我想做的事情吗?
[编辑1]:我为什么要这样做?我正在为一个 N 长度的输入字符串耗尽哈希算法的搜索空间,寻找部分碰撞。我生成的每个数字相当于一个唯一的输入字符串,包括熵等。基本上,我在使用自定义字母表进行"计数"。
[编辑2]:这意味着上面例子中的f(x)
是一个生成哈希并将其与常量目标哈希值进行部分碰撞比较的方法。我在调用f(x)
后无需存储x
的值,因此内存应该随时间保持恒定。
[编辑3/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