在Python中从大文件中删除重复行

Question

我有一个csv文件，我想删除其中的重复行，但它太大，无法放入内存。我找到了一种方法来完成它，但我猜这不是最好的方法。

每行包含15个字段和几百个字符，所有字段都需要确定唯一性。与其比较整行以查找重复项，不如比较hash(row-as-a-string)，以节省内存。我设置了一个过滤器，将数据划分成大致相等数量的行（例如一周中的几天），并且每个分区都足够小，以至于该分区的哈希值查找表可以放在内存中。我为每个分区传递一次文件，检查唯一的行并将它们写入第二个文件（伪代码）：

import csv

headers={'DayOfWeek':None, 'a':None, 'b':None}
outs=csv.DictWriter(open('c:\dedupedFile.csv','wb')
days=['Mon','Tue','Wed','Thu','Fri','Sat','Sun']

outs.writerows(headers)

for day in days:
    htable={}
    ins=csv.DictReader(open('c:\bigfile.csv','rb'),headers)
    for line in ins:
        hvalue=hash(reduce(lambda x,y:x+y,line.itervalues()))
        if line['DayOfWeek']==day:
            if hvalue in htable:
                pass
            else:
                htable[hvalue]=None
                outs.writerow(line)

我想加快速度的一个方法是找到一个更好的过滤器来减少必要的通过次数。假设行的长度是均匀分布的，可以代替

for day in days: 

以及

if line['DayOfWeek']==day:

我们有

for i in range(n):

以及

if len(reduce(lambda x,y:x+y,line.itervalues())%n)==i:

在内存允许的范围内。但这仍然使用同样的方法。

Wayne Werner在下面提供了一个很好的实用解决方案；我很好奇是否有更好/更快/更简单的方法从算法的角度来实现这一点。

p.S.I仅限于Python2.5。

Answer 1

您基本上是在进行合并排序，并删除重复的条目。

一般来说，将输入分解为内存大小的片段，对每个片段进行排序，然后在删除重复项的同时合并片段是一个合理的想法。

事实上，我会让虚拟内存系统处理它，然后写下：

input = open(infilename, 'rb')
output = open(outfile, 'wb')

for key,  group in itertools.groupby(sorted(input)):
    output.write(key)

Answer 2

您当前的方法不能保证正常工作。

首先，实际上不同的两行产生相同散列值的可能性很小。hash(a) == hash(b)并不总是意味着a == b

第二，你的“reduce/lambda”戏谑让概率更高：

>>> reduce(lambda x,y: x+y, ['foo', '1', '23'])
'foo123'
>>> reduce(lambda x,y: x+y, ['foo', '12', '3'])
'foo123'
>>>

顺便问一句，是不是“.join（['foo'，'1'，'23']）更清晰一些？

BTW2，为什么不使用set而不是dict来表示htable？

这里有一个实用的解决方案：从GnuWin32站点获取“core utils”包并安装它。然后：

1. 写一份没有标题的文件副本到（比如）infile.csv
2. c:\gnuwin32\bin\sort --unique -ooutfile.csv infile.csv
3. 读取outfile.csv并编写一份标题位于前面的副本

对于步骤1&3中的每一步，都可以使用Python脚本或其他一些GnuWin32实用程序（head、tail、tee、cat…）。

Answer 3

如果您想要一个非常简单的方法来完成此任务，只需创建一个sqlite数据库：

import sqlite3
conn = sqlite3.connect('single.db')
cur = conn.cursor()
cur.execute("""create table test(
f1 text,
f2 text,
f3 text,
f4 text,
f5 text,
f6 text,
f7 text,
f8 text,
f9 text,
f10 text,
f11 text,
f12 text,
f13 text,
f14 text,
f15 text,
primary key(f1,  f2,  f3,  f4,  f5,  f6,  f7,  
            f8,  f9,  f10,  f11,  f12,  f13,  f14,  f15))
"""
conn.commit()

#simplified/pseudo code
for row in reader:
    #assuming row returns a list-type object
    try:
        cur.execute('''insert into test values(?, ?, ?, ?, ?, ?, ?, 
                       ?, ?, ?, ?, ?, ?, ?, ?)''', row)
        conn.commit()
    except IntegrityError:
        pass

conn.commit()
cur.execute('select * from test')

for row in cur:
    #write row to csv file

那么您就不必担心任何比较逻辑了——只需要让sqlite为您处理它。它可能不会比散列字符串快得多，但可能要容易得多。当然，如果需要，您可以修改存储在数据库中的类型，或者视情况而定。当然，因为您已经将数据转换为字符串，所以您可以只使用一个字段。这里有很多选择。