1

私は以下のコードを持っています：

def shuffle arr
  shuffled = []
  while arr.length > 0
    randNum = rand(arr.length)
    idx = 0
    unshuf = []
    arr.each do |item|
      if idx == randNum
        shuffled.push item
      else
        unshuf.push item
      end
      idx = idx + 1
    end
    arr = unshuf
  end
  return shuffled
end

puts(shuffle([ 11, 12, 13]))

unshufメソッドshuffleが呼び出されたときの配列のステータスを理解しようとしています。メソッドが呼び出される前に、配列unshufは毎回空の配列にリセットされます。そのような実装の下で、次の条件のラウンドのためにeach数字はどのように保持されますか？unshufif

4

3 に答える 3

3

コードは次のように機能します。

  • 最終結果が保存される空の配列を作成します。

  • 0から最初の配列の捕捉までの乱数を取得します。

  • indexcounterをゼロに初期化します。
  • シャッフルされていない空の配列を作成します。
  • 初期配列をループします
    • すべてのアイテムをシャッフルされていない配列にプッシュし、
    • indexcounter ==乱数であるものを除いて、それは結果の配列に行きます
    • インデックスカウンターを維持しながら。
  • シャッフルされていない配列の名前を初期配列に変更します。
  • 最初の配列が空になるまで、手順2から繰り返します。

言うまでもなく、これは不器用です。また、それは非常にunRubyの方法で書かれており、手動のインデックスを保持し、のような変数名を使用していますrandNum。これはほぼ同じです：

def shuffle(arr)
  dup = arr.dup
  arr.size.times.map do # actually arr.map would work
    dup.slice!(rand(dup.size))
  end
end

しかし、他の人が述べているように、[1,2,3].shuffle標準のRubyです。

于 2012-12-30T23:24:15.147 に答える
2

上記のコードをどこで入手したのかわかりません。Ruby Array＃shuffleメソッドは#shuffleを呼び出します！ネイティブメソッドrb_ary_shuffle_bang。次のようになります。

static VALUE
rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
{
  VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
  long i, snap_len;

  if (OPTHASH_GIVEN_P(opts)) {
    randgen = rb_hash_lookup2(opts, sym_random, randgen);
  }
  if (argc > 0) {
    rb_raise(rb_eArgError, "wrong number of arguments (%d for 0)", argc);
  }
  rb_ary_modify(ary);
  i = RARRAY_LEN(ary);
  ptr = RARRAY_PTR(ary);
  snap_len = i;
  snap_ptr = ptr;
  while (i) {
    long j = RAND_UPTO(i);
    VALUE tmp;
    if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
      rb_raise(rb_eRuntimeError, "modified during shuffle");
    }
    tmp = ptr[--i];
    ptr[i] = ptr[j];
    ptr[j] = tmp;
  }
  return ary;
}

ここでは、シャッフルへの正しいアプローチを見ることができます。上記のコードの上半分を無視すると、whileループだけに注意してください。ループは配列を上から下に通過し、常にインデックスの下のセクションからiランダムに要素を選択し、現在の位置のに移動し、iデクリメントを続けますi。その複雑さは、シャッフルの場合と同様に、n =配列の長さのO（n）です。

一方、本のコードの動作はまったく異なります。常に配列から1つの要素（rand( arr.length )）を選択し、配列を反復処理して、そのインデックスを持つ要素がいつ検出されるかを確認します。複雑さはO（n ** 2/2）です。 。コードは、#pushメソッドを使用する良い例も示して#<<いますが、毎回1つの要素しかプッシュされないため、十分です。あなたのコードは、ループidx内のインデックスを手動で維持するという悪い例を示しています。代わりにメソッドを使用する必要があります。もちろん、デモンストレーションの目的以外では、内部ループを完全に削除し、ネイティブメソッドと同様のアプローチを使用する必要があります。each#each_with_index#shuffle

于 2012-12-30T22:33:26.630 に答える
1 
def shuffle arr
  shuffled = []

  while arr.length > 0
    randNum = rand(arr.length)

    idx = 0
    unshuf = []

    print '--- arr='; p arr # <--------
    arr.each do |item|
      if idx == randNum
        shuffled.push item
      else
        unshuf.push item
      end
      print 'shuffled='; print shuffled; print ', unshuf='; p unshuf # <--------
      idx = idx + 1
    end

    arr = unshuf
  end

  return shuffled
end

p shuffle([ 11, 12, 13, 14, 15])

実行：

$ ruby -w t.rb 
--- arr=[11, 12, 13, 14, 15]
shuffled=[], unshuf=[11]
shuffled=[], unshuf=[11, 12]
shuffled=[13], unshuf=[11, 12]
shuffled=[13], unshuf=[11, 12, 14]
shuffled=[13], unshuf=[11, 12, 14, 15]
--- arr=[11, 12, 14, 15]
shuffled=[13, 11], unshuf=[]
shuffled=[13, 11], unshuf=[12]
shuffled=[13, 11], unshuf=[12, 14]
shuffled=[13, 11], unshuf=[12, 14, 15]
--- arr=[12, 14, 15]
shuffled=[13, 11, 12], unshuf=[]
shuffled=[13, 11, 12], unshuf=[14]
shuffled=[13, 11, 12], unshuf=[14, 15]
--- arr=[14, 15]
shuffled=[13, 11, 12, 14], unshuf=[]
shuffled=[13, 11, 12, 14], unshuf=[15]
--- arr=[15]
shuffled=[13, 11, 12, 14, 15], unshuf=[]
[13, 11, 12, 14, 15]

説明：のコンテンツは、シャッフルされたものarrとシャッフルされていないものの間でランダムに分散されます。次に、unshufがarrに置き換わり、unshufに何かがあった場合、whileループはシャッフルで少し、unshufで少しランダムに再配布されます。unshufが空になるまで続けます。したがって、シャッフルされた要素は、メソッドにarr最初に指定されたパラメーターからランダムに取得された要素で徐々に埋められますが、シャッフルされていない要素のみをに保持することによって徐々に空になります。もちろん、arrに移動した後、新しいディストリビューションを受信するには、unshufを空の配列にリセットする必要がありますが、シャッフルは成長し続ける必要があります。それが明確であることを願っています。shufflearrarr = unshuf

于 2012-12-30T23:08:21.220 に答える