python - 在列表中找到重新编译匹配项的最快方法

Question

我有一个包含 120000 行的文本文件，其中每一行都具有以下格式:ean_code;plu;name;price;state

我尝试了各种操作，包括直接处理文件，如果文件只是用 readlines() 逐行加载到内存中并写入列表(在程序开始时)，则会给出最好的结果。

所以我有这两行:

matcher = re.compile('^(?:'+eanic.strip()+'(?:;|$)|[^;]*;'+eanic.strip()+'(?:;|$))').match
line=[next(l.split(';') for l in list if matcher(l))]
do sth with line....

这些行试图完成的是，他们试图(尽可能快地)找到一个 plu/ean，这是由用户在字段中输入的:ean_code 或 plu。

我对第二行特别感兴趣，因为它会影响我在 WinCE 设备(python 2.5 的 PyCE 端口)上的性能。

我尝试了所有可能的解决方案以使其更快，但这是遍历特定列表以找到 re.compile 生成的匹配项的最快方法。

除了 for 在列表理解中迭代大列表(在我的例子中是 120000 行)之外，还有什么更快的方法吗？

我正在寻找任何类型的数据结构(直到 Python 2.5 才支持)的任何可能的方式，这将使我比上面两行更快的结果...

只需提及，这是在手持设备 (630MHz ARM) 上执行的，具有 256MB RAM，并且除了 USB 之外没有任何类型的连接。遗憾的是，数据库访问和存在不是一种选择。

Answer 1

我制作了一个测试文件并测试了一些变体。通过遍历文件来搜索静态字符串(正如您看起来正在做的那样)的最快方法是使用 string in line。

但是，如果您将使用加载的数据进行多次搜索(根据下面的测试数字，实际上超过 30 次)，则值得您(计算)时间为dicts 的形式，并将其用于将来的搜索。

loaded 120000 lines
question regex    0.114868402481
simpler regex     0.417045307159
other regex       0.386662817001
startswith        0.236350297928
string in         0.020356798172  <-- iteration winner
dict construction 0.611148500443
dict lookup       0.000002503395  <-- best if you are doing many lookups

测试代码如下:

import re
import timeit

def timefunc(function, times, *args):
    def wrap():
        function(*args)
    t = timeit.Timer(wrap)
    return t.timeit(times) / times

def question(lines):
    eanic = "D41RP9"
    matcher = re.compile('^(?:'+eanic.strip()+'(?:;|$)|[^;]*;'+eanic.strip()+'(?:;|$))').match
    line=[next(l.split(';') for l in lines if matcher(l))]
    return line

def splitstart(lines):
    eanic = "D41RP9"
    ret = []
    for l in lines:
        s = l.split(';')
        if s[0].startswith(eanic) or s[1].startswith(eanic):
            ret.append(l)
    return ret

def simpler(lines):
    eanic = "D41RP9"
    matcher = re.compile('(^|;)' + eanic)
    return [l for l in lines if matcher.search(l)]

def better(lines):
    eanic = "D41RP9"
    matcher = re.compile('^(?:' + eanic + '|[^;]*;' + eanic + ')')
    return [l for l in lines if matcher.match(l)]

def strin(lines):
    eanic = "D41RP9"
    return [l for l in lines if eanic in l]

def mkdicts(lines):
    ean = {}
    plu = {}
    for l in lines:
        s = l.split(';')
        ean[s[0]] = s
        plu[s[1]] = s
    return (ean, plu)

def searchdicts(ean, plu):
    eanic = "D41RP9"
    return (ean.get(eanic, None), plu.get(eanic, None))

with open('test.txt', 'r') as f:
    lines = f.readlines()

    print "loaded", len(lines), "lines"
    print "question regex\t", timefunc(question, 10, lines)
    print "simpler regex\t", timefunc(simpler, 10, lines)
    print "other regex\t", timefunc(simpler, 10, lines)
    print "startswith\t", timefunc(splitstart, 10, lines)
    print "string in\t", timefunc(strin, 10, lines)
    print "dict construction\t", timefunc(mkdicts, 10, lines)
    ean, plu = mkdicts(lines)
    print "dict lookup\t", timefunc(searchdicts, 10, ean, plu)