Создание дерева каталогов из списка путей к файлам

Question

Я ищу эффективный по времени метод для анализа списка файлов в дереве. Может быть сотни миллионов путей к файлам.

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

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

C: \ Users \ Aaron \ AppData \ Amarok \ AFile

C: \ Users \ Aaron \ AppData \ Amarok \ Afile2

C: \ Users \ Aaron \ AppData \ Amarok \ Afile3

C: \ Users \ Aaron \ AppData \ Blender \ alibrary.dll

C: \ Users \ Aaron \ AppData \ Blender \ and_so_on.txt

Исходя из этого порядка, моя естественная реакция - разделить списки каталогов на группы ... каким-то образом ... перед выполнением медленного сравнения строк. Я действительно не уверен. Буду признателен за любые идеи.

Редактировать: Было бы лучше, если бы это дерево было лениво загружено сверху вниз, если это возможно.

Answer 1

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

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

Answer 2

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

Answer 3

если это возможно, вы можете сгенерировать древовидную структуру с помощью команды tree, здесь