python - 从 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下面提供了一个很好的实用解决方案；我很好奇从算法的角度来看是否有更好/更快/更简单的方法来做到这一点。

附言我仅限于 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 为您处理即可。它可能不会比散列字符串快多少，但它可能容易得多。当然，如果需要，您可以修改存储在数据库中的类型，也可以不修改。当然，由于您已经将数据转换为字符串，因此您可以只使用一个字段。这里有很多选择。