4

特定のフォルダー内のすべてのファイルとフォルダーの幅優​​先走査を実行するイテレーターを作成しようとしています。私はすでに深さ優先トラバーサルでこれを実行しました。これは、たとえば次のように戻ります。

\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の場合、以前に列挙したすべてのエントリを完全に無視できます。階層内の同じレベル。

だから私の質問は：フォルダをトラバースするためにメモリを使用するための線形よりも優れた方法はありますか？

4

1 に答える 1

3

プラットフォームがの概念をサポートしている場合は、ディレクトリごとに1つの番号を格納して、その特定のディレクトリでアクセスした最大のiノード番号を示すinode numberことができる場合があります。iノードに番号順にアクセスする場合、単一のエントリを追跡することで、「次の」エントリがどこにあるかを知るのに十分です。

システム上のすべてのディレクトリに対してiノード番号を維持する必要があるため、これは小さなメリットですが、ディレクトリの内容を気にする必要はありません。

もちろん、トラバーサルメカニズムはひどい競合状態にさらされることを念頭に置いて、ファイルシステムが静止しているか、コードがディレクトリ/ファイルの削除、作成、移動などに対して回復力があることをある程度保証する必要があります。 、コードの進行中。

于 2011-03-12T09:16:02.197 に答える