Was ist der schnellste Weg, um zu bestimmen, ob ein Dict einen Schlüssel enthält, der mit einer bestimmten Zeichenfolge beginnt? Können wir besser als linear? Wie können wir eine O (1) -Operation erreichen, wenn wir nur den Anfang eines Schlüssels kennen?schnellste Möglichkeit, Python-Dict mit Teilschlüsselwort zu suchen
Hier ist die aktuelle Lösung:
for key in dict.keys():
if key.start_with(str):
return True
return False
Ohne die dict zu Vorverarbeitung, O(n) ist das Beste, was Sie tun können. Es muss nicht kompliziert sein, aber:
any(key.startswith(mystr) for key in mydict)
(. Verwenden Sie dict und str als Variablennamen nicht, die sind bereits die Namen von zwei built-in functions)
Wenn Sie können Vorprozess Denken Sie daran, die Schlüssel in einen Präfixbaum zu setzen (aka trie). Es gibt sogar einen Python implementation im Wikipedia-Artikel.
Ein Trie ist O (log N), nicht O (1). Aber es ist fast sicher, was Sie hier wollen. Dies ist so ziemlich der Paradigmenfall für die Datenstruktur. – abarnert
@abarnert Nein, solange Sie nicht die seltsame Annahme machen, dass die größte Stringlänge in der Anzahl der Strings logarithmisch ist. Die Suche in einem Trie ist linear in der Länge des Schlüssels und somit unabhängig von der Anzahl der Strings im Trie. – delnan
@delnan: N ist nicht die Anzahl der Strings, es ist die Anzahl der verschiedenen Symbole. Wenn Sie eine kleine und statische Anzahl von Symbolen haben (z. B. mit ASCII-Zeichenfolgen), können Sie dies ignorieren. Wenn Sie eine große Anzahl von Symbolen (z. B. beliebigen Unicode) haben, können Sie nicht. Entweder man führt eine lineare Suche auf jeder Trie-Ebene oder einmal ein log N durch. (Ja, es ist auch _ linear in der Länge der Saiten, und ich vernachlässige das ...) – abarnert
Sie könnten alle Präfixe der eingesetzten Schlüssel zum dict setzen, so dass für Schlüssel foo Sie f, fo und foo einfügen würde. Sie würden O (1) Lookup, aber Sie würden Zeit auf der Vorverarbeitung (O (k), wobei k eine Schlüssellänge) verbringen und viel Speicher verschwenden:
def insert_with_prefixes(key, value, dict_):
prefixes = (key[:i+1] for i in xrange(len(key)))
dict_.update((prefix, value) for prefix in prefixes)
Für den täglichen Gebrauch würde ich gehen (und ich gehe) mit der Methode in arshajii's beantworten. Und natürlich im Sinn haben, möglich, viele Kollisionen für kurze Präfixe (hier: "h"):
>>> a = {}
>>> insert_with_prefixes('hello', 'world', a)
>>> insert_with_prefixes('homo', 'sapiens', a)
>>> a
{'h': 'sapiens', 'hom': 'sapiens', 'homo': 'sapiens', 'ho': 'sapiens',
'hel': 'world', 'hell': 'world', 'hello': 'world', 'he': 'world'}
Ich bezweifle, können Sie nichts besseres acheive, da Sie nicht den Hash-Wert des Schlüssels aus einem Teil des Schlüssels ableiten kann. Auch dies lässt Raum für Mehrdeutigkeiten, wenn zwei Schlüssel mit dem gleichen Präfix beginnen. – Hyperboreus
Es gibt Datenstrukturen, die dies können, aber sie sind in der Python-Standardbibliothek nicht verfügbar. Versuche oder binäre Suchbäume, zum Beispiel. – delnan
Da es sich um Geschwindigkeit handelt, fühle ich mich verpflichtet, darauf hinzuweisen, dass 'for key in dict_:' viel schneller ist als 'for key in dict_.keys():', da letzterer eine Liste von Schlüsseln erstellt. –