Effizientester Sortieralgorithmus für eine große Menge von Zahlen

Question

Ich arbeite an einem großen Projekt, ich werde mir nicht die Mühe machen, es hier zusammenzufassen, aber dieser Teil des Projekts ist es, ein sehr großes Dokument von Text (mindestens rund 50.000 Wörter (nicht eindeutig)) zu nehmen, und jedes einzelne Wort in der Reihenfolge der am häufigsten verwendeten zu am wenigsten verwendet (wahrscheinlich Top drei werden "ein" "an" und "die").

Meine Frage ist natürlich, was wäre der beste Sortieralgorithmus zu verwenden? Ich las von Zählen sortieren, und ich mag es, aber meine Sorge ist, dass der Bereich der Werte zu groß im Vergleich zu der Anzahl der eindeutigen Wörter sein wird.

Irgendwelche Vorschläge?

Answer 1

Zunächst benötigen Sie eine Karte der Wörter -> Anzahl. 50.000 Wörter sind nicht viel - sie passen problemlos in den Speicher, also kein Grund zur Sorge. In C++ können Sie die Standard-STL std::map verwenden.

Wenn Sie dann die Karte haben, können Sie alle Schlüssel der Karte in einen Vektor kopieren.

Dann sortieren Sie diesen Vektor mit einem benutzerdefinierten Vergleichsoperator: Vergleichen Sie nicht die Wörter, sondern die Anzahl der Wörter in der Karte. (Machen Sie sich keine Gedanken über den spezifischen Sortieralgorithmus - Ihr Array ist nicht so groß, also wird jede Sortierung der Standardbibliothek für Sie funktionieren).

Answer 2

Ich würde mit einer Schnellsortierung und gehen von dort aus.

Überprüfen Sie die wiki-Seite über Sortieralgorithmen um die Unterschiede zu erkennen.

Answer 3

Sie sollten eine MSD-Radix sortieren. Es sortiert Ihre Einträge in lexikographische Ordnung . Hier ist eine Google-Code-Projekt die Sie interessieren könnten.

Answer 4

Schauen Sie sich den Link an. Eine bildliche Darstellung der Funktionsweise verschiedener Algorithmen. Dies wird Ihnen einen Hinweis geben!

Sortieralgorithmen

Answer 5

Bei diesem speziellen Problem kann man eine bessere Leistung als mit Quicksort erzielen, wenn man davon ausgeht, dass es keine Rolle spielt, in welcher Reihenfolge man zwei Wörter ausgibt, wenn sie gleich oft vorkommen.

Erster Schritt: Erstellen Sie eine Hash-Map mit den Wörtern als Schlüsselwerten und der Häufigkeit als den zugehörigen Werten. Sie werden diese Hash-Map beim Parsen der Datei ausfüllen. Achten Sie dabei darauf, dass Sie die höchste gefundene Häufigkeit im Auge behalten. Dieser Schritt ist O(n) komplex.

Zweiter Schritt: Erstellen Sie eine Liste mit der Anzahl der Einträge, die der höchsten Häufigkeit aus dem ersten Schritt entspricht. Der Index jedes Slots in dieser Liste enthält eine Liste der Wörter, deren Häufigkeit gleich dem Index ist. Wörter, die 3 Mal im Dokument vorkommen, werden also beispielsweise in list[3] gespeichert. Iterieren Sie durch die Hash-Map und fügen Sie die Wörter an den entsprechenden Stellen in die Liste ein. Dieser Schritt ist O(n) komplex.

Dritter Schritt: Iterieren Sie die Liste in umgekehrter Reihenfolge und geben Sie alle Wörter aus. Dieser Schritt ist O(n) komplex.

Insgesamt wird dieser Algorithmus Ihre Aufgabe erfüllen in O(n)-Zeit und nicht O(nlogn) wie bei Quicksort.