Python：在包含数百万数据的文件中查找重复项的性能问题

Question

我正在使用 core-python API 在 python 2.7 中为我的项目编写详细的文件验证脚本。这是用于比较另一个 ETL 代码的源文件和目标文件。这包括逐行元数据验证、计数验证、重复检查、空检查和完整数据验证。我已经完成了脚本并且它在 100k 数据集上运行良好（我在 100k,200k 卷上做了一些测试运行）。但是如果我运行，重复检查的方法将永远运行（我的意思是花费大量时间）数以百万计的数据。我调试了代码，发现下面的重复检查方法导致了问题。    def dupFind(dup_list=[],output_path=""):        #dup_list is the list containing duplicates. Actually this is the list of contents of a file line by line as entries        #output_path is the path to which output records and respective duplicate count of each records are saved as a single file        #duplicates is a set which contains tuples with two elements each in which first element is the duplicated record and second is the duplicated count        duplicates=set((x,dup_list.count(x)) for x in filter(lambda rec : dup_list.count(rec)>1,dup_list))         print "time taken for preparing duplicate list is {}".format(str(t1-t0))        dup_report="{}\dup.{}".format(output_path, int(time.time()))        print "Please find the duplicate records  in {}".format(dup_report)        print ""        with open(dup_report, 'w+') as f:            f.write("RECORD|DUPLICATE_COUNT\n")            for line in duplicates:                f.write("{}|{}\n".format(line[0], line[1]))首先，我正在读取文件并将其转换为如下所示的列表（运行速度很快）：     with open(sys.argv[1]) as src,open(sys.argv[2]) as tgt:            src = map(lambda x : x.strip(),list(src))            tgt = map(lambda x : x.strip(),list(tgt))输出重复文件如下所示：    RECORD|DUPLICATE_COUNT    68881,2014-07-19 00:00:00.0,2518,PENDING_PAYMENT|2    68835,2014-05-02 00:00:00.0,764,COMPLETE|2    68878,2014-07-08 00:00:00.0,6753,COMPLETE|2    68834,2014-05-01 00:00:00.0,6938,COMPLETE|2谁能帮我修改一下逻辑或者写一个新的逻辑，这样我就可以一次处理数百万条记录。在我的项目中，文件最大可达40M或50M。

Answer 1

您正在list.count循环中使用。这是非常低效的。相反，先通过一次来获取计数，然后再通过一次来过滤这些计数。线性与二次时间。因此，使用快速collections.Counter对象：

from collections import Counter

def dupFind(dup_list=(),output_path=""):

    counts = Counter(dup_list)

    duplicates = {(x, c) for x, c in counts.iteritems() if c > 1}

    ...

请注意，我将您的默认dup_list参数切换为空元组而不是空列表。如果您不了解可变默认参数的工作原理，则它们可能会导致错误。

上面的解决方案确实需要辅助空间，但应该是相当快的，acollections.Counter本质上是dict针对计数进行了优化。

Answer 2

我看不出与src和 有任何区别tgt，因此我在此介绍了通用列表的解决方案。我认为这个解决方案会加快扫描速度。为了加快速度，我将尝试使用 pypy 或 c。

import sys

def dup_find(sequence, marker=object()):

    prev = marker

    c = 1 

    for item in sequence:

        if item == prev:

            c += 1

        else:

            if c > 1:

                yield prev, c

            prev = item

            c = 1 

    if c > 1:

        yield prev, c

def print_dup(sequence, output):

    for item, count in dup_find(sequence):

        output.write('%s|%s\n' % (item, count))

with open(sys.argv[1]) as fp: 

    lines = sorted(map(str.strip, fp))

if len(set(lines)) < len(lines):

    print_dup(lines, sys.stdout)