Python新手-如何更快地在大文件中查找和替换？

Question

我有一个大约有一亿行的文件，我想要在其中用制表符分隔的文件中替换文本为另一种文本。目前我的代码运行正常，但是处理前70K行需要一个小时左右。作为一名Python初学者，我想知道是否有更快的方法。谢谢！

输入文件的格式如下：

CHROMOSOME_IV ncRNA gene 5723085 5723105 . - . ID=Gene:WBGene00045518 CHROMOSOME_IV ncRNA ncRNA 5723085 5723105 . - . Parent=Gene:WBGene00045518

替换值的文件格式如下：

WBGene00045518 21ur-5153

以下是我的代码：

infile1 = open('f1.txt', 'r')
infile2 = open('f2.txt', 'r')
outfile = open('out.txt', 'w')

import re
from datetime import datetime
startTime = datetime.now()

udict = {}
for line in infile1:
    line = line.strip()
    linelist = line.split('\t')
    udict1 = {linelist[0]:linelist[1]} 
    udict.update(udict1)

mult10K = []
for x in range(100):
    mult10K.append(x * 10000)   
linecounter = 0
for line in infile2:
    for key, value in udict.items():
        matches = line.count(key)
        if matches > 0: 
            print key, value
            line = line.replace(key, value)
            outfile.write(line + '\n')
        else:
            outfile.write(line + '\n')
    linecounter += 1
    if linecounter in mult10K:
        print linecounter   
        print (datetime.now()-startTime)
infile1.close()
infile2.close()
outfile.close()

- pandaSeq

---

你的代码中存在一个 bug - 按照你的方法，你正在为 udict 中的每个项编写一行输出。那么你的输出文件难道不比原始文件大得多吗？ - jsbueno

请告诉我们您的文件格式是否出现在此处：http://biopython.org/wiki/SeqIO - bukzor

等待 @pandaSeq 回答这些问题。 - nycynik

@bukzor：抱歉，这不是一个太严肃的评论。我的意思是“先让代码做正确的事情”，我认为这应该在优化之前完成。这段代码之所以慢，主要原因可能是jsbueno提到的错误，很可能没有这个错误它就足够快了。 - Sven Marnach

@senderle - udict 大约有20K个条目，因此这里建议的正则表达式解决方案可能会是更好的解决方案。 - pandaSeq

Answer 1

你应该将文本按照“单词”划分，并仅在字典中查找这些单词：

>>> re.findall(r"\w+", "CHROMOSOME_IV ncRNA gene 5723085 5723105 . - . ID=Gene:WBGene00045518 CHROMOSOME_IV ncRNA ncRNA 5723085 5723105 . - . Parent=Gene:WBGene00045518")
['CHROMOSOME_IV', 'ncRNA', 'gene', '5723085', '5723105', 'ID', 'Gene', 'WBGene00045518', 'CHROMOSOME_IV', 'ncRNA', 'ncRNA', '5723085', '5723105', 'Parent', 'Gene', 'WBGene00045518']

这将消除您为每个单独的行执行的字典循环。

完整代码如下：

import re

with open("f1.txt", "r") as infile1:
    udict = dict(line.strip().split("\t", 1) for line in infile1)

with open("f2.txt", "r") as infile2, open("out.txt", "w") as outfile:
    for line in infile2:
        for word in re.findall(r"\w+", line):
            if word in udict:
                line = line.replace(word, udict[word])
        outfile.write(line)

编辑: 另一种方法是从你的字典中构建一个单一的超级正则表达式:

with open("f1.txt", "r") as infile1:
    udict = dict(line.strip().split("\t", 1) for line in infile1)
regex = re.compile("|".join(map(re.escape, udict)))
with open("f2.txt", "r") as infile2, open("out.txt", "w") as outfile:
    for line in infile2:
        outfile.write(regex.sub(lambda m: udict[m.group()], line))

- Sven Marnach

---

@jsbueno: 这样更快，因为您只需要在单行中迭代单词，而不是整个“udict”。 我假设“udict”中的条目比每行的单词要多得多。 当然，我肯定应该指出这个假设！ - Sven Marnach

@jsbueno：特别是如果udict很大，你指出的错误是相关的！我相当确定你找到了主要问题。尽管如此，我认为我在这个答案中给出的两种实现也很有用，因为它们也修复了这个主要问题。 - Sven Marnach

@Lattyware：为什么那样会更好呢？ - Sven Marnach

哇！使用我原来的代码并结合这里提出的所有改进，前70K行需要约15.5分钟。采用这里的第一个建议（循环遍历每行中的单词而不是循环遍历字典中的键），同样的任务只需1.8秒钟。我也会尝试正则表达式，但我确实已经学到了一个教训，即我需要考虑给定循环中所涉及的计算次数。谢谢！ - pandaSeq

@pandaSeq：确保第一种方法中将行拆分为单词时对您的数据执行正确操作。它不会在字典中查找任何“子单词”。第二种方法没有此限制。 - Sven Marnach

Answer 2

我在思考你对字典键进行循环的方式，以及优化此过程的方法，并计划稍后对你的代码进行其他评论。

但是，我遇到了以下部分：

if linecounter in mult10K:
    print linecounter   
    print (datetime.now()-startTime)

这段看似无害的代码实际上会让Python逐个比较"linecounter"列表中的10000个项目，对于文件中的每一行都要执行这个操作。

将其替换为：

if linecounter % 10000 == 0:
    print linecounter   
    print (datetime.now()-startTime)

(忽略所有的mult10k部分) - 这样可以显著提高速度。

此外，似乎您正在记录每个输入行的多个输出行 - 你的主循环应该像这样:

linecounter = 0
for line in infile2:
    for key, value in udict.items():
        matches = line.count(key)
        if matches > 0: 
            print key, value
            line = line.replace(key, value)
            outfile.write(line + '\n')
        else:
            outfile.write(line + '\n')
    linecounter += 1

将它替换为这个：

for linecounter, line in enumerate(infile2):
    for key, value in udict.items():
        matches = line.count(key)
        if matches > 0: 
            print key, value
            line = line.replace(key, value)
    outfile.write(line + '\n')

如何只针对每个输入行正确写入一条输出行（除了消除代码重复和以“Pythonic”方式处理行计数之外）

- jsbueno

---

我认为你在回答的最后部分指出了主要问题：为udict的每个条目编写一行输出将是导致速度缓慢的主要原因。 - Sven Marnach

不需要 line.count 这一行。如果没有匹配项，replace 只会返回字符串的副本；如果有匹配项，则会进行两次线性搜索，而不是一次。 - senderle

最好的选择 - 如果值得检查的话 - 是执行 if key in line: - 至少这样可以短路。 - Gareth Latty

@senderle：确实-这可以进一步改进。lattyware：我认为完全不使用“if”调用“replace”，正如senderle所指出的那样，会更好。无论如何，如果在此处指出的修复后代码仍然缓慢，由于udict超过20、30个条目，那么就该反向搜索了，正如SvenManarch的答案中所指出的那样。 - jsbueno

@jsbueno确实 - 这就是为什么我说“如果值得检查”的原因 - 我主要是提到它，以便将来在其他情况下参考OP。 - Gareth Latty

Answer 3

这段代码中充斥着线性搜索，难怪运行缓慢。如果没有更多关于输入的信息，我无法给出如何解决这些问题的建议，但我至少可以指出问题。我会记录主要问题和一些次要问题。

udict = {}
for line in infile1:
    line = line.strip()
    linelist = line.split('\t')
    udict1 = {linelist[0]:linelist[1]} 
    udict.update(udict1)

不要在这里使用update；只需将该项添加到字典中即可：

    udict[linelist[0]] = linelist[1]

这比为每个条目创建一个字典要快。实际上，Sven Marnach的基于生成器的方法创建此字典更好。尽管如此，这只是相对较小的问题。

mult10K = []
for x in range(100):
    mult10K.append(x * 10000)

这完全是不必要的。删除它；我会向您展示一种在没有它的情况下按间隔打印的方法。

linecounter = 0
for line in infile2:
    for key, value in udict.items():

这是您的第一个大问题。您正在对每行中的键在字典中进行线性搜索。如果字典非常大，这将需要大量操作：100,000,000 * len(udict)。

        matches = line.count(key)

这是另一个问题。您正在使用线性搜索查找匹配项。然后，您执行 replace，它也执行相同的线性搜索！您不需要检查匹配项；如果没有匹配项，replace 只返回相同的字符串。这也不会有很大的区别，但它会为您带来一些收益。

        line = line.replace(key, value)

继续进行这些替换，只有当所有替换都完成后，才编写该行代码：

    outfile.write(line + '\n')

最后，

    linecounter += 1
    if linecounter in mult10K:

请原谅我，但这是一种荒谬的方法！您正在通过linecounter进行线性搜索以确定何时打印一行。再次强调，这将增加近1亿*100次操作。您应该至少在集合中进行搜索；但如果您确实必须这样做，最好的方法是执行模运算并测试它。

    if not linecounter % 10000: 
        print linecounter   
        print (datetime.now()-startTime)

为了使这段代码更加高效，你需要摆脱这些线性搜索。Sven Marnach的答案提出了一种可能有效的方法，但我认为它取决于文件中的数据，因为替换键可能不对应于明显的单词边界。（他添加的正则表达式方法解决了这个问题。）

- senderle

---

这些改进（大多数情况下，我认为是消除了错误）使速度提高了4倍以上。感谢您解释了每个步骤涉及的操作数量 - 谢谢！我将尝试@Sven Marnach的解决方案进行比较。有几个人指出了其中的一些问题，但我要感谢您的彻底回答。 - pandaSeq

Answer 4

这并不是特定于Python的问题，但你可以将双重循环展开一些，以便文件写入不会在每次循环迭代时发生。也许每1000或10000行向文件写入一次。

- David Mann

---

-1：这根本没有任何帮助。Python 无论如何都会缓冲输出。 - Sven Marnach

Answer 5

我希望每行输入都返回一行输出，乘以替换字符串的数量只是一个错误，你真正想要的是为每个输入写一个输出。

你需要找到一种尽可能快速地测试输入行匹配的方法。循环遍历整个字典可能是瓶颈所在。

我相信正则表达式被预编译成状态机可以高效运行。我不知道当你生成一个巨大的表达式时性能会受到多少影响，但值得一试。

freakin_huge_re = re.compile('(' + ')|('.join(udict.keys()) + ')')
for line in infile2:
    matches = [''.join(tup) for tup in freakin_huge_re.findall(line)]
    if matches:
        for key in matches:
            line = line.replace(key, udict[key])

- Mark Ransom

---

我对一个有 100000 个项的 udict 进行了测试。编译正则表达式大约需要 8 秒钟，但性能比朴素方法快了约 10 倍。 - Lauritz V. Thaulow

Answer 6

在Python中显然最明显的是列表推导式 - 这是一种更快（也更易读）的做法：

mult10K = []
for x in range(100):
    mult10K.append(x * 10000)

像这样：

mult10K = [x*10000 for x in range(100)]

同样地，在编程中，如果你有这样的代码：

udict = {}
for line in infile1:
    line = line.strip()
    linelist = line.split('\t')
    udict1 = {linelist[0]:linelist[1]} 
    udict.update(udict1)

我们可以使用一个字典推导式（带有生成器表达式）：

lines = (line.strip().split('\t') for line in infile1)
udict = {line[0]: line[1] for line in lines}

这里值得注意的是，您似乎正在使用制表符分隔的文件。在这种情况下，使用csv模块可能比使用split()更好。

还要注意，使用with语句将增加可读性，并确保您的文件被关闭（即使出现异常）。

如果每次循环都执行打印语句，它们也会大大减慢速度-虽然它们对于调试很有用，但在运行主数据块时，最好将它们删除。

您可以做的另一件“更具Python风格”的事情是使用{{link3：enumerate()}}而不是每次添加一个变量。例如：

linecounter = 0
for line in infile2:
   ...
   linecouter += 1

可以被替换为：

for linecounter, line in enumerate(infile2):
    ...

当你需要计算一个键出现的次数时，更好的解决方案是使用in：

if key in line:

由于在找到实例后会短路，因此如此操作。

将所有这些加起来，让我们看看我们有什么：

import csv
from datetime import datetime
startTime = datetime.now()

with open('f1.txt', 'r') as infile1:
    reader = csv.reader(delimiter='\t')
    udict = dict(reader)

with open('f2.txt', 'r') as infile2, open('out.txt', 'w') as outfile:
    for line in infile2:
        for key, value in udict.items():
            if key in line: 
                line = line.replace(key, value)
        outfile.write(line + '\n')

编辑：根据评论的要求，列出列表推导式与普通循环的区别：

python -m timeit "[i*10000 for i in range(10000)]"
1000 loops, best of 3: 909 usec per loop

python -m timeit "a = []" "for i in range(10000):" "  a.append(i)"
1000 loops, best of 3: 1.01 msec per loop

请注意 usec 与 msec 的区别。这不是很大，但也有点儿不同。

- Gareth Latty

---

-1：对于这个问题本身，这些部分的代码是实际进行多百万行文件替换设置的前置条件，这些建议并没有什么用。 - jsbueno

将代码中的 mult10K = [x*10000 for x in range(100)] 真正改成这样会加快脚本的运行速度吗？ - Anurag Uniyal

@AnuragUniyal 是的，列表推导式在C端循环中完成，因此速度更快。我会提供一些“timeit”测量结果。 - Gareth Latty

@Lattyware 我并不是这个意思，你正在优化的部分是在循环之外的，并且有更好的方法来间隔打印，而不需要那个mult10k列表。 - Anurag Uniyal

@AnuragUniyal 我知道这一点，这就是为什么我会继续说其他的事情 - 包括如果可能的话完全省略打印。 - Gareth Latty

F：\ folder> fart file.txt“\””“” --remove - JAGJ jdfoxito