Обратный путь в каталог в ширину: возможно ли это с помощью O (log n) памяти?

Question

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

\A
\A\1
\A\1\x
\A\1\y
\A\2
\B
\B\1

и т. Д.

Теперь я пытаюсь создать программу, которая вместо этого будет возвращать результатыв ширину: (или уровень за уровнем)

\A
\B
\A\1
\A\2
\B\1
\A\1\x
\A\1\y

для той же иерархии.Однако я наткнулся на камень преткновения: предполагая, что я хочу, чтобы это происходило в правильном порядке (и, в частности, , а не в обратном порядке), я не могу найти способ выполнить это действие, не требуя в конечном итоге O(n) память, где n - это количество файлов / папок на диске, потому что мне кажется, что в конечном итоге мне понадобится сохранить всю иерархию дисков в памяти в некоторых случаях.точка, тогда как для DFS я могу полностью игнорировать все записи, которые я перечислял ранее на том же уровне в иерархии.

Итак, мой вопрос: есть ли лучше, чем линейный способ использовать память для того, чтобыпройти через папку?

Answer 1

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

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

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