5

ArrayBufferの一部を、できればインプレースでシャッフルする必要があるので、コピーは必要ありません。たとえば、ArrayBufferに10個の要素があり、要素を3〜7個シャッフルしたい場合：

// Unshuffled ArrayBuffer of ints numbered 0-9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

// Region I want to shuffle is between the pipe symbols (3-7)
0, 1, 2 | 3, 4, 5, 6, 7 | 8, 9

// Example of how it might look after shuffling
0, 1, 2 | 6, 3, 5, 7, 4 | 8, 9

// Leaving us with a partially shuffled ArrayBuffer
0, 1, 2, 6, 3, 5, 7, 4, 8, 9

以下に示すようなものを作成しましたが、コピーとループの反復が数回必要です。これを行うにはもっと効率的な方法があるはずです。

def shufflePart(startIndex: Int, endIndex: Int) {

  val part: ArrayBuffer[Int] = ArrayBuffer[Int]()

  for (i <- startIndex to endIndex ) {
    part += this.children(i)
  }

  // Shuffle the part of the array we copied
  val shuffled = this.random.shuffle(part)
  var count: Int = 0

  // Overwrite the part of the array we chose with the shuffled version of it
  for (i <- startIndex to endIndex ) {
    this.children(i) = shuffled(count)
    count += 1
  }
}

GoogleでArrayBufferを部分的にシャッフルすることについては何も見つかりませんでした。自分でメソッドを書く必要があると思いますが、そうすることでコピーを防ぎたいと思います。

4

2 に答える 2

5

のサブタイプを使用できる場合は、保護されたメンバーがあるArrayBufferため、基になる配列に直接アクセスできます。ResizableArrayarray

import java.util.Collections
import java.util.Arrays
import collection.mutable.ArrayBuffer


val xs = new ArrayBuffer[Int]() {
  def shuffle(a: Int, b: Int) {
    Collections.shuffle(Arrays.asList(array: _*).subList(a, b))
  }
}

xs ++= (0 to 9)    // xs = ArrayBuffer(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
xs.shuffle(3, 8)   // xs = ArrayBuffer(0, 1, 2, 4, 6, 5, 7, 3, 8, 9)

ノート：

  • の上限java.util.List#subListは排他的です
  • Arrays#asList要素の新しいセットを作成しないため、かなり効率的です。配列自体に支えられています（したがって、追加または削除メソッドはありません）
  • a実際に使用する場合は、境界チェックを追加したいと思うでしょう。b
于 2012-03-06T01:41:58.920 に答える
3

なぜそれが適切な場所にある必要があるのか​​ 完全にはわかりません-それについて考えてみてください。しかし、それが正しいことであると仮定すると、これはそれを行うことができます:

import scala.collection.mutable.ArrayBuffer

implicit def array2Shufflable[T](a: ArrayBuffer[T]) = new {
  def shufflePart(start: Int, end: Int) = {
    val seq = (start.max(0) until end.min(a.size - 1)).toSeq
    seq.zip(scala.util.Random.shuffle(seq)) foreach { t =>
      val x = a(t._1)
      a.update(t._1, a(t._2))
      a(t._2) = x
    }
    a
  }
}

次のように使用できます。

val a = ArrayBuffer(1,2,3,4,5,6,7,8,9)
println(a)
println(a.shufflePart(2, 7))

編集: 中間シーケンスの追加コストを支払う意思がある場合、アルゴリズム的に言えば、これはより合理的です。

  def shufflePart(start: Int, end: Int) = {
    val seq = (start.max(0) until end.min(a.size - 1)).toSeq
    seq.zip(scala.util.Random.shuffle(seq) map { i =>
      a(i)
    }) foreach { t =>
      a.update(t._1, t._2)
    }
    a
  }
}
于 2012-03-05T19:31:12.933 に答える