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

InformationsquelleAutor Roee Adler | 2009-05-16
  1. 16

    Python Set ist, was Sie sollten versuchen.

    Einem set-Objekt ist eine ungeordnete Sammlung von unterschiedlichen hashable Objekte. Häufige Verwendungen gehören Mitgliedschaft testen, das entfernen von Duplikaten aus einer Sequenz-und computing-mathematische Operationen wie Schnitt, Vereinigung, Differenz und symmetrische Differenz.

    • Würden Sie erwarten, dass alle speed-Unterschied zwischen set und frozenset?
    • Beachten Sie, dass die Verbesserung der Wechsel zu 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.
    InformationsquelleAutor gimel
  2. 4

    Beispiel Python code:

    L = ['foo', 'bar', 'baz'] # Your list
s = set(L)  # Converted to Set

print 'foo'  in s # True
print 'blah' in s # False
    • Wenn Sie nur ein paar look-ups, die die Konvertierung von list->stellen kann, nehmen Sie mehr Zeit als Sie sparen, indem Sie mit einem Satz.. Hängt von der Größe der Liste und die Anzahl der loop-ups natürlich
    InformationsquelleAutor Roman Zeyde
  3. 3

    Einen Trie Struktur würde für Ihre Zwecke anpassen. Zweifellos gibt es Python-Implementierungen zu finden gibt...

    InformationsquelleAutor Paul Dixon
  4. 2

    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, um O(1) im besten Fall.

    • Genau - Sets sind gebaut mit Hashtables - also O(1)
    InformationsquelleAutor SilentGhost
  5. 2

    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?

    • Sie nicht sogar müssen .add(). Satz nimmt einen iterator als argument, vorausgesetzt die Worte sind gespeichert, eine pro Zeile, "f=open("words.txt") ; s = set(f)" funktioniert, und keine unnötige Liste. Beizen ist nicht eine gute Idee, obwohl - es wird wohl noch mindestens so lange bei der Wiederherstellung von einer Gurke, als die Rekonstruktion des Satzes. Wenn die Initialisierung Zeit ist wichtig, mit einem format auf der Festplatte wie die dbm-Bibliotheken besser werden würde.
    • Danke. Ich werde daran denken, dass.
    InformationsquelleAutor behindthefall
  6. 2

    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:

    f=open('words.txt')
s = set(word.strip() for word in f)

    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:

    import dbm
f=open('wordlist.txt')
db = dbm.open('words.db','c')
for word in f:
    db[word] = '1'
f.close()
db.close()

    Dann Ihr Programm überprüfen kann die Mitgliedschaft mit:

    db = dbm.open('words.db','r')
if db.has_key(word):
    print "%s is english" % word
else:
    print "%s is not english" % word

    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).

    • Beachten Sie, dass der Bau der Satz direkt aus der Datei, während elegante, enthält das Zeilenende-Zeichen, das kann nicht sein, was Sie wollen.
    • Hoppla, du hast Recht. Aktualisiert strip line endings / extra Leerzeichen.
    InformationsquelleAutor Brian
  7. 1

    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).

    InformationsquelleAutor Swaroop C H
  8. 1

    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.

    • +1, aber ich werde den alten sah: Suche in hashtables ist nicht wirklich O(1) - es wird nur O(1), wenn (a) der Datensatz ist hinreichend klein und b) Sie nicht speichern Sie eines der pathologischen Schlüssel-sets, die produziert O(n) (linked-list-lookup-Zeiten. In der Praxis (b) ist fast nie verletzt, aber viele Implementierungen gegen (a) durch Anpassung der Anzahl der Gruppen entsprechend der Zahl der Elemente in der hashtable gespeichert. Aber unabhängig von der wahren Zeit, Komplexität, Hashtabellen sollte gut funktionieren in Ihrem Fall.
    • Python macht umfangreichen Gebrauch von Hashtabellen im Laufe seiner Umsetzung (alle Klassen-Mitglieder, Module, etc). Fast alles ist gespeichert in hashtables in python, und weil dieser, finden Sie python-hashtable-Implementierung ist eine der besten und effizientesten, zumindest wenn es um "den täglichen Gebrauch"
    • Ich war unter dem Eindruck, dass die sets sind implementiert, ausgewogene Bäume, hashes nicht (was bedeutet, dass O(log n) - lookup). Ist das nicht Recht?
    InformationsquelleAutor John Feminella
  9. 0

    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:

    if 'foo' in some_list:
    do_something()

    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.

    InformationsquelleAutor Jason Baker
Schreibe einen Kommentar