logo标签列表

如何在多个文件中高效地搜索多个字符串？

pythonshellcsvawk
4

你好，我会发布我的代码部分，然后解释一下我的目标：

for eachcsv in matches:
    with open(eachcsv, 'r') as f:
        lines = f.readlines()
        for entry in rs:
            for line in lines:
                if entry in line:
                    print("found %s in %s" % (entry, eachcsv))

在“匹配”中，我得到了一个csv文件列表（其路径）。我打开每个csv文件，并使用readlines()将它们加载到内存中。rs是唯一id的列表。对于列表rs的每个元素，我需要搜索csv文件的每一行，并在找到该id时每次打印它（稍后我还将测试该行是否包含另一个固定词）。

上面的代码对我的目的很有效，但我不知道为什么处理一个40万行的文件要花费超过10分钟的时间，我需要为成千上万个文件执行此任务，所以这对我来说是不可能完成的任务。我觉得慢的部分是测试过程，但我不确定。

请注意，我使用Python是因为我更熟悉它，如果有任何其他工具可以解决我的问题，我也可以接受。

编辑：我将尝试发布一些示例

"rs" list:
rs12334435
rs3244567
rs897686
....

files

# header data not needed
# data
# data
# data
# data
# data [...]
#COLUMN1    COLUMN2               COLUMN3   ...
data        rs7854.rs165463       dataSS=1(random_data)
data        rs465465data          datadata
data        rs798436              dataSS=1  
data        datars45648           dataSS=1

最终目标是统计每个文件中每个rs出现的次数，并且如果第三列中包含SS=1，则在输出中将其标记。类似于：
found rs12345 SS yes file 3 folder /root/foobar/file
found rs74565 SS no file 3 folder /root/foobar/file
1
使用for line in f:代替lines = f.readlines(); for line in lines:是否有助于提高速度，因为它不需要在开始循环之前将400k行加载到内存中？ - jonhopkins
1
@BlueStarry 远非线性。假设 n=l=m=k，则为 O(n^4)。 - timgeb
@BlueStarry，你试过jonhopkins的建议了吗？很可能是内存问题。 - timgeb
你应该将所有的ID连接成一个大正则表达式。然后将这个正则表达式应用到每一行中。这样可以将复杂度从O(nmkl)降低到O(nkl)。 - John Smith Optional
谢谢大家到目前为止的支持，@DanielHepper 我已经给您和其他人提供了示例。 - BlueStarry
显示剩余17条评论
2个回答
1
很大一部分问题是由于嵌套循环太多所致。通过消除循环，您可能可以使程序更快：
  1. 其中一个循环是在文件中的每一行上执行的。但是，如果您只想确定文件中是否存在任何匹配项，则可以在一次操作中搜索整个文件正文。确保这样做会搜索更长的字符串，但它是在本机代码中进行而不是在Python中进行。
  2. 您遍历所有匹配字符串。但是，在开始之前，您已经知道了它们，并且对于每个文件都是相同的。因此，这是一个很好的例子，说明在前期做更多工作将在程序的其余时间中节省时间的情况。
这里是结合了这两个想法的代码版本：
import re
import random
import sys
import time

# get_patterns makes up some test data.
def get_patterns():
    rng = random.Random(1)  # fixed seed, for reproducibility
    n = 300
    # Generate up to n unique integers between 60k and 80k.
    return list(set([str(rng.randint(60000, 80000)) for _ in xrange(n)]))

def original(rs, matches):
    for eachcsv in matches:
        with open(eachcsv, 'r') as f:
            lines = f.readlines()
            for entry in rs:
                for line in lines:
                    if entry in line:
                        print("found %s in %s" % (entry, eachcsv))

def mine(rs, matches):
    my_rx = re.compile(build_regex(rs))
    for eachcsv in matches:
        with open(eachcsv, 'r') as f:
            body = f.read()
            matches = my_rx.findall(body)
            for match in matches:
                print "found %s in %s" % (match, eachcsv)

def build_regex(literal_patterns):
    return "|".join([re.escape(pat) for pat in literal_patterns])

def print_elapsed_time(label, callable, args):
    t1 = time.time()
    callable(*args)
    t2 = time.time()
    elapsed_ms = (t2 - t1) * 1000
    print "%8s: %9.1f milliseconds" % (label, elapsed_ms)


def main(args):
    rs = get_patterns()
    filenames = args[1:]
    for function_name_and_function in (('original', original), ('mine', mine)):
        name, func = function_name_and_function
        print_elapsed_time(name, func, [rs, filenames])
    return 0

if __name__ == '__main__':
    sys.exit(main(sys.argv))

你的原始代码在original中，我的替换代码在mine中。

对于300个模式，在我的电脑上实现的运行时间为400毫秒，速度提高了约30倍。对于更多的匹配字符串，改进应该会更大。将模式数量翻倍，您的实现运行时间大致翻倍，但基于正则表达式的实现仅需要多约3%的时间（尽管这部分是因为我的测试模式都有相似的前缀，而真实数据可能不是这样）。

编辑：更新代码以打印每个匹配项的消息。我的代码现在有点慢，但仍然是一种改进，并且在匹配更多字符串时应该相对更快：

~/source/stackoverflow/36923237$ python search.py example.csv
found green fox in example.csv
original:    9218.0 milliseconds
found green fox in example.csv
    mine:     600.4 milliseconds

编辑: 根据要求解释正则表达式技术。

假设您想在文件中搜索字符串foobar和umspquux。一种方法是先搜索文件中的foobar，然后再搜索umspquux。这是您开始使用的方法。

另一种方法是同时搜索两个字符串。想象一下，您检查文件的第一个字符。如果它是'f'或'u'，那么您可能正在寻找一个匹配项，并且应该检查第二个字符是否分别为'o'或'm'。依此类推。如果到达文件结尾，则已经找到了文件中要查找的所有匹配项。

一种告诉计算机同时查找多个字符串的方便方法是使用正则表达式。普通字符串也是正则表达式。正则表达式'foobar'匹配'the foobar is all fuzzy'中的子字符串'foobar'。但是，您可以做更复杂的事情。您可以将两个分别匹配某些内容的正则表达式组合成一个组合的正则表达式，该组合的正则表达式将匹配其中任何一个内容。这是使用备选符号'|'完成的。因此，正则表达式'foobar|umspquux'将匹配'foobar'或'umspquux'。您还可以通过反斜杠'\'转义'|'的含义来匹配真正的'|'。
这就是'build_regex_literal_patterns'的全部内容。它将把列表['foobar'，'umspquux']转换为字符串'foobar | umspquux'。试一下-将函数定义放入自己的文件中，并使用一些尝试性参数调用它，以查看其行为。
顺便说一句，这是弄清楚任何代码如何工作的好方法-运行其中的一部分并打印中间结果。当然，对于具有副作用的程序来说，这样做更难，但这个程序没有。

build_regex_literal_patterns方法中调用re.escape函数，该函数简单地确保任何特殊的正则表达式运算符（如'|'）都被转义（在这种情况下变成'\|'），以便它们能够与自身匹配。

这里正则表达式方法的最后一部分是使用编译好的正则表达式的findall方法。这仅仅返回输入字符串（即文件内容）中所有与我们的正则表达式匹配的结果。

你可以在Python正则表达式文档中了解Python正则表达式。那个文档基本上是参考材料，因此你可能会发现Google开发者网站上的Python正则表达式介绍更适合作为起点的一个更加友善的介绍。Jeffrey Friedl的《精通正则表达式》是关于正则表达式的一本非常全面的著作，虽然它没有涵盖Python方言的正则表达式。

非常感谢您的工作，但我不明白您的代码是否能够打印文件中的所有出现次数，即如果找到特定的rs 100次，搜索函数是否会打印100次。再次感谢您。 - BlueStarry
我无法强调我有多感激。但我还有一个问题。我知道一些关于Perl正则表达式的内容，但我无法理解你对正则表达式方面想法的概念。 - BlueStarry
解释一下。但是尝试拆开程序，看看各个部分的作用。这是理解代码的宝贵技巧。 - James Youngman
0

你最耗费内存的操作将是读取每一行，这应该在外部循环中完成。

你也不想使用readlines一次性读取整个文档，而是使用readline。readline的内存占用要少得多。

for eachcsv in matches:
    with open(eachcsv, 'r') as f:
        for line in f:
            for entry in rs:
                if entry in line:
                    print("found %s in %s" % (entry, eachcsv))

更多阅读请点击这里 https://docs.python.org/2/tutorial/inputoutput.html

还有其他优化方法可以采取，超出了本问题的范围，例如使用线程或使用多进程同时读取多个csv文件。https://docs.python.org/2/library/threading.html

import threading

def findRSinCSVFile(csvFile,rs)
    with open(csvFile, 'r') as f:
        for line in f:
            for entry in rs:
                if entry in line:
                    print("found %s in %s" % (entry, eachcsv))

for csvFile in csvFiles():
    threads.append(threading.Thread(target=findRSinCSVFile,args=(csvFile,rs)))

for thread in threads:
    thread.start()
for thread in threads:
    thread.join()

这将允许您同时解析所有的 csv 文件。

（注意，我没有测试过任何此代码，并仅作为示例）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接