如何使用正则表达式快速过滤列表？

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毫秒内，并与每次按键您都可以重新安排搜索。这将防止搜索速度变慢，同时仍然给用户看起来相当快速的结果。