Ist es schneller, eine Liste zu sortieren, nachdem Elemente eingefügt oder einer sortierten Liste hinzugefügt wurden?

72

Wenn ich eine sortierte Liste habe (z. B. Quicksortierung zum Sortieren), wenn ich viele Werte hinzufügen möchte, ist es besser, die Sortierung auszusetzen und sie am Ende hinzuzufügen, dann zu sortieren oder binär zu schneiden, um die Elemente währenddessen korrekt zu platzieren Hinzufügen. Macht es einen Unterschied, ob die Elemente zufällig sind oder bereits mehr oder weniger in der richtigen Reihenfolge?

Steve
quelle
Ist es ein Array oder eine verknüpfte Liste? Ich weiß, dass Sie 'Liste' gesagt haben, aber Sie haben erwähnt, dass Sie einen Binär-Chop ausführen, der ein Array impliziert.
Tag "Algorithmen" in "Algorithmus" geändert
Eric

Antworten:

36

Wenn Sie genügend Elemente hinzufügen, um die Liste effektiv von Grund auf neu zu erstellen, sollten Sie in der Lage sein, eine bessere Leistung zu erzielen, indem Sie die Liste anschließend sortieren.

Wenn die Elemente größtenteils in Ordnung sind, können Sie sowohl die inkrementelle Aktualisierung als auch die regelmäßige Sortierung optimieren, um dies zu nutzen, aber ehrlich gesagt ist es normalerweise nicht die Mühe wert. (Sie müssen auch auf Dinge achten, wie zum Beispiel sicherzustellen, dass eine unerwartete Reihenfolge Ihren Algorithmus nicht viel länger dauern lässt, siehe naive Quicksortierung)

Sowohl die inkrementelle Aktualisierung als auch die reguläre Listensortierung sind O (N log N), aber Sie können einen besseren konstanten Faktor erhalten, der danach alles sortiert (ich gehe hier davon aus, dass Sie über eine zusätzliche Datenstruktur verfügen, damit Ihre inkrementelle Aktualisierung schneller auf Listenelemente zugreifen kann als O. (N) ...). Im Allgemeinen hat das Sortieren auf einmal viel mehr Gestaltungsfreiheit als das schrittweise Beibehalten der Reihenfolge, da bei der inkrementellen Aktualisierung jederzeit eine vollständige Reihenfolge beibehalten werden muss, bei einer vollständigen Sortierung jedoch nicht.

Denken Sie nicht zuletzt daran, dass viele hochoptimierte Massensorten verfügbar sind.

kommender Sturm
quelle
21

Normalerweise ist es viel besser, einen Haufen zu verwenden . Kurz gesagt, es teilt die Kosten für die Aufrechterhaltung der Ordnung zwischen dem Drücker und dem Kommissionierer auf. Beide Operationen sind O (log n) anstelle von O (n log n), wie die meisten anderen Lösungen.

Javier
quelle
5
Dies ist besonders dann ein guter Rat, wenn es sich bei der Liste um eine Prioritätswarteschlange handelt. Google für schwache Haufen in diesem Fall.
Daniel Rikowski
10

Wenn Sie Bündel hinzufügen, können Sie eine Zusammenführungssortierung verwenden. Sortieren Sie die Liste der hinzuzufügenden Elemente, kopieren Sie sie aus beiden Listen und vergleichen Sie die Elemente, um festzustellen, welche als Nächstes kopiert werden. Sie können sogar direkt kopieren, wenn Sie die Größe Ihres Zielarrays ändern und von Ende an rückwärts arbeiten.

Die Effizienz dieser Lösung ist O (n + m) + O (m log m), wobei n die Größe der ursprünglichen Liste und m die Anzahl der eingefügten Elemente ist.

Bearbeiten: Da diese Antwort keine Liebe findet, dachte ich, ich würde sie mit etwas C ++ - Beispielcode ausarbeiten. Ich gehe davon aus, dass die sortierte Liste in einer verknüpften Liste und nicht in einem Array gespeichert ist. Dies ändert den Algorithmus so, dass er eher wie eine Einfügung als wie eine Zusammenführung aussieht, aber das Prinzip ist dasselbe.

// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
    std::sort(itemstoadd.begin(), itemstoadd.end());
    std::list<T>::iterator listposition = sortedlist.begin();
    std::vector<T>::iterator nextnewitem = itemstoadd.begin();
    while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
    {
        if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
            sortedlist.insert(listposition, *nextnewitem++);
        else
            ++listposition;
    }
}
Mark Ransom
quelle
O (n + m) + O (m log m) ist O (n + m)
Miles Rout
3
@ MilesRout, überhaupt nicht wahr. m log m > mDas Beste, was Sie vereinfachen können, ist O(n+(m log m)).
Mark Ransom
oops, habe das m vor dem log m nicht gesehen. ignoriere mich!
Miles Rout
4

Im Prinzip ist es schneller, einen Baum zu erstellen, als eine Liste zu sortieren. Die Baumeinfügungen sind O (log (n)) für jede Einfügung, was zu insgesamt O (n log (n)) führt. Sortieren in O (n log (n)).

Aus diesem Grund verfügt Java über TreeMap (zusätzlich zu den Implementierungen einer Liste durch TreeSet, TreeList, ArrayList und LinkedList).

  • Ein TreeSet hält die Dinge in der Reihenfolge des Objektvergleichs. Der Schlüssel wird von der Schnittstelle Comparable definiert.

  • Eine LinkedList hält die Dinge in der Einfügereihenfolge.

  • Eine ArrayList benötigt mehr Speicher und ist für einige Vorgänge schneller.

  • Eine TreeMap macht das Sortieren nach einem Schlüssel ebenfalls überflüssig. Die Karte wird während der Einfügungen in Schlüsselreihenfolge erstellt und jederzeit in sortierter Reihenfolge verwaltet.

Aus irgendeinem Grund ist die Java-Implementierung von TreeSet jedoch etwas langsamer als die Verwendung einer ArrayList und einer Sortierung.

[Es ist schwer zu spekulieren, warum es dramatisch langsamer sein würde, aber es ist. Es sollte durch einen Durchgang durch die Daten etwas schneller sein. Diese Art von Dingen sind oft die Kosten für die Speicherverwaltung, die die algorithmische Analyse übertreffen.]

S.Lott
quelle
2
Ich würde vorsichtig sagen, dass ein Baum schneller ist als eine Liste. Dies hängt wirklich von der Größe der Eingabe und der verwendeten Baumimplementierung ab.
Hazzen
2
Führen Sie einige Geschwindigkeitstests durch, und Sie werden feststellen, dass dies nicht der Fall ist. TreeSet vs. ArrayList, ArrayList war ~ 2x schneller, um 500.000 Zufallszahlen hinzuzufügen, zu sortieren und in eine andere Liste zu kopieren. Wenn wir sie nicht auf einer anderen Liste ablegen, gewinnt ArrayList mit ~ 1,6x.
Hazzen
TreeSet und TreeMap sind im Wesentlichen dieselbe Klasse. Ein TreeSet <E> ist eine TreeMap <E, Object>, deren Wert beim Einfügen auf ein Singleton-Objekt festgelegt wird. Die Zeiten sind fast identisch und immer noch ~ 2x langsamer als bei einer ArrayList-Lösung.
Hazzen
Ich sagte, dass das Einfügen aller Elemente in eine ArrayList + Collections.sort etwa doppelt so schnell ist wie das Einfügen aller Elemente in einen Baum [Set | Map]. Dies gilt für eine große Anzahl von Werten. Der Unterschied beträgt bei einer kleinen Anzahl von Werten immer noch ungefähr 2x, aber 1 ms gegenüber 2 ms spielt keine Rolle.
Hazzen
Der Grund für den Geschwindigkeitsunterschied besteht darin, dass ArrayList mit einem einzelnen Array implementiert wird, während die Baumzuordnung eine verknüpfte Struktur mit unterschiedlichen Knotenobjekten für jeden Eintrag ist. Der Zugriff auf Arrays ist viel schneller und die JVM kann besser optimieren als Objekte (Wiederverwendungsregister, bessere Cache-Lokalität)
ddimitrov
4

Ich würde sagen, lass es uns testen! :) :)

Ich habe es mit Quicksort versucht, aber das Sortieren eines fast sortierenden Arrays mit Quicksort ist ... na ja, keine wirklich gute Idee. Ich habe einen modifizierten ausprobiert, bei 7 Elementen abgeschnitten und dafür die Einfügesortierung verwendet. Trotzdem schreckliche Leistung. Ich wechselte zu Sortieren zusammenführen. Es benötigt möglicherweise ziemlich viel Speicher zum Sortieren (es ist nicht vorhanden), aber die Leistung ist bei sortierten Arrays viel besser und bei zufälligen fast identisch (die anfängliche Sortierung dauerte für beide fast gleich lange, Quicksort war nur geringfügig schneller ).

Dies zeigt bereits eines: Die Antwort auf Ihre Fragen hängt stark vom verwendeten Sortieralgorithmus ab. Wenn die Leistung bei fast sortierten Listen schlecht ist, ist das Einfügen an der richtigen Position viel schneller als das Hinzufügen am Ende und das anschließende erneute Sortieren. und Sortieren zusammenführen ist möglicherweise keine Option für Sie, da es bei umfangreicher Liste möglicherweise viel zu viel externen Speicher benötigt. Übrigens habe ich eine benutzerdefinierte Merge-Sort-Implementierung verwendet, die nur die Hälfte des externen Speichers für die naive Implementierung verwendet (die so viel externen Speicher benötigt wie die Array-Größe selbst).

Wenn die Zusammenführungssortierung keine Option und die Quicksortierung keine Option ist, ist die Heap-Sortierung wahrscheinlich die beste Alternative.

Meine Ergebnisse sind: Das Hinzufügen der neuen Elemente einfach am Ende und das anschließende erneute Sortieren des Arrays war mehrere Größenordnungen schneller als das Einfügen an der richtigen Position. Mein ursprüngliches Array hatte jedoch 10 Millionen Elemente (sortiert) und ich fügte ein weiteres Millionen hinzu (unsortiert). Wenn Sie also 10 Elemente zu einem Array von 10 Millionen hinzufügen, ist das korrekte Einfügen viel schneller als das erneute Sortieren aller Elemente. Die Antwort auf Ihre Frage hängt also auch davon ab, wie groß das anfängliche (sortierte) Array ist und wie viele neue Elemente Sie hinzufügen möchten.

Mecki
quelle
1

Wenn die Liste a) bereits sortiert und b) dynamisch ist, sollte das Einfügen in eine sortierte Liste immer schneller erfolgen (finden Sie die richtige Stelle (O (n)) und fügen Sie sie ein (O (1))).

Wenn die Liste jedoch statisch ist, muss der Rest der Liste gemischt werden (O (n), um den richtigen Ort zu finden, und O (n), um die Dinge nach unten zu schieben).

In beiden Fällen sollte das Einfügen in eine sortierte Liste (oder in einen binären Suchbaum) schneller sein.

O (n) + O (n) sollte immer schneller sein als O (N log n).

Labyrinth
quelle
Die Einfügung in einem dynamischen Konstrukt wie einer verknüpften Liste ist immer noch O (1) pro Einfügung . Also ja, insgesamt ergibt das ein O (N) - aber es ist nicht multiplikativ, es ist additiv (dh 2 mal O (n), nicht O (n ^ 2)).
Warren
Das Einfügen sollte O (log (N)) sein, wenn Sie es richtig machen und relativ gleichmäßig verteilte Daten haben
tloach
Ihr erster Absatz beschreibt eine einzelne Zusammenführung von zwei sortierten verknüpften Listen. Wenn eine Zusammenführung O (N) ist, ist Ihre Gesamtsortierung O (NlogN), es sei denn, Sie können irgendwie eine O (1) Anzahl sortierter Blöcke in weniger als O (NlogN) erhalten. Die inkrementelle Sortierung durch Einfügen jedes Elements in einen binären Suchbaum ist O (N log N), da die Einfügeoperation O (logN) ist und Sie dies N-mal tun müssen. (Einfache Binärbäume haben eine O (N) Worst-Case-Einfügung für ein Element.) Wie auch immer, die letzten beiden Absätze sind Unsinn. Keines davon hilft Ihnen, O (NlogN) oder sogar qsort zu schlagen.
Peter Cordes
@ PeterCordes- Ich beschreibe überhaupt keine Zusammenführung von zwei sortierten Listen: Ich beschreibe das Hinzufügen von Elementen einer unbekannten sortierten Reihenfolge zu einer bereits sortierten Liste
Warren
1

Es ist ungefähr das gleiche. Das Einfügen eines Elements in eine sortierte Liste ist O (log N). Wenn Sie dies für jedes Element in der Liste tun, ist N (wodurch die Liste erstellt wird) O (N log N). Dies ist die Geschwindigkeit der Quicksortierung (oder Zusammenführungssortierung) was diesem Ansatz näher kommt).

Wenn Sie sie stattdessen auf der Vorderseite einfügen würden, wäre es O (1), aber wenn Sie danach eine Quicksortierung durchführen, wäre es immer noch O (N log N).

Ich würde mit dem ersten Ansatz gehen, weil es das Potenzial hat, etwas schneller zu sein. Wenn die anfängliche Größe Ihrer Liste N viel größer ist als die Anzahl der einzufügenden Elemente X, lautet der Einfüge-Ansatz O (X log N). Nach dem Einfügen in den Kopf der Liste wird nach O (N log N) sortiert. Wenn N = 0 (IE: Ihre Liste ist anfangs leer), ist die Geschwindigkeit des Einfügens in sortierter Reihenfolge oder der anschließenden Sortierung gleich.

bmdhacks
quelle
Nicht wählerisch zu sein, aber N ist die Anzahl der Elemente, die eingefügt werden müssen. Der letzte Absatz Ihrer Antwort macht für mich also keinen allzu großen Sinn! Meinten Sie "wenn N nicht zu groß ist"?
Remo.D
Nach dem Kommentar von Remo.D zur Verdeutlichung bearbeitet.
BMDHacks
Absatz 2 ist in einigen Fällen falsch. Eine schnelle Sortierung in einer fast sortierten Liste nähert sich eher O (n ^ 2) als O (n log n).
Tony BenBrahim
0

(Wenn die Liste, über die Sie sprechen, wie C # ist List<T>.) Das Hinzufügen einiger Werte zu richtigen Positionen zu einer sortierten Liste mit vielen Werten erfordert weniger Operationen. Wenn jedoch die Anzahl der hinzugefügten Werte groß wird, ist mehr erforderlich.

Ich würde vorschlagen, in Ihrem Fall keine Liste, sondern eine geeignetere Datenstruktur zu verwenden. Zum Beispiel wie ein Binärbaum. Eine sortierte Datenstruktur mit minimaler Einfügezeit.

Ihar Bury
quelle
0

Das Einfügen eines Elements in eine sortierte Liste benötigt O(n)Zeit, nicht O(log n)Zeit. Sie müssen den Platz finden, um es zu platzieren, und sich O(log n)Zeit nehmen. Aber dann muss man alle Elemente verschieben - sich O(n)Zeit nehmen. Das Einfügen unter Beibehaltung der Sortierung ist also O(n ^ 2)das Einfügen aller und das anschließende Sortieren O(n log n).

Abhängig von Ihrer Sortierimplementierung können Sie sogar noch besser werden, als O(n log n)wenn die Anzahl der Einfügungen viel kleiner als die Listengröße ist. Aber wenn das der Fall ist, spielt es keine Rolle.

Machen Sie also die Insert All- und Sortierlösung, wenn die Anzahl der Inserts groß ist, sonst spielt es wahrscheinlich keine Rolle.

Hazzen
quelle
Ich denke, Sie haben eine völlig falsche Sicht auf die O-Notation. Das Einfügen eines Elements in eine Liste ist nicht O (n), sondern im Algorithmus-Theorem immer O (1). Das Verschieben von Millionen von Bytes im Speicher ist möglicherweise keine konstante Operation, aber bei der O-Notation geht es nicht um die Zeit, die benötigt wird, sondern um die Komplexität, die 1
Mecki
Wenn es sich nicht um eine konstante Operation handelt, ist es nicht O (1). Zeitraum. Der Code zum Einfügen in eine Liste lautet (für Array-basierte Liste): for (i = last; i> idx; --i) {list [i + 1] = list [i]; } list [idx] = item; Ich glaube nicht, dass Sie darüber diskutieren werden, dass dies O (n) ist. Sie können nicht einfach einen Teil Ihres Codes in Big O ignorieren.
Hazzen
1
Es ist O (1), wenn es für ein N durch eine Konstante begrenzt ist. Es gibt Möglichkeiten, ein Array so zu organisieren, dass das Einfügen effizient ist, z. B. indem es aus Blöcken mit einem bestimmten leeren Raum erstellt wird.
Mike Dunlavey
0

Auf hoher Ebene ist dies ein ziemlich einfaches Problem, da Sie sich das Sortieren als nur iterierte Suche vorstellen können. Wenn Sie ein Element in ein geordnetes Array, eine geordnete Liste oder einen geordneten Baum einfügen möchten, müssen Sie nach dem Punkt suchen, an dem es eingefügt werden soll. Dann setzen Sie es zu hoffentlich niedrigen Kosten ein. Sie können sich also einen Sortieralgorithmus vorstellen, bei dem Sie nur eine Reihe von Dingen aufnehmen und nacheinander nach der richtigen Position suchen und diese einfügen. Somit ist eine Einfügungssortierung (O (n * n)) eine iterierte lineare Suche (O (n)). Baum, Heap, Zusammenführen, Radix und schnelles Sortieren (O (n * log (n))) können als iterierte binäre Suche (O (log (n))) betrachtet werden. Es ist möglich, eine O (n) -Sortierung durchzuführen, wenn die zugrunde liegende Suche O (1) wie in einer geordneten Hash-Tabelle ist. (Ein Beispiel hierfür ist das Sortieren von 52 Karten, indem sie in 52 Fächer geworfen werden.)

Die Antwort auf Ihre Frage lautet also, Dinge einzeln einzufügen, anstatt sie zu speichern und dann zu sortieren, sollte im großen Sinne keinen großen Unterschied machen. Sie könnten natürlich konstante Faktoren haben, mit denen Sie sich befassen müssen, und diese könnten von Bedeutung sein.

Wenn n klein ist, wie 10, ist die ganze Diskussion natürlich albern.

Mike Dunlavey
quelle
-1

Wenn dies .NET ist und die Elemente Ganzzahlen sind, können Sie sie schneller zu einem Wörterbuch hinzufügen (oder wenn Sie mit .NET 3.0 oder höher arbeiten, verwenden Sie das HashSet, wenn Sie nichts dagegen haben, Duplikate zu verlieren). Dadurch erhalten Sie eine automatische Sortierung.

Ich denke, dass Saiten genauso funktionieren würden. Das Schöne ist, dass Sie auf diese Weise O (1) einfügen und sortieren können.

Michael Brown
quelle
3
Wörterbuch <T> ist keine sortierte Sammlung. SortedDictionary <T> ist.
Ihar Bury
-2

Das Einfügen eines Elements in eine sortierte Liste ist O (log n), während das Sortieren einer Liste O (n log N) ist. Dies würde bedeuten, dass es immer besser ist, zuerst zu sortieren und dann einzufügen

Denken Sie jedoch daran, dass das große "O" nur die Skalierung der Geschwindigkeit mit der Anzahl der Elemente betrifft. Es kann sein, dass für Ihre Anwendung eine Einfügung in der Mitte teuer ist (z. B. wenn es sich um einen Vektor handelt), sodass das Anhängen und anschließende Sortieren möglicherweise besser ist.

Martin Beckett
quelle
Das Einfügen in eine sortierte Liste ist O (log n). Das Einfügen in einen Hash ist O (1).
BMDHacks
Ok, Sie haben Ihre Notation korrigiert, aber jetzt ist Ihre erste Aussage falsch. Sortieren und Einfügen sind gleich schnell. Das Sortieren ist O (N log N), und das Einfügen führt N-mal eine O (log N) -Operation aus, also O (N log N).
BMDHacks
1
Aber es ist anders N, wenn Sie nur 10 Elemente in eine Million einfügen müssen, dann schlagen 10 * (log 1M) 10 + (1M log 1M) ps. Tut mir leid, dass ich Ihnen einen Kommentar hinterlassen habe. Ich danke Ihnen, dass Sie den Tippfehler entdeckt haben, aber er scheint verschwunden zu sein.
Martin Beckett
Meinetwegen. Technisch gesehen kümmert sich Big-O nicht um die Größe von N, nur Big-Omega, aber wahrscheinlich nur Informatikprofessoren. Vielen Dank, dass Sie sich mit meiner Prüfung abgefunden haben.
BMDHacks
Und die meisten Leute nehmen an, dass O () Ihnen alles über die Geschwindigkeit sagt. Das Bauen von Pyramiden ist O (n), aber immer noch viel langsamer als das Sortieren ihrer Höhen!
Martin Beckett