Ich arbeite an einem großen Projekt, ich werde mich nicht darum kümmern, es hier zusammenzufassen, aber dieser Teil des Projekts besteht darin, ein sehr großes Textdokument (mindestens etwa 50.000 Wörter (nicht einzigartig)) zu nehmen, und Gib jedes einzelne Wort in der Reihenfolge der am häufigsten verwendeten aus, um es am wenigsten zu verwenden (wahrscheinlich sind die obersten drei "a" "an" und "das").
Meine Frage ist natürlich, was wäre der beste Sortieralgorithmus? Ich habe gelesen, wie ich zähle, und ich mag es, aber meine Sorge ist, dass der Wertebereich im Vergleich zur Anzahl der einzelnen Wörter zu groß ist.
Irgendwelche Vorschläge?
Zuerst benötigen Sie eine Karte des Wortes - & gt; Anzahl. 50.000 Wörter sind nicht viel - es wird leicht in die Erinnerung passen, also gibt es keine Sorgen. In C ++ können Sie die Standard STL std :: map verwenden.
Sobald Sie die Karte haben, können Sie alle Kartenschlüssel in einen Vektor kopieren.
Sortieren Sie diesen Vektor dann mit einem benutzerdefinierten Vergleichsoperator: Vergleichen Sie die Zahlen nicht mit der Karte, anstatt die Wörter zu vergleichen. (Machen Sie sich keine Sorgen um den speziellen Sortieralgorithmus - Ihr Array ist nicht so groß, so dass jede Standardbibliotheks-Sortierung für Sie funktioniert.)
Ich würde mit einem Quicksort beginnen und von dort aus weitergehen.
Sehen Sie sich die Wiki-Seite zu Sortieralgorithmen an , um die Unterschiede zu erfahren.
Sie sollten versuchen, MSD radix zu sortieren. Es wird Ihre Einträge in lexikographischer Reihenfolge sortieren. Hier ist ein Google-Code-Projekt , für das Sie sich interessieren könnten.
Dies ist ein bisschen schwierig, weil Sie eine Karte von Wörtern wollen - & gt; Häufigkeit, und Sie möchten nach dem Wert und nicht nach dem Schlüssel sortieren (was üblich ist). Es gibt ein Java-Beispiel hier , das zeigt, wie es funktioniert ein benutzerdefinierter Vergleicher.
Der bestimmte Algorithmus, den Sie verwenden, wird nicht viel bewirken, also würde ich einfach bei Ihrer Standard-Bibliotheksimplementierung bleiben.
Sie können eine bessere Leistung als Quicksort mit diesem speziellen Problem erhalten, wenn zwei Wörter die gleiche Anzahl von Malen auftreten, dann spielt es keine Rolle, in welcher Reihenfolge Sie sie ausgeben.
Erster Schritt: Erstellen Sie eine Hash-Map mit den Wörtern als Schlüsselwerte und Häufigkeit als zugehörige Werte. Sie füllen diese Hash-Map beim Analysieren der Datei ein. Achten Sie dabei auf die höchste gefundene Frequenz. Dieser Schritt ist O (n) -Komplexität.
Zweiter Schritt: Erstellen Sie eine Liste mit der Anzahl der Einträge, die der höchsten Häufigkeit des ersten Schritts entspricht. Der Index jedes Slots in dieser Liste enthält eine Liste der Wörter mit der Häufigkeitszählung, die dem Index entspricht. Wörter, die dreimal im Dokument vorkommen, werden beispielsweise in der Liste [3] angezeigt. Iterieren Sie durch die Hash-Karte und fügen Sie die Wörter an den entsprechenden Stellen in der Liste ein. Dieser Schritt ist O (n) -Komplexität.
Dritter Schritt: Iterieren Sie rückwärts durch die Liste und geben Sie alle Wörter aus. Dieser Schritt ist O (n) -Komplexität.
Insgesamt erfüllt dieser Algorithmus Ihre Aufgabe in O (n) time und nicht in O (nlogn), die von quicksort benötigt werden.
In fast allen Fällen, die ich je getestet habe, hat Quicksort für mich am besten funktioniert. Ich hatte jedoch zwei Fälle, in denen Combsort der Beste war. Könnte sein, dass Combsort in diesen Fällen besser war, weil der Code so klein war, oder aufgrund einer Eigenart in der Reihenfolge der Daten.
Wenn die Sortierung in meinem Profil angezeigt wird, probiere ich die wichtigsten Arten aus. Ich hatte nie etwas, das sowohl Quicksort als auch Combsort übertraf.
Bei großen Mengen können Sie beim Informationsabruf die so genannte sortierte Indexierung verwenden, aber für 50.000 Wörter können Sie Folgendes verwenden:
Tags und Links algorithm performance list sorting numbers