正規表現を使ってリストをすばやくフィルタリングする方法はありますか？

Question

まあ...私はエントリを作成するという些細な要求があり、その場でエントリのリストをフィルタリングします。 （エディタの自動補完機能を考えてください）

要求は、リスト全体に正規表現フィルタをサポートし、一致するエントリだけを表示することです。

例えば、

リストが含まれています。ここではエントリに

abc.efg.hij.entry 
abc.ddd.hij.entry2 
hij.some.value.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 

は、私は、リストをフィルタリングするために使用しているコードです：

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

実生活stには〜300Kの文字列（それぞれ100文字まで）が含まれており、GUIの応答時間を考慮すると、上記のパフォーマンスは非常に悪いです。 私は実際のテストケースをプロファイリングしました。エントリのキー入力ごとに〜0.8sが得られます。

速い方法がありますか？

Answer 1

通常のpythonリストに対して300,000個のアイテムを含む正規表現パターンマッチングを行っている場合、それは自然に遅くなるでしょう。また、リストボックスに300,000個のアイテムを表示しようとすると、それらのアイテムをすべて表示するのが遅くなります。

あなたの最善の策は、より良いデータ構造を選ぶことです。たとえば、私のシステムでは、約250msで300,000個のアイテムに対してフィルタを実行できますが、300,000行のメモリ内sqliteデータベースに対するクエリは、その約半分の時間を要します。どちらの場合でも、結果が非​​常に大きい場合（たとえば、300,000がすべて一致する場合）、ディスプレイを完全に更新する別の秒を追加できます。

もちろん、sqliteは正規表現をサポートしていませんが、いくつかの一般的なパターンをsqlパターンに変換します（例： 'foo。* bar'は 'foo％bar'に変換できます）。 sqliteとregexの詳細については、How do I use regex in a SQLite query?

を参照してください。使用する別の戦略は、入力されたすべての文字を検索しないことです。ユーザーが入力を一時停止するまで待ちます。たとえば、「Lorem」と入力すると、「L」、「Lo」、「Lor」などを検索する必要はありません。代わりに、100ミリ秒で検索が実行されるようにスケジュールを設定します。キーを押すたびに検索のスケジュールを変更できます。これにより検索が遅くなるのを防ぎますが、ユーザーにはかなり迅速な結果が得られます。