11

範囲をランダムに繰り返したいと思います。各値は1回だけ訪問され、すべての値が最終的に訪問されます。例えば：

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)は各値を操作する関数です。フィッシャー-イェーツシャッフルは、ランダムな順序を効率的に提供するために使用されます。

私の問題は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長の入力文字列のハッシュアルゴリズムの検索スペースを使い果たしようとしています。私が生成する各数値は、一意の入力文字列、エントロピー、およびすべてに相当します。基本的に、私はカスタムアルファベットを使用して「カウント」しています。

[Edit2]：これはf(x)、上記の例では、ハッシュを生成し、それを定数のターゲットハッシュと比較して部分的な衝突を行うメソッドであることを意味します。x呼び出した後の値を保存する必要がないf(x)ので、メモリは時間の経過とともに一定に保たれるはずです。

[編集3/4/5/6]：さらなる説明/修正。

[解決策]：次のコードは@btaの解決策に基づいています。簡潔にするために、next_primeは表示されていません。それは許容できるランダム性を生み出し、各番号を1回だけ訪問します。詳細については、実際の投稿を参照してください。

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. 開始点に等しい新しい点を生成するまで繰り返します。

秘訣は、同じ値を2回生成することなく、範囲全体をトラバースできるイテレータを見つけることです。私が正しく覚えていれば、互いに素Nで機能しQます（数値が範囲の境界に近いほど、入力の「ランダム」は少なくなります）。その場合、因数ではない素数が機能するNはずです。結果の数値のバイト/ニブルを交換して、生成されたポイントがで「ジャンプ」するパターンを変更することもできますN。

このアルゴリズムでは、開始点（x[0]）、現在の点（x[n]）、イテレータ値（Q）、および範囲制限（N）のみを保存する必要があります。

おそらく他の誰かがこのアルゴリズムを覚えていて、私がそれを正しく覚えているかどうかを確認できますか？

于 2010-03-18T21:10:52.110 に答える
3

@Turtleが答えたように、あなたの問題には解決策がありません。@KandadaBogguおよび@btaソリューションは、乱数がランダムであるかランダムでない範囲であるかを示します。あなたは数のクラスターを取得します。

しかし、なぜあなたが同じ数の二重発生を気にするのか分かりません。が範囲である場合(0..99**99)、1秒あたり10 ^ 10の乱数を生成できる場合（3 GHzプロセッサと約4コアがあり、CPUサイクルごとに1つの乱数を生成する場合-これは不可能であり、rubyはそれをさらに遅くします大幅に減少します）、すべての数値を使い果たすには約10^180年かかります。また、1年の間に2つの同じ数が生成される確率は約10^-180です。私たちの宇宙はおそらく約10^9年あるので、時間が始まったときにコンピューターが計算を開始できれば、2つの同じ数が生成された確率は約10^-170になります。言い換えれば、実際には不可能であり、気にする必要はありません。

この1つのタスクだけでジャガー（ 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

私は間違っているかもしれませんが、これはいくつかの状態を保存せずに実行できるとは思いません。少なくとも、いくつかの状態が必要になります。

値ごとに1ビットのみを使用する場合（この値がyesまたはnoで試行された場合）、結果を格納するために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でreduce

于 2010-03-17T05:06:56.503 に答える
1

シャッフルメソッドを使用して配列をランダムに反復できます

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 に答える
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より大きく、sample_sizeで均等に割り切れないようにする必要がありますが、新しいランダムな順序が得られますが、重複することはありません。

于 2014-04-23T23:37:04.037 に答える
0

データベースシステムやその他の大規模システムは、再帰的な並べ替えの中間結果を一時データベースファイルに書き込むことでこれを行います。そうすれば、一度に限られた数のレコードのみをメモリに保持しながら、膨大な数のレコードをソートできます。これは実際には複雑になる傾向があります。

于 2010-03-17T05:06:27.693 に答える
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

コードコメントが私の元の質問に光を当てるのに役立つことを願っています。

ペーストビン：完全なソース

注：より迅速な結果を得るために、PW_LENunderを小さい数値に変更できます。# options

于 2010-03-18T19:54:44.120 に答える
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

基本的に、一度に1桁ずつランダムに生成することにより、インデックスを作成します。最悪のシナリオでは、これには10 *（桁数）を格納するのに十分なメモリが必要になります。範囲内のすべての数値に1回だけ遭遇します(0..(10**3))が、順序は疑似乱数のみです。つまり、最初のループが設定されている場合、数百桁の変化が見られる前a=1に、フォームの3桁の数字すべてに遭遇します。1xx

もう1つの欠点は、指定した深さまで関数を手動で作成する必要があることです。あなたの(0..(99**99))場合、これはおそらく問題になるでしょう（ただし、コードを生成するためのスクリプトを書くことができると思います）。これを状態に応じて再帰的に書き直す方法はおそらくあると思いますが、頭のてっぺんから考えることはできません（アイデア、誰か？）。

于 2010-03-17T19:11:43.483 に答える
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までの場合にのみ機能しますが、一般的な考え方は任意のサイズの配列に使用できます。

私はそれを説明するために最善を尽くします。最初の部分は、「2の累乗のサイズのドメインに対して」可逆的なハッシュが必要なことです。考えてみてくださいx = i + 1。xが何であっても、整数がオーバーフローしても、iが何であったかを判別できます。より具体的には、xの下位nビットからiの下位nビットをいつでも決定できます。加算は可逆ハッシュ演算であり、奇数による乗算も、定数によるビット単位のxorの実行も同様です。特定の2の累乗ドメインがわかっている場合は、そのドメインのビットをスクランブルできます。たとえばx ^= (x & 0xFF) >> 5)、16ビットドメインで有効です。たとえば、マスクを使用してそのドメインを指定するmask = 0xFFと、ハッシュ関数はになりx = hash(i, mask)ます。もちろん、そのハッシュ関数に「シード」値を追加して、さまざまなランダム化を取得できます。

つまり、リバーシブル関数がありますx = hash(i, mask, seed)。問題は、インデックスをハッシュすると、配列サイズ、つまり「ドメイン」よりも大きい値になる可能性があることです。これをモジュロすることはできません。そうしないと、衝突が発生します。

リバーシブルハッシュは、「任意の有限ドメインを持つ暗号」で紹介されている「サイクルウォーキング」と呼ばれる手法を使用するための鍵です。ハッシュはリバーシブル（つまり1対1）であるため、ハッシュ値が配列より小さくなるまで、同じハッシュを繰り返し適用できます。同じハッシュを適用していて、マッピングは1対1であるため、最終的に得られる値はすべて、正確に1つのインデックスにマッピングされ、衝突は発生しません。したがって、32ビット整数（擬似コード）の場合、関数は次のようになります。

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

ドメインに到達するまでに多くのハッシュが必要になる可能性があるため、ケンスラーは簡単なトリックを実行します。彼はハッシュを次の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 に答える