Beim Durchsehen der Dokumente von Data.Set habe ich gesehen, dass Das Einfügen eines Elements in den Baum wird als O (log (n)) bezeichnet. Ich würde jedoch intuitiv erwarten, dass es O (n * log (n)) (oder vielleicht O (n)?) Ist, da referenzielle Transparenz das Erstellen einer vollständigen Kopie des vorherigen Baums in O (n) erfordert.
Ich verstehe, dass zum Beispiel (:) O (1) anstelle von O (n) gemacht werden kann, da hier die vollständige Liste nicht kopiert werden muss; Die neue Liste kann vom Compiler als erstes Element plus einem Zeiger auf die alte Liste optimiert werden (beachten Sie, dass dies ein Compiler ist - keine Sprachlevel - Optimierung). Das Einfügen eines Werts in ein Data.Set beinhaltet jedoch ein Rebalancing, das für mich ziemlich komplex aussieht, bis zu dem Punkt, an dem ich bezweifle, dass die Listenoptimierung ähnlich ist. Ich habe versucht, das Papier zu lesen, auf das von den Set-Dokumenten verwiesen wird , konnte aber meine Frage nicht beantworten damit.
Also: Wie kann das Einfügen eines Elements in einen Binärbaum O (log (n)) in einer (rein) funktionalen Sprache sein?
Es muss keine vollständige Kopie von Set erstellt werden, um ein Element einzufügen. Intern werden Elemente in einem Baum gespeichert, was bedeutet, dass Sie nur neue Knoten entlang des Pfads der Einfügung erstellen müssen. Unberührte Knoten können zwischen der Pre-Insert- und der Post-Insertion-Version von Set geteilt werden. Und als Deitrich Epp darauf hingewiesen, in einem ausgewogenen tree O(log(n)) ist die Länge des Pfades der Einfügung. (Entschuldigung dafür, dass diese wichtige Tatsache weggelassen wurde.)
Sagen Sie, Ihr Tree Typ sieht so aus:
... und sagen Sie haben ein Tree , das so aussieht
... wo tl und tr' einige benannte Unterbäume sind. Nun sagen Sie, dass Sie 12 in diesen Baum einfügen möchten. Nun, das wird ungefähr so aussehen:
Die Unterbäume tl und tr' werden zwischen t und t' geteilt, und Sie mussten nur 3 neue Nodes erstellen, obwohl die Größe von t viel größer sein könnte als 3.
EDIT: Rebalancing
Denken Sie im Hinblick auf die Neuausrichtung darüber nach, und beachten Sie, dass ich hier keine Strenge beanspruche. Angenommen du hast einen leeren Baum. Schon ausgeglichen! Jetzt sagen Sie, dass Sie ein Element einfügen. Schon ausgeglichen! Jetzt sagen Sie, dass Sie ein anderes -Element einfügen. Nun, es gibt eine ungerade Zahl, also kannst du dort nicht viel machen.
Hier ist der schwierige Teil. Angenommen, Sie fügen ein anderes -Element ein. Dies könnte zwei Wege gehen: links oder rechts; ausgeglichen oder unausgewogen. Für den Fall, dass es unausgewogen ist, können Sie eine Drehung des Baumes durchführen, um ihn auszugleichen. Für den Fall, dass es ausgewogen ist, schon ausgeglichen!
Es ist wichtig zu beachten, dass Sie ständig neu ausbalancieren. Es ist nicht so, als hättest du ein Chaos in einem Baum, hast beschlossen, ein Element einzufügen, aber bevor du das tust, musst du das Gleichgewicht wieder herstellen und dann ein Durcheinander hinterlassen, nachdem du das Einfügen abgeschlossen hast.
Nun sagen Sie, dass Sie Elemente einfügen. Die Gonna des Baumes werden unausgewogen, aber nicht viel. Und wenn das passiert, korrigierst du das zuerst sofort und zweitens tritt die Korrektur entlang des Pfades der Einfügung auf, der O(log(n)) in einem ausgeglichenen Baum ist. Die Rotationen in dem Papier, mit dem Sie verbunden sind, berühren höchstens drei Knoten im Baum, um eine Rotation durchzuführen. Du machst also O(3 * log(n)) work beim Rebalancing. Das ist immer noch O(log(n)) .
Um das, was dave4420 in einem Kommentar gesagt hat, zusätzliche Betonung hinzuzufügen, gibt es keine Compileroptimierungen, die (:) in konstanter Zeit ausführen lassen. Sie könnten Ihren eigenen Listendatentyp implementieren und ihn in einem einfachen nicht optimierenden Haskell-Interpreter ausführen, und dieser wäre immer noch O (1).
Eine Liste ist definiert als ein Anfangselement plus eine Liste (oder es ist im Basisfall leer). Hier ist eine Definition, die den nativen Listen entspricht:
%Vor% Wenn Sie also ein Element und eine Liste haben und eine neue Liste mit Cons erstellen möchten, erstellen Sie einfach eine neue Datenstruktur direkt aus den Argumenten, die der Konstruktor benötigt. Es besteht keine Notwendigkeit mehr, die Endliste zu prüfen (geschweige denn zu kopieren), als die Zeichenfolge zu untersuchen oder zu kopieren, wenn Sie etwas wie Person "Fred" machen.
Sie irren sich einfach, wenn Sie behaupten, dass dies eine Compiler-Optimierung ist und keine Sprachebene. Dieses Verhalten folgt direkt aus der Definition der Sprachebene des Listdatentyps.
Ebenso muss für einen Baum, der als ein Element plus zwei Bäume (oder ein leerer Baum) definiert ist, wenn Sie ein Element in einen nicht leeren Baum einfügen, es entweder in den linken oder rechten Teilbaum gehen. Sie müssen eine neue Version des Baums erstellen, der das Element enthält. Dies bedeutet, dass Sie einen neuen übergeordneten Knoten erstellen müssen, der den neuen Teilbaum enthält. Aber der andere Teilbaum muss überhaupt nicht durchlaufen werden; es kann wie es ist in den neuen Elternbaum eingefügt werden. In einem ausgeglichenen Baum ist das eine vollständige Hälfte des Baums, die geteilt werden kann.
Wenn Sie diese Argumentation rekursiv anwenden, sollten Sie erkennen, dass Datenelemente überhaupt nicht kopiert werden müssen. Es gibt nur die neuen übergeordneten Knoten, die auf dem Pfad bis zur endgültigen Position des eingefügten Elements benötigt werden. Jeder neue Knoten speichert 3 Dinge: ein Element (das direkt mit dem Objektverweis im Originalbaum geteilt wird), einen unveränderten Teilbaum (der direkt mit dem Originalbaum geteilt wird) und einen neu erstellten Teilbaum (der fast die gesamte Struktur mit dem Original teilt Baum). Es wird O (log (n)) von denen in einem ausgeglichenen Baum geben.
Tags und Links haskell complexity-theory referential-transparency