如何在大范围内进行随机迭代？

Question

如何在大范围内进行随机迭代？

11

我希望能够随机遍历一个范围，每个值只会被访问一次，所有的值最终都会被访问到。例如：

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

- void

2

你显然没有存储函数调用的结果，因为那也会占用大量内存。那么你到底在做什么呢？为什么需要以随机顺序进行操作？如果你只是累加值，顺序可能并不重要。如果你想要解决方案，我希望能了解更多信息。 - Turtle

1

"sort_by rand" 也不正确，它会产生偏见的结果。请参阅 http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html（JavaScript，但概念相同）。 - Matthew Flaschen

1

正如@Matthew Flaschen所写，您尝试随机化列表的顺序是非常错误的，并且会返回看起来随机但实际上并不是随机的结果。他提供的链接给出了一个很好的问题描述。 - Turtle

好的，我明白你的意思了。我已经改变了示例，使用了 Fisher-Yates 洗牌算法。 - void

将此内容创建为迭代器：http://gist.github.com/363914 - Colin Curtin

显示剩余2条评论

11个回答

3

正如@Turtle所回答的那样，你的问题没有解决方案。@KandadaBoggu和@bta的解决方案为您提供了一些范围内的随机数，这些随机数可能是或不是随机的。您会得到数字的聚集。

但我不知道为什么您关心相同数字的双重出现。如果(0..99**99)是您的范围，那么如果您可以每秒生成10^10个随机数（如果您有一个3 GHz的处理器和大约4个核心，在这些核心上每个CPU周期生成一个随机数 - 这是不可能的，并且Ruby会减慢它的速度），那么需要大约10^180年才能耗尽所有数字。您还有大约10^-180的概率，在整个一年中生成两个相同的数字。我们的宇宙可能有大约10^9年，因此如果您的计算机可以在时间开始时开始计算，那么您将有大约10^-170的概率生成两个相同的数字。换句话说，实际上是不可能的，您不必关心它。

即使你使用排名第一的www.top500.org 超级计算机“Jaguar”来完成这个任务，你仍需要10^174年才能得到所有数字。

如果你不相信我，可以尝试一下。

tried = {} # store previous attempts
bigint = 99**99
bigint.times {
  x = rand(bigint)
  puts "Oh, no!" if tried[x]
  tried[x] = true
}

如果你一生中屏幕上出现过“Oh, no!”，我会请你喝一杯啤酒:)

- klew

感谢提供有用的信息。范围（0..99**99）只是一个例子。我正在测试的哈希算法在现实时间内可以穷尽搜索空间，适用于现实长度的输入。我只是想让我的算法在高效缩放的同时，使每个数字被选择的概率相同。至于啤酒，我认为太阳自发地瞬移到银河系的另一侧的概率更高 :) - void

我正在测试的搜索空间为(0..(80**N-1))，输入长度为N。 - void

当N = 11时，以与上面示例相同的速度耗尽所有数字需要34年。因此，当您使用Ruby不仅生成数字，而且还对它们进行一些计算时，您不应该关心重复的数字，因为用尽所有可能性需要很长时间。另一方面，对于N = 6，您可以在数组中的单个位上存储所有尝试过的数字 - 大约需要409 MB。对于N = 7，您应该拥有大约32 GB的内存 - 因此可能应该将其存储在硬盘驱动器上。但是这又需要很长时间。 - klew

在我的电脑上，像这样的简单循环：a = 80**4; b = 0; a.times {b = b+1} 大约需要16秒。这意味着当你将N增加1时，这个时间会增加80倍，因此对于N=6，它将需要24分钟，对于N=7，需要28小时，对于N=8，需要超过9天。根据这个计算，对于N=11，需要13300年（这是一个真实的例子，在一个2.13 GHz的核心上）。 - klew

看起来你的数学出了点问题。从 N=7 到 N=8 时，你乘以了 8 而不是 80。实际上，N=8 的时间略微超过3个月。如果在选择测试密钥时有足够的随机性，平均情况下的时间将减少一半。利用多核 CPU 将把平均情况下的时间除以您拥有的核心数。如果需要更高的效率，我可以切换到另一种语言。将其提升到更高的水平，我可以使用 GPU 进行流处理。 - void

1

将范围分成可管理的批次，如下所示：

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

您可以通过随机选择批次进行处理来进一步随机化解决方案。

附言：这是一个非常适合使用Map-reduce的好问题。每个批次可以由独立节点进行处理。

参考资料：

Ruby中的Map-reduce

- Harish Shetty

在你的问题中并没有明确说明你想要将结果作为一个数组返回。我认为你只是想随机处理一个范围内的数字，确保每个数字都被处理了。这个解决方案可以做到不考虑范围大小。如果你想将这些数字作为一个数组返回，那么你就有了另一个问题。 - Harish Shetty

我已经解决了问题。请再试一次。内存消耗将保持不变。由于连续处理，CPU 接近 60%。 - Harish Shetty

我是否正确理解这段代码？范围被分成批次。每个批次都有一个随机分布。然而，当需要随机访问它们时，这些批次仍然按顺序访问。现在我们又回到了同样的问题。 :-) - void

@void：这是随机性和内存使用之间的权衡。按顺序访问批次可以节省相当多的内存。只要有一个限制，即每个输入仅被访问一次，那么几乎任何解决方案都将为了内存使用而牺牲随机性。 - bta

@void：另一种看待这个问题的方式是：批次不是按顺序访问的，而是并行访问的。使用多处理器、多核心的机器，在每个核心上加载一个批次。这种类型的问题似乎非常适合并行化处理，而这种解决方案似乎将其分解成了并行块。 - bta

显示剩余4条评论

1

你可以使用 shuffle 方法随机迭代一个数组

a = [1,2,3,4,5,6,7,8,9]
a.shuffle!
=> [5, 2, 8, 7, 3, 1, 6, 4, 9]

- shweta

1

你需要的是所谓的“完整循环迭代器”…

以下是最简单版本的伪代码，适用于大多数情况…

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且不能被其整除），则会得到一个新的随机顺序，但仍不会出现重复。

- Nick Steele

1

我可能错了，但我认为这是不可行的，除非存储一些状态。至少，你需要一些状态。

即使你每个值只使用一个比特（已尝试过此值是是还是否），那么你将需要X/8字节的内存来存储结果（其中X是最大数字）。假设你有2GB的空闲内存，这将留给你超过1600万个数字。

- Turtle

0

对于一个非常大的空间，比如

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提出的方法。

- captainpete

0

这并不是一个特定于Ruby的答案，但我希望它是被允许的。Andrew Kensler在他的"Correlated Multi-Jittered Sampling"报告中提供了一个C++的"permute()"函数，可以完美地实现这个功能。

据我所知，他提供的确切函数只适用于大小不超过2^27的"数组"，但是这个通用的思路可以用于任何大小的数组。

我会尽力解释一下。首先，你需要一个可逆的哈希函数，“适用于任何2的幂次方大小的域”。考虑 x = i + 1。无论 x 是什么，即使你的整数溢出了，你也可以确定 i 是什么。更具体地说，你总是可以从 x 的底部 n 位确定 i 的底部 n 位。加法是可逆的哈希操作，乘以奇数也是，按位异或常数也是。如果你知道特定的2的幂次方域，你可以在该域中混淆位。例如，x ^= (x & 0xFF) >> 5) 对于16位域是有效的。你可以使用掩码指定该域，例如 mask = 0xFF，然后你的哈希函数变成了 x = hash(i, mask)。当然，你可以在该哈希函数中添加“种子”值以获得不同的随机化。Kensler 在论文中列出了更多有效的操作。

假设您有一个可逆函数：x = hash(i, mask, seed)。问题是，如果您对索引进行哈希，可能会得到一个大于数组大小的值，即您的“域”。您不能仅对此取模，否则会导致冲突。

可逆哈希是使用一种称为“循环行走”的技术的关键，该技术在“Ciphers with Arbitrary Finite Domains”中介绍。由于哈希是可逆的（即1对1），因此您可以重复应用相同的哈希，直到您的哈希值小于您的数组！因为您正在应用相同的哈希，并且映射是一对一的，所以无论您最终到达哪个值，它都将映射回完全相同的索引，因此您不会发生冲突。因此，您的函数可能如下所示，针对32位整数（伪代码）：

fun permute(i, length, seed) {
  i = hash(i, 0xFFFF, seed)
  while(i >= length): i = hash(i, 0xFFFF, seed)
  return i
}

要到达您的域可能需要很多哈希，因此Kensler使用了一个简单的技巧：他将哈希保留在下一个2的幂次方的域内，这使得它只需要很少的迭代（平均约为2），通过屏蔽掉不必要的位数。最终算法如下：

fun next_pow_2(length) {
  # This implementation is for clarity.
  # See Kensler's paper for one way to do it fast.
  p = 1
  while (p < length): p *= 2
  return p
}

permute(i, length, seed) {
  mask = next_pow_2(length)-1
  i = hash(i, mask, seed) & mask
  while(i >= length): i = hash(i, mask, seed) & mask
  return i
}

就是这样！显然，重要的是选择一个好的哈希函数，Kensler在论文中提供了这个函数，但我想解释一下。如果你想每次都有不同的随机排列，可以向permute函数添加一个“种子”值，然后将其传递给哈希函数。

- Andrew

0

你的顺序需要多么“随机”？如果你不需要特定的输入分布，你可以尝试像这样的递归方案来最小化内存使用：

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））情况下，这可能是一个问题（尽管我想您可以编写一个脚本为您生成代码）。我相信可能有一种方法可以以状态化、递归的方式重新编写它，但我无法立即想出（有任何想法吗？）。

- bta

尽可能随机。这样可以有效地耗尽搜索空间。这也是生日攻击成为可能的原因，大大缩短了搜索时间。将其视为强制破解锁的组合。 - void

0

[编辑]：考虑到@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: full source

注意：在# options下，PW_LEN可以更改为较小的数字，以便更快地获得结果。

- void

很好，但你看到它不是真正的洗牌吧？第一个数字将被随机分配，但接下来的BLOCK_SIZE个数字将全部来自同一范围。 - mckeed

除非我误解了你的评论，Fisher-Yates是一种真正的洗牌算法，并且它被正确地使用。每个块都被分割并以随机顺序访问。然而，它所能做到的最好的就是批量生成随机数... - void

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bta · Accepted Answer

我刚想起来一个类似的问题，这是我几年前上课时遇到的，即在极其紧密的内存限制下（相对）随机地遍历一组数据（完全耗尽它）。如果我没记错的话，我们的解决算法大致如下：

定义范围从0到某个数字N
生成一个N之内的随机起点x [0]
生成一个小于N的迭代器Q
通过将Q添加到前一个点并在需要时进行环绕，生成连续的点x [n]。也就是说，x [n + 1] =（x [n] + Q）％N
重复此过程，直到生成与起始点相等的新点。

诀窍是找到一个迭代器，让您在不重复生成相同值的情况下遍历整个范围。如果我没记错，任何互质的N和Q都可以工作（距离范围边界越近，输入的“随机性”越小）。在这种情况下，不是N的因子的质数应该有效。您还可以在生成的数字中交换字节/半字节以更改生成的点如何“跳动”。

此算法只需要存储起始点（x [0]），当前点（x [n]），迭代器值（Q）和范围限制（N）。

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