Warum ist das Löschen normalerweise viel schwieriger zu implementieren als das Einfügen in viele Datenstrukturen?

33

Können Sie sich einen bestimmten Grund vorstellen, warum das Löschen in der Regel für viele (die meisten?) Datenstrukturen erheblich schwieriger zu implementieren ist als das Einfügen?

Kurzes Beispiel: Verknüpfte Listen. Das Einfügen ist trivial, aber das Löschen hat einige Sonderfälle, die es erheblich erschweren. Selbstausgleichende binäre Suchbäume wie AVL und Rot-Schwarz sind klassische Beispiele für schmerzhafte Löschimplementierungen.

Ich möchte sagen, dass es mit der Art und Weise zu tun hat, wie die meisten Leute denken: Es fällt uns leichter, Dinge konstruktiv zu definieren, was zu einfachen Einfügungen führt.

algorithms data-structures Leo Brito
quelle
4
Was popist mit extract-min?
Coredump
5
"Schwieriger zu implementieren" ist mehr eine Frage der Psychologie (Kognition und der Stärken und Schwächen des menschlichen Geistes) als der Programmierung (Eigenschaften von Datenstrukturen und Algorithmen).
outis
1
Wie ich finde, sollte es mindestens so einfach sein, Stacks wie Add zu löschen (für einen Array-Backed-Stack ist Popping nur eine Zeiger-Dekrementierung [1], wohingegen das Pushen eine vollständige Kopie des Arrays erfordern kann, wenn Sie die Maximalgröße des Stacks erreichen) Array). Es gibt auch einige Anwendungsfälle, in denen angenommen wird, dass Einfügungen häufig und Löschungen seltener vorkommen, es sich jedoch um eine sehr magische Datenstruktur handelt, bei der die Anzahl der Löschungen die Anzahl der Einfügungen übersteigt. [1] Sie sollten wahrscheinlich auch den jetzt unsichtbaren Verweis auf das aufgetauchte Objekt auf null setzen, um Speicherlecks zu vermeiden, an die ich mich erinnere, weil Liskovs Lehrbuch dies nicht getan hat
Foon,
43
"Kellner, könnten Sie bitte mehr Mayo zu diesem Sandwich geben?" "Sicher, kein Problem, Sir." "Könnten Sie auch den ganzen Senf entfernen?" "Äh ..."
Cobaltduck
3
Warum ist Subtraktion komplizierter als Addition? Division (oder Primfaktorisierung) komplizierter als Multiplikation? Wurzeln komplizierter als Potenzierung?
mu ist zu kurz

Antworten:

69

Es ist mehr als nur ein Geisteszustand; Es gibt physikalische (dh digitale) Gründe, warum das Löschen schwieriger ist.

Wenn Sie löschen, hinterlassen Sie ein Loch, in dem sich früher etwas befand. Der Fachbegriff für die resultierende Entropie lautet "Fragmentierung". In einer verknüpften Liste müssen Sie den entfernten Knoten "patchen" und die Zuordnung des verwendeten Speichers aufheben. In binären Bäumen führt dies zu einem Ungleichgewicht des Baums. In Speichersystemen wird der Speicher für eine Weile nicht verwendet, wenn neu zugewiesene Blöcke größer sind als die beim Löschen verbleibenden Blöcke.

Kurz gesagt, das Einfügen ist einfacher, da Sie auswählen können, wo Sie einfügen möchten. Das Löschen ist schwieriger, da Sie nicht im Voraus vorhersagen können, welches Element gelöscht wird.

Robert Harvey
quelle
3
Fragmentierung ist kein Thema, bei dem Zeiger und Indirektion eine Rolle spielen, sei es für die Struktur im Speicher oder in Diagrammen. Im Speicher spielt es keine Rolle, wo einzelne Knoten aufgrund der Indirektion existieren. Für Listen ist das Löschen eines internen Knotens (an der Stelle, an der Sie eine Lücke im Diagramm hätten) mit etwas weniger Operationen verbunden als das Einfügen (1 Zeigerzuweisung und 1 freie vs. 1 Zuweisung und 2 Zeigerzuweisungen). Bei Bäumen kann das Einfügen eines Knotens einen Baum genauso aus dem Gleichgewicht bringen wie das Löschen. Es sind die Randfälle, die die Schwierigkeiten verursachen, auf die sich brito bezieht, wo Fragmentierung keine Rolle spielt.
outis
12
Ich bin nicht einverstanden, dass Einfügungen und Löschungen sich in der Vorhersagbarkeit unterscheiden. Das "Patchen um" eines Listenknotens ist genau das Gegenteil, wenn stattdessen derselbe Knoten eingefügt werden soll. Es gibt in keiner Richtung eine Ungewissheit, und in jedem Container ohne eigene Struktur für seine Elemente (z. B. ein ausgeglichener Binärbaum, ein Array mit einer strengen Beziehung zwischen Elementversätzen) gibt es überhaupt keine "Lücke". Aus diesem Grund weiß ich leider nicht, wovon Sie hier sprechen.
sqykly
2
Sehr interessant, aber ich würde sagen, Argumente fehlen. Sie können Datenstrukturen um einfaches / schnelles Löschen problemlos organisieren. Es ist nur weniger verbreitet, wahrscheinlich auch weniger nützlich.
Luk32
@sqykly Ich denke, die Liste war ein schlechtes Beispiel, weil die mittlere Einfügung und die mittlere Beziehung gleichermaßen schwierig sind. In einem Fall wird Speicher zugewiesen, in dem der andere neu zugewiesen wird. Einer öffnet ein Loch, während der andere ein Loch verschließt. Daher ist das Löschen nicht in allen Fällen komplexer als das Hinzufügen.
Ydobonebi
36

Warum ist das Löschen in der Regel schwieriger als das Einfügen? Datenstrukturen werden eher mit dem Gedanken an das Einfügen als an das Löschen entworfen, und das zu Recht.

Bedenken Sie Folgendes: Um etwas aus einer Datenstruktur zu löschen, muss es an erster Stelle vorhanden sein. Sie müssen es also zuerst hinzufügen, was bedeutet, dass Sie höchstens so viele Löschungen haben, wie Sie Einfügungen haben. Wenn Sie eine Datenstruktur für das Einfügen optimieren, erhalten Sie garantiert mindestens den gleichen Nutzen, als wäre sie für das Löschen optimiert worden.

Was nützt es außerdem, jedes Element nacheinander zu löschen? Warum nicht einfach eine Funktion aufrufen, die alles auf einmal löscht (möglicherweise indem Sie einfach eine neue erstellen)? Datenstrukturen sind auch dann am nützlichsten, wenn sie tatsächlich etwas enthalten. Der Fall, dass so viele Deletionen wie Insertionen vorliegen, wird in der Praxis nicht sehr häufig sein.

Wenn Sie etwas optimieren, möchten Sie die Dinge optimieren, die es am meisten tut und die die meiste Zeit in Anspruch nehmen. Im normalen Gebrauch kommt das Löschen von Elementen einer Datenstruktur seltener vor als das Einfügen.

Rob Watts
quelle
4
Es gibt einen Anwendungsfall, den ich mir vorstellen kann. Eine Datenstruktur, die zum erstmaligen Einfügen und dann zum individuellen Verbrauch vorbereitet wird. Natürlich ist dies selten der Fall und algorithmisch nicht sehr interessant, da, wie Sie sagten, eine solche Operation das Einfügen nicht asymptotisch dominieren kann. Vielleicht besteht in der Tat die Hoffnung, dass sich die Amortisation des Batch-Einfügens zu einem guten Preis auswirkt und das Löschen schnell und einfach vonstatten geht. Es hätte also komplizierte, aber praktische Batch-Einfügungen und einfache und schnelle Einzellöschungen zur Folge gehabt. Mit Sicherheit ein sehr ungewöhnliches praktisches Bedürfnis.
Luk32
1
Ummm, ich denke, ein Beispiel könnte ein umgekehrt geordneter Vektor sein. Sie können kziemlich schnell eine Reihe von Elementen hinzufügen : Sortiereingabe umkehren und mit vorhandenem Vektor zusammenführen - O(k log k + n). Dann haben Sie eine Struktur mit ziemlich kompliziertem Einfügen, aber das Aufwenden von oberen uElementen ist trivial und schnell. Nehmen Sie einfach das letzte uund verschieben Sie das Ende des Vektors. Aber wenn jemand so etwas braucht, werde ich verdammt sein. Ich hoffe, das stärkt zumindest Ihre Argumentation.
Luk32
Sollten Sie nicht lieber für das durchschnittliche Nutzungsmuster optimieren wollen, als was Sie am meisten tun?
Shiv
Eine einfache FIFO-Warteschlange versucht in der Regel, die meiste Zeit leer zu sein. Eine gut gestaltete Warteschlange ist sowohl für Einfügungen als auch für Löschvorgänge gut optimiert (dh O (1)) (und eine sehr gute Warteschlange unterstützt auch schnelle gleichzeitige Vorgänge, aber das ist ein anderes Problem).
Kevin
6

Es ist nicht schwerer.

Bei doppelt verknüpften Listen ordnen Sie beim Einfügen Speicher zu und verknüpfen dann entweder mit dem Kopf oder dem vorherigen Knoten und entweder mit dem Ende oder dem nächsten Knoten. Wenn Sie löschen, wird die Verknüpfung zu genau derselben Person aufgehoben und Speicher freigegeben. Alle diese Operationen sind symmetrisch.

Dies setzt voraus, dass Sie in beiden Fällen den Knoten zum Einfügen / Löschen haben. (Und im Falle des Einfügens, dass Sie auch den Knoten vor dem Einfügen haben, könnte das Einfügen in gewisser Weise als etwas komplizierter angesehen werden.) Wenn Sie versuchen, zu löschen, müssen Sie nicht den Knoten löschen, sondern die Nutzdaten des Knotens müssen Sie dann natürlich zuerst die Liste nach der Nutzlast durchsuchen, aber das ist kein Mangel an Löschung, oder?

Bei ausgeglichenen Bäumen gilt dasselbe: Ein Baum muss in der Regel unmittelbar nach dem Einfügen und auch unmittelbar nach dem Löschen ausgeglichen werden. Es empfiehlt sich, nur eine Auswuchtroutine zu verwenden und diese nach jedem Vorgang anzuwenden, unabhängig davon, ob es sich um eine Einfügung oder eine Löschung handelt. Wenn Sie versuchen, eine Einfügung zu implementieren, bei der der Baum immer im Gleichgewicht bleibt, und eine Löschung, bei der der Baum immer im Gleichgewicht bleibt, ohne dass beide dieselbe Abgleichsroutine verwenden, verkomplizieren Sie unnötigerweise Ihr Leben.

Kurz gesagt, es gibt keinen Grund, warum das eine schwerer sein sollte als das andere, und wenn Sie dies feststellen, ist es in der Tat möglich, dass Sie der (sehr menschlichen) Tendenz zum natürlichen Denken zum Opfer fallen Konstruktiv als subtraktiv, was bedeutet, dass Sie das Löschen möglicherweise komplizierter implementieren, als es sein muss. Aber das ist ein menschliches Problem. Aus mathematischer Sicht gibt es kein Problem.

Mike Nakis
quelle
1
Ich muss nicht zustimmen. Der AVL-Löschalgorithmus ist komplexer als das Einfügen. Für bestimmte Knotenlöschvorgänge müssen Sie möglicherweise den gesamten Baum neu verteilen. Dies erfolgt normalerweise rekursiv, kann aber auch nicht rekursiv erfolgen. Sie müssen dies nicht für das Einfügen tun. Ich kenne keine Algorithmusverbesserungen, bei denen eine solche Neuverteilung des gesamten Baums in allen Fällen vermieden werden kann.
Dennis
@Dennis: Es könnte sein, dass AVL-Bäume eher der Ausnahme als der Regel folgen.
outis
@outis IIRC, alle ausgeglichenen Suchbäume haben kompliziertere Löschroutinen (als das Einfügen).
Raphael
Was ist mit geschlossenen Hash-Tabellen? Das Einfügen ist (relativ) unkompliziert, das Löschen ist zumindest schwieriger zu konzipieren, da Sie das Problem beheben müssen, dass "das, was eigentlich im Index X enthalten sein sollte, sich derzeit im Index Y befindet und wir es suchen und zurücksetzen müssen". Probleme.
Kevin
3

Beachten Sie, dass die Einfüge- und Löschoperationen in Bezug auf die Laufzeit im Vergleich zur Zeitkomplexität der Datenstrukturoperationen in Wikipedia dieselbe Komplexität aufweisen. Die dort hinterlegte Löschoperation ist Löschen nach Index, wobei Sie einen Verweis auf das zu löschende Strukturelement haben; Das Einfügen erfolgt nach Artikel. Die längere Laufzeit für das Löschen in der Praxis liegt darin, dass Sie normalerweise ein Element löschen müssen und nicht dessen Index, sodass Sie auch eine Suchoperation benötigen. Die meisten Datenstrukturen in der Tabelle erfordern keine zusätzliche Suche für eine Einfügung, da die Platzierungsposition nicht vom Element abhängt oder die Position implizit während der Einfügung bestimmt wird.

In Bezug auf die kognitive Komplexität gibt es eine Antwort auf die Frage: Randfälle. Das Löschen kann mehr von ihnen als das Einfügen haben (dies muss im allgemeinen Fall noch festgestellt werden). Zumindest einige dieser Randfälle können jedoch in bestimmten Designs vermieden werden (z. B. mit einem Sentinel-Knoten in einer verknüpften Liste).

outis
quelle
2
"Die meisten Datenstrukturen erfordern keine Suche für eine Einfügung." -- sowie? Ich würde sogar das Gegenteil behaupten. (Sie "finden" die Einfügeposition, die genauso teuer ist, wie dasselbe Element später wieder zu finden.)
Raphael
@Raphael: Diese Antwort sollte im Zusammenhang mit der verknüpften Tabelle der Operationskomplexitäten gelesen werden, in der die Suchoperation nicht als Teil des Löschvorgangs enthalten ist. Als Antwort auf Ihre Frage kategorisierte ich die Struktur nach dem gebräuchlichen Namen. Von Arrays, Listen, Bäumen, Hash-Tabellen, Stapeln, Warteschlangen, Heaps und Mengen erfordern Bäume und Mengen einen Fund für eine Einfügung. Die anderen verwenden einen Index, der nicht mit dem Element verbunden ist (bei einfachen Stapeln, Warteschlangen und Haufen wird nur 1 Index angezeigt und die Suche wird nicht unterstützt), oder berechnen ihn anhand des Elements. Diagramme können in beide Richtungen verlaufen, je nachdem, wie sie verwendet werden.
outis
... Versuche könnten als Bäume betrachtet werden; Wenn sie jedoch als ihre eigene Struktur klassifiziert werden, ist es eher umstritten, ob es beim Einfügen einen "Fund" gibt, weshalb ich ihn nicht einbeziehe. Beachten Sie, dass die Datenstrukturliste die Schnittstelle gegenüber der Implementierung nicht berücksichtigt. Wie Sie zählen, hängt auch stark von Ihrer Kategorisierung ab. Ich werde sehen, ob mir eine objektivere Aussage einfällt.
outis
Ich gebe zu, ich hatte das Dictionary / Set-Interface im Sinn (wie in CS üblich). Wie auch immer, diese Tabelle ist irreführend und an mehreren Stellen sogar falsch - Wikipedia, die Grube der CS-Fehlinformation. : /
Raphael
0

Zu allen genannten Problemen kommt noch die referenzielle Datenintegrität hinzu. Für die Erstellung einer Datenstruktur wie Datenbanken in SQL ist die referenzielle Integrität von Oracle sehr wichtig.
Um sicherzustellen, dass Sie es nicht versehentlich zerstören, wurden viele verschiedene Dinge erfunden.
Zum Beispiel Kaskade beim Löschen, die nicht nur löscht, was auch immer Sie versuchen, zu löschen, sondern auch die Bereinigung von verwandten Daten auslöst.
Diese bereinigen Datenbank von Junk-Daten sowie Integrität der Daten intakt zu halten.
Zum Beispiel haben Sie Tabellen mit Eltern und Arten als zugehörige Datensätze in der zweiten Tabelle.
Wo Eltern ist Haupttabelle. Wenn Sie keine verstärkte referenzielle Integrität haben, können Sie alle Datensätze in jeder Tabelle löschen, und später wissen Sie nicht, wie Sie die vollständigen Familieninformationen abrufen können, da Sie Daten in der untergeordneten Tabelle und nichts in der übergeordneten Tabelle haben.
Aus diesem Grund können Sie bei der Überprüfung der referenziellen Integrität keine Datensätze aus der übergeordneten Tabelle löschen, bis die Datensätze aus der untergeordneten Tabelle bereinigt wurden.
Aus diesem Grund ist es in den meisten Datenquellen schwieriger, Daten zu löschen.

Alex
quelle
Ich denke, die Frage bezog sich eher auf speicherinterne Strukturen wie verknüpfte Listen, Hash-Tabellen usw. als auf Datenbanken, aber die referenzielle Integrität ist selbst bei speicherinternen Strukturen ein großes Problem.
Supercat