16.12.2023 15:30
thsiganenko 37 3600 Источник

История начинается с несложной задачи и небольшого Python приложения.

Несложная задача это периодическое удаление дубликатов файлов из указанных каталогов. Изначально она возникла из следующих условий. Есть домашнее хранилище фотографии и видео, в котором определен порядок хранения файлов по тематике, датам и т.д. И есть источники для пополнения этого хранилища: смартфоны, фотоаппараты, контент из сети, электронной почты и т.д. Синхронизации источников контента и хранилища нет. Периодически со смартфонов и фотоаппаратов скидываются все хранящиеся там файлы на жесткий диск компьютера, и получается набор каталогов, в которых оказываются как те файлы, что уже есть в хранилище, так и новые файлы. И чтобы поместить в хранилище новые файлы, их нужно каким-то образом отделить их от тех, что уже сохранены. Самый простой способ, который пришел в голову, это удалить дубликаты из каталогов "пополнения", а с остатком уже работать.

С источников файлы не удаляются пока в этом не появится острая необходимость, в первую очередь потому, что это "естественная" резервная копия. Ну и бывает удобно иметь какие-то фотографии и видео у себя под рукой.

В процессе своего повествования, постараюсь пояснить принятые мной решения, некоторые из которых прямо напрашиваются на решение иным способом.

Определение технического задания

Первый шаг на пути к успеху, это формализация условия задачи, которую необходимо решить, и создание "технического задания". Есть каталог с "образцовыми" файлами (source), то есть это те файлы, дубликаты которых мы хотели бы найти и удалить, так же у нас есть один или более каталогов с файлами, среди которых нужно эти дубликаты найти и удалить (target). Как каталог source, так и каталоги target могут иметь вложенные каталоги. Кроме того, если в процессе удаления дубликатов окажется, что каталог любого уровня вложенности в target оказывается пустым, то его тоже необходимо удалить.

"Классические" решения по дедупликации файлов, как правило, работают с одним каталогом, и внутри него ищут дубликаты, а дальше механика работы с ними может отличаться, где-то дубликат заменяют на "жесткую" ссылку, где-то удаляют по порядку нахождения, то есть первый найденный остается, остальные удаляются, где-то выбор предлагают сделать пользователю в красивом графическом интерфейсе и т.д.

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

Интерфейс CLI должен выглядеть следующим образом:

$ dedublicate /home/user/media /home/user/backup/phone /home/user/backup/camera

где /home/user/media - это медиа хранилище, которое будет источником для образцов файлов, а /home/user/backup/phone и /home/user/backup/camera, это каталоги из которых будут удалены дубликаты. Каталогов target может быть передано любое количество.

Дополнительные ограничения, приложение должно быть написано на чистом Python без использования сторонних зависимостей, только стандартная библиотека.

Определять являются ли файлы дубликатами будем с помощью сравнения контрольных сумм CRC файлов. То есть фактически будем сравнивать файлы по содержимому.

Циклический избыточный код (англ. Cyclic redundancy check, CRC) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных.

Алгоритм работы приложения будет следующим:

  • обходим дерево каталогов source

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

  • после завершения обхода дерева каталогов source, начинаем обходит деревья каталогов target, но в этот раз идем в глубину

  • если встретили файл, вычисляем для него контрольную сумму

  • проверяем, если ли в нашем множестве вычисленных контрольных сумм контрольная сумма для этого файла, если есть, то удаляем файл считая его дубликатом, если нет, оставляем и продолжаем обход дерева

  • при обходе в глубину, когда будем возвращаться обратно, нужно понять, являются ли каталоги пустыми, после удаления дубликатов или нет, и если являются, то удалить.

Разработка интерфейса командной строки (CLI)

Процесс разработки будет проходит, если можно так выразиться, "сверху вниз" по шагам.

Начнем с интерфейса командной строки, а потом уже перейдем к деталям. Поскольку есть ограничение на использование только стандартной библиотеки Python, то разработка CLI интерфейса будет с использованием стандартного модуля argparse

#!/usr/bin/env python3
"""Приложение для удаления дубликатов и пустых каталогов"""

import argparse
import sys

from pathlib import Path
from typing import List


def main(source: Path, target: List[Path]):
    pass


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description=__doc__)

    parser.add_argument('source', type=Path,
        help='путь к каталогу с образцами файлов')

    parser.add_argument('target', type=Path, nargs='+',
        help='пути к каталогам, из которых нужно удалить дубликаты')

    args = parser.parse_args()

    exit_code = main(args.source, args.target)

    sys.exit(exit_code)

Первый вопрос, который может возникнуть по поводу данного кусочка кода, почему типы аргументов функции main аннотированы с использованием модуля typing, а не в современном стиле? Особенно учитывая, что начиная с версии 3.9 class typing.List помечен как deprecated.

Ответ, в целях обратной совместимости, чтобы приложение можно было запускать на интерпретаторе Python начиная с версии 3.6.

Если приложение не планируется запускать на версиях интерпретатора младше чем 3.9, то объявление функции следует написать следующим образом:

def main(source: Path, target: list[Path]):
	pass

Теперь если запустить этот кусочек кода из командной строки с ключом --help, то будет получен следующий вывод:

usage: dedublicate.py [-h] source target [target ...]

Приложение для удаления дубликатов и пустых каталогов

positional arguments:
  source      путь к каталогу с образцами файлов
  target      пути к каталогам, из которых нужно удалить дубликаты

options:
  -h, --help  show this help message and exit

Очевидный недостаток, это "смесь языков", лучше все же сохранять консистентное состояние, и в данном случае, проще перевести на английский, русские строки используя Google переводчик.

#!/usr/bin/env python3
"""Application to remove duplicates and empty directories"""

import argparse
import sys

from pathlib import Path
from typing import List


def main(source: Path, target: List[Path]) -> int:

    return 0


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description=__doc__)

    parser.add_argument('source', type=Path,
        help='path to the directory with sample files')

    parser.add_argument('target', type=Path, nargs='+',
        help='paths to directories from which duplicates need to be removed')

    args = parser.parse_args()

    exit_code = main(args.source, args.target)

    sys.exit(exit_code)

Теперь вывод приобретает достойный вид:

usage: dedublicate.py [-h] source target [target ...]

Application to remove duplicates and empty directories

positional arguments:
  source      path to the directory with sample files
  target      paths to directories from which duplicates need to be removed

options:
  -h, --help  show this help message and exit

Настраиваем логирование

Потенциально, разрабатываемое приложение может работать достаточно долго, и было бы не плохо понимать, что оно вообще работает, и в какой стадии находится.

Для информирования пользователя о ходе процесса обработки будет использован модуль стандартной библиотеки logging. Данные будет выводить на стандартный поток вывода ошибок stderr.

import logging

logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)
formatter = logging.Formatter('%(asctime)s [%(levelname)s] %(message)s')
handler = logging.StreamHandler(sys.stderr)
handler.setFormatter(formatter)
logger.addHandler(handler)

В формате записи лога нет наименования файла, а точнее модуля, в котором произошло событие, поскольку модуль будет единственным.

Описываем основную логику приложения

Как мы уже отмечали в начале, базовый алгоритм можно свести к двум шагам:

  • необходимо создать множество контрольных сумм для "образцовых" файлов

  • необходимо удалить дубликаты из каталогов target

На данном этапе этого достаточно, чтобы описать эти действия в коде:

def main(source: Path, targets: List[Path]) -> int:

    logger.info('Creating set of hashes for "%s" has begun', source)
    hashes = create_set_of_crc(source)

    for target in targets:
        logger.info('Processing of the target directory %s has begun', target)
        if source.resolve() == target.resolve():
            logger.error('The source and target directory are the same: %s',
                         source.resolve())
            continue

        remove_duplicates(target, hashes)

    return 0

Хотелось обратить внимание на один важный момент, который не упоминался ранее.

А что будет если в качестве target будет передан путь source?

В этом случае, наше приложение, которое на первом шаге получило информацию о образцах файлов, просто методично очистит нам каталог source, так как сочтет все файлы дубликатами. Именно для этого случая добавлена проверка на совпадение пути source и target, причем используется функция получения абсолютного пути, потому что можно легко передать два различных относительных пути, которые будут указывать на один и тот же объект.

Ну и для того, чтобы код можно было вообще запустить, объявим функции, которые мы использовали в этом фрагменте кода, и опишем их сигнатуру:

def create_set_of_crc(source: Path) -> set:
    """Return a set of files hashes for the path"""


def remove_duplicates(target: Path, hashes: set):
    """Remove file duplicates and empty dirs by the path""

Функция создания множества контрольных сумм

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

  • обойти дерево каталогов source

  • вычислить контрольную сумму для каждого файла

И тут возникает вопрос, как это лучше организовать. В голову приходят два варианта:

  • делать это одновременно, то есть обходим дерево каталогов и как только встретили файл, начинаем вычислять его контрольную сумму;

  • разделить эти две операции, то есть сначала составить список путей файлов, а потом передать этот список функции для вычисления контрольных сумм.

Следующая задача, как обходить дерево каталогов:

  • описать свою рекурсивную функцию;

  • воспользоваться готовой функцией walk из модуля os.

Мой выбор при решении этих двух задач пал на вторые варианты, то есть разделить операции обхода дерева каталогов и вычисление контрольных сумм; обходить дерево каталогов с использование готовой функции walk.

В результате получилась следующая функция:

import os

def create_set_of_crc(source: Path) -> set:
    """Return a set of files hashes for the path"""

    logger.info('Directory tree traversal %s started', source)
    paths = [Path(root, filename)
                for root, __, files in os.walk(source, topdown=False)
                for filename in files]

    logger.info('Checksums calculation for a set of paths has begun')
    hashes = set(calculate_crc(path) for path in paths)

    if None in hashes:
        hashes.remove(None)

    return hashes

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

Первая мысль, выбросить исключение, и на уровне выше его обработать. Но уровнем выше мы использовали генераторное выражение, и внутри не получится перехватить и обработать исключение. С другой стороны, можно обработать исключение внутри функции, и в качестве значение вместо контрольной суммы вернуть None:

def calculate_crc(path: Path) -> Optional[str]:
    """Returns CRC file for the path"""

С учетом вышесказанного, нужно внести изменения в функцию create_set_of_crc, и перед возвращением из нее значений, из множества контрольных сумму удалить None, если он есть в множестве:

def create_set_of_crc(source: Path) -> set:
    """Return a set of files hashes for the path"""
    paths = [Path(root, filename)
                for root, __, files in os.walk(source, topdown=False)
                for filename in files]

    hashes = set(calculate_crc(path) for path in paths)

    if None in hashes:
        hashes.remove(None)

    return hashes

Функция вычисления контрольной суммы

Для вычисление контрольной суммы воспользуемся функцией модуля hashlib стандартной библиотеки.

import hashlib

READING_BLOCK_SIZE = 4096

def calculate_crc(path: Path) -> Optional[str]:
    """Returns CRC file for the path"""
    crc = hashlib.md5()
    try:
        with open(path, 'rb') as fd:
            while True:
                chunk = fd.read(READING_BLOCK_SIZE)
                if not chunk:
                    break
                crc.update(chunk)
    except OSError as err:
        logger.error("Processing attempt: %s failed with error: %s", path, err)
        return None

    return crc.hexdigest()

К этой функции может возникнуть много вопросов, на которые сложно ответить полностью аргументированно.

Например, почему выбран алгоритм MD5, а не какой-либо другой? Если кратко, то этот алгоритм кажется достаточным для решения поставленной задачи, поскольку вероятность коллизии при работе с файлами ничтожна мала.

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

def calculate_crc(path: Path) -> Optional[str]:
    """Returns CRC file for the path"""

    crc = hashlib.md5()
    try:
        crc.update(path.read_bytes())
    except OSError as err:
        logger.error("Processing attempt: %s failed with error: %s", path, err)
        return None

    return crc.hexdigest()

Но вот только что произойдет, если вдруг такой функции попадется файл объемом больше, чем доступная оперативная память? А если этот файл в два раза больше оперативной памяти? Хотя в целом, такой вариант остается работоспособным. С высокой долей вероятности интерпретатор Python и операционная система справятся с данной задачей, но я предпочел более безопасный вариант с чтением файлов по кусочкам.

Почему размер одного блока для чтение READING_BLOCK_SIZE равен 4096 байт? Потому что кажется это количество байт равное размеру одного блока на файловой системе.

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

Функция удаления дубликатов

Остался последний шаг на пути к цели. Нужно реализовать функцию remove_dublicates.

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

def remove_duplicates(target: Path, hashes: set):
    """Remove file duplicates and empty dirs by the path"""

    for root, folders, files in os.walk(target, topdown=False):
        for filename in files:
            target_file = Path(root, filename)
            crc = calculate_crc(target_file)
            if crc in hashes:
                try:
                    os.remove(target_file)
                    logger.info('File %s was removed', target_file)
                except OSError:
                    logger.error('Deleting of file %s failed', target_file)

        for folder in folders:
            target_folder = Path(root, folder)
            try:
                os.rmdir(target_folder)
                logger.info('Empty dir %s was removed', target_folder)
            except OSError:
                pass

К этому небольшому кусочку кода тоже возникает целый ряд вопросов.

И первый из них - что происходит с обработкой каталогов? Может показаться, что данный фрагмент кода при запуске просто удалит все каталоги, но это нет так. Этот код использует особенность функции os.rmdir. Если каталог не пустой, то попытка его удаление приведет к выбрасыванию исключения. Таким образом этот кусочек кода действительно пытается удалить все каталоги, но в результате удалит только действительно пустые каталоги. Это один из принципов Python: "Проще просить прощения, чем разрешения". Попытались удалить не пустой каталог, извинились, в форме обработанного исключения, и пошли дальше.

Прекрасно понимаю, что это решение может показаться очень и очень спорным. Скорее всего можно найти более изящное решение.

Заключение

Осталось только взглянуть по полный текст приложения, которое получилось, и можно использовать его при решении поставленных задач.

Полный текст приложения
#!/usr/bin/env python3
"""Application to remove duplicates and empty directories"""

import argparse
import sys
import logging
import os
import hashlib

from pathlib import Path
from typing import List, Optional


logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)
formatter = logging.Formatter('%(asctime)s [%(levelname)s] %(message)s')
handler = logging.StreamHandler(sys.stderr)
handler.setFormatter(formatter)
logger.addHandler(handler)


READING_BLOCK_SIZE = 4096


def calculate_crc(path: Path) -> Optional[str]:
    """Returns CRC file for the path"""
    crc = hashlib.md5()
    try:
        with open(path, 'rb') as fd:
            while True:
                chunk = fd.read(READING_BLOCK_SIZE)
                if not chunk:
                    break
                crc.update(chunk)
    except OSError as err:
        logger.error("Processing attempt: %s failed with error: %s", path, err)
        return None

    return crc.hexdigest()


def create_set_of_crc(source: Path) -> set:
    """Return a set of files hashes for the path"""

    logger.info('Directory tree traversal %s started', source)
    paths = [Path(root, filename)
                for root, __, files in os.walk(source, topdown=False)
                for filename in files]

    logger.info('Checksums calculation for a set of paths has begun')
    hashes = set(calculate_crc(path) for path in paths)

    if None in hashes:
        hashes.remove(None)

    return hashes


def remove_duplicates(target: Path, hashes: set):
    """Remove file duplicates and empty dirs by the path"""

    for root, folders, files in os.walk(target, topdown=False):
        for filename in files:
            target_file = Path(root, filename)
            crc = calculate_crc(target_file)
            if crc in hashes:
                try:
                    os.remove(target_file)
                    logger.info('File %s was removed', target_file)
                except OSError:
                    logger.error('Deleting of file %s failed', target_file)

        for folder in folders:
            target_folder = Path(root, folder)
            try:
                os.rmdir(target_folder)
                logger.info('Empty dir %s was removed', target_folder)
            except OSError:
                pass


def main(source: Path, targets: List[Path]) -> int:

    logger.info('Creating set of hashes for "%s" has begun', source)
    hashes = create_set_of_crc(source)

    for target in targets:
        logger.info('Processing of the target directory %s has begun', target)
        if source.resolve() == target.resolve():
            logger.error('The source and target directory are the same: %s',
                         source.resolve())
            continue

        remove_duplicates(target, hashes)

    return 0


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description=__doc__)

    parser.add_argument('source', type=Path,
        help='path to the directory with sample files')

    parser.add_argument('targets', type=Path, nargs='+',
        help='paths to directories from which duplicates need to be removed')

    args = parser.parse_args()

    exit_code = main(args.source, args.targets)

    sys.exit(exit_code)

Остается еще не мало вопросов, оставленных без ответов. Например, почему нет тестов? Каким образом можно поискать узкие места в приложении и ускорить их?

Попытки ускорить выполнение приложения

Ответом на вопрос: "Можно ли сократить время первоначального расчета контрольных сумм для "образцового" каталога, за счет многопроцессной обработки?", - может являться небольшое изменение функции create_set_of_crc, в результате чего она приобретает следующий вид:

from concurrent.futures import ProcessPoolExecutor

def create_set_of_crc(source: Path) -> set:
    """Return a set of files hashes for the path"""

    logger.info('Directory tree traversal %s started', source)
    paths = [Path(root, filename)
                for root, __, files in os.walk(source, topdown=False)
                for filename in files]

    logger.info('Checksums calculation for a set of paths has begun')
    with ProcessPoolExecutor() as executor:
        hashes = set(executor.map(calculate_crc, paths))

    if None in hashes:
        hashes.remove(None)

    return hashes

Вот только как оценить эффективность данного решения? Эта оптимизация исходит из того, что нам нужно выполнять вычисления на CPU, а действительно ли это было узким местом?

В ходе тестирования оказалось, что при большом количестве файлов ProcessPoolExecutor показывает результат по времени хуже, чем при работе в одни поток. В попытках выяснить причину этого явления, попалась статья Jason Brownlee от 09.02.2022 года ProcessPoolExecutor Example in Python. Оказывается, что прежде чем передать задания на обработку дочерним процессам, родительский процесс производит подготовку, и пока он не подготовит все задачи, он не отдаст ни одного задания в работу. В результате это подготовка для большого числа заданий поглощает всю выгоду от многопроцессной обработки. Автор также предлагает некоторое решение этой проблемы, но я решил попробовать воспользоваться ThreadPoolExecutor.

Таким образом код функции create_set_of_crcпревратился в следующий:

from concurrent.futures import ProcessPoolExecutor

def create_set_of_crc(source: Path) -> set:
    """Return a set of files hashes for the path"""

    logger.info('Directory tree traversal %s started', source)
    paths = [Path(root, filename)
                for root, __, files in os.walk(source, topdown=False)
                for filename in files]

    logger.info('Checksums calculation for a set of paths has begun')
    with ThreadPoolExecutor() as executor:
        hashes = set(executor.map(calculate_crc, paths))

    if None in hashes:
        hashes.remove(None)

    return hashes

В результате получено то ускорение, которое ожидалось. Если говорить очень грубо, поскольку измерения производительности занятие очень непростое, то сократить время обработки удалось в 3,5 раза, при условии, что каталог source 338 039 файлов в среднем размером около 71,5Кб, а вот каталог target просто пустой.

Опять же, это пример, неправильного подхода к оптимизации, поскольку не проводилось профилирование, не были найдены узкие места. Это не инженерный, а рабоче-крестьянский подход, но он тоже имеет право на существование.

P.S.

В этой статья предпринята попытка показать, что происходит в голове того, кто занимается написанием даже самых простых скриптов. Надеюсь, что мне удалось хоть в какой-то степени показать, что же такое практическое решение задачи.

Первоначально на написание приложения ушло менее 30 минут, но вот для того, чтобы описать этот процесс потребовалось несколько дней.

Дополнение к статье

Данное дополнение появилось из обсуждения статьи в комментариях. Комментарий пользователя @VT100 заставил задуматься, а действительно ли вычисление контрольной суммы с помощью алгоритма MD5 достаточно для принятия решения об уникальности файла? Действительно ли вероятность коллизии настолько мала, что ей можно пренебречь?

В результате небольшого исследования была найдена статья "Cautions (or why it’s hard to write a dupefinder)" (прим. статья на английском), в разделе "Collision Robustness" которой показан практический пример того, когда для двух разных файлов контрольная сумма MD5 совпадает, а вот SHA1 уже отличается. При этом размер файлов также совпадает.

$ mkdir test && cd test

$ wget http://web.archive.org/web/20071226014140/http://www.cits.rub.de/imperia/md/content/magnus/order.ps
$ wget http://web.archive.org/web/20071226014140/http://www.cits.rub.de/imperia/md/content/magnus/letter_of_rec.ps

$ ls -l
total 8
-rwxrwxrwx 1 user user 2029 Jun 19  2007 letter_of_rec.ps
-rwxrwxrwx 1 user user 2029 Jun 19  2007 order.ps

$ md5sum *
a25f7f0b29ee0b3968c860738533a4b9  letter_of_rec.ps
a25f7f0b29ee0b3968c860738533a4b9  order.ps

$ sha1sum *
07835fdd04c9afd283046bd30a362a6516b7e216  letter_of_rec.ps
3548db4d0af8fd2f1dbe02288575e8f9f539bfa6  order.ps

$ sha256sum *
de4e4c6e2b94e95a3c5bd72a9a6af29bc5f83bf759325d9921943a6fc08ea245  letter_of_rec.ps
077046dd66015e05c3e03a43a6e4de129038e0701de5a4103fc7ed91c3782d06  order.ps

$ diff --binary letter_of_rec.ps order.ps
Binary files letter_of_rec.ps and order.ps differ

$ stat *
  File: letter_of_rec.ps
  Size: 2029            Blocks: 8          IO Block: 4096   regular file
Device: eh/14d  Inode: 35184372088972066  Links: 1
Access: (0777/-rwxrwxrwx)  Uid: ( 1000/ user)   Gid: ( 1000/ user)
Access: 2023-12-17 03:40:20.897605000 +0500
Modify: 2007-06-19 14:01:09.000000000 +0600
Change: 2023-12-17 03:37:36.616898300 +0500
 Birth: -
  File: order.ps
  Size: 2029            Blocks: 8          IO Block: 4096   regular file
Device: eh/14d  Inode: 59672695062770586  Links: 1
Access: (0777/-rwxrwxrwx)  Uid: ( 1000/ user)   Gid: ( 1000/ user)
Access: 2023-12-17 03:40:20.897605000 +0500
Modify: 2007-06-19 14:01:09.000000000 +0600
Change: 2023-12-17 03:37:28.041841500 +0500
 Birth: -

И вот так, в качестве приятной неожиданности, удалось продемонстрировать еще один этап разработки приложения - выявление ошибок. Который, в данном случае, стал возможен благодаря совместной работе, умению одного участника обратить на внимание на потенциальную проблему, и способности другого участника услышать проблему и предпринять какие-либо действия.

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

Комментарии (37)


  1. yarolig
    16.12.2023 15:48
    #26273556

    Есть программка jdupes под Linux. Делает примерно то же самое. Из заметных оптимизаций - она сначала собирает все размеры файлов и считает CRC только если есть файлы одного размера.

    Сам я её пользуюсь примерно для того же (выкидывания одинаковых файлов). Запускаю примерно так:

    jdupes --recurse --linkhard /path/to/photo/storage


    1. thsiganenko Автор
      16.12.2023 15:48
      #26273576

      Спасибо за интересную идею, в части оптимизации подсчета CRC файлов, в случае, если различается размер файлов. На вскидку можно собирать словарь, ключом в котором будет размер файла, а значением список путей. Интересно, какой будет эффект от такой оптимизации, насколько я понимаю, у нас потенциально может сократится количество операций полного чтения файлов для вычисления CRC.

      Опять же плата за такую оптимизацию - это усложнение логики работы приложения.


      1. sixxio
        16.12.2023 15:48
        #26273666

        Конечно, во многом это зависит от файлов, с которыми работаем.
        Но скорее всего контрольная сумма будет считаться сильно реже, так как одинаковый размер файла вплоть до бита встречается не так уж часто.
        Условно, даже два очень похожих внешне кадра не будут иметь одинаковый размер в силу механизмов под капотом у формата .jpeg.


      1. MountainGoat
        16.12.2023 15:48
        #26273768

        Если вы пробегаетесь по дереву файлов правильно, например, так:

        path = Path("c:\files")
for p in path.rglob("*"):
     do_it(p)

        То у вас размер файла считывается в память вместе с именем, и проверять его несравнимо быстрее, чем дочитывать что-либо с диска.


      1. longclaps
        16.12.2023 15:48
        #26274210

        Эх, был и я когда-то молод, учил питон, а еще качал без меры книжки. Глаза завидущие, руки загребущие. Дубликаты случались. Ну и написал вот это. Это не cli, это для выполнения в IDE, мне так удобно. Смотрел на вывод, выбирал что удалять. Писал для себя, давно было, учился, тапками не кидаться.

        Не так чтобы очень сложно. 
        from os import walk
from os.path import basename, getsize, islink, join
from hashlib import md5
from collections import defaultdict


def duplicates(*roots, findLink=False, extensions=(".pdf", ".djvu", ".djv")):
    """
    usage: duplicates("папка1", "папка2", "папка3")
    """
    uniq_sizes = defaultdict(list)
    for root in roots:
        for pth, folder, files in walk(root):
            for name in [join(pth, f) for f in files if f.lower().endswith(extensions)]:
                if findLink or not islink(name):
                    uniq_sizes[getsize(name)].append(name)
    if uniq_sizes[0]:
        print("файлы-пустышки:", *sorted(uniq_sizes.pop(0)), sep="\n", end="\n\n")
    for v in [v for v in uniq_sizes.values() if 1 < len(v)]:
        duples = defaultdict(list)
        for name in v:
            with open(name, "rb") as f:
                duples[md5(f.read()).hexdigest()].append(name)
        for names in [v for v in duples.values() if 1 < len(v)]:
            print(min(map(basename, names), key=len))
            for name in names:
                print(f'rm "{name}"')
            print()

        ps Сейчас запустил, глянул - мама дорогая, что творится-то!


    1. plFlok
      16.12.2023 15:48
      #26273646

      когда-то писал похожее для себя.

      там можно ещё промежуточную оптимизацию ввести: при совпадении размеров считать crc от первых N килобайт, и лишь при совпадении даже этих crc можно уже сравнить полное содержимое файлов, а не считать crc от всего объёма.

      Зачем так: моя экшн-камера gopro hero black 8 из-за особенностей своей файловой системы нарезает все видео строго кусками не больше 4гб, и в результате у меня терабайты заполнены одинаковыми поразмеру видео. Считать crc32 от всего терабайта - долго, результат заранее почти всегда ясен.


      1. thsiganenko Автор
        16.12.2023 15:48
        #26273722

        Спасибо за комментарий! Ваша идея тоже очень интересна, и думаю, что так же как и те оптимизации, что предложили выше, оно даст свою выгоду.

        Когда отвечал на первый комментарий, то отреагировал на него именно как человек, который разрабатывает приложение, и, наверное, это естественная реакция для тех, кто любит заниматься разработкой, находить различные способы решения задачи, пробовать ускорить время выполнения приложения или уменьшить потребляемые приложением ресурсы. Вот только идея статьи, которая легла в ее основы была иной.

        Идея была постараться на относительно простой задаче показать, что даже небольшая утилита командной строки требует комплексного подхода. Необходимо подумать о интерфейсе, то есть о том, как пользователь будет использовать данное приложение. Следующим шагом нужно подумать, как дать возможность пользователю понять, что приложение работает и выполняет полезную работу, при этом дать ему возможность в случает необходимости избавиться от вывода. Важно, еще перед началом разработки понять задачу, формализовать ее, и потом приступать к решению.

        Целью статьи не являлось создание самого эффективного способа решения обозначенной задачи, хотя это было бы очень амбициозным проектом, а показать способ начинающим разработчикам, как можно начать процесс разработки. Видимо мне это не удалось.

        Почему я вообще позволил себе говорить об этом? В первую очередь потому, что когда-то мне было сложно перейти от решения алгоритмических задач, а разработке приложений. И я помню о том, как это было.

        После реализации некоторое количество алгоритмов, структур данных, отдельных функций, которые решают какую-то задачу, бывает сложно перейти к написанию комплексного приложения, законченного продукта, которым будет пользоваться другие. Сложно бывает даже определиться в одном файле написать приложение, или разбить его на несколько модулей.

        Здорово, когда есть наставник, который подскажет и направит, но когда его нет, как это было в моем случае, хотелось бы что-бы кто-то показал на что стоит обратить внимание, и о чем не плохо было бы подумать. Причем часто это те вещи, которые профессионалы воспринимают как само собой разумеющееся, и не обращают на них внимание.


      1. khacsam
        16.12.2023 15:48
        #26275980

        А если первые N килобайт совпадают, а где-то в середине или в конце файла кто-то (или что-то) изменил/заменил содержимое, но при этом размер файла не изменился?


        1. plFlok
          16.12.2023 15:48
          #26276448

          душненько. Да, в такой ситуации мы проиграли и сфоллбечились на полное сравнение файлов, как в исходной статье (точнее сравнение crc32 полных файлов). Но я наблюдал, что такая ситуация редка настолько, что ею можно пренебречь.


          1. khacsam
            16.12.2023 15:48
            #26276512

            Я для общего развития интересуюсь, т.к. к разработке отношения не имею.


    1. VT100
      16.12.2023 15:48
      #26273790

      CRC, как и любой другой hash, может дать одинаковый результат для разных файлов. Так-что, проверка равенства размеров файлов - абсолютно необходима.


      1. thsiganenko Автор
        16.12.2023 15:48
        #26274266

        Спасибо за комментарий! Благодаря вам засомневался в достаточности вычисления только контрольной суммы с помощью алгоритма MD5, и пошел искать информацию по этому вопросу.

        В статье "Cautions (or why it’s hard to write a dupefinder)" (прим. статья на английском), есть раздел "Collision Robustness", где показан практический пример того, когда для двух разных файлов контрольная сумма MD5 совпадает, а вот SHA1 уже отличается. При этом размер файлов также совпадает, так что даже проверки на совпадение размера файлов в дополнении к контрольной сумме может быть недостаточно!

        $ mkdir test && cd test

$ wget http://web.archive.org/web/20071226014140/http://www.cits.rub.de/imperia/md/content/magnus/order.ps
$ wget http://web.archive.org/web/20071226014140/http://www.cits.rub.de/imperia/md/content/magnus/letter_of_rec.ps

$ ls -l
total 8
-rwxrwxrwx 1 user user 2029 Jun 19  2007 letter_of_rec.ps
-rwxrwxrwx 1 user user 2029 Jun 19  2007 order.ps

$ md5sum *
a25f7f0b29ee0b3968c860738533a4b9  letter_of_rec.ps
a25f7f0b29ee0b3968c860738533a4b9  order.ps

$ sha1sum *
07835fdd04c9afd283046bd30a362a6516b7e216  letter_of_rec.ps
3548db4d0af8fd2f1dbe02288575e8f9f539bfa6  order.ps

$ sha256sum *
de4e4c6e2b94e95a3c5bd72a9a6af29bc5f83bf759325d9921943a6fc08ea245  letter_of_rec.ps
077046dd66015e05c3e03a43a6e4de129038e0701de5a4103fc7ed91c3782d06  order.ps

$ diff --binary letter_of_rec.ps order.ps
Binary files letter_of_rec.ps and order.ps differ

$ stat *
  File: letter_of_rec.ps
  Size: 2029            Blocks: 8          IO Block: 4096   regular file
Device: eh/14d  Inode: 35184372088972066  Links: 1
Access: (0777/-rwxrwxrwx)  Uid: ( 1000/ user)   Gid: ( 1000/ user)
Access: 2023-12-17 03:40:20.897605000 +0500
Modify: 2007-06-19 14:01:09.000000000 +0600
Change: 2023-12-17 03:37:36.616898300 +0500
 Birth: -
  File: order.ps
  Size: 2029            Blocks: 8          IO Block: 4096   regular file
Device: eh/14d  Inode: 59672695062770586  Links: 1
Access: (0777/-rwxrwxrwx)  Uid: ( 1000/ user)   Gid: ( 1000/ user)
Access: 2023-12-17 03:40:20.897605000 +0500
Modify: 2007-06-19 14:01:09.000000000 +0600
Change: 2023-12-17 03:37:28.041841500 +0500
 Birth: -

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

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


    1. thsiganenko Автор
      16.12.2023 15:48
      #26276620

      Еще раз хочу поблагодарить за комментарий! Решил повнимательнее посмотреть на утилиту jdupes, обнаружил, что в репозитории Ubuntu 23.04 доступна версия 1.21.3-1. Оказалось, что она делает ровно тоже, что было описано в статье, за исключением удаления пустых каталогов, но это можно решить с помощью утилиты find. То есть сеанс работы может выглядеть следующим образом:

      $ # Удаляем дубликаты
$ jdupes --delete --no-prompt --recurse source target

$ # Удаляем пустые каталоги  
$ find target/ -type d -empty -delete

      И еще раз хочу обратить внимание на то, что задумкой статьи было показать способ начинающим разработчикам, сам процесс разработки, и продемонстрировать возможные "грабли", на которые мне, если присмотреться к комментариям, удалось не просто наступить, а прям станцевать.


  1. Andy_U
    16.12.2023 15:48
    #26273696

    А сравнить скорость работы с CloneSpy?


    1. thsiganenko Автор
      16.12.2023 15:48
      #26273736

      Простите, долго писал комментарий, отвечая на предыдущие.

      Сравнивать разработку, описанную в статье, с другими приложениями, решающие похожую задачу, нет смысла. Сам по себе подход к решению, описанный в статье, можно назвать "рабоче-крестьянским", то есть минимально возможные вложения для достижения желаемого результата.

      Статья преследовала другую цель, и об этом я постарался сказать в комментарии выше.


  1. Demon416
    16.12.2023 15:48
    #26273800

    Дедупликаторов очень много, но мне не встречался ни один в котором можно было бы прописывать правила дедупликации

    Типа автоматически удалять фото меньшего размера при одинаковом содержимом или оставлять наиболее глубоко расположенный в файловой системе экземпляр. В общем есть ещё куда работать.


    1. thsiganenko Автор
      16.12.2023 15:48
      #26273930

      Спасибо за комментарий! Вы подняли очень важный вопрос - вопрос интерфейса и взаимодействия пользователя с программой. Под интерфейсом понимается множество вариантов, начиная от текстового интерфейса командной строки (CLI), до графического интерфейса (GUI).

      Многое в этом зависит от квалификации пользователя. Потому что одно дело, если это пользователь GNU/Linux, который привык к консоли, чтению мануалов и т.д., и другое, если это пользователь, который привык только к "интуитивному" графическому интерфейсу.

      Допустим, у нас есть ядро, то есть приложение, которое выдает нам список дубликатов, при этом решающее эту задачу максимально эффективным способом. Тогда, вероятно, можно создать некоторый специфичный для этой задачи язык (DSL), на котором можно описывать правила, как обрабатывать данный список. При этом такой DSL может быть реализован в виде ключей, передаваемых при запуске приложения.

      Вот только сразу же появляется задача обучения данному языку пользователя приложения, тут одного "интуитивного подхода" уже будет недостаточно. А так же другая задача, это определение поведения по умолчанию.

      Опять же, как реализовывать DSL в формате графического интерфейса, слабо могу представить, за исключение того, чтобы дать пользователю возможность описывать правила в виде текстового файла, или набора полей ввода, то есть опять же, с помощью текста. А если же это какой-то вариант, когда можно собирать правила из "кубиков", то, боюсь, интерфейс приложения будет сложнее, чем ядро этого приложения. Да и "собирать кубики" пользователя тоже придется учить. Насколько усилия по разработке такого приложения будут оправданы, и получить ли вообще сделать его привлекательным для пользователя.

      Возвращаясь к идее, что у нас есть "ядро", которое умеет эффективно решать задачу нахождения дубликатов, и отдавать нам, например, в виде текста список путей. Тогда используя командный интерпретатор (shell), или язык общего назначения, например, Python, мы можем описать правила обработки получаемого вывода, и нам не нужно будет придумывать DSL для этой задачи. Но, в этом случае, у нас должна быть достаточна высокая квалификация пользователя.

      Вообще интересно, а можно ли найти общее решение для данной задачи, или же это задача частного характера, подобно задачи генерации отчетов? И еще ощущение, что это возвращает нас к истокам философии UNIX, когда при выборе решить задачу комбинируя существующие программы или написать отдельную, в большинстве случаев предпочтение отдается первому варианту.

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


      1. Demon416
        16.12.2023 15:48
        #26274016

        Рабочее решение можно подсмотреть в интерфейсе почтовых клиентов, а точнее в редакторе правил распределения писем. А вообще про плачевное состояние нынешних ui и ux, и предпосылки этого в виде той самой философии юникс и капитализма можно не одну статью написать.


  1. mc2
    16.12.2023 15:48
    #26274022

    Контрольная сумма CRC (cyclic redundancy check) - это алгоритм, используемый для проверки целостности данных. Он вычисляется по определенному алгоритму на основе содержимого файла и используется для сравнения с контрольным значением, сохраненным в файле. Если контрольные суммы совпадают, файл считается неизмененным.

    CRC часто используется для проверки целостности файлов при передаче их по сети, а также при резервном копировании и восстановлении данных.

    Но CRC не следует использовать для сравнения файлов, если необходимо обнаружить даже небольшие изменения в файле. Это связано с тем, что CRC имеет относительно низкую чувствительность к изменениям в данных.

    Вот некоторые причины, по которым не следует использовать CRC для сравнения файлов:

    • CRC нечувствителен к перестановкам байтов. Например, если в файле поменять местами два байта, контрольная сумма CRC не изменится.

    • CRC нечувствителен к изменениям в данных, которые не влияют на их общую сумму. Например, если в файле добавить или удалить один байт, контрольная сумма CRC также не изменится.

    • CRC может давать ложные срабатывания. Это означает, что контрольные суммы двух файлов могут совпадать, даже если файлы содержат разные данные.

    Для сравнения файлов, в которых необходимо обнаруживать даже небольшие изменения, рекомендуется использовать другие алгоритмы, такие как MD5, SHA-1 или SHA-256. Эти алгоритмы имеют более высокую чувствительность к изменениям в данных и обеспечивают более высокую точность.


    1. Demon416
      16.12.2023 15:48
      #26274036

      В данном случае можно даже просто последовательно ксорить по n байт. В любом случае по итогам быстрого сравнения нужно будет проводить полное потому что ни один хеш не даёт да и не может давать стопроцентной гарантии отсутствия коллизий


    1. thsiganenko Автор
      16.12.2023 15:48
      #26274048

      Спасибо за уточнение терминологии! В предлагаемом решении для вычисления контрольной суммы был использован именно алгоритм MD5. Я исходил из того, что CRC это не конкретный алгоритм, а термин описывающий множество алгоритмов, в которые как раз входят MD5, SHA-1 или SHA-256 и т.д.


      1. sci_nov
        16.12.2023 15:48
        #26274960

        CRC это класс алгоритмов, фактически один алгоритм. MD5 и SHA никоим образом не относятся к CRC. Последние связаны с нахождением остатка от деления, линейный алгоритм.


      1. starik-2005
        16.12.2023 15:48
        #26278180

        Ну, собственно, мысль в том, что два разных файла одной длины могут иметь одинаковый MD5. Ну да, вероятность невелика, но реально бывает.


    1. VT100
      16.12.2023 15:48
      #26275710

      Хм-м-м. Есть пруфы про "перестановку байт" и "удаление байта" в CRC?


  1. dyadyaSerezha
    16.12.2023 15:48
    #26274310

    except OSError:
    logger.error('Deleting of file %s failed', target_file)

    А почему не выведена сама ошибка? Плохо. Как потративший тысячи часов на сопровождение больших систем, могу сказать, что такие "информативные" сообщения об ошибках просто бесят. Самый топ, это сообщение типа "ой, что-то пошло не так".

    Попытка удалить директорию - ну прямо неправильно. Неправильно по действию - сделать что-то плохое, зная, что не сработает. Неправильно по философии исключений - тут исключение является стандартной ситуацией. То есть, так можно, если нет "более лучшего" варианта.

    Ну и в подпрограмме удаления, почему выбран другой метод итерации? Было было логично точно так же построить набор путей, а потом уже с ними работать. Так обе части (с source и с targets) выглядели бы почти идентичными. Даже можно было бы сделать одну подпрограмму и подсовывать ей разные методы действия с файлом (считаем crc и кладем в сет или считаем crc, сравниваем и удаляем)

    Ну и конечно, я бы не стал отдельно делать этот список с путями - совершенно ненужный объект, только тратится процессор и память.


    1. thsiganenko Автор
      16.12.2023 15:48
      #26274560

      Спасибо за комментарий. Отсутствие вывода причины, которое вызвало исключение, а только сам факт исключения, действительно было не лучшим решением, тем более, что исправить это практически ничего не стоит, например, можно сделать следующим образом:

      try:
	os.remove(target_file)
	logger.info('File %s was removed', target_file)
except OSError as error:
	logger.error('Deleting of file %s failed, reason: %s', target_file, error)

      Что касается использования исключений, как инструмента в рамках нормального потока исполнения, а не обработки действительно исключительных ситуаций, как отмечено в тексте статьи, является очень и очень спорным решением. Хотя подход "проще просить прощения, чем разрешения", мне встретился на одной из международных Python конференций.

      Опять же, вы обратили внимание на то, что показывает разницу между скриптом, написанным для личного использования, и продуктовую разработку. Использовать исключения для нормального потока выполнения в продуктовой разработке, скорее можно отнести к "антипатернам".

      Выбор иного способа обработки дерева каталогов при удалении, то есть одновременный обход, вычисление контрольной суммы и удаление, в первую очередь был обусловлен желанием показать, что так тоже возможно. То есть в рамках одного примера, показать разные способы решения задачи.

      Безусловно вы правы в том, что можно описать обобщенную функцию обхода дерева каталогов, и передавать ей в качестве параметра функцию, которая будет выполняться в зависимости от того, на каком этапе выполнения находится программа. Но это может оказаться сложнее для понимания, и такое решение было бы скорее интересно для опытных разработчиков.

      Ну и последнее. Список путей, который формируется, появился в процессе попыток сократить время выполнения приложения за счет использования ProcessPoolExecutor и ThreadPoolExecutor. Вычисление контрольных сумму можно распараллелить, а вот как распараллелить обход дерева каталогов? Поэтому сначала выполняем то, что можно сделать только последовательно, собираем результат, а потом выполняем то, что можно делать одновременно.


      1. dyadyaSerezha
        16.12.2023 15:48
        #26274944

        проще просить прощения, чем разрешения

        И где же тут просят прощения? Не катит ссылка на конференцию.

        А пробовали увеличить размер блока с 4К до 256К, например?


        1. thsiganenko Автор
          16.12.2023 15:48
          #26275356

          Соглашусь с вами, что просто отсылка на конференцию выглядит слабовато. Тогда позвольте сослаться на книгу: Седер Наоми / Python. Экспресс-курс. 3-е изд. — СПб.: Питер, 2019. — 480 с.: ил. — (Серия «Библиотека программиста»). ISBN 978-5-4461-0908-1

          Об авторе
          Наоми Седер, автор третьего издания книги, занимается программированием на различных языках в течение почти 30 лет. Она работала системным администратором Linux, преподавателем программирования, разработчиком и системным архитектором. Она начала использовать Python в 2001 году, и с тех пор преподавала Python пользователям всех уровней, от 12-летних до профессионалов. Она рассказывает о Python и о достоинствах Python-сообщества каждому, кто готов слушать. В настоящее время Наоми руководит группой разработки для Dick Blick Art Materials и является председателем Python Software Foundation

          14.2. Исключения в Python
          Подход к обработке ошибок в Python в целом отличается от подхода в таких языках, как, скажем, Java. Эти языки по возможности стараются выявить как можно больше возможных ошибок заранее, поскольку обработка исключений после их возникновения может обойтись достаточно дорого. Такой стиль описан в первой части этой главы; иногда он обозначается сокращением LBYL (Look Before You Leap, то есть «Смотри, прежде чем прыгать»).

          С другой стороны, Python скорее полагается на то, что исключения будут обработаны после их возникновения. И хотя такой подход может показаться рискованным, при разумном использовании исключений код получается менее громоздким и лучше читается, а ошибки обрабатываются только в случае их возникновения. Подход Python к обработке ошибок часто описывается сокращением EAFP (Easier to Ask Forgiveness than Permission, то есть «Проще просить прощения, чем разрешения»).

          Так же, есть обсуждение на StackOverflow "What is the EAFP principle in Python?"

          Опять же не исключено, что в данном случае я неправильно применил данный подход. Есть повод вернуться и подумать над этим.

          Что касается изменения размеров считываемого блока, то нет менять его не пробовал. Если быть честным, то мысль была поэкспериментировать с этим, но тут нужно каким-то образом измерять результаты изменений, а это, мягко говоря, не очень просто.

          Когда я пробовал тестировать данный скрипт в Windows 10 22H2, я столкнулся с какой-то "магией" кэширования, причем даже не смог найти где именно оно происходит, когда при первом запуске приложение работает 90 секунд, а вот повторный запуск завершается за 1,5 секунды и дает тот же самый результат.


          1. dyadyaSerezha
            16.12.2023 15:48
            #26276190

            Конечно используете питоровский исключений неправильно - ключевое слово pass говорит всё - исключение у вас вовсе не исключение.

            Насчёт кэширования - интересно (наверное, кэширует ОС) и прекрасно показывает, как мало времени занимает расчёт crc по сравнению с чтением с диска. То есть, оптимизировать надо чтение, а не расчёт.


  1. furior
    16.12.2023 15:48
    #26274434

    Для покрытия всего кода тайп хинтами, можно использовать кастомный неймспейс в методе parse_args, либо специальную библиотеку, но я не знаю достаточно проработанных.


  1. EvilsInterrupt
    16.12.2023 15:48
    #26275654

    Зря вы не выложили код на GitHub можно было бы создать Issues.

    Предложил бы добавить вот какие фичи:

    1. Добавить работу с переменными среды MY_PHOTOS_DIR и чтоб можно было указать путь до моей основной коллекции. В коллекции чтоб хранился индекс-файл photos.index с хэшами всех моих файлов моих проиндексированных файлов

    2. Добавить в коллекцию файл removed_files.index. Его назначение хранить хэши файлов, которые я решил удалить когда-либо. Что если у меня еще где-то сохранилась копия фоток? А ведь среди них могут уже быть ранее удаленные мною файлы. Как избежать повторного просмотра? Если я решил удалить, значит все! Смысл возвращаться к этому процессу? Итак фоток столько, что не пересмотреть )))


    1. thsiganenko Автор
      16.12.2023 15:48
      #26276066

      Спасибо за ваше предложение! Но, если честно, то сейчас, после обсуждения и выявления фундаментального изъяна в алгоритме, который при определении идентичности файлов полагается только на алгоритм MD5, я считаю, хорошо, что исходный текст приложения находится в тексте статьи, и вероятность заметить предупреждение о потенциальной ошибке выше, чем если бы он был выложен на GitHub.

      Хотя, предложенный вариант, пусть с оговорками и ограничениями, может быть использован для решения практических задач, все же не имеет смысла создавать дополнительные возможности и развивать приложение, пока не будет устранен описанный выше недостаток.

      И еще раз хотел бы упомянуть, что целью статьи не являлось создание самого эффективного способа решения обозначенной задачи, а показать способ начинающим разработчикам, как можно начать процесс разработки.

      А вообще у меня есть вариант скрипта для одной из задач, который как раз хранит файл с вычисленными значениями MD5, и при добавлении новых файлов обновляется, это позволяет существенно экономить время работы. Есть вариант, в котором эти процессы разделены, PowerShell скрипт считает контрольные суммы и экспортирует их в файл формата CSV, а скрипт на Python уже на основании этого файла производит обработку.


  1. WebPrg
    16.12.2023 15:48
    #26275934

    запустил финальный скрипт (Ubuntu 20.04 Python 3.11.1) просто ради интереса - не работает оно, если бы я предварительно вызовы "os." не закомментировал, то удалило бы мне далеко не пустые дирректории вот в том месте где logger.info('Empty dir %s was removed')


    1. thsiganenko Автор
      16.12.2023 15:48
      #26275998

      Прошу меня простить, за резкий тон данного ответа, но я утверждаю, что приложение работает так, как и должно. В приложении действительно есть потенциальная ошибка, связанная с коллизиями при использовании алгоритма MD5, о чем указано в дополнении к статье, но в остальном все работает ровно так как задумано и описано.

      Почему вы решили, что если бы вы не закомментировали вызов os.rmdir, то были бы удалены не пустые каталоги?

      Могу предположить, что вы исходите из того, что после того, как вы закомментировали вызов os.rmdir, в выводе вы увидели строки "Empty dir /some/path/to/dir was removed"?

      Если это так, то смею вас уверить, в случае если вызов os.rmdir будет вызван с передачей в качества аргумента непустого каталога, то будет выброшено исключение, и строка logger.info(Empty dir %s was removed) просто не будет выполнена.

      Ну и чтобы не быть голословным, ссылка на документацию https://docs.python.org/3/library/os.html?highlight=os rmdir#os.rmdir, в которой явно указано, что если каталог не пустой, то будет выброшено исключение OSError:

      os.rmdir(path, *, dir_fd=None)
	Remove (delete) the directory path. If the directory does not exist
	or is not empty, a FileNotFoundError or an OSError is raised respectively.
	In order to remove whole directory trees, shutil.rmtree() can be used.

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

      И было бы очень хорошо, если бы вы сообщили результаты своего нового тестирования в ответном комментарии.


  1. starik-2005
    16.12.2023 15:48
    #26278172

    Как-то делали такое приложение с одним коллегой в универе. Тоже быстро придумали читать файлы один раз: при наличии файла такой же длины получали контрольную сумму (собирали путь к файлу, его длину и CRC, при наличии уже файла такой же длины в списке). Потом выводили в две панели аля Нортон (ну или Фар, если кто не застал Нортон).

    Однако, стоит иметь ввиду, что два разных файла могут иметь одну и ту же контрольную сумму. И вроде кажется, что вероятность небольшая, но это только кажется, т.к. количество коллизий хеш-суммы/CRC равняется двойке в степени разности бит между размером хеш-суммы и итоговых данных. Вообще, проблемы с коллизиями контрольных сумм встречаются достаточно часто (как-то даже на гите было).


  1. DenSigma
    16.12.2023 15:48
    #26279094

    Не вижу в требованиях условий про переименования файлов. Файлы в target могут быть переименованы?


    1. thsiganenko Автор
      16.12.2023 15:48
      #26279118

      Да, приложение, предложенном варианте, не принимает во внимание ни имя файла, ни иные метаданные файла, а опирается только на результат преобразования содержимого файла в контрольную сумму с помощью алгоритма MD5. Иными словами, если обобщить и упростить, то файлы сравниваются по содержимому. Но не стоит забывать о существовании вероятности коллизии при использовании данного подхода.

      Действительно, в требованиях это не указано, что именование файлов не должно иметь значение, поскольку опять же это требование воспринималось как само собой разумеющееся, что, судя по вашему вопросу, таковым не является.