Algorithmen zum Teilen und Erobern - Warum nicht in mehr als zwei Teile teilen?

Bei Divide- und Conquer-Algorithmen wie QuickSort und Mergesort wird die Eingabe normalerweise (zumindest in einleitenden Texten) in zwei Teile geteilt , und die beiden kleineren Datensätze werden dann rekursiv behandelt. Für mich macht es Sinn, dass die Lösung eines Problems dadurch schneller vonstatten geht, wenn die beiden Hälften weniger als die Hälfte der Arbeit für die Bearbeitung des gesamten Datensatzes in Anspruch nehmen. Aber warum nicht den Datensatz in drei Teile aufteilen? Vier? n ?

Ich denke, die Arbeit, die Daten in viele, viele Untergruppen aufzuteilen, macht es nicht wert, aber mir fehlt die Intuition, zu sehen, dass man bei zwei Untergruppen aufhören sollte.

Ich habe auch viele Hinweise auf 3-Wege-Quicksort gesehen. Wann ist das schneller? Was wird in der Praxis angewendet?

Für mich macht es Sinn, dass die Lösung eines Problems dadurch schneller vonstatten geht, wenn die beiden Hälften weniger als die Hälfte der Arbeit für die Bearbeitung des gesamten Datensatzes in Anspruch nehmen.

Das ist nicht die Essenz von Divide-and-Conquer-Algorithmen. Normalerweise ist der Punkt, dass die Algorithmen überhaupt nicht "mit dem gesamten Datensatz umgehen" können. Stattdessen wird es in Teile unterteilt, die trivial zu lösen sind (wie das Sortieren von zwei Zahlen), dann werden diese trivial gelöst und die Ergebnisse so rekombiniert, dass sich eine Lösung für den gesamten Datensatz ergibt.

Aber warum nicht den Datensatz in drei Teile aufteilen? Vier? n?

Hauptsächlich, weil das Aufteilen in mehr als zwei Teile und das erneute Kombinieren von mehr als zwei Ergebnissen zu einer komplexeren Implementierung führt, die grundlegende (Big O) -Charakteristik des Algorithmus jedoch nicht ändert - der Unterschied ist ein konstanter Faktor und kann zu einer Verlangsamung führen wenn die Aufteilung und Rekombination von mehr als 2 Teilmengen zusätzlichen Overhead erzeugt.

Wenn Sie beispielsweise eine 3-Wege-Zusammenführungssortierung durchführen, müssen Sie in der Rekombinationsphase für jedes Element das größte von 3 Elementen ermitteln. Dies erfordert 2 Vergleiche anstelle von 1, sodass Sie insgesamt doppelt so viele Vergleiche durchführen . Im Gegenzug reduzieren Sie die Rekursionstiefe um den Faktor ln (2) / ln (3) == 0,63, sodass Sie 37% weniger Swaps haben, aber 2 * 0,63 == 26% mehr Vergleiche (und Speicherzugriffe). Ob das gut oder schlecht ist, hängt davon ab, welche Hardware teurer ist.

Ich habe auch viele Hinweise auf 3-Wege-Quicksort gesehen. Wann ist das schneller?

Anscheinend erfordert eine Dual-Pivot-Variante von Quicksort nachweislich die gleiche Anzahl von Vergleichen, aber im Durchschnitt 20% weniger Swaps, was einen Nettogewinn bedeutet.

Was wird in der Praxis angewendet?

Heutzutage programmiert kaum jemand mehr seine eigenen Sortieralgorithmen. Sie verwenden eine, die von einer Bibliothek bereitgestellt wird. Beispielsweise verwendet die Java 7-API tatsächlich die Dual-Pivot-QuickSort-Funktion.

Leute, die aus irgendeinem Grund tatsächlich ihren eigenen Sortieralgorithmus programmieren, werden sich eher an die einfache 2-Wege-Variante halten, da weniger Fehlerpotential die meiste Zeit 20% bessere Leistung übertrifft. Denken Sie daran: Die mit Abstand wichtigste Leistungsverbesserung ist, wenn der Code von "nicht funktioniert" zu "funktioniert" wechselt.

Asymptotisch gesehen spielt es keine Rolle. Beispielsweise führt die binäre Suche ungefähr log ₂  n Vergleiche durch, und die ternäre Suche führt ungefähr log ₃  n Vergleiche durch. Wenn Sie Ihre Logarithmen kennen, wissen Sie, dass log _a  x = log _b  x / log _b  a ist, sodass die binäre Suche nur ungefähr 1 / log ₃ ergibt 2 ≈ 1,5-mal so viele Vergleiche wie bei der ternären Suche. Dies ist auch der Grund, warum niemand die Basis des Logarithmus in der großen Oh-Notation angibt: Es ist immer ein konstanter Faktor, der vom Logarithmus in einer gegebenen Basis abweicht, unabhängig davon, was die tatsächliche Basis ist. Eine Aufteilung des Problems in mehrere Teilmengen führt also nicht zu einer Verbesserung der Zeitkomplexität und ist praktisch nicht ausreichend, um die komplexere Logik aufzuwiegen. Tatsächlich kann diese Komplexität die praktische Leistung negativ beeinflussen, den Cache-Druck erhöhen oder Mikrooptimierungen weniger unmöglich machen.

Auf der anderen Seite verwenden einige baumartige Datenstrukturen einen hohen Verzweigungsfaktor (viel größer als 3, oft 32 oder mehr), jedoch normalerweise aus anderen Gründen. Es verbessert die Auslastung der Speicherhierarchie: Datenstrukturen, die im RAM gespeichert sind, nutzen den Cache besser aus, Datenstrukturen, die auf der Festplatte gespeichert sind, erfordern weniger Lesevorgänge für HDD-> RAM.

Es gibt Such- / Sortieralgorithmen, die nicht nach zwei, sondern nach N. unterteilen.

Ein einfaches Beispiel ist die Suche durch Hash-Codierung, die O (1) -Zeit benötigt.

Wenn die Hash-Funktion die Reihenfolge beibehält, kann sie verwendet werden, um einen O (N) -Sortieralgorithmus zu erstellen. (Sie können sich jeden Sortieralgorithmus so vorstellen, dass Sie nur N Suchvorgänge ausführen, um herauszufinden, wo eine Zahl im Ergebnis stehen soll.)

Das grundlegende Problem ist, wenn ein Programm einige Daten untersucht und dann in folgende Zustände wechselt, wie viele folgende Zustände gibt es und wie nahe sind ihre Wahrscheinlichkeiten gleich?

Wenn ein Computer beispielsweise zwei Zahlen vergleicht und dann springt oder nicht, wenn beide Pfade gleich wahrscheinlich sind, "kennt" der Programmzähler ein Bit mehr Informationen zu jedem Pfad, sodass er im Durchschnitt einen "gelernt" hat Bit. Wenn ein Problem das Erlernen von M Bits erfordert, kann es mit binären Entscheidungen die Antwort nicht in weniger als M Entscheidungen erhalten. So kann beispielsweise das Nachschlagen einer Zahl in einer sortierten Tabelle der Größe 1024 nicht mit weniger als 10 binären Entscheidungen durchgeführt werden, schon weil weniger nicht genug Ergebnisse haben würden, aber es kann mit Sicherheit auch mit mehr getan werden.

Wenn ein Computer eine Zahl aufnimmt und sie in einen Index in ein Array umwandelt, "lernt" er, bis er die Basis 2 der Anzahl der Elemente im Array protokolliert, und dies in konstanter Zeit. Wenn es zum Beispiel eine Sprungtabelle mit 1024 Einträgen gibt, die alle mehr oder weniger gleich wahrscheinlich sind, dann "lernt" das Springen durch diese Tabelle 10 Bits. Das ist der grundlegende Trick hinter der Hash-Codierung. Ein Sortierbeispiel dafür ist, wie Sie ein Kartenspiel sortieren können. Habe 52 Fächer, eines für jede Karte. Werfen Sie jede Karte in den Papierkorb und schöpfen Sie sie dann alle auf. Keine Unterteilung erforderlich.

Da es sich hier nicht nur um das Sortieren, sondern um das Teilen und Erobern handelt, wundert es mich, dass niemand den Hauptsatz aufgegriffen hat

Kurz gesagt, die Laufzeit von Divisions- und Eroberungsalgorithmen wird durch zwei Verschleierungskräfte bestimmt: den Nutzen, den Sie daraus ziehen, größere Probleme in kleine Probleme umzuwandeln, und den Preis, den Sie dafür zahlen, wenn Sie mehr Probleme lösen müssen. Abhängig von den Details des Algorithmus kann es sich lohnen oder auch nicht, ein Problem in mehr als zwei Teile aufzuteilen. Wenn Sie in jedem Schritt in die gleiche Anzahl von Teilproblemen aufteilen und die zeitliche Komplexität der Kombination der Ergebnisse in jedem Schritt kennen, gibt Ihnen der Hauptsatz Auskunft über die zeitliche Komplexität des Gesamtalgorithmus.

Der Karatsuba- Algorithmus für die Multiplikation verwendet eine 3-Wege-Division und Eroberung, um eine Laufzeit von O (3 n ^ log_2 3) zu erreichen, die das O (n ^ 2) für den gewöhnlichen Multiplikationsalgorithmus übertrifft (n ist die Anzahl der Stellen in der Zahlen).

Aufgrund seiner binären Natur ist ein Computer sehr effizient darin, Dinge in 2 und nicht so sehr in 3 zu teilen. Sie erhalten eine Teilung in 3, indem Sie zuerst in 2 teilen und dann einen der Teile erneut in 2 teilen. Wenn Sie also teilen müssen, müssen Sie Durch 2 erhalten Sie Ihre 3 Division, Sie könnten genauso gut in 2 teilen.