Python os.system call slow ~ 1/2 second

Question

Я пишу скрипт, чтобы найти все дубликаты файлов в двух разных файлах. Скрипт отлично работает, за исключением того, что он слишком медленный, чтобы практично использовать большое количество файлов (> 1000). Профилирование моего скрипта cProfile показало, что одна строка в моем коде отвечает за почти все время выполнения.

Линия является вызовом os.system():

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

Этот вызов внутри для цикла, который вызывается примерно 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 

Update: Спасибо за обратную связь! Я попытаюсь рассмотреть большинство ваших комментариев и дать дополнительную информацию. @Iarsmans. Вы абсолютно правы, что мои вложенные в петлевые масштабы с n² я уже выяснил, что могу сделать то же самое, используя словарь или набор и выполнять операции. Но даже накладные расходы на этот «плохой» алгоритм незначителен для времени, затрачиваемого на запуск os.system. Фактическое предложение if запускается примерно один раз для каждого имени файла (я ожидаю, что для каждого имени файла будет только один дубликат). Таким образом, os.system получает только N раз, а не N² раз, но даже для этого линейного времени это не достаточно быстро.

@ Iarsman и @Alex Reynolds: Причина, по которой я не выбрал решение хэширования, как вы предлагаете, заключается в том, что в случае использования я предполагаю, что сравниваю меньшее дерево каталогов с большим и хешируя все файлы в для большего дерева потребуется очень много времени (так как это могут быть все файлы в целом разделе), в то время как мне требуется только фактическое сравнение на небольшой части файлов.

@abarnert: Причина, по которой я использую shell = True в команде вызова, - это просто потому, что я начал с os.system, а затем прочитал, что лучше использовать subprocess.call, и это был способ преобразования между ними. Если есть лучший способ запустить команду cmp, я хотел бы знать. Причина, по которой я аргументирую аргументы, состоит в том, что у меня были проблемы с пробелами в именах файлов, когда я просто передал результат os.path.join в команде.

Спасибо за ваше предложение, я изменю его if cmpout == 0

@Gabe: Я не знаю, как ко времени команды Баша, но я считаю, что это работает намного быстрее, чем половина второго, когда я просто запустить команда.

Я сказал, что ограничение байтов не имеет большого значения, потому что, когда я изменил его только на 10Kib, он изменил общее время выполнения моего тестового прогона до 290 секунд вместо около 300 секунд. Причина, по которой я соблюдала ограничение, - это не сравнивать сравнение действительно больших файлов (например, видеофайлов 1GiB).

Update 2: Я следовал @abarnert предложение «s и изменил вызов:

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

Время выполнения для моего тестового сценария в настоящее время снизилась до 270S от 300seconds. Пока недостаточно, но это начало.

Answer 1

Для этого вы используете неправильный алгоритм. Сравнение всех пар файлов занимает thetas; время (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 хешу, затем фильтрует файлы во втором каталоге по наличию файлов с тем же хэшем в индексе, построенном из первого каталога. Несколько очевидных оптимизаций оставлены в качестве упражнения для читателя :)

Функция предполагает, что каталоги содержат только обычные файлы или символические ссылки, и она считывает файлы в память за один раз (но это не так сложно исправить).

(SHA-512 фактически не гарантирует равномерность файлов, поэтому полное сравнение может быть установлено в качестве меры резервного копирования, хотя вам будет трудно найти два файла с одним и тем же SHA-512.)