如何使用正則表達式快速過濾列表？

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

如果您正在對包含300,000個項目的普通python列表進行正則表達式模式匹配，它自然會變得很慢。另外，如果您要在列表框中顯示300,000個項目，則顯示所有這些項目的速度會很慢。

你最好的選擇可能是選擇一個更好的數據結構。例如，在我的系統上，我可以在大約250ms內針對300,000個項目運行過濾器，但對內存爲300,000行的sqlite數據庫的查詢需要大約一半的時間。無論哪種情況，如果結果非常大（例如，如果全部300,000匹配），它可以增加另一秒來完全更新顯示器

當然，sqlite不支持開箱即用的正則表達式，但是您可以將一些常見模式轉換爲sql模式（例如：'foo。* bar'可以轉換爲'foo％bar'）。有關sqlite和正則表達式的更多信息，請參閱How do I use regex in a SQLite query?

另一種使用的策略是不搜索每個鍵入的字符。等待用戶暫停輸入。因此，例如，如果他們鍵入「Lorem」，則不需要搜索「L」，然後搜索「Lo」，然後搜索「Lor」等。相反，安排搜索發生在100毫秒內，並與每次按鍵您都可以重新安排搜索。這將防止搜索速度變慢，同時仍然給用戶看起來相當快速的結果。