正则表达式的慢列表理解

Question

假设我有一个文件列表，如下所示：

['regular0000.png', 'regular0001.png', 'regular0002.png', 
 'depth.0000.png', 'emission0000.png', 'emission0001.png',   
 'emission0002.png', 'diffusefilter0000.png']

我的目标是保留此列表中的所有“png 序列”；换句话说，所有带有多次出现前缀的 png。比如我想过滤列表得到：

['regular0000.png', 'regular0001.png', 'regular0002.png', 
 'emission0000.png', 'emission0001.png', 'emission0002.png']

我编写了以下列表理解来执行此操作，但是对于大型 PNG 序列（1000 多个文件），它开始变得非常慢。

prefix_regex = r'(.*)[0-9]{4,}\.png'
pngs = glob.glob(os.path.join(os.getcwd(), folder, "*.png"))
pngs = [png for png in pngs if sum((re.search(prefix_regex, 
         png2).group(1) == re.search(prefix_regex, png).group(1)) 
             for png2 in pngs) > 1]

有人知道我怎样才能加快这个列表的理解速度吗？如果有帮助，我正在使用 Python 3.8。

Answer 1

在这种特定情况下，我建议制作一个 collections.defaultdict(list) 并单次传递您的文件，append 将每个文件发送到 list 以您的前缀作为键控提炼。用便宜的分组操作 O(n) 替换 all-to-all 比较 O(n**2)；对于 1000 个文件，这意味着减少与 ~1,000,000 成比例的工作到 ~1000。

Side-note：需要了解的一些常规优化：

当你只关心一次命中时，不要做sum(...) > 1；将其替换为 any(...)，以便在您命中时立即 short-circuits。它不会修复 big-O 性能（这里是你的大问题），但它在其他情况下很有用。
Pre-compile 你的正则表达式 re.compile 并使用编译后的正则表达式对象的 search （re 确实缓存了正则表达式的编译形式，但它仍然需要一遍又一遍地进行缓存查找；自己编译和保存已编译的正则表达式可以避免这项工作）

Answer 2

这是使用@ShadowRanger 描述的defaultdict 方法的答案：

from collections import defaultdict
import os
import string

imgs = ['regular0000.png', 'regular0001.png', 'regular0002.png', 'depth.0000.png', 'emission0000.png', 'emission0001.png', 'emission0002.png', 'diffusefilter0000.png']

d = defaultdict(list)
for i in imgs:
    name, ext = os.path.splitext(i)
    no_num = name.rstrip(string.digits)
    d[no_num].append(i)

result = [i for  _, v in d.items() if len(v) > 1 for i in v]

这至少在将原始 imgs 列表乘以 1000 时仍然是瞬时的。

Answer 3

您可以使用正则表达式 .groupby:

from itertools import groupby 
import re


li=['regular0000.png', 'regular0001.png', 'regular0002.png', 
 'depth.0000.png', 'emission0000.png', 'emission0001.png',   
 'emission0002.png', 'diffusefilter0000.png']

for k,v in groupby(sorted(li), key=lambda s: re.search(r'(^[^\d]+)', s).group(1)):
    print(k,list(v))

打印：

depth. ['depth.0000.png']
diffusefilter ['diffusefilter0000.png']
emission ['emission0000.png', 'emission0001.png', 'emission0002.png']
regular ['regular0000.png', 'regular0001.png', 'regular0002.png']

那么如果你只想要群组：

for k,v in groupby(sorted(li), key=lambda s: re.search(r'(^[^\d]+)', s).group(1)):
    tgt=list(v)
    if len(tgt)>1: print(tgt)

如果我运行使用您的示例 *10000 它会在 152 毫秒内完成整个列表...

正则表达式的慢列表理解

Slow List Comprehension with Regex

python

regex

performance

python-3.x

python-3.8