如何随机迭代大范围？
https://stackoverflow.com/questions/2459913
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我想随机迭代一个范围。每个值只会被访问一次，所有值最终都会被访问。例如：
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) 是对每个值进行操作的某个函数。A 费舍尔-耶茨洗牌 用于有效地提供随机排序。
我的问题是 shuffle 需要对数组进行操作，这并不酷，因为我正在使用 天文上的 大数。Ruby 会快速消耗大量 RAM 来尝试创建一个巨大的数组。想象一下替换 (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) 上面示例中的方法生成哈希并将其与常量目标哈希进行比较以发现部分冲突。我不需要存储的值 x 我打电话后 f(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
解决方案
我只是想起了一个类似的问题从一个类我花了好几年前；那是迭代(相对)通过随机设置(完全用尽其)鉴于非常紧迫的存的约束。如果我记忆正确的，我们的方案算法是这样的：
- 定义的范围从0到
一些号码
N - 产生一个随机的起始点
x[0]内部N - 产生一个迭代
Q不到N - 产生连续点
x[n]通过加入Q要 前一点并围绕如果需要的话。那 是,x[n+1] = (x[n] + Q) % N - 重复，直到产生一个新的起点平等的起点。
窍门是要找到一个迭代将让你穿越整个范围内没有产生同样的价值的两倍。如果我记忆正确的话，任何相对首相 N 和 Q 将工作(接近数量的边界范围内的少"随机"的输入)。在这种情况下，一个总理数量，不是一个因素 N 应工作。你还可以交换字节/啃在产生的数量变化的模式与其生成点"跳跃"在 N.
这个算法仅需要起点(x[0])，目前的点(x[n])，迭代值(Q)，并将范围限制(N)被存储。
也许别人记住这种算法，并可以验证，如果我记忆正确的?
其他提示
由于@Turtle回答说，你的问题没有解决。 @KandadaBoggu和@bta解决方案为您提供了随机数是一定的范围，其是或不是随机的。你得到的数字集群。
但我不知道为什么你关心的相同数量的双occurence。如果(0..99**99)是你的范围，那么，如果你能产生每秒10 ^ 10个随机数字（如果你有在其上产生每个CPU周期的一个随机数为3 GHz处理器和4核心 - 这是IMPOSIBLE和红宝石甚至会慢它下降了很多），则这将需要约的 10 ^180年以用尽所有的数字。你还概率约为10 ^ -180两个相同的数字将在全年产生。我们的宇宙中有大概10 ^ 9年，所以如果到时候开始你的电脑就可以开始计算，那么你将有大约10 ^ -170已生成两个相同号码的概率。在换句话说 - practicaly是IMPOSIBLE ，你不必在意它。
即使你将（从 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内存，这将让你有超过16万个号码。
打破到可管理批次的范围内，如下所示：
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| p z}
end
d = (range.end - size%batch_size + 1)
(d..range.end).sort_by{rand}.each{|z| p z }
end
可以进一步通过随机选择用于处理的批处理随机化的解决方案。
<强> PS：：此为地图，减少了良好的问题。每个批次可以由独立的节点工作。
<强>参考：
可以随机迭代与混洗方法的阵列
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，那么你会看到数百位改变之前遇到的形式1xx的所有三位数字。
另一个缺点是需要手动构造函数到指定深度。在你的(0..(99**99))情况下，这可能会是一个问题（虽然我想你可以写一个脚本生成的代码为你）。我敢肯定，有可能是一个方式在一个国家FUL，递归的方式重新写这一点，但我不认为它把我的头（的想法，任何人吗？）的顶部。
[编辑] ：考虑到@klew和@乌龟的答案，我希望最好是随机的（或接近随机）数批
这是一个递归执行类似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
我希望代码注释帮助阐明了我原来的问题的一些情况。
注：下PW_LEN # options可以为了得到更快的结果被改变到较低的数目
对于一个非常大的空间，比如
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 小几个数量级，就有很大的随机性。
