6. Агрегация

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

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

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

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

const tree = mkdir('/', [
  mkdir('etc', [
    mkfile('bashrc'),
    mkfile('consul.cfg'),
  ]),
  mkfile('hexletrc'),
  mkdir('bin', [
    mkfile('ls'),
    mkfile('cat'),
  ]),
]);

// В реализации используем рекурсивный процесс,
// чтобы добраться до самого дна дерева.
const getNodesCount = (tree) => {
  if (isFile(tree)) {
    // Возвращаем 1 для учёта текущего файла
    return 1;
  }

  // Если узел — директория, получаем его детей
  const children = getChildren(tree);
  // Самая сложная часть
  // Считаем количество потомков для каждого из детей,
  // вызывая рекурсивно нашу функцию getNodesCount
  const descendantCounts = children.map((child) => getNodesCount(child));
  // Возвращаем 1 (текущая директория) + общее количество потомков
  return 1 + _.sum(descendantCounts);
};

getNodesCount(tree); // 8

https://repl.it/@hexlet/js-trees-aggregation-getNodesCount-nodejs

Кода здесь немного, но он довольно хитрый. Есть несколько ключевых моментов:

1. Функция проверяет тип узла. Если узел — это файл, тогда из функции возвращается единица.
2. В случае, если узел — директория, тогда получаем детей и для каждого ребёнка вновь вызываем нашу функцию. Затем повторяем алгоритм заново.
3. Вызов функции на каждом ребёнке возвращает свой собственный результат (количество его потомков). Эти результаты образуют массив с числами, которые нужно объединить.
4. В конце считается общее количество всех потомков узла + единица (текущий узел сам по себе).

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

Тесты

Вопрос 1

Какие виды операций относятся к агрегации?

(нужно выбрать все корректные ответы)

Удаление файлов определенного типа

Поиск самого большого файла

Массовое переименование файлов

Подсчет размера директории

Вопрос 2

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

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

Рекурсивно вызываем исходную функцию для каждого ребенка и затем из вывода убираем данные вернувшиеся от файлов (так как файлы не учитываются)

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

Вопрос 3

Может ли в результате агрегации получится другое дерево?

Нет, агрегация должна вернуть какой-то из встроенных типов данных

Агрегация может вернуть все что угодно

Нет, агрегация должна вернуть какое-то примитивное значение

Упражнение

getHiddenFilesCount.js

Реализуйте и экспортируйте по умолчанию функцию, которая считает количество скрытых файлов в директории и всех поддиректориях. Скрытым файлом в Linux системах считается файл, название которого начинается с точки.

Пример

import { mkdir, mkfile } from '@hexlet/immutable-fs-trees';
import getHiddenFilesCount from '../getHiddenFilesCount.js';

const tree = mkdir('/', [
  mkdir('etc', [
    mkdir('apache'),
    mkdir('nginx', [
      mkfile('.nginx.conf', { size: 800 }),
    ]),
    mkdir('.consul', [
      mkfile('.config.json', { size: 1200 }),
      mkfile('data', { size: 8200 }),
      mkfile('raft', { size: 80 }),
    ]),
  ]),
  mkfile('.hosts', { size: 3500 }),
  mkfile('resolve', { size: 1000 }),
]);

getHiddenFilesCount(tree); // 3

getHiddenFilesCount.js file

// @ts-check
import _ from 'lodash';import { isFile, getName, getChildren } from '@hexlet/immutable-fs-trees';
// BEGIN (write your solution here)
// END

Хештеги