Effizienteste Weg, um herauszufinden, Ob eine Große Liste Enthält eine Bestimmte Zeichenfolge (Python)
Ich habe eine Datei, die etwa alle Wörter in Englisch (~60k Wörter, ~500k Zeichen). Ich möchte testen, ob ein bestimmtes Wort erhalte ich als input "in englischer Sprache" (d.h. wenn genau dieses Wort ist in der Liste).
Was wäre der effizienteste Weg, dies zu tun in Python?
Die triviale Lösung ist das laden der Datei in eine Liste und prüfen Sie, ob das Wort in dieser Liste. Die Liste kann sortiert werden, die ich glaube, schrumpft die Komplexität auf O(logn). Aber ich bin mir nicht sicher, wie Python implementiert die Suche durch Listen, und ob es einen performance-Strafe, wenn eine so große Liste ist im Speicher. Kann ich den "Missbrauch" der Tat, ich kann eine Kappe auf die Länge von Wörtern? (z.B. sagen, der längste ist 15 Zeichen lang).
Bitte beachten Sie ich die Anwendung auf einem Computer mit viel Arbeitsspeicher, so Sorge ich mich weniger für den Speicher-Verbrauch als für die Geschwindigkeit und die CPU-Auslastung.
Dank
Du musst angemeldet sein, um einen Kommentar abzugeben.
Python Set ist, was Sie sollten versuchen.
set
riesig sein kann. In meinem Fall, überprüfen Sie 1000-mal, wenn ein element gehörte zu einer Liste mit 270.000 Elementen ohne Duplikate dauerte rund 20-25seconds. Die überprüfung, ob es gehört zu einer Reihe dauert nur etwa 0.005 Sekunden.Beispiel Python code:
Einen Trie Struktur würde für Ihre Zwecke anpassen. Zweifellos gibt es Python-Implementierungen zu finden gibt...
500k Charakter ist nicht eine große Liste. wenn die Elemente in Ihrer Liste sind einzigartig und müssen Sie dies tun, suchen Sie immer wieder verwenden
set
würde geringer die Komplexität, umO(1)
im besten Fall.Zwei Dinge:
Python 'mutable-set" - Typ hat eine " add " - Methode ( en.add(item) ), so dass Sie könnte gehen Sie nach rechts Lesen (eine Zeile) aus Ihrer großen Datei direkt in einen Satz ohne Verwendung einer Liste als Zwischenprodukt der Struktur der Daten.
Python können Sie 'Gurke' eine Daten-Struktur, so können Sie speichern Sie Ihre großen Satz in eine Datei und speichern Sie die Zeit erneut eingestellt.
Zweiten, ich habe auf der Suche nach einer Liste mit allen single-Silben-Wörter in Englisch für mein eigenes Vergnügen, aber die, die ich gefunden habe, erwähnt zu sein scheinen proprietäre. Wenn es nicht aufdringlich, könnte ich Fragen, ob Ihr die Liste der englischen Wörter kann man durch andere?
Andere gegeben haben, die in-memory-Weg mit set(), und dies ist im Allgemeinen der Schnellste Weg, und sollte nicht von der Steuer Ihren Speicher für ein 60k Wort dataset (ein paar MiBs am meisten). Sie sollten in der Lage sein zu konstruieren, die Ihren Satz mit:
Jedoch, es erfordert eine gewisse Zeit zum laden der Satz in den Speicher. Wenn Sie überprüfen möchten viele Wörter, das ist kein problem, die lookup-Zeit wird mehr als wettmachen. Aber wenn Sie nur gehen, zu prüfen, ein Wort pro Befehl-Ausführung (zB. dies ist ein Kommandozeilen-app wie "checkenglish [Wort]" ) die Start-Zeit wird länger sein, als es hätte Sie einfach die Suche über die Datei Zeile für Zeile.
Wenn dies Ihre situation, oder Sie haben eine viel größere dataset, mit einem format auf der Festplatte besser sein könnte. Der einfachste Weg wäre mit der dbm Modul. Erstellen Sie eine solche Datenbank aus einer wordlist mit:
Dann Ihr Programm überprüfen kann die Mitgliedschaft mit:
Dieser wird langsamer sein als eine set-lookup, da wird die Festplatte zugreifen, aber schneller als die Suche, geringer Speicher und keine signifikanten Initialisierung Zeit.
Gibt es auch andere alternativen, wie die Verwendung einer SQL-Datenbank (z.B. sqlite).
Bist du grundsätzlich testen, ob ein Element in einer Menge oder nicht, richtig?
Wenn dem so ist, und weil Sie gesagt haben, Sie haben viel Speicher, warum nicht einfach laden Sie alle Wörter als Schlüssel in memcache, und dann für jedes Wort, nur schauen, wenn es vorhanden ist, in memcache oder nicht.
Oder nutzen Sie das Daten-Struktur, die von bash benutzten, um AutoVervollständigen-Befehl Namen - das ist schnelle und effiziente in-memory (kann nicht an den Namen erinnern).
Wenn der Speicher Verbrauch ist nicht ein Problem, und die Worte werden sich nicht ändern, der Schnellste Weg, dies zu tun ist, setzen Sie alles in einen hash und suchen auf diese Weise. In Python ist dies die
Set
. Sie haben Konstante Zeit-lookup.Umwandlung der Liste in ein set wird nur nützlich sein, wenn Sie wiederholt ausgeführt hat diese Art der Abfrage für die Daten, so wird die Sortierung der Liste und dabei eine binäre Suche. Wenn Sie nur wollen, ziehen Sie Daten aus der Liste einmal, eine einfache alte lineare Suche ist Ihre beste Wette:
Sonst, Ihre beste Wette ist, um entweder einen Satz wie bereits erwähnt, oder eine binäre Suche. Die man Sie wählen sollten, hängt weitgehend davon ab, wie groß die Daten sind und wie viel Speicher Sie erübrigen können. Ich sagte, dass die wirklich großen Listen neigen zu mehr nutzen aus der Vermischung auf, obwohl die Menge an Speicher, die ergriffen wurden, kann teuer werden.
Schließlich ist eine Dritte option, die Sie importieren können die Daten in einer sqlite-Datenbank und Lesen Sie direkt von ihm. Sqlite ist sehr schnell und es kann sparen Sie sich die Mühe des Ladens der ganze Liste aus Datei. Python hat ein sehr gutes eingebautes sqlite-Bibliothek.