Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Аккумулятор Python: Деревья

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

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

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

Как работать с аккумулятором

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

Сначала реализуем простую версию, затем усложним ее и внедрим аккумулятор. Посмотрим на пример файловой системы:

from hexlet import fs

tree = fs.mkdir('/', [
    fs.mkdir('etc', [
        fs.mkdir('apache'),
        fs.mkdir('nginx', [
            fs.mkfile('nginx.conf'),
        ]),
        fs.mkdir('consul', [
            fs.mkfile('config.json'),
            fs.mkdir('data'),
        ]),
    ]),
    fs.mkdir('logs'),
    fs.mkfile('hosts'),
])

В этой структуре три пустых директории:

  • /logs
  • /etc/apache
  • /etc/consul/data

Код, решающий эту задачу, выглядит так:

def find_empty_dirs(tree):
    name = fs.get_name(tree)
    # Получаем потомков узла (директории)
    children = fs.get_children(tree)
    # Если потомков нет, то возвращаем директорию
    if len(children) == 0:
        return name
    # Фильтруем файлы, они нас не интересуют
    dir_names = filter(fs.is_directory, children)
    # Ищем пустые директории внутри текущей
    empty_dir_names = list(map(find_empty_dirs, dir_names))
    # Далее flatten делает список плоским
    return fs.flatten(empty_dir_names)


print(find_empty_dirs(tree))
# => ['apache', 'data', 'logs']

https://repl.it/@hexlet/python-trees-search-find-empty-dirs

Самое необычное в этой реализации — это функция flatten(). Далее обсудим, зачем она нужна.

Если оставить только map(), то результат может удивить:

find_empty_dirs(tree)
# [['apache', [], ['data']], 'logs']

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

Попробуем усложнить задачу. Найдем все пустые директории, но с максимальной глубиной поиска в два уровня. Например, директории /logs и /etc/apache подходят под это условие, а вот /etc/consul/data — нет.

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

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

Такую переменную называют аккумулятором — она аккумулирует, то есть накапливает данные.

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

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

def find_empty_dirs(tree):
    # Внутренняя функция, которая может передавать аккумулятор
    # Аккумулятором выступает depth — переменная, содержащая текущую глубину
    def walk(node, depth):
        name = fs.get_name(node)
        children = fs.get_children(node)
        # Если потомков нет, то возвращаем директорию
        if len(children) == 0:
            return name
        # Если это второй уровень вложенности, и директория не пустая,
        # то не имеет смысла смотреть дальше
        if depth == 2:
            # Почему возвращается именно пустой список?
            # Потому что снаружи выполняется flatten
            # Он раскрывает пустые списки
            return []
        # Оставляем только директории
        dir_paths = filter(fs.is_directory, children)
        # Не забываем увеличивать глубину
        output = list(map(
            lambda child: walk(child, depth + 1),
            dir_paths,
          ))
        # Перед возвратом выпрямляем список
        return fs.flatten(output)

    # Начинаем с глубины 0
    return walk(tree, 0)


print(find_empty_dirs(tree))
# => ['apache', 'logs']

https://repl.it/@hexlet/python-trees-accumulator-find-empty-dirs-with-depth

Можно пойти еще дальше и позволить указывать максимальную глубину снаружи:

def find_empty_dirs(tree, max_depth=2):
    # ...

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

Правильный способ сделать это – использовать в качестве значения по умолчанию бесконечность math.inf:

def find_empty_dirs(tree, max_depth=math.inf):
    # ...

Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

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

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы
профессия
Обучитесь разработке бэкенда сайтов и веб-приложений — серверной части, которая отвечает за логику и базы данных
10 месяцев
с нуля
Старт 7 ноября

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»