Was ist der beste Sortieralgorithmus für die kontinuierliche (NICHT FIXED) Eingabe von Zufallszahlen?

Question

Angenommen, ich ein System, das einen nach dem anderen als eine Eingabe kontinuierlich Zufallszahlen die ganze Zeit,

(0,5,2,10,6,20......) erhält

Mein Ziel sie mit der besten Leistung zu sortieren ist.

So wird die Ausgabegröße nach jeder Iteration erhöht und die Eingabe ist sequentiell.

Ich dachte, entweder Insertionsort oder BST zu verwenden, aber ich weiß nicht, was für dieses Problem besser ist, wie ich weiß, Sort Einsetzen O(n-n^2) und BST Insertion ist O(log(n))

Bitte, irgendwelche Vorschläge?

Answer 1

Wenn Sie jedes Mal sortieren müssen, wenn ein Element hinzugefügt wird, ist dies kein Sortierproblem, sondern ein Einfügungsproblem. Jeder Sortieralgorithmus wird übertrieben sein.

Wenn Ihre Daten in einem Array gespeichert werden müssen, können Sie die Elemente nicht verschieben und die Lösung ist Ω (N). Dies wird effizient durch geradliniges Einfügen erreicht (O (N)). (Dichotomische Suche gefolgt von Einfügung wird weniger Vergleiche, aber es ist nicht sicher, dass Sie einen Unterschied feststellen werden.)

Wenn Sie mehr Freiheit haben, ist eine BST in der Tat eine effizientere Lösung. Wenn Sie eine absolute Garantie auf die Worst-Case-Kosten (O (Log N)) benötigen, muss die BST ausgeglichen sein (also AVL, Rot-Schwarz ... ganz nach Ihrem Geschmack). Wenn Ihre Daten ausreichend zufällig sind, könnte dies unnötig sein.

Wenn Ihre Daten spezielle Eigenschaften haben (z. B. kleiner diskreter Bereich), können Ad-hoc-Lösungen eingesetzt werden. In dem gegebenen Beispiel wird ein einfaches Zählhistogramm eine 0 (1) Aktualisierungszeit erreichen.

Answer 2

Einfügesortierung ist effizient bei kleinen Eingaben (weniger als 1000), da die Laufzeit von O (n^2) sehr schnell zunimmt, wenn Sie nicht sicher sind, wie groß Ihre Eingabe sein würde Verwenden Sie dann Quick Sort oder Heap Sort, die eine Laufzeit von O (nlogn) haben, die viel schneller ist als O (n^2).

Answer 3

Es hängt davon ab, wie Sie das Ergebnis verwenden möchten.

Zum Beispiel: Wenn Sie viele Zahlen eingeben und BST zum Speichern verwenden, benötigen Sie mehr als 1000 Schritte, um den Index 1000 zu finden. Wenn Sie das sortierte Ergebnis in einem Array speichern, brauchen Sie nur 1 Schritt (Rückkehrindex [1000]).

Wenn Sie nur die höchste oder niedrigste Nummer benötigen, löschen Sie sie aus Ihrer Liste. Danach brauchst du die nächst höhere oder niedrigste Zahl, mit einem Heap bist du viel schneller.

Denken Sie auch daran, wenn die Zufallszahlen irgendwie sortiert sind, sieht die BST wie eine Liste aus und Sie haben dann kein O (log n), sondern O (n) zum Einfügen.

Es gibt eine Menge mehr Dinge, über die Sie nachdenken müssen. Also bitte sagen Sie uns, wofür Sie diese benötigen

Answer 4

Ich denke, dass mit einigen BST, die O(log n) performacne verspricht (wie AVL, schwarz-rot, etc.) ist Ihre beste Option.

Das Ausdrucken der aktuellen Daten erfolgt mithilfe einer Intra-order-Traversierung des Baums.

Answer 5

Es gibt mehrere Faktoren, die die Effizienz Ihrer Lösung wiegen:

• Anzahl liest die Einfügemarke
• Anzahl von Schreibvorgängen zu finden (zB Verschiebungen, Neuverteilung) Einfügen
• Gesamtspeicher/Lokalität (beeinflusst Cache-Misses) Die Größe der Konstante (K) ist relevant, da sie beeinflusst, wie viele Elemente in jede Cache-Ebene passen.
• Verzweigungsvorhersage verfehlt

Beachten Sie, dass diese mehr auf der Grundlage der Datenstruktur als der Algorithmus variieren, die zu sein eine Variante der Insertionsort immer scheint, da Sie mit jedem Element hinaus greifen

Data Structure | READS | WRITES | Memory  | locality | Branches 
---------------|--------|--------|------------|----------|--------- 
Sorted Vector |O(logN) | O(N) | O(N)  | high  | high (FFTFFT) 
Linked List |O(N) | O(1) | O(K*N)  | low  | low (FFFFFFFFFFT) 
Red Black Tree |O(logN) | O(K) | O(K*NlogN) | low  | high (FFTFFT) 
Btree 16 node |O(logN) | O(16) | O(NlogN) | medium | medium (FFTF) 

* K bedeutet eine deutlich höhere Konstante als andere Lösungen mit gleichem O()

Die optimale Lösung kann je nach der aktuellen Architektur variieren Einschränkungen. Wenn die Speicher-/Cachegrößen klein sind, ist ein sortierter Vektor wahrscheinlich optimal. Wenn Zweig Misses eine verkettete Liste teuer sind, werden wahrscheinlich optimal sein als Zweige mit Ausnahme der letzten alle falsch sein

Aber es scheint, wenn Sie einen Btree mit einer großen Anzahl von Knoten verwenden P Sie den Ort und Speicher gewinnen Effizienz eines Vektors, haben die indexierte O (logN) READ-Geschwindigkeit und werden die Anzahl der WRITES auf 0 (P) nicht O (N) begrenzen. Ich würde mit P von 16, beginnen und dann binäre Suche verwenden, um P zu optimieren,

Leider ist die wirkliche Antwort ist, versuchen sie alle und Benchmark mit Ihren Anwendungsfall

Answer 6

Die ursprüngliche Frage macht es nicht klar, wie Oft müssen Daten abgerufen werden, während sie Zahlen empfängt, oder wie die Zahlen abgerufen werden sollen (nach Index, nur der kleinste, nur der größte oder alle, ...).

Eine Option besteht darin, die Logik für eine Bottom-Up-Merge-Sortierung für verknüpfte Listen zu verwenden, die ein kleines Array von Referenzen oder Zeigern (26 bis 32 Elemente) verwendet, die jeweils auf eine Liste verweisen. Array [i] ist eine Referenz oder ein Zeiger auf eine Liste mit (2 zu den Power-I) Knoten, Array [0] Punkte zu einer Liste der Größe 1, Array [1] -> Liste der Größe 2, Array [2] -> Liste der Größe 4, wobei das letzte Mitglied des Arrays auf eine unbegrenzte Liste zeigt. Knoten werden nacheinander in das Array eingefügt, was dem Empfangen von Zahlen nacheinander entspricht.

Das Problem ist, dass die Daten in Array von Listen gespeichert werden, also nur teilweise sortiert. Um eine vollständig sortierte Liste zu erhalten, wird das Array von Listen in einer einzigen Liste zusammengeführt. Normalerweise wird dies erst durchgeführt, nachdem alle Daten im Array gespeichert wurden.

Wiki Artikel für bottom up merge sort auf verkettete Listen:

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Diese Methode bietet eine schnelle durchschnittliche Einfügungszeit, mit gelegentlichen langen Zeiten. Jede andere Zahl wird nur in Array [0] gespeichert. Eingaben an der Leistung von 2 Grenzen beinhalten mehrere Zusammenführungsschritte, die 16. Eingabe endet am Zusammenführen von zwei Listen von 8 Zahlen, die 1024. Eingabe endet beim Zusammenführen von zwei Listen von 512 Nummern.

Wie bereits erwähnt, eine binäre Suchbaum (gelegentlich neu ausbalanciert), kann eine bessere Lösung sein.