如何优化Python中字符串列表与前缀列表的匹配计数效率？

我有一个字符串列表list1（示例：["abc","acd","df"]），以及一个可变长度的前缀列表list2（示例：["ha","ab","ad",..]），需要统计list1中以list2元素为前缀的元素数量。

最初我用双重循环实现，时间复杂度为O(nk)（n为list1元素数，k为前缀数），效率较低，初始代码如下：

def match(string,prefixes):
  for i in prefixes:
    if match.beginswith(i):
      return 1
  return 0

def countmatches(list,prefixes):
  totalmat=0 
  for elem in list:
    totalmat+=match(elem,prefixes)
  return totalmat

后来我更新了代码，改用列表推导式结合元组，优化后处理10万条数据耗时约0.1秒，但仍希望进一步提升效率：

import time
def countmatches(list,prefixtuple):
    matches= [e for e in list if e.startswith(prefixtuple)]
    return len(matches)
Prefixes=tuple(["X0","Y7","z34","W3","X23"])# 实际前缀列表约15个元素，固定规模
list=["X23789","V78930","H789078","W23445"]# 字符串列表规模可变
init=time.time()*1000.0
match=countmatches(list,Prefixes)
deltat=time.time()*1000.0-init
print(f"Time: {deltat}")
if(match>0):
  print(list)

实际场景中前缀已过滤，每个字符串仅匹配一个前缀，现寻求更高效的优化技巧。

1. 预编译正则表达式 #

将所有前缀合并为一个正则模式，利用正则引擎的内部优化批量匹配，避免逐个前缀检查：

import re
import time

def countmatches_regex(str_list, prefixes):
    # 转义前缀避免正则特殊字符干扰，构建匹配任意前缀开头的模式
    pattern = '^(' + '|'.join(re.escape(p) for p in prefixes) + ')'
    regex = re.compile(pattern)
    # 生成器表达式统计匹配数，减少内存占用
    return sum(1 for s in str_list if regex.match(s))

# 测试：模拟10万条数据
prefixes = ["X0","Y7","z34","W3","X23"]
str_list = ["X23789","V78930","H789078","W23445"] * 10000

init = time.time() * 1000.0
match_count = countmatches_regex(str_list, prefixes)
deltat = time.time() * 1000.0 - init
print(f"Time: {deltat:.2f}ms, Match count: {match_count}")

正则引擎会自动对前缀进行优化（比如构建状态机），相比逐个调用startswith能减少重复字符检查，尤其适合前缀数量较多的场景。

2. 构建前缀树（Trie） #

前缀树将所有前缀的公共字符合并，匹配时只需遍历字符串的字符直到找到前缀终点或不匹配，平均时间复杂度低于O(nk)：

import time

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def build_trie(prefixes):
    root = TrieNode()
    for prefix in prefixes:
        node = root
        for char in prefix:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    return root

def has_prefix_trie(s, root):
    node = root
    for char in s:
        if node.is_end:
            return True
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end  # 处理字符串与前缀完全相等的情况

def countmatches_trie(str_list, prefixes):
    root = build_trie(prefixes)
    return sum(1 for s in str_list if has_prefix_trie(s, root))

# 测试：模拟10万条数据
prefixes = ["X0","Y7","z34","W3","X23"]
str_list = ["X23789","V78930","H789078","W23445"] * 10000

init = time.time() * 1000.0
match_count = countmatches_trie(str_list, prefixes)
deltat = time.time() * 1000.0 - init
print(f"Time: {deltat:.2f}ms, Match count: {match_count}")

当前缀存在公共前缀（如示例中的"X0"和"X23"）时，前缀树能大幅减少重复字符的检查次数，匹配效率提升明显。

3. 按前缀长度分组+集合快速查询 #

先按前缀长度分组并存入集合，对每个字符串优先检查对应长度的前缀是否在集合中，利用集合O(1)的查询效率减少比较次数：

import time
from collections import defaultdict

def countmatches_grouped(str_list, prefixes):
    # 按前缀长度分组，存储为集合
    prefix_groups = defaultdict(set)
    for p in prefixes:
        prefix_groups[len(p)].add(p)
    # 按前缀长度降序排列，优先检查长前缀（避免短前缀误判，符合每个字符串仅匹配一个前缀的场景）
    lengths = sorted(prefix_groups.keys(), reverse=True)
    
    count = 0
    for s in str_list:
        s_len = len(s)
        for l in lengths:
            if l > s_len:
                continue
            if s[:l] in prefix_groups[l]:
                count +=1
                break
    return count

# 测试：模拟10万条数据
prefixes = ["X0","Y7","z34","W3","X23"]
str_list = ["X23789","V78930","H789078","W23445"] * 10000

init = time.time() * 1000.0
match_count = countmatches_grouped(str_list, prefixes)
deltat = time.time() * 1000.0 - init
print(f"Time: {deltat:.2f}ms, Match count: {match_count}")

该方法避免了对每个字符串遍历所有前缀，尤其适合前缀长度差异较大的场景，查询效率接近O(n)。

内容的提问来源于stack exchange，提问作者RD-43337