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 会很快消耗大量 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这段代码非常幼稚，并且随着获得更多条目而迅速耗尽内存。

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

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

[Edit2]：这意味着f(x)在上面的示例中是一种生成散列并将其与部分冲突的常量目标散列进行比较的方法。我不需要存储x调用后的值，f(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
4

11 回答 11

12

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

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

诀窍是找到一个迭代器，它可以让您遍历整个范围而不会两次生成相同的值。如果我没记错的话，任何相对的素数N都会Q起作用（数字越接近范围的边界，输入的“随机”就越少）。在这种情况下，一个不是因子的素数N应该起作用。您还可以交换结果数字中的字节/半字节，以更改生成的点在N.

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

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

于 2010-03-18T21:10:52.110 回答
3

正如@Turtle 回答的那样，您的问题没有解决方案。@KandadaBoggu 和@bta 解决方案为您提供随机数是一些随机或非随机的范围。你得到一串数字。

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

即使您只使用 Jaguar（来自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
}

如果你能看到“哦，不！”，我就给你买杯啤酒。在你的一生中在你的屏幕上:)

于 2010-03-18T20:23:02.227 回答
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 整除），您将获得一个新的随机顺序，但是您仍然永远不会得到重复。

于 2014-04-23T23:37:04.037 回答
1

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

即使每个值只使用一位（是否尝试过这个值），那么您将需要 X/8 字节的内存来存储结果（其中 X 是最大的数字）。假设您有 2GB 的可用内存，这将使您拥有超过 1600 万个数字。

于 2010-03-17T05:02:25.567 回答
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

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

PS：这对 map-reduce 来说是个好问题。每个批次都可以由独立的节点工作。

参考：

Ruby 中的 Map-reduce

于 2010-03-17T05:06:56.503 回答
1

您可以使用 shuffle 方法随机迭代数组

a = [1,2,3,4,5,6,7,8,9]
a.shuffle!
=> [5, 2, 8, 7, 3, 1, 6, 4, 9]
于 2012-05-08T13:37:10.057 回答
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))情况下，这可能是一个问题（尽管我想您可以编写一个脚本来为您生成代码）。我确信可能有一种方法可以以有状态的递归方式重新编写它，但我无法想到它（想法，有人吗？）。

于 2010-03-17T19:11:43.483 回答
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：完整源代码

注意：PW_LENunder# options可以更改为较小的数字以获得更快的结果。

于 2010-03-18T19:54:44.120 回答
0

数据库系统和其他大型系统通过将递归排序的中间结果写入临时数据库文件来做到这一点。这样，他们可以对大量记录进行排序，同时在任何时候只在内存中保留有限数量的记录。这在实践中往往很复杂。

于 2010-03-17T05:06:27.693 回答
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的方法。

于 2017-09-22T01:40:25.963 回答
0

这不是一个真正的 Ruby 特定的答案，但我希望它是允许的。Andrew Kensler 在他的“Correlated Multi-Jittered Sampling”报告中给出了一个 C++“permute()”函数，该函数正是这样做的。

据我了解，他提供的确切功能仅在您的“数组”最大为 2^27 时才有效，但总体思路可用于任何大小的数组。

我会尽力解释一下。第一部分是您需要一个“对于任何二次方大小的域”可逆的哈希。考虑x = i + 1。无论 x 是什么，即使您的整数溢出，您也可以确定 i 是什么。更具体地说，您总是可以从 x 的底部 n 位确定 i 的底部 n 位。加法是一种可逆的散列操作，与奇数相乘，按位异或乘以常数也是如此。如果您知道特定的二次幂域，则可以对该域中的位进行加扰。例如x ^= (x & 0xFF) >> 5)对 16 位域有效。您可以使用掩码指定该域，例如mask = 0xFF，并且您的哈希函数变为x = hash(i, mask)。当然，您可以将“种子”值添加到该哈希函数中以获得不同的随机化。

所以你有一个可逆的功能x = hash(i, mask, seed)。问题是，如果你散列你的索引，你最终可能会得到一个大于你的数组大小的值，即你的“域”。您不能只取模，否则会发生冲突。

可逆哈希是使用“循环行走”技术的关键，该技术在“具有任意有限域的密码”中介绍。因为哈希是可逆的（即 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
}

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

于 2021-03-06T20:05:33.413 回答