Должен ли я сначала использовать ширину или глубину для поиска в файловой системе заранее определенного количества ошибок?

Question

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

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

ПРИМЕЧАНИЕ. Это НЕ домашнее задание. Это требование к сценарию, которое мой начальник попросил написать.

РЕДАКТИРОВАТЬ 1: Эффективность времени гораздо важнее, чем экономия пространства, поскольку сценарий будет в основном выполняться в течение ночи и, следовательно, может по существу использовать всю системную память, если это необходимо.

РЕДАКТИРОВАТЬ 2: Хотя кажется, что популярный ответ BFS для моей проблемы, у меня проблемы с пониманием, почему это не будет проблемой DFS. Так как (A) все ошибки должны быть в конечном итоге достигнуты и (B) мы знаем, содержит ли каталог ошибки, защита BFS от кроличьих дыр в действительности не применяется. Имея это в виду, единственное реальное различие, по-видимому, заключается в используемом пространстве, что улучшило бы DFS. Кто-нибудь может дать хороший аргумент относительно того, почему это не так?

Answer 1

Исходя из требований, я бы порекомендовал поиск в ширину, который в целом быстрее для структур на основе узлов, и (я почти уверен) эту ситуацию также.быстрее для основанных на узлах структур из-за улучшенной производительности кэша, даже при том, что он должен поддерживать список «дел».Это делает в первую очередь рекомендацию для поиска в каталоге.Поскольку ваш алгоритм является алгоритмом поиска, я бы хотел воспользоваться общей рекомендацией.

Answer 2

Зависит от нескольких вещей.

• Могут ли в ваших каталогах содержаться ссылки, и проследите ли вы по ссылкам? В таком случае, возможно ли ссылки сделать цикл? В таком случае BFS имеет больше смысла, если вы хотите игнорировать проверку цикла. В противном случае это не имеет значения.

• Как происходит распределение ошибок? Может ли быть так, что в одном каталоге содержится большинство ошибок, а в других почти нет ошибок? В этом случае BFS, скорее всего, закончится раньше, потому что он ищет все каталоги понемногу. В таком случае вы должны были бы провести долгое время с DFS в одном огромном дереве каталогов, которое содержит, скажем, 1 ошибку, в самых нижних листьях только для того, чтобы узнать, что следующий каталог содержит все ошибки, которые вам нужны, прямо на уровне 1. Если ошибки распределено более равномерно, опять же, не имеет значения, что вы используете.

• Насколько велика ваша структура? Если у вас есть дерево с коэффициентом ветвления n (n подкаталогов на каждый каталог) и дерево имеет глубину d, BFS может занять O(d^n) памяти, тогда как DFS может быть записана таким образом, что она занимает только O(d) памяти ( или в более простой реализации O(d*n)), которая в реальных огромных каталогах может иметь значение.

Мое общее чувство при чтении вашего вопроса - это BFS, но вам все равно придется решать, исходя из свойств вашей проблемы.