Der Union-Find-Algorithmus in Scala: eine rein funktionale Implementierung

In diesem Beitrag werde ich den Union-Find-Algorithmus in Scala implementieren, zunächst auf eine unreine Art und Weise und dann auf eine rein funktionale Art, also ohne Zustand oder Seiteneffekte. Dann können wir beide Implementierungen überprüfen und den Code und auch die Leistung vergleichen.

Der Grund, warum ich union-find für diesen Blog ausgewählt habe, ist, dass er relativ einfach ist. Es handelt sich um einen klassischen Algorithmus, der zur Lösung des folgenden Problems verwendet wird: Angenommen, wir haben eine Menge von Objekten. Jedes dieser Objekte kann mit null oder mehr anderen verbunden sein. Und die Verbindungen sind transitiv: Wenn A mit B verbunden ist und B mit C, dann ist A auch mit C verbunden. Nun nehmen wir zwei Objekte aus der Menge und wollen wissen: Sind sie miteinander verbunden oder nicht?

Dieses Problem tritt in einer Reihe von Bereichen auf, z. B. in sozialen Netzwerken (sind zwei Personen über Freunde verbunden oder nicht) oder in der Bildverarbeitung (sind Pixel verbunden oder getrennt). Da die Gesamtzahl der Objekte und Verbindungen in der Menge sehr groß sein kann, ist die Leistung des Algorithmus wichtig.

Quick Union Die von mir gewählte Implementierung ist die so genannte Quick Union-Implementierung. Sie ist gut skalierbar, aber es gibt noch schnellere Implementierungen, von denen eine in den Referenzen unter dem Artikel aufgeführt ist. Für diesen Beitrag habe ich mich entschieden, die Dinge einfach zu halten, damit wir uns auf den Vergleich der beiden Implementierungen konzentrieren können.

Der Algorithmus verfolgt die verbundenen Elemente mit einer Datenstruktur: Er stellt jedes Element als einen Knoten dar, der auf ein anderes Element zeigt, mit dem er verbunden ist. Jeder Knoten zeigt auf nur einen Knoten, mit dem er verbunden ist, und diesen Knoten nennt er seinen Elternteil. Auf diese Weise bilden Gruppen von verbundenen Knoten Bäume. Die Wurzel eines solchen verbundenen Baums ist ein Knoten, der eine leere Elterneigenschaft hat.

Wenn die Frage gestellt wird, ob zwei Knoten miteinander verbunden sind, sucht der Algorithmus nach den Wurzeln der verbundenen Bäume beider Knoten und prüft, ob sie gleich sind. Der knifflige Teil bei Algorithmen zum Finden von Vereinigungen besteht darin, neue Verbindungen zu einer Gruppe von Elementen hinzufügen zu können, ohne zu viel Leistung zu verlieren. Mit der Datenstruktur mit den verbundenen Bäumen können wir dies sehr gut bewerkstelligen. Wir beginnen mit der Suche nach der Wurzel beider Elemente und setzen dann das Elternelement des einen Baums auf die Wurzel des anderen Baums.

Dabei ist jedoch eine gewisse Vorsicht geboten, denn mit der Zeit können verbundene Bäume aus dem Gleichgewicht geraten. Deshalb wird die Größe jedes Baums in seinem Wurzelknoten gespeichert. Wenn Sie zwei Teilbäume verbinden, wird der kleinere immer zum größeren hinzugefügt. Dies garantiert, dass alle Teilbäume ausgeglichen bleiben. Dies war nur eine kurze Beschreibung des Algorithmus, aber es gibt einige ausgezeichnete Erklärungen im Internet. Hier ist eine schöne, weil sie visuell und interaktiv ist:visual algo

Die unreine Implementierung Sehen wir uns nun etwas Code an! Die unreine Implementierung:

[code language="scala"]
import scala.annotation.tailrec
class IUnionFind(val size: Int) {
private case class Node(var parent: Option[Int], var treeSize: Int)
private val nodes = Array.fill[Node](size)(new Node(None, 1))
def union(t1: Int, t2: Int): IUnionFind = {
if (t1 == t2) return this
val root1 = root(t1)
val root2 = root(t2)
if (root1 == root2) return this
val node1 = nodes(root1)
val node2 = nodes(root2)
if (node1.treeSize < node2.treeSize) {
node1.parent = Some(t2)
node2.treeSize += node1.treeSize
} else {
node2.parent = Some(t1)
node1.treeSize += node2.treeSize
}
this
}
def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)
@tailrec
private def root(t: Int): Int = nodes(t).parent match {
case None => t
case Some(p) => root(p)
}
}
[/code]

Wie Sie sehen können, habe ich ein Array von Nodes verwendet, um die verbundenen Komponenten darzustellen. Die meisten Lehrbuchimplementierungen verwenden zwei Integer-Arrays: eines für die Eltern jedes Elements und das andere für die Baumgrößen der Komponenten, zu denen die Elemente gehören. Speichertechnisch ist das eine effizientere Implementierung als meine. Aber abgesehen davon bleibt das Konzept des Algorithmus dasselbe und in Bezug auf die Geschwindigkeit macht der Unterschied nicht viel aus. Ich denke, dass die Verwendung von Node-Objekten besser lesbar ist als zwei Integer-Arrays, deshalb habe ich mich für die Nodes entschieden. Die rein funktionale Implementierung [code language="scala"] import scala.annotation.tailrec case class Node(parent: Option[Int], treeSize: Int) object FUnionFind { def create(size: Int): FUnionFind = { val nodes = Vector.fill(size)(Node(None, 1)) new FUnionFind(nodes) } } class FUnionFind(nodes: Vector[Node]) { def union(t1: Int, t2: Int): FUnionFind = { if (t1 == t2) return this val root1 = root(t1) val root2 = root(t2) if (root1 == root2) return this val node1 = nodes(root1) val node2 = nodes(root2) val newTreeSize = node1.treeSize + node2.treeSize val (newNode1, newNode2) = if (node1.treeSize < node2.treeSize) { val newNode1 = Knoten(Some(t2), newTreeSize) val newNode2 = Node(node2.parent, newTreeSize) (neuerKnoten1, neuerKnoten2) } sonst { val newNode2 = FNode(Some(t1), newTreeSize) val newNode1 = FNode(node1.parent, newTreeSize) (neuerKnoten1, neuerKnoten2) } val newNodes = nodes.updated(root1, newNode1).updated(root2, newNode2) new FUnionFind(newNodes) } def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2) @tailrec private def root(t: Int): Int = nodes(t).parent match { Fall Keine => t case Some(p) => Wurzel(p) } } [/code] Im Vergleich zur ersten Implementierung sind einige Teile gleich geblieben. So z.B. Node, mit Ausnahme der Tatsache, dass es keine innere Klasse mehr ist. Auch die Methoden connected und root haben sich nicht geändert. Was sich geändert hat, ist die Methode, die für die Aktualisierung der Verbindungen zuständig ist: union. In der rein funktionalen Implementierung können wir kein Array aktualisieren, also wird stattdessen ein neues FUnionFind-Objekt erstellt und am Ende zurückgegeben. Außerdem müssen zwei Node-Objekte erstellt werden, wenn Teilbäume zusammengeführt werden; die Wurzel des kleineren, weil sie ein neues Elternteil erhält, und die Wurzel des größeren, weil dessen Baumgröße erhöht werden muss. Vielleicht überrascht es, dass die reine Implementierung mehr Codezeilen benötigt als die unreine. Die Leistung Die reine Implementierung muss ein wenig zusätzliche Arbeit leisten, wenn sie die neuen Objekte in ihrer Union-Methode erstellt. Die Frage ist, wie viel das in Bezug auf die Leistung kostet.Um das herauszufinden, habe ich beide Implementierungen durch eine Reihe von Leistungstests (mit ScalaMeter) laufen lassen, bei denen ich eine große Anzahl von Verbindungen zu einer Reihe von Objekten hinzugefügt habe. Ich habe auch eine (unreine) Java 8-Implementierung zu dem Test hinzugefügt. Hier sind die Ergebnisse:

Es überrascht nicht, dass die Zeit mit der Anzahl der Verbindungen und Elemente wächst. Das Wachstum ist etwas schneller als linear, denn die asymptotische Zeitkomplexität des Quick-Union-Algorithmus liegt in der Größenordnung von n log(n). Der reine Algorithmus ist etwa 65% langsamer als die unreine Implementierung. Die Ursache liegt auf der Hand: Bei jedem Aufruf von union muss der reine Algorithmus drei zusätzliche Objekte allozieren und garbage collect. Der Vollständigkeit halber habe ich den Test auch mit Java 8 durchgeführt. Der Code wird hier nicht angegeben, aber wenn Sie daran interessiert sind, finden Sie unter dem Artikel einen Link zum vollständigen Quelltext. Die Implementierung ist der Scala-Version sehr ähnlich. Fazit Rein funktionaler Code hat einige Vorteile gegenüber nicht reinen Implementierungen. Da es keine Seiteneffekte gibt, ist es einfacher, über Codeblöcke nachzudenken, und auch die Gleichzeitigkeit wird einfacher, da es keinen gemeinsam genutzten Zustand gibt. Im Allgemeinen führt dies auch zu prägnanterem Code, da Sammlungsmethoden wie map und filter einfach verwendet werden können. Aber in diesem Beispiel war das nicht der Fall, die reine Implementierung benötigte sogar ein paar Zeilen mehr. Der größte Nachteil des reinen Union-Find-Algorithmus war seine Leistung. Es hängt von den Anforderungen des Projekts ab, in dem der Code verwendet wird, ob dies ein Hemmschuh ist oder ob das bessere gleichzeitige Verhalten der reinen Implementierung diesen Nachteil aufwiegt. Erläuterung einer schnelleren Union-Findung mit Pfadkomprimierung Der gesamte Quellcode des Artikels, einschließlich der Tests