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

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

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

Answer 2

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

Answer 3

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

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