具有大量文件的目录结构的树遍历算法

Question

当递归遍历目录结构时,如果文件多于目录,那么最有效的算法是什么？我注意到,当使用深度优先遍历时,当给定目录中存在大量文件时,似乎需要更长时间.在这种情况下,广度优先遍历是否更有效？我目前无法对这两种算法进行分析,因此非常欢迎您的见解.

编辑:为了回应alphazero的评论,我在Linux机器上使用PHP.

Answer 1

广度优先会更好，这是有道理的。当您进入根文件夹时，您将创建一个需要处理的项目列表。其中一些项目是文件，一些是目录。

如果您使用广度优先，您将处理目录中的文件并在转到子目录之一之前忘记它们。

如果您使用深度优先，则需要不断增加文件列表，以便稍后在深入钻取时处理。这将使用更多内存来维护要处理的文件列表，可能导致更多页面错误等......

另外，无论如何，您都需要浏览新项目列表，以确定哪些是您可以深入研究的目录。当您需要处理文件时，您需要再次浏览相同的列表（减去目录）。