通过深度优先或广度优先发现文件夹树

Question

我必须找到通往文件夹中"最深"文件夹的路径。为此，我实施了两种算法，一种算法比另一种算法要快。有人知道为什么吗？我想这与硬盘硬件有一些链接，但我想了解。这是快速的：

    private function getHostAux($path) {
        $matches = array();
        $folder = rtrim($path, DIRECTORY_SEPARATOR);
        $moreFolders = glob($folder.DIRECTORY_SEPARATOR.'*', GLOB_ONLYDIR);
        if (count($moreFolders) == 0) {
           $matches[] = $folder;
        } else {
            foreach ($moreFolders as $fd) {
                $arr = $this->getHostAux($fd);
                $matches = array_merge($matches, $arr);
            }
        }
        return $matches;
    }

这是一个慢的：

    /**
     * Breadth-first function using glob
     */
private function getHostAux($path) {
    $matches = array();
    $folders = array(rtrim($path, DIRECTORY_SEPARATOR));
    $i = 0;
    while($folder = array_shift($folders)) {
        $moreFolders = glob($folder.DIRECTORY_SEPARATOR.'*', GLOB_ONLYDIR);
        if (count($moreFolders == 0)) {
            $matches[$i] = $folder;
        }
        $folders = array_merge($folders, $moreFolders);
        $i++;
    }
    return $matches;
}

谢谢！

Answer 1

您尚未提供其他信息，这些信息对于理解您观察到的这些"时间"至关重要。（我故意写了报价，因为您还没有指定"慢"one_answers"快速"的含义，以及您如何衡量它。）

假设所提供的信息是正确的，并且第一种方法的加速大于百分之几，并且您已经在各种尺寸和深度的目录上对其进行了测试...

首先，我想评论所提供的答案：

• 我不确定您的答案。首先，我认为您的意思是" kernel handles "。但这不是事实，因为glob没有打开手柄。您是如何提出这个答案的？
• 两个版本的总迭代数量相同。

并添加我自己的东西：

• 我会怀疑array_shift()可能会导致放缓，因为每次调用它都会使整个数组重新索引。
• 根据基础操作系统和文件系统，您的球体可能重要的顺序。
• 您的代码中有一个错误。您可以在每个地球上递增$i，而不是将元素添加到$matches数组之后。这会导致$matches数组稀疏，这可能会导致合并，移动甚至添加过程的速度较慢。我不知道是否与PHP发生这种情况，但是我知道几种语言中具有这些属性，这些属性有时在编码时很难牢记。我建议修复此问题，再次对代码进行计时，看看是否有任何区别。

Answer 2

我认为您的第一个带有递归的算法比第二个算法要少。尝试观察每种算法使用辅助变量进行多少次迭代。