python - 在python中高效处理~5000万条记录文件

Question

我们有一个包含大约 4600 万条 CSV 格式记录的文件。每条记录大约有 18 个字段，其中一个是 64 字节的 ID。我们还有另一个文件，其中包含大约 167K 个唯一 ID。 ID对应的记录需要被抽出。因此，我们编写了一个 python 程序，将 167K ID 读入数组并处理 4600 万条记录文件，检查这些记录中是否存在 ID。这是代码片段:

import csv
...
csvReadHandler = csv.reader(inputFile, delimiter=chr(1))
csvWriteHandler = csv.writer(outputFile, delimiter=chr(1), lineterminator='\n')
for fieldAry in csvReadHandler:
    lineCounts['orig'] += 1
    if fieldAry[CUSTOMER_ID] not in idArray:
        csvWriteHandler.writerow(fieldAry)
        lineCounts['mod'] += 1

在一小组数据上测试了程序，这里是处理时间:

lines: 117929 process time: 236.388447046 sec
lines: 145390 process time: 277.075321913 sec

我们已于昨晚美国东部标准时间凌晨 3:00 开始在 4600 万条记录文件(大约 13 GB 大小)上运行该程序，现在是美国东部时间上午 10 点左右，它仍在处理中!

问题:

1. 是否有更好的方法来处理这些记录以缩短处理时间？
2. Python 是正确的选择吗？ awk 或其他工具会有帮助吗？
3. 我猜测在以下语句中对 167K 数组进行 64 字节 ID 查找是罪魁祸首:
   如果 fieldAry[CUSTOMER_ID] 不在 idArray 中:

有更好的选择吗？

谢谢!

更新:这是在带有 EBS 附加卷的 EC2 实例上处理的。

Answer 1

你应该必须使用set而不是list； 在 for 循环之前:

idArray = set(idArray)

csvReadHandler = csv.reader(inputFile, delimiter=chr(1))
csvWriteHandler = csv.writer(outputFile, delimiter=chr(1), lineterminator='\n')
for fieldAry in csvReadHandler:
    lineCounts['orig'] += 1
    if fieldAry[CUSTOMER_ID] not in idArray:
        csvWriteHandler.writerow(fieldAry)
        lineCounts['mod'] += 1

并看到令人难以置信的加速；您正在使用 天 不必要的处理时间，只是因为您选择了错误的数据结构。

---

in 运算符与 set 具有 O(1) 时间复杂度，而 O(n) 时间复杂度使用 list。这可能听起来“没什么大不了的”，但实际上这是脚本中的瓶颈。即使 set 对那个 O 会有更高的常量。因此，您的代码在单个 in 操作上使用的时间比必要的多 30000 次。如果在最佳版本中它需要 30 秒，那么现在您仅在这一行上就花费了 10 天。

请看下面的测试:我生成了 100 万个 ID，然后将 10000 个放到另一个列表中 - to_remove。然后我像您一样执行 for 循环，为每条记录执行 in 操作:

import random
import timeit

all_ids = [random.randint(1, 2**63) for i in range(1000000)]
to_remove = all_ids[:10000]
random.shuffle(to_remove)
random.shuffle(all_ids)


def test_set():
    to_remove_set = set(to_remove)
    for i in all_ids:
        if i in to_remove_set:
            pass

def test_list():
    for i in all_ids:
        if i in to_remove:
            pass


print('starting')
print('testing list', timeit.timeit(test_list, number=1))
print('testing set', timeit.timeit(test_set, number=1))

结果:

testing list 227.91903045598883
testing set 0.14897623099386692

set 版本耗时 149 毫秒； list 版本需要 228 秒。现在这些都是小数字:在你的例子中，你有 5000 万条输入记录，而我有 100 万条；因此，您需要将 testing set 时间乘以 50:对于您的数据集，大约需要 7.5 秒。

另一方面，列表版本需要将时间乘以 50 * 17 - 不仅输入记录多 50 倍，而且要匹配的记录多 17 倍。因此我们得到 227 * 50 * 17 = 192950。

因此，您的算法需要 2.2 天才能完成使用正确的数据结构可以在 7.5 秒内完成的事情。当然，这并不意味着您可以在 7.5 秒内扫描整个 50 GB 的文档，但也可能不会超过 2.2 天。所以我们从:

             2 days                           2.2 days 
 |reading and writing the files||------- doing id in list ------|

类似于

             2 days            7.5 seconds (doing id in set)
 |reading and writing the files||