Определено перед этим блоком кода:
dataset может быть Vector или ListnumberOfSlices - это Int, обозначающий, сколько "раз" для набора данных фрагментовЯ хочу разбить набор данных на 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
}
Если поведение 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)
}
Типичный "оптимальный" раздел вычисляет точную дробную длину после резки, а затем округляет, чтобы найти фактическое число:
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))
Здесь однострочный, который выполняет эту работу для меня, используя знакомый трюк Scala рекурсивной функции, который возвращает Stream. Обратите внимание на использование (x+k/2)/k для округления размеров блоков, интеркалирования меньших и больших кусков в конечном списке, все с размерами не более одного элемента разницы. Если вместо этого вы округлите, (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 не пытается выровнять размер всех подписок.
Как упоминает 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)
}
Я бы применил его так: Учитывая n элементы и m разделы (n > m), либо n mod m == 0, в этом случае каждый раздел будет иметь n/m элементов, или n mod m = y, и в этом случае вы будете иметь каждый раздел с элементами n/m, и вам нужно распределить y над некоторым m.
У вас будут слоты y с элементами n/m+1 и (m-y) слотами с n/m. Как вы их распределяете, это ваш выбор.
Вот мой взгляд на проблему:
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
}
Оно более многословно, чем некоторые другие решения, но, надеюсь, более понятно. обратное необходимо только в том случае, если вы хотите сохранить заказ.