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

我必须找到文件夹中“最深”文件夹的路径。为此，我实现了两种算法，一种比另一种算法快。有谁知道为什么？我想这与硬盘硬件有一些联系，但我想明白。这里是一个快：通过深度优先或宽度优先发现文件夹树

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; 
}

谢谢！

来源

2012-10-17 diea

“慢”和“快”是什么意思？你如何衡量它？你有多少次调用每种方法来防止第一次读取速度减慢？ – andr

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

来源

2012-10-17 15:46:44 yur4ik

您尚未提供可能对了解您观察到的这些“时机”至关重要的其他信息。（我故意写了引号，因为你没有指定什么“慢”和“快”的意思，以及你是如何测量它的。）

假设提供的信息是真的，并且第一种方法的加速是超过几个百分点的更大，你已经测试了不同大小和深度的目录...

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

我就不会这么肯定关于你的答案。首先，我认为你的意思是“kernel 句柄”。但这不是真的，因为glob不打开句柄。你是怎么想出这个答案的？
两个版本都有相同的总迭代次数。

并添加一些东西自己：

我会怀疑array_shift()可能导致经济放缓，因为它重新索引每次调用时整个阵列。
根据底层操作系统和文件系统，您的glob的顺序可能很重要。
你有一个错误（可能）在你的代码。在每个glob之后增加$i，而不是在将元素添加到$matches数组之后。这会导致$matches数组稀疏，这可能会导致合并，移位或甚至添加过程变慢。我不确切知道PHP是否属于这种情况，但我知道有几种语言中的数组具有这些属性，这些属性在编码时有时难以记住。我会建议解决这个问题，再次对代码进行计时，看看是否有所作为。

来源

2013-01-26 15:54:52 andr

感谢您的精心答复！不幸的是，我不再在这个项目上工作，也没有访问/或时间来检查所有这些......但其他人也告诉我你提到的这个错误，你可能是正确的:-)再次，我我不打算在这方面进一步挖掘，但谢谢！ – diea

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

回答

相关问题