加快大型数据集的正则表达式查找器

Question

我正在尝试在大型数据集中找到匹配项（N 或 -）的位置。每个字符串（300 万个字母）的匹配数约为 300,000。我有 110 个字符串要在同一文件中搜索，所以我使用 re.finditer 做了一个循环来匹配和报告每个匹配项的位置，但这需要很长时间。每个字符串（DNA序列）仅由六个字符（ATGCN-）组成。11 小时内只处理了 17 个字符串。问题是我能做些什么来加快这个过程？我正在谈论的代码部分是：

for found in re.finditer(r"[-N]", DNA_sequence):
    position = found.start() + 1
    positions_list.append(position)
    positions_set = set(positions_list)
all_positions_set = all_positions_set.union(positions_set)
count += 1
print(str(count) + 't' +record.id+'t'+'processed')
output_file.write(record.id+'t'+str(positions_list)+'n')

我也尝试使用 re.compile，

因为我用谷歌搜索，发现它可以提高性能，但没有任何变化（match = re.compile（'[-N]'））

Answer 1

如果您有大约 300k 个匹配项 - 您将重新创建越来越大的set，其中包含与您已经添加到的list完全相同的元素：

for found in re.finditer(r"[-N]", DNA_sequence):
    position = found.start() + 1
    positions_list.append(position)
    positions_set = set(positions_list) # 300k times ... why? why at all? 

相反，您可以简单地使用您获得的列表，并在找到所有列表后将其放入您的all_positions_set：

all_positions_set = all_positions_set.union(positions_list) # union takes any iterable

这应该会减少 50% 以上的内存（集合比列表更昂贵），并且还会显着减少运行时。

---

我不确定什么更快，但你甚至可以跳过使用正则表达式：

t = "ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-"
pos = []
for idx,c in enumerate(t):
    if c in "N-":
        pos.append(idx)
print(pos)  # [4, 5, 10, 11, 16, 17, 22, 23, 28, 29, 34, 35, 40, 41, 46, 47]

而是在你的字符串上使用枚举（）来查找位置....您需要测试这是否更快。

Answer 2

关于不使用正则表达式，我实际上这样做了，现在使用定义的函数修改了我的脚本以在不到 45 秒的时间内运行

def find_all(a_str, sub):
start = 0
while True:
    start = a_str.find(sub, start)
    if start == -1: return
    yield start + 1
    start += len(sub)

所以新的编码部分是：

N_list = list(find_all(DNA_sequence, 'N'))
dash_list = list(find_all(DNA_sequence, '-'))
positions_list = N_list + dash_list
all_positions_set = all_positions_set.union(positions_list)
count += 1
print(str(count) + 't' +record.id+'t'+'processed')
output_file.write(record.id+'t'+str(sorted(positions_list))+'n')