Как ускорить сравнение?

Question

[pinguine]

import sys
import os


def get_all_files(dir):
    path_f = []
    for dirs, subdirs, files in os.walk(dir):
        for f in files:
            if not f.startswith("."):
                path = os.path.join(dirs, f)
                path_f.append(path)
    return path_f


def are_files_duplicates(file1, file2):
    return os.path.basename(file1) == os.path.basename(file2) and os.path.getsize(file1) == os.path.getsize(file2)


def find_duplicates(dir):
    if not os.path.exists(dir):
        print("Такой директории не существует")
        return None
    path_f = get_all_files(dir)
    for counter_1 in range(0, len(path_f)):
        for counter_2 in range(counter_1+1, len(path_f)):
            if are_files_duplicates(path_f[counter_1], path_f[counter_2]):
                    print("Файл {} дублируется с файлом {}".format(path_f[counter_2], path_f[counter_1]))


if __name__ == '__main__':
    try:
        find_duplicates(sys.argv[1])
    except IndexError:
        print("Укажите название файла")

Сейчас find_duplicates работает за квадратичное время – сравнивает каждый файл с каждым. Как это можно ускорить?

Answer 1

[longclaps]

Самый быстрый и самый жадный до памяти способ вот:

from collections import defaultdict

d = defaultdict(list)
for file in (чо-то там):
    d[basename(file), size(file)].append(file)
for (nm, sz), flist in d.items():
    if len(flist) > 1:
        print("**", nm, sz, "**")
        for file in flist:
            print(file)

Comments

[RedSkotina]

а разве тут не происходит сравнение с ключами при вставке в словарь?
тоесть тожесамое сравнение каждого файла с каждым, только вид сбоку

[javedimka]

RedSkotina: нет, не тоже самое

[longclaps]

RedSkotina:
Почитай про "вид сбоку" ))
https://habrahabr.ru/post/247843/
Незакомые слова вроде "хэш-таблицы" ищи в гугле, это - важное ))

[RedSkotina]

longclaps: а хэш таблицы строятся волшебным образом мгновенно? а сравниваются хэши тоже мгновенно ?

[longclaps]

RedSkotina:
Нет, не мгновенно, а за линейное время от числа элементов таблицы. Нет, не мгновенно, а за константное время.
Кончай кидать предъявы, потрудись сам хоть в чём-то разобраться.

[RedSkotina]

longclaps: ну я пока не получил внятного ответа почему это не вид сбоку.
а посылать в гугл на сайте вопросов и ответов. кажется кто то не понимает сути сайта.

[longclaps]

RedSkotina: Скудоумным не подаю.

Answer 2

[xmoonlight]

Попробуйте адаптировать этот алгоритм (Сообщение #7) для перебора без повторов.