Эффективно Дерево каталогов Пересечения с opendir (), readdir () и closedir ()
Стандартные программы C opendir (), readdir () и closedir () позволяют, чтобы я пересек структуру каталогов. Однако каждая dirent структура, возвращенная readdir (), кажется, не обеспечивает полезный способ для меня получить набор указателей на DIR, который я должен был бы рекурсивно вызвать в подкаталоги каталога.
Конечно, они дают мне название файлов, таким образом, я мог или добавить то имя к пути к каталогу и статистике () и opendir () их, или я мог изменить текущий рабочий каталог процесса через chdir () и откатывать его через chdir (".. ").
Проблема с первым подходом состоит в том что, если длина пути к каталогу будет достаточно большой, то стоимость для передачи строки, содержащей его к opendir (), будет избыточный вес стоимость открытия каталога. Если Вы являетесь более теоретическими, Вы могли бы сказать, что Ваша сложность могла бы увеличиться вне линейного времени (в общем счетчике символов (относительных) имен файлов в дереве каталогов).
Кроме того, второй подход имеет проблему. Так как каждый процесс имеет единственный текущий рабочий каталог, все кроме одного потока должны будут заблокироваться в многопоточном приложении. Кроме того, я не знаю, является ли текущий рабочий каталог просто простым удобством (т.е. относительный путь будет добавлен к нему до запроса файловой системы). Если это будет, то этот подход будет неэффективен также.
Я принимаю альтернативы этим функциям. Таким образом, как это, можно пересечь дерево каталогов UNIX эффективно (линейное время в общем счетчике символов файлов под ним)?
3 ответа
Вы пробовали ftw () aka File Tree Walk ?
Фрагмент от человека 3 ftw :
int ftw (const char * dir, int (* fn) (const char * file, const struct stat * sb, int flag), int nopenfd);
ftw () проходит через дерево каталогов, начиная с указанного каталога dir. Для каждой найденной записи в дереве он вызывает fn () с полным путем к записи, указателем на структуру stat (2) для записи и флагом int
Похоже, вы упускаете один основной момент: обход каталога подразумевает чтение данных с диска. Даже если эти данные находятся в кэше, вам придется проделать изрядный объем кода, чтобы доставить их из кэша в ваш процесс. Пути также обычно довольно короткие - больше пары сотен байт не бывает. Все это означает, что вы можете без особых проблем создать строки для всех необходимых вам путей. Время, затрачиваемое на создание строк, все еще довольно незначительно по сравнению со временем чтения данных с диска. Это означает, что вы можете игнорировать время, потраченное на работу со строками, и работать исключительно над оптимизацией использования диска.
Мой собственный опыт показывает, что для большинства случаев обхода каталога предпочтительнее поиск в ширину - пока вы обходите текущий каталог, поместите полные пути ко всем подкаталогам в нечто вроде очереди приоритетов. Когда вы закончите обход текущего каталога, вытащите первый элемент из очереди и обходите его, продолжая до тех пор, пока очередь не опустеет. Это, как правило, улучшает локальность кэша и уменьшает время, затрачиваемое на чтение с диска. В зависимости от системы (скорость диска по сравнению со скоростью процессора, общий объем доступной памяти и т.д.) это почти всегда по крайней мере так же быстро, как обход в глубину, и может быть в два раза быстрее (или около того).
Способ использования opendir/readdir/closedir заключается в том, чтобы сделать функцию рекурсивной! Посмотрите фрагмент здесь на Dreamincode.net.
Надеюсь, это поможет.
EDIT Спасибо R.Sahu, ссылка истекла, однако я нашел ее через wayback archive и взял на себя смелость добавить ее в gist. Пожалуйста, не забывайте проверять лицензию и указывать авторство источника! :)