Scala-Listen: Achten Sie auf Ihre append und prepends

Heute bin ich auf ein nettes Problem in einem Stück Code gestoßen, das einer unserer Kollegen mit der Bitte um Verbesserungen herumgeschickt hat. Das Problem besteht darin, eine große Liste von Zeilen nach einigen Merkmalen zu gruppieren. Als die Liste zu groß wurde, brauchte die Funktion, die die Gruppierung vornahm, über 2 Minuten, um den Datensatz zu gruppieren.

Das Problem

Lassen Sie uns zunächst ein fiktives Beispiel für die Domäne und die Funktion geben, die das Chaos verursacht hat:

[code lang="scala"]
case class Container(lines: List[Contained])
case class Contained(key: String, value: String)
def group(ts: List[_]) = ts.foldLeft(List[Container]()) {
case (l: List[Container], r: Contained) =>
r match {
case Contained("", "") => l
case x @ Contained("", _) => {
l.init ++ List(Container(l.last.lines ::: x :: Nil))
}
case x : Contained => l ++ List(Container(List[Contained](x)))
case _ => l
}
}
[/code]

Wenn die Funktion mit einer entsprechend großen Liste (100.000 Elemente) aufgerufen wurde, stieg die Ausführungszeit auf 130 Sekunden. Obwohl der Code funktionell einwandfrei ist, ist er nicht gerade für Scala-Listen optimiert. Das lässt uns eine Reihe von Optimierungsmöglichkeiten:

1. Ersetzen Sie jede Liste durch ListBuffer, so dass sie effektiv eine veränderbare Sammlung veränderbarer Objekte ist.
2. Machen Sie das Container-Objekt veränderbar, indem Sie einen ListBuffer verwenden
3. Optimieren Sie die Funktion für Listen

Da sich das erste und das zweite Szenario nicht wesentlich unterscheiden, werde ich hier nur das erste und das letzte Szenario vorstellen.

Vollständig veränderbare Lösung

[code lang="scala"]
case class Container(lines: ListBuffer[Contained])
case class Contained(key: String, value: String)
def group(ts: List[_]) = ts.foldLeft(ListBuffer[Container]()) {
case (l: ListBuffer[Container], r: Contained) =>
r match {
case Contained("", "") => l
case x @ Contained("", _) => {
l.last.lines.append(x)
l
}
case x : Contained => l.append(Container(ListBuffer[Contained](x))); l
case _ => l
}
}
[/code]

Die Ausführungsgeschwindigkeit für 100.000 Objekte liegt bei dieser Lösung bei etwa 350 ms, eine beachtliche Leistung, wenn man nur veränderbare Objekte verwendet.

Optimieren der unveränderlichen Funktion

Die ersten beiden Optionen verbessern die Laufzeitgeschwindigkeit erheblich, aber beide machen die Objekte veränderbar. Dieses Übel können wir vermeiden, wenn wir uns die Gruppenfunktion und die von ihr verwendeten Listenoperationen genauer ansehen. Die beiden wichtigsten Operationen, die die Funktion group verwendet, sind: List.init und List.last. Werfen wir einen Blick auf die Operationen mit List und ihre Komplexität:

Wir können die Gruppenfunktion einfach umschreiben, um head und tail anstelle von last und init zu verwenden. Jedes ist das Gegenstück des anderen in einer umgekehrten Liste, d.h..

[code lang="scala"]
list.init == list.reverse.tail.reverse
and
list.last == list.reverse.head
[/code]

Wenn wir die umgekehrten Listen sofort erstellen, müssen wir am Ende nur einmal umkehren. Und wir haben eine Menge O(n)-Operationen gespart. Werfen wir einen Blick auf die optimierte Version ohne die abschließende Umkehrung:

[code lang="scala"]
def improvedGroup(ts: List[_]) = ts.foldLeft(List[Container]()) {
case (l: List[Container], r: Contained) =>
r match {
case Contained("", "") => l
case x @ Contained("", _) => {
List(Container(List(x) ++ l.head.lines)) ++ l.tail
}
case x : Contained => List(Container(List[Contained](x))) ++ l
case _ => l
}
}
[/code]

Das einzige verbleibende Problem ist nun, dass die Liste[Container] und die Zeilen des Containers beide umgekehrt sind. Um also das gleiche Ergebnis zu erhalten, muss die Funktion noch etwas angepasst werden:

[code lang="scala"]
def fastGroup(ts: List[_]) = improvedGroup(ts).reverse.map(x => Container(x.lines.reverse))
[/code]

Jetzt liefert die Funktion fastGroup die gleichen Ergebnisse, und ihre Laufzeit beträgt bei 100.000 Elementen etwa 450 ms. Ich weiß nicht, wie es Ihnen geht, aber ich bevorzuge die letzte Lösung. Sie müssen zwar daran denken, die Elemente nach der Gruppierung wieder in die richtige Reihenfolge zu bringen, aber Sie opfern nicht die Unveränderlichkeit. Manchmal zahlt es sich aus, Schritt für Schritt auf eine Lösung hinzuarbeiten, anstatt zu versuchen, alles auf einmal zu schaffen.