Wie schnell eine Liste mit Regex filtern?

Question

Nun ... Ich habe eine triviale Anfrage, einen Eintrag zu erstellen, der eine Liste von Einträgen während des Betriebs filtert. (Denken Sie an eine Funktion zur automatischen Vervollständigung des Editors)

Die Anforderung besteht darin, einen Regex-Filter über die gesamte Liste zu unterstützen und nur übereinstimmende Einträge anzuzeigen.

zB

Die Liste enthält:

abc.efg.hij.entry 
abc.ddd.hij.entry2 
hij.some.value.entry 

Typing im Entry

Value : List 
hij  : abc.efg.hij.entry, abc.ddd.hij.entry2, hij.some.value.entry 
ddd  : abc.ddd.hij.entry2 
dd*entry : abc.ddd.hij.entry2 
val  : hij.some.value.entry 

Hier ist der Code i zum Filtern der Liste bin mit:

regex = re.compile(r"{0}".format(entry_value), re.IGNORECASE) 
display_list = list(filter(regex.search, display_list)) 

Das wahre Leben li st enthält ~ 300K Einträge von Strings (bis zu jeweils 100 char) und die Leistung der oben genannten ist sehr schlecht, unter Berücksichtigung einer GUI-Antwortzeit. Ich habe meinen echten Testfall profiliert und es ergibt ~ 0.8s für jeden im Eintrag eingegebenen Schlüssel.

Gibt es einen schnelleren Weg?

Answer 1

Wenn Sie reguläre Ausdruck Mustervergleich gegen eine normale Python-Liste, die 300.000 Elemente enthält, tun, wird es nur natürlich langsam sein. Wenn Sie 300.000 Elemente in einer Listbox anzeigen möchten, wird es langsam sein, all diese Elemente anzuzeigen.

Ihre beste Wette könnte sein, eine bessere Datenstruktur auszuwählen. Zum Beispiel kann ich auf meinem System Ihren Filter gegen 300.000 Elemente in etwa 250ms ausführen, aber eine Abfrage gegen eine SQL-In-Memory-Datenbank mit 300.000 Zeilen dauert etwa die Hälfte dieser Zeit. In jedem Fall kann es eine weitere Sekunde hinzufügen, um die Anzeige vollständig zu aktualisieren, wenn das Ergebnis sehr groß ist (z. B. wenn alle 300.000 übereinstimmen).

Natürlich unterstützt sqlite Regex nicht standardmäßig, aber Sie können Übersetzen Sie einige gebräuchliche Muster in SQL-Muster (zB: 'foo. * bar' könnte in 'foo% bar' übersetzt werden). Weitere Informationen zu sqlite und regex finden Sie unter How do I use regex in a SQLite query?

Eine andere Strategie wäre es, nicht bei jedem eingegebenen Zeichen zu suchen. Warten Sie, bis der Benutzer bei der Eingabe pausiert. Wenn Sie beispielsweise "Lorem" eingeben, müssen Sie nicht nach "L" und dann nach "Lo" und dann nach "Lor" usw. suchen. Planen Sie stattdessen die Suche in 100 ms und mit Mit jedem Tastendruck können Sie die Suche neu planen. Dies verhindert, dass die Suche langsamer wird, während dem Benutzer immer noch ein ziemlich schnelles Ergebnis angezeigt wird.