Python os.system 调用慢约 1/2 秒

Question

我正在编写一个脚本来查找两个不同文件树中的所有重复文件。该脚本运行良好，但速度太慢，无法在处理大量文件(> 1000)时使用。使用 cProfile 对我的脚本进行分析后发现，代码中的一行几乎占据了所有的执行时间。

该行是对 os.system() 的调用:

cmpout = os.system("cmp -s -n 10MiB %s %s" % (callA, callB));

此调用位于 for 循环内，如果我有 N 个相同的文件，则该循环会被调用大约 N 次。平均执行时间0.53秒

  ncalls  tottime  percall  cumtime  percall filename:lineno(function)        
  563  301.540    0.536  301.540    0.536 {built-in method system}

这当然很快就会增加一千多个文件。我尝试通过用子进程模块的调用替换它来加速它:

cmpout = call("cmp -s -n 10MiB %s %s" % (callA, callB), shell=True); 

但这具有几乎相同的执行时间。我也尝试过减少 cmp 命令本身的字节限制，但这只能节省很少的时间。

有什么办法可以加快速度吗？

我正在使用的完整功能:

def dirintersect(dirA, dirB):
    intersectionAB = []
    filesA = listfiles(dirA);
    filesB = listfiles(dirB);
    for (pathB, filenameB) in filesB:
        for (pathA, filenameA) in filesA:
            if filenameA == filenameB:
                callA = shlex.quote(os.path.join(pathA, filenameA));
                callB = shlex.quote(os.path.join(pathB, filenameB));
                cmpout = os.system("cmp -s -n 10MiB %s %s" % (callA, callB));
                #cmpout = call("cmp -s -n 10MiB %s %s" % (callA, callB), shell=True); 
                if cmpout is 0:
                    intersectionAB.append((filenameB, pathB, pathA))                
    return intersectionAB

更新:感谢您的所有反馈!我将尽力解决您的大部分评论并提供更多信息。 @Iarsmans。你说得对，我的嵌套 for 循环与 n² 成比例，我自己已经发现我可以通过使用字典或集合并执行集合操作来完成相同的操作。但即使是这种“糟糕”算法的开销对于运行 os.system 所需的时间来说也是微不足道的。实际的 if 子句对每个文件名大约触发一次(也就是说，我希望每个文件名只有一个重复项)。因此 os.system 只运行了 N 次，而不是 N² 次，但即使对于这个线性时间，它也不够快。

@Iarsman 和 @Alex Reynolds:我没有选择像您建议的那样的散列解决方案的原因是因为在使用案例中，我设想我将较小的目录树与较大的目录树进行比较，并对目录中的所有文件进行散列较大的树将花费很长时间(因为它可能是整个分区中的所有文件)，而我只需要对一小部分文件进行实际比较。

@abarnert:我在 call 命令中使用 shell=True 的原因很简单，因为我从 os.system 开始，然后读到最好使用 subprocess.call，这也是在两者之间进行转换的方法。如果有更好的方法来运行 cmp 命令，我想知道。我 qoute 参数的原因是因为当我刚刚在命令中传递 os.path.join 结果时，我遇到了文件名中空格的问题。

感谢您的建议，我将其更改为if cmpout == 0

@Gabe:我不知道如何计算 bash 命令的时间，但我相信当我运行该命令时，它的运行速度比半秒快得多。

我说字节限制并不重要，因为当我将其更改为仅 10Kib 时，它将测试运行的总执行时间更改为 290 秒，而不是大约 300 秒。我保留限制的原因是为了防止它比较非常大的文件(例如 1GiB 视频文件)。

更新 2: 我已遵循 @abarnert 的建议并将调用更改为:

cmpout = call(["cmp", '-s', '-n', '10MiB', callA, callB])

我的测试场景的执行时间现已从 300 秒降至 270 秒。虽然还不够，但这是一个开始。

Answer 1

您使用了错误的算法来执行此操作。比较所有文件对需要 n 个文件的 Θ(n²) 时间，而通过对文件进行哈希处理可以在线性时间内获得两个目录的交集:

from hashlib import sha512
import os
import os.path

def hash_file(fname):
    with open(fname) as f:
        return sha512(f.read()).hexdigest()

def listdir(d):
    return [os.path.join(d, fname) for fname in os.listdir(d)]

def dirintersect(d1, d2):
    files1 = {hash_file(fname): fname for fname in listdir(d1)}
    return [(files1[hash_file(fname)], fname) for fname in listdir(d2)
            if hash_file(fname) in files1]

此函数循环遍历第一个目录，存储按 SHA-512 哈希索引的文件名，然后根据第一个目录构建的索引中是否存在具有相同哈希的文件来过滤第二个目录中的文件。一些明显的优化留给读者作为练习:)

该函数假设目录仅包含常规文件或这些文件的符号链接(symbolic link)，并且它会将文件一次性读入内存(但这并不难修复)。

(SHA-512 实际上并不保证文件相等，因此可以安装完整比较作为备份措施，尽管您很难找到具有相同 SHA-512 的两个文件。)