两个CSV文件之间计算差异的更快方法

Question

我正在尝试计算两个大型csv文件（约4GB）之间的差异，以获取新添加的行并将其写入输出csv文件。对于相对较小的文件（~50MB），我可以使用以下代码获得此功能。

input_file1 = "data.csv"
input_file2 = "data_1.csv"
output_path = "out.csv"

with open(input_file1, 'r') as t1, open(input_file2, 'r') as t2:
    fileone = t1.readlines()
    filetwo = t2.readlines()

with open(output_path, 'w') as outFile:
    for line in filetwo:
        if line not in fileone:
            outFile.write(line)

然而，对于较大的文件，以上代码要么速度过慢（运行约半个小时），要么因内存空间不足而崩溃。

有没有更快的方法来获取大型csv文件的差异？

- iprof0214

---

也许将数据转储到数据库并去重？对于这种需要处理大量计算的任务来说，4 GB 的文件太大了。至少在数据库中，引擎应该能够相当优雅地处理内存管理... - Jacob H

试着阅读这个答案：https://stackoverflow.com/questions/44447107/fastest-way-to-compare-two-huge-csv-files-in-pythonnumpy?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa - Grant Williams

@Sneha，第二个CSV文件的新数据是否总是添加到文件底部？还是以不同的方式排序到数据中？ - Grant Williams

如果.csv文件都已排序，您可以使用类似于合并排序的整理器进行操作。这具有O(N+M)的复杂度，而您的双循环则为O(N*M)。此外：它只需要在内存中存储一个M +一个N记录。 - wildplasser

@Grant - 第二个csv文件将会在文件底部添加新数据。 - iprof0214

Answer 1

您不必完全阅读第二个文件，只需逐行阅读即可。

对于速度，只需从第一个文件创建一个set（快速查找，并在存在重复行时节省内存）。为此，在编写结果时必须保持第二个文件处于打开状态:

input_file1 = "data.csv"
input_file2 = "data_1.csv"
output_path = "out.csv"

with open(input_file1, 'r') as t1:
    fileone = set(t1)

with open(input_file2, 'r') as t2, open(output_path, 'w') as outFile:
    for line in t2:
        if line not in fileone:
            outFile.write(line)

• for line in t2 逐行读取文件（如果可以的话，始终避免使用 readlines()），因此即使文件很大，内存占用也很小。
• fileone 占用一些内存，但希望它更小和/或有重复行，这样就不会占用太多内存，当然比使用 readlines() 更少。
• if line not in fileone 看起来与之前相同，但其平均复杂度为 O(1)，这使得程序运行速度更快。

- Jean-François Fabre

Answer 2

你可以使用数据库，或者选择 排序合并（Sort Merge）。 我会给你基本算法的描述（而不是Python代码）。

排序合并算法描述

这个算法的思路是将两个文件按照相同的顺序进行排序。然后按顺序读取这两个文件：

• 如果两个文件中的记录相等 --> 在两个文件中都存在
• 如果旧文件记录 > 新文件记录 --> 该记录已经被插入
• 如果旧文件记录 < 新文件记录 --> 该记录已经被删除

排序合并算法

Sort the 2 files to new SortedFiles using the Operating Systems sort 
(use the whole record as sort key)

Open/Read  SortedOldFile
Open/Read  SortedNewFile

while (not end-of-file-SortedOldFile) and (not end-of-file-SortedOldFile):
    if SortedOldFile.record < SortedNewFile.record:
       ## Deleted processing goes here
       read SortedOldFile
    elseif SortedOldFile.record > SortedNewFile.record:
       ## Insert processing  goes here
       read SortedNewFile
    else
       read SortedOldFile
       read SortedNewFile

while (not end-of-file-SortedOldFile):
   ## Deleted processing
   read SortedOldFile

while (not end-of-file-SortedNewFile):
   ## Insert processing
   read SortedNewFile

优点：

• 使用的内存极少
• 可扩展到超级大的文件
• 应该足够快，操作系统排序非常高效

缺点：

• 会使用额外的磁盘空间（现在磁盘空间很便宜）
• 代码依赖于操作系统

- Bruce Martin

Answer 3

你可以对行进行哈希以压缩较小的集合，然后进行比较。
或者使用更高级的算法来查找指纹。

https://en.wikipedia.org/wiki/Fingerprint_(computing)

import hashlib
input_file1 = "data.csv"
input_file2 = "data_1.csv"
output_path = "out.csv"

def get_data(file_):
    res = {}
    m = hashlib.md5()
    for i, line in file_:
      hashed_line = m.update(line).hexdigest()
      if hashed_line not in res:
        res[hashed_line ] = []
      res[hashed_line ].append(i)


with open(input_file1, 'r') as t1, open(input_file2, 'r') as t2:
    file1_data =  get_data(t1)
    file2_data =  get_data(t2)
    file2_raw = t2.readlines()


with open(output_path, 'w') as outFile:
    for line in file2_data:
        if line not in file1_data:
            outFile.write(file2_raw[file2_data[line]])

- galaxyan

---

哈希算法很有趣，但它并不能节省内存，因为你仍然需要原始数据来写回文件。此外，如果哈希值匹配，你仍然需要比较实际的字符串值。所以并不确定你能节省时间。 - Jean-François Fabre

@Jean-FrançoisFabre 它不是在比较字符串。它在字典中比较哈希字符串，因此速度为O(1)。对于内存使用，它应该比op的更小。 - galaxyan

@Jean-FrançoisFabre在字典中哈希字符串应该比内存中的字符串哈希（集合）小。 - galaxyan

是的，但我的观点是你可以有md5.hexdigest(s1) == md5.hexdigest(s2)，而s1 != s2。虽然不太可能，但确实有可能。 - Jean-François Fabre

谢谢您提供处理这个问题的方法。我会尝试并告诉您是否能够处理这么大的文件。 - iprof0214