如何快速筛选包含另一列表子串的字符串列表元素

我有一个可能包含多达10^6个元素的字符串列表：

samples = ['2345_234_1.0_1.35_001', '0345_123_2.09_1.3_003', ...]

还有一个子串匹配列表：

matches = ['7895_001', '3458_669', '0345_123', ...]

需要生成matched_samples列表，只保留samples中包含matches里至少一个子串的元素。比如samples[1]会被选中，因为matches[2]是它的子串。

目前用列表推导式的写法是：

matched_samples = [s for s in samples if any(xs in s for xs in matches)]

但这种双重循环的方式速度太慢，想找更高效的替代方案。已知如果用pandas DataFrame可以通过拼接正则表达式实现高效匹配：

matches_regex = '|'.join(matches)
matched_samples = samples[samples['sample'].str.contains(matches_regex)]

想知道针对普通Python列表，有没有同样高效的实现方式？

针对普通列表，有两种主流的高效实现方式，性能远优于原生的双重循环：

方法一：利用正则表达式模块re #

和pandas的思路一致，把所有匹配子串拼接成一个正则表达式，借助正则引擎的内部优化实现批量匹配，避免Python层面的逐个子串检查：

import re

# 先转义子串中的正则特殊字符（比如.、*、?等），避免语法冲突
escaped_matches = [re.escape(x) for x in matches]
matches_regex = '|'.join(escaped_matches)
# 预编译正则表达式，提升重复匹配效率
pattern = re.compile(matches_regex)

matched_samples = [s for s in samples if pattern.search(s)]

优势： #

• 正则引擎的多模式匹配做了底层优化，效率远高于Python原生的双重循环
• 代码简洁，和pandas的实现思路统一，易理解易维护

方法二：Aho-Corasick多模式匹配算法 #

如果matches的规模很大（比如上万个子串），正则表达式的性能可能会下降，这时可以用专门的多模式匹配算法——Aho-Corasick，它的时间复杂度接近线性，适合大规模场景。

可以用第三方库pyahocorasick实现：

import ahocorasick

# 构建AC自动机
automaton = ahocorasick.Automaton()
for key in matches:
    automaton.add_word(key, key)
automaton.make_automaton()

# 批量遍历样本并匹配
matched_samples = []
for s in samples:
    # 只要找到任意一个匹配子串，就加入结果并跳出当前字符串的匹配循环
    for _ in automaton.iter(s):
        matched_samples.append(s)
        break

优势： #

• 时间复杂度为O(N + M)，其中N是所有样本字符串的总长度，M是所有匹配子串的总长度，性能稳定
• 不会因为匹配子串数量过多导致性能骤降，适合超大规模多模式匹配场景

内容的提问来源于stack exchange，提问作者DeltaIV