从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:

其中'n'和内存一样小.但这仍然使用相同的方法.

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

PS我只限于Python 2.5.

Answer 1

如果你想要一个非常简单的方法来做到这一点,只需创建一个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为你处理它.它可能不会比散列字符串快得多,但它可能要容易得多.当然,如果需要,您可以修改存储在数据库中的类型,视情况而定.当然,因为您已经将数据转换为字符串,所以您可以只使用一个字段.这里有很多选择.

Answer 2

您基本上正在进行合并排序,并删除重复的条目.

将输入分解为内存大小的片段,对每个片段进行排序,然后合并片段同时删除重复片段通常是一个合理的想法.

实际上,我会让虚拟内存系统处理它并且只写几个演出:

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

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