Ich muss eine Reihe von Ganzzahlen sortieren, die Werte zwischen 30.000.000 und 350.000.000 haben können. Es wird zwischen 0 und 65.535 Ganzzahlen geben, wobei die durchschnittliche Anzahl 20.000 beträgt. RAM-Nutzung ist irrelevant und Geschwindigkeit ist nur wichtig.
Später werde ich sie auch in Gruppen aufteilen müssen, wobei die Division immer dann gesetzt wird, wenn die Lücke zwischen zwei dieser Werte & gt; 65.535 ist, wozu ich den Algorithmus brauche.
Wenn es einen Unterschied macht, wird der Algorithmus in einem Perl-Skript verwendet.
Edit: Nachdem ich darüber nachgedacht und die Antworten gelesen habe, habe ich etwas realisiert: Ich interessiere mich nicht wirklich für die Daten selbst. Da ich nur die Anfangs- und Endwerte von Gruppen mit kleinen Lücken suchen möchte, muss die Sortierung nur Buckets erstellen und die Daten verwerfen.
Edit2: Nach einigen Tests und dem Ausprobieren der Antworten war der schnellste Weg, den ich gefunden habe:
%Vor%Ich würde nur ein Array von Buckets erstellen, bevor ich den Algorithmus starte, einen für jede Gruppe von 65536 aufeinanderfolgenden Werten. Die Buckets enthalten einen Min- und Max-Wert ihres Inhalts, speichern den Inhalt jedoch nicht selbst. Führen Sie nach dem Ausführen des Algorithmus einen einzelnen Durchlauf über die Buckets aus. Wenn es zwei aufeinanderfolgende nicht leere Buckets mit min (bucket2) -max (bucket1) & lt; 65536, kombiniere sie. Das Kombinieren findet erst statt, wenn der Algorithmus beendet ist. Entsorgen Sie leere Eimer. Dieser Algorithmus ist eine lineare Zeit.
Achten Sie auf Bucket-Sortieren .
Es ist unwahrscheinlich, dass Sie in Perl einen Sortieralgorithmus schreiben können, der besser funktioniert als Perls eingebaute sort -Funktion:
Sie können mit dem Sortier-Pragma experimentieren, um zu sehen, ob ein bestimmter Algorithmus besser ist:
%Vor%Da Ihre Cutpoints abhängig von der Datenverteilung variieren, müssen Sie die gesamte Liste zuerst sortieren und dann zum Überschneiden übergehen.
%Vor%Ich wollte nur sagen, radix sort, Ссылка , aber das könnte etwas über dem sein, was Sie implementieren wollten , Introsort ist in der Regel die akzeptierte Sortierlösung für Daten Ссылка , es handelt sich um eine Variante von Quicksort, die bei Erreichen kleinerer Sätze auf Heapsort umschaltet da es bei kleineren Sets schneller ist als Quicksort.
Wenn Sie die Zahl als Index für ein Array verwenden und dann die Anzahl dieser Position erhöhen, haben Sie sie "gruppiert" und in einem Durchgang erstellt.
im Pseudocode:
%Vor%Wenn der Bereich im Voraus bekannt ist, können Sie die Werte reduzieren (zum Beispiel den Wert -30000, um ihn in den richtigen Bereich zu bringen).
Tags und Links algorithm perl performance sorting