通過深度優先或寬度優先發現文件夾樹

我必須找到文件夾中「最深」文件夾的路徑。爲此，我實現了兩種算法，一種比另一種算法快。有誰知道爲什麼？我想這與硬盤硬件有一些聯繫，但我想明白。這裏是一個快：通過深度優先或寬度優先發現文件夾樹

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

通過深度優先或寬度優先發現文件夾樹

回答

相關問題