Partizione una raccolta in "k" close to uguale pezzi (Scala, ma il linguaggio agnostico)

Question

definiti prima questo blocco di codice:

• dataset può essere un Vector o List
• numberOfSlices è un Int denotare quante "volte" per segmentare dataset

Voglio dividere il set di dati in fette numberOfSlices, distribuite nel modo più uniforme possibile. Con "split" intendo dire "partizione" (l'intersezione di tutti dovrebbe essere vuota, l'unione di tutti dovrebbe essere l'originale) per usare il termine di teoria dell'insieme, sebbene questo non sia necessariamente un insieme, solo una raccolta arbitraria.

ad es.

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

C'è un modo migliore per farlo rispetto a quello che ho qui sotto? (che non sono nemmeno sicuro sia ottimale ...) O forse questo non è uno sforzo gestibile dal punto di vista algoritmico, nel qual caso qualsiasi nota euristica valida?

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

Se il comportamento di xs.grouped(xs.size/n) non funziona per voi, è abbastanza facile definire esattamente quello che vuoi. Il quoziente è la dimensione dei pezzi più piccoli, e il resto è il numero dei pezzi più grandi:

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

Come Kaito cita grouped è esattamente quello che stai cercando. Ma se vuoi solo sapere come implementare un tale metodo, ci sono molti modi ;-). Si potrebbe per esempio fare in questo modo:

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

mi piacerebbe avvicinarsi in questo modo: Dato n elementi e m partizioni (n> m), sia n mod m == 0 nel qual caso, ogni partizione avrà n/m elementi, o n mod m = y, nel qual caso avrai ciascuna partizione con gli elementi n/m e devi distribuire su qualche m.

Avrai slot con elementi n/m+1 e slot (m-y) con n/m. Come li distribuisci è la tua scelta.

Answer 4

La tipica partizione "ottimale" calcola un'esatta lunghezza frazionaria dopo il taglio e poi arrotonda per trovare il numero effettivo di prendere:

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

In questo modo il più a lungo e blocchi più brevi saranno intervallate, che è spesso più auspicabile per uniformità:

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

È anche possibile tagliare più volte di quanto si dispone di elementi:

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

Answer 5

Ecco un one-liner che fa il lavoro per me, usando il familiare trucco di Scala di una funzione ricorsiva che restituisce un Stream. Si noti l'uso di (x+k/2)/k per arrotondare le dimensioni del blocco, intercalando i pezzi più piccoli e più grandi nell'elenco finale, tutti con dimensioni con al massimo un elemento di differenza.Se invece si arrotonda, con (x+k-1)/k, si spostano i blocchi più piccoli fino alla fine e x/k li sposta all'inizio.

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 

Notate come grouped non cerca di uniformare le dimensioni di tutte le sotto-liste.