Ich habe diesen Code, der bestimmt, ob ein Wort (ohne Berücksichtigung des Falls) in einer WordList-Textdatei enthalten ist. Die WordList-Textdatei kann jedoch 65000 ++ Zeilen haben, und um nur ein Wort unter Verwendung meiner Implementierung unten zu suchen, dauert fast eine Minute. Können Sie sich eine bessere Implementierung vorstellen?
Danke!
%Vor% Verwenden Sie ein HashSet , in das Sie für jedes Wort eine Kleinbuchstabeversion eingeben. Wenn überprüft wird, ob HashSet eine angegebene Zeichenfolge enthält, handelt es sich im Durchschnitt um eine Operation mit konstanter Zeit (Lesen: extrem schnell).
Da Sie suchen, sollten Sie die Liste vor der Suche sortieren. dann können Sie die binäre Suche durchführen, die viel schneller ist als die lineare Suche. Dies kann hilfreich sein, wenn Sie mehrere Suchvorgänge in derselben Liste durchführen, da sich sonst die Strafe, die Sie zum Sortieren der Liste zahlen, für die einmalige Suche nicht lohnt.
Auch die lineare Suche in einer verknüpften Liste mit "lxx.get (i)" wird nach Problemen gefragt. LinkedList.get () ist O (n). Sie können entweder einen Iterator verwenden (einfache Methode: for (String s: lxx)) oder zu einem Listentyp mit O (1) Zugriffszeit wechseln, z. B. ArrayList.
Jede Suche durch l in einer O (n) -Operation, so wird dies ziemlich teuer, wenn Sie Tausende von Wörtern haben. Verwenden Sie stattdessen HashSet :
und dann lxx.contains(theWord.toLowerCase()) , um zu prüfen, ob das Wort in der Datei enthalten ist.
Jedes Nachschlagen in HashSet ist eine O (1) -Operation, also sind die Zeiten, die es dauert, (fast) unabhängig von der Größe Ihrer Datei.
Als erstes deklarieren Sie Ihre Variable nicht als LinkedList, deklarieren Sie sie als eine Liste (Teile des Codes, die nicht mit der gelöschten Liste zusammenhängen:
%Vor%Als nächstes rufen Sie nicht auf die Liste, verwenden Sie eine LinkedList get wird sehr langsam. Verwenden Sie stattdessen einen Iterator ... besser noch die neue stype for-Schleife, die einen Iterator für Sie verwendet:
%Vor%Als nächstes ändern Sie die neue LinkedList in eine neue ArrayList:
lxx = neue ArrayList ();
Dieser Code sollte schneller sein, aber Sie können immer noch besser.
Da Sie sich nicht um doppelte Wörter kümmern, verwenden Sie Set statt einer Liste und verwenden Sie ein HashSet anstelle einer ArrayList.
Dadurch wird das Programm erheblich beschleunigt.
Ihr ursprünglicher Code, der eine LinkedList mit get verwendet, muss jedes Mal, wenn nach dem nächsten Wort in der Liste gesucht wird, am Anfang der Liste erneut beginnen. Die Verwendung des Iterators (über den neuen Stil für jede Schleife) verhindert dies.
Wenn Sie eine LinkedList verwenden, bedeutet dies, dass jedes Mal, wenn Sie zum nächsten Wort in der Liste gehen müssen, eine Suche durchgeführt wird, die ArrayList diesen Overhead nicht hat.
Die Verwendung eines HashSet wird (wahrscheinlich) mit einer Baumstruktur durchgeführt, die sehr schnell nachschlägt.
Hier ist meine Implementierung, die unter 50 ms sucht.
Zuerst müssen Sie die Datei laden und sie im Speicher sortiert halten.
Sie können es laden, wie Sie wollen, aber wenn Sie es in große Stücke geladen haben, wird es einfacher.
Meine Eingabe war das Byte im Python-Buch (Download der HTML-Einzeldateiversion) und das Java-Sprachspezifikation (HTML heruntergeladen und eine einzige Datei aus allen HTML-Seiten erstellt)
Um die Liste in eine große Datei zu erstellen, habe ich das gleiche Programm benutzt (siehe kommentierten Code).
Sobald ich eine große Datei mit ungefähr 300k Wörtern habe, lief das Programm mit dieser Ausgabe:
%Vor%Immer unter 50 ms.
Hier ist der Code:
%Vor%Der schwierigste Teil war eine Beispieleingabe: P
zwei Vorschläge: Beide Datenstrukturen geben Ihnen eine bessere Leistung.
Tags und Links java data-structures