19

このコードブロックの前に定義されています：

  • datasetVectorまたは_List
  • numberOfSlicesIntデータセットをスライスする「回数」を示します

numberOfSlicesデータセットをスライスに分割し、可能な限り均等に分散させたいと思います。「分割」とは、集合論の用語を使用するための「パーティション」（すべての共通部分は空で、すべての和集合は元の値である必要があります）を意味すると思いますが、これは必ずしも集合ではなく、任意のコレクションです。

例えば

dataset = List(1, 2, 3, 4, 5, 6, 7)
numberOfSlices = 3
slices == ListBuffer(Vector(1, 2), Vector(3, 4), Vector(5, 6, 7))

私が以下に持っているものよりもそれを行うためのより良い方法はありますか？（これが最適かどうかさえわかりません...）または、これはアルゴリズム的に実行可能な試みではない可能性があります。その場合、既知の優れたヒューリスティックはありますか？

val slices = new ListBuffer[Vector[Int]]
val stepSize = dataset.length / numberOfSlices
var currentStep = 0
var looper = 0
while (looper != numberOfSlices) {
  if (looper != numberOfSlices - 1) {
    slices += dataset.slice(currentStep, currentStep + stepSize)
    currentStep += stepSize
  } else {
    slices += dataset.slice(currentStep, dataset.length)
  }
  looper += 1
}
4

6 に答える 6

14

の動作がxs.grouped(xs.size / n)うまくいかない場合は、必要なものを正確に定義するのは非常に簡単です。商は小さい方のピースのサイズで、余りは大きい方のピースの数です。

def cut[A](xs: Seq[A], n: Int) = {
  val (quot, rem) = (xs.size / n, xs.size % n)
  val (smaller, bigger) = xs.splitAt(xs.size - rem * (quot + 1))
  smaller.grouped(quot) ++ bigger.grouped(quot + 1)
}
于 2012-07-12T16:55:57.933 に答える
7

典型的な「最適な」パーティションは、切断後に正確な小数部の長さを計算し、次に丸めて実際の数を見つけます。

def cut[A](xs: Seq[A], n: Int):Vector[Seq[A]] = {
  val m = xs.length
  val targets = (0 to n).map{x => math.round((x.toDouble*m)/n).toInt}
  def snip(xs: Seq[A], ns: Seq[Int], got: Vector[Seq[A]]): Vector[Seq[A]] = {
    if (ns.length<2) got
    else {
      val (i,j) = (ns.head, ns.tail.head)
      snip(xs.drop(j-i), ns.tail, got :+ xs.take(j-i))
    }
  }
  snip(xs, targets, Vector.empty)
}

このようにして、より長いブロックとより短いブロックが散在します。これは、均一性のためにより望ましいことがよくあります。

scala> cut(List(1,2,3,4,5,6,7,8,9,10),4)
res5: Vector[Seq[Int]] = 
  Vector(List(1, 2, 3), List(4, 5), List(6, 7, 8), List(9, 10))

要素よりも多くの時間をカットすることもできます。

scala> cut(List(1,2,3),5)
res6: Vector[Seq[Int]] = 
  Vector(List(1), List(), List(2), List(), List(3))
于 2012-07-12T18:27:43.187 に答える
4

これは、を返す再帰関数のよく知られたScalaトリックを使用して、私のために仕事をするワンライナーですStream。を使用し(x+k/2)/kてチャンクサイズを丸め、最終的なリストに小さいチャンクと大きいチャンクを挿入します。すべてのサイズには、最大で1つの違いの要素があります。代わりに切り上げる場合は、を使用して(x+k-1)/k、小さいブロックを最後にx/k移動し、それらを最初に移動します。

def k_folds(k: Int, vv: Seq[Int]): Stream[Seq[Int]] =
    if (k > 1)
        vv.take((vv.size+k/2)/k) +: k_folds(k-1, vv.drop((vv.size+k/2)/k))
    else
        Stream(vv)

デモ：

scala> val indices = scala.util.Random.shuffle(1 to 39)

scala> for (ff <- k_folds(7, indices)) println(ff)
Vector(29, 8, 24, 14, 22, 2)
Vector(28, 36, 27, 7, 25, 4)
Vector(6, 26, 17, 13, 23)
Vector(3, 35, 34, 9, 37, 32)
Vector(33, 20, 31, 11, 16)
Vector(19, 30, 21, 39, 5, 15)
Vector(1, 38, 18, 10, 12)

scala> for (ff <- k_folds(7, indices)) println(ff.size)
6
6
5
6
5
6
5

scala> for (ff <- indices.grouped((indices.size+7-1)/7)) println(ff)
Vector(29, 8, 24, 14, 22, 2)
Vector(28, 36, 27, 7, 25, 4)
Vector(6, 26, 17, 13, 23, 3)
Vector(35, 34, 9, 37, 32, 33)
Vector(20, 31, 11, 16, 19, 30)
Vector(21, 39, 5, 15, 1, 38)
Vector(18, 10, 12)

scala> for (ff <- indices.grouped((indices.size+7-1)/7)) println(ff.size)
6
6
6
6
6
6
3

groupedすべてのサブリストのサイズを均等にしようとしないことに注意してください。

于 2017-02-14T21:53:00.827 に答える
1

これが問題に対する私の見解です：

  def partition[T](items: Seq[T], partitionsCount: Int): List[Seq[T]] = {
    val minPartitionSize = items.size / partitionsCount
    val extraItemsCount = items.size % partitionsCount

    def loop(unpartitioned: Seq[T], acc: List[Seq[T]], extra: Int): List[Seq[T]] =
      if (unpartitioned.nonEmpty) {
        val (splitIndex, newExtra) = if (extra > 0) (minPartitionSize + 1, extra - 1) else (minPartitionSize, extra)
        val (newPartition, remaining) = unpartitioned.splitAt(splitIndex)
        loop(remaining, newPartition :: acc, newExtra)
      } else acc

    loop(items, List.empty, extraItemsCount).reverse
  }

他のいくつかのソリューションよりも冗長ですが、うまくいけばより明確になります。逆は、順序を保持したい場合にのみ必要です。

于 2019-05-04T13:58:02.130 に答える
0

Kaitoが言及してgroupedいるように、まさにあなたが探しているものです。しかし、そのようなメソッドを実装する方法を知りたいだけの場合は、多くの方法があります;-)。たとえば、次のようにすることができます。

def grouped[A](xs: List[A], size: Int) = {
  def grouped[A](xs: List[A], size: Int, result: List[List[A]]): List[List[A]] = {
    if(xs.isEmpty) {
      result
    } else {
      val (slice, rest) = xs.splitAt(size)
      grouped(rest, size, result :+ slice)
    }
  }
  grouped(xs, size, Nil)
}
于 2012-07-12T16:52:24.353 に答える
0

私はこのようにアプローチします：n要素とmパーティション（n> m）が与えられた場合、n mod m == 0の場合、各パーティションはn / m要素を持つか、n mod m = yの場合、各パーティションにはn/m要素があり、yいくつかに分散する必要がありますm。

y要素のあるスロットn/m+1と（my）n/mのスロットがあります。それらをどのように配布するかはあなたの選択です。

于 2012-07-12T17:02:43.627 に答える