podziału kolekcji na „k” blisko do równe części (Scala, ale język agnostyka)

Question

określona do tego bloku kodu:

• dataset może być Vector lub List
• numberOfSlices jest Int oznaczające, ile "razy" należy wyciąć zbiór danych

Chcę podzielić zbiór danych na plasterki numberOfSlices, rozprowadzane tak równomiernie, jak to możliwe. Przez "split" myślę, że mam na myśli "partycję" (przecięcie wszystkich powinno być puste, uncja wszystkich powinna być oryginalna) do użycia terminu teorii zbiorów, choć niekoniecznie jest to zbiór, tylko arbitralny zbiór.

np.

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

Czy jest lepszy sposób to zrobić niż to, co mam poniżej? (które nie jestem nawet pewien, jest optymalny ...) A może to nie jest algorytmicznie wykonalne przedsięwzięcie, w którym to przypadku wszelkie znane dobre heurystyki?

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 
} 

Answer 1

Jeśli zachowanie xs.grouped(xs.size/n) nie działa dla Ciebie, to dość łatwo określić dokładnie, co chcesz. Iloraz wielkość mniejszych kawałków, a reszta jest liczba większych kawałków:

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) 
} 

Answer 2

Jako że Kaito wspomina o grouped jest dokładnie tym, czego szukasz. Ale jeśli chcesz tylko wiedzieć, jak wdrożyć taką metodę, istnieje wiele sposobów ;-). Można by na przykład nie podoba to:

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) 
} 

Answer 3

ja podejście, w następujący sposób: Z uwagi n elementy i m przegrody (n> m), albo n mod m == 0 w takim przypadku, każda partycja będzie miała elementy n/m lub n mod m = y, w takim przypadku będziesz miał każdą partycję z elementami n/m i będziesz musiał rozpowszechniać y przez jakieś m.

Będziesz mieć gniazdaz elementami n/m+1 i (m-y) z n/m. Jak je rozprowadzasz, to twój wybór.

Answer 4

Typowa „optymalne” partycja oblicza dokładną długość ułamkową po cięciu, a następnie zaokrągla się znaleźć rzeczywistą liczbę brać:

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) 
} 

ten sposób Państwa dłuższe i krótsze bloki będą przeplatane, który jest często bardziej pożądane dla równości:

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)) 

można nawet wyciąć więcej razy niż masz elementy:

scala> cut(List(1,2,3),5) 
res6: Vector[Seq[Int]] = 
    Vector(List(1), List(), List(2), List(), List(3)) 

Answer 5

Oto jedna liniówka, która wykonuje to zadanie za mnie, używając znanej Scala trick funkcji rekursywnej, która zwraca Stream. Zauważ użycie (x+k/2)/k, aby zaokrąglić rozmiary porcji, wstawiając mniejsze i większe kawałki w ostateczną listę, wszystkie o rozmiarach z co najwyżej jednym elementem różnicy.Jeśli zamiast tego zaokrąglisz, z (x+k-1)/k przesuniesz mniejsze bloki do końca, a x/k przeniesie je na początek.

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) 

Demo:

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 

Wskazówki jak grouped nie stara się wyrównać rozmiary wszystkich podrzędnych list.