Teilen Sie die Liste in mehrere Listen mit einer festen Anzahl von Elementen auf

119

Wie teile ich eine Liste von Elementen in Listen mit höchstens N Elementen auf?

Beispiel: Erstellen Sie bei einer Liste mit 7 Elementen 4er-Gruppen, wobei die letzte Gruppe möglicherweise weniger Elemente enthält.

split(List(1,2,3,4,5,6,"seven"),4)

=> List(List(1,2,3,4), List(5,6,"seven"))
Johnny Everson
quelle

Antworten:

213

Ich denke du suchst grouped. Es gibt einen Iterator zurück, aber Sie können das Ergebnis in eine Liste konvertieren.

scala> List(1,2,3,4,5,6,"seven").grouped(4).toList
res0: List[List[Any]] = List(List(1, 2, 3, 4), List(5, 6, seven))
Kipton Barros
quelle
25
Scala-Listen haben für alles etwas zu bieten.
J Atkin
Ich habe eine seltsame Frage. Für den gleichen Fall, wenn ich die Daten in eine Sequenz konvertiere, erhalte ich ein Stream-Objekt. Warum ist das so?
Rakshith
2
@ Rakshith Das klingt nach einer separaten Frage. Scala hat einen mysteriösen Gnom, der eine Datenstruktur auswählt und einen Stream für Sie auswählt. Wenn Sie eine Liste möchten, sollten Sie eine Liste anfordern, aber Sie können auch einfach dem Urteil des Gnomen vertrauen.
Ion Freeman
12

Es gibt eine viel einfachere Möglichkeit, die Aufgabe mithilfe der Gleitmethode auszuführen. Es funktioniert so:

val numbers = List(1, 2, 3, 4, 5, 6 ,7)

Nehmen wir an, Sie möchten die Liste in kleinere Listen der Größe 3 aufteilen.

numbers.sliding(3, 3).toList

werde dir geben

List(List(1, 2, 3), List(4, 5, 6), List(7))
Dorjee
quelle
9

Oder wenn Sie Ihre eigenen machen wollen:

def split[A](xs: List[A], n: Int): List[List[A]] = {
  if (xs.size <= n) xs :: Nil
  else (xs take n) :: split(xs drop n, n)
}

Verwenden:

scala> split(List(1,2,3,4,5,6,"seven"), 4)
res15: List[List[Any]] = List(List(1, 2, 3, 4), List(5, 6, seven))

edit : Wenn ich dies 2 Jahre später überprüfe, würde ich diese Implementierung nicht empfehlen, da sie sizeO (n) ist, und daher ist diese Methode O (n ^ 2), was erklären würde, warum die eingebaute Methode für große Listen schneller wird. wie in den Kommentaren unten angegeben. Sie können Folgendes effizient implementieren:

def split[A](xs: List[A], n: Int): List[List[A]] =
  if (xs.isEmpty) Nil 
  else (xs take n) :: split(xs drop n, n)

oder sogar (etwas) effizienter mit splitAt:

def split[A](xs: List[A], n: Int): List[List[A]] =
  if (xs.isEmpty) Nil 
  else {
    val (ys, zs) = xs.splitAt(n)   
    ys :: split(zs, n)
  }
Luigi Plinge
quelle
4
xs splitAt nist eine Alternative zu der Kombination xs take nundxs drop n
Kipton Barros
1
Dies wird den Stapel explodieren lassen, betrachten Sie eine rekursive Implementierung
Jed Wesley-Smith
@Kipton, stimmt, aber Sie müssen die Ergebnisse in temporäre Werte extrahieren, damit einer Methode ein paar Zeilen hinzugefügt werden. Ich habe einen schnellen Benchmark durchgeführt und es scheint, dass die Leistung im Durchschnitt um 4% splitAtanstelle von take/ dropverbessert wird. beide sind 700-1000% schneller als .grouped(n).toList!
Luigi Plinge
@ Luigi, Wow. Irgendwelche Gedanken darüber, warum grouped-toListes so langsam ist? Das klingt nach einem Fehler.
Kipton Barros
@Jed Sie haben in extremen Fällen Recht, aber Ihre Implementierung hängt davon ab, wofür Sie sie verwenden. Für den Anwendungsfall von OP (falls groupednicht vorhanden :)) ist die Einfachheit der übergeordnete Faktor. Für die Standardbibliothek sollten Stabilität und Leistung die Eleganz übertreffen. Es gibt jedoch viele Beispiele sowohl in der Programmierung in Scala als auch in den Standardbibliotheken für normal rekursive (und nicht für schwanzrekursive) Aufrufe. Es ist eine Standard- und wichtige Waffe in der FP-Toolbox.
Luigi Plinge
4

Ich füge eine rekursive Schwanzversion der Split-Methode hinzu, da einige Diskussionen über Schwanzrekursion und Rekursion geführt wurden. Ich habe die Annotation tailrec verwendet, um den Compiler zu zwingen, sich zu beschweren, falls die Implementierung tatsächlich nicht tail-recusive ist. Ich glaube, die Schwanzrekursion wird zu einer Schleife unter der Haube und verursacht daher auch bei einer großen Liste keine Probleme, da der Stapel nicht unbegrenzt wächst.

import scala.annotation.tailrec


object ListSplitter {

  def split[A](xs: List[A], n: Int): List[List[A]] = {
    @tailrec
    def splitInner[A](res: List[List[A]], lst: List[A], n: Int) : List[List[A]] = {
      if(lst.isEmpty) res
      else {
        val headList: List[A] = lst.take(n)
        val tailList : List[A]= lst.drop(n)
        splitInner(headList :: res, tailList, n)
      }
    }

    splitInner(Nil, xs, n).reverse
  }

}

object ListSplitterTest extends App {
  val res = ListSplitter.split(List(1,2,3,4,5,6,7), 2)
  println(res)
}
Mike
quelle
1
Diese Antwort könnte durch Hinzufügen einer Erklärung verbessert werden. Angesichts der Tatsache, dass die akzeptierte Antwort der kanonische, beabsichtigte Weg zu sein scheint, sollten Sie erklären, warum jemand diese Antwort bevorzugen würde.
Jeffrey Bosboom
0

Ich denke, dies ist die Implementierung mit splitAt anstelle von take / drop

def split [X] (n:Int, xs:List[X]) : List[List[X]] =
    if (xs.size <= n) xs :: Nil
    else   (xs.splitAt(n)._1) :: split(n,xs.splitAt(n)._2)
Hydrosan
quelle