萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 非遞歸遍歷目錄:堆疊模擬、SPL 迭代器、Generator 三種方案深度比較

為什麼要避免遞歸遍歷目錄?

遞歸雖然代碼簡潔,但存在硬傷:

  • **棧溢出風險**:深度目錄結構 (超過 ~1000 層) 導致 PHP 棧溢出崩潰
  • **記憶體壓力**:遞歸調用棧佔用記憶體,大量文件時明顯
  • **難以中斷/暫停/恢復**:遞歸調用鏈難以外部控制
  • **無法輕易並行化**

**非遞歸 (迭代) 方案** 使用**顯式堆疊 (Stack/Queue)** 模擬遞歸調用棧,徹底解決上述問題。

方案一:手動堆疊 (Stack/Queue) —— 最底層、可控性最強

<?php
/**
 * 非遞歸遍歷目錄 (深度優先 DFS - Stack)
 * @param string $rootDir 根目錄
 * @param callable $callback 處理每個文件/目錄的回調: fn(string $path, bool $isDir): void
 * @param int $maxDepth 最大深度 (-1 不限制)
 * @return void
 */
function traverseDirDfs(string $rootDir, callable $callback, int $maxDepth = -1): void
{
    $rootDir = rtrim($rootDir, '/\\');
    if (!is_dir($rootDir)) throw new InvalidArgumentException("Not a directory: $rootDir");

    // 堆疊元素: ['path' => string, 'depth' => int]
    $stack = [['path' => $rootDir, 'depth' => 0]];

    while (!empty($stack)) {
        $current = array_pop($stack); // LIFO = 深度優先 (DFS)
        $path = $current['path'];
        $depth = $current['depth'];

        // 深度限制
        if ($maxDepth >= 0 && $depth > $maxDepth) continue;

        // 回調處理當前項
        $isDir = is_dir($path);
        $callback($path, $isDir);

        // 若是目錄,將子項推入堆疊
        if ($isDir) {
            $children = scandir($path);
            // 反轉順序,使原始順序先處理 (可選)
            $children = array_reverse($children);
            foreach ($children as $child) {
                if ($child === '.' || $child === '..') continue;
                $childPath = $path . DIRECTORY_SEPARATOR . $child;
                $stack[] = ['path' => $childPath, 'depth' => $depth + 1];
            }
        }
    }
}

/**
 * 非遞歸遍歷目錄 (廣度優先 BFS - Queue)
 * 適合:逐層處理、尋找最近文件、限制深度
 */
function traverseDirBfs(string $rootDir, callable $callback, int $maxDepth = -1): void
{
    $rootDir = rtrim($rootDir, '/\\');
    if (!is_dir($rootDir)) throw new InvalidArgumentException("Not a directory: $rootDir");

    $queue = [['path' => $rootDir, 'depth' => 0]]; // 使用陣列模擬隊列 (array_shift 會重建鍵,效能稍差,大量數據建議用 SplQueue)

    while (!empty($queue)) {
        $current = array_shift($queue); // FIFO = 廣度優先 (BFS)
        $path = $current['path'];
        $depth = $current['depth'];

        if ($maxDepth >= 0 && $depth > $maxDepth) continue;

        $isDir = is_dir($path);
        $callback($path, $isDir);

        if ($isDir) {
            $children = scandir($path);
            foreach ($children as $child) {
                if ($child === '.' || $child === '..') continue;
                $childPath = $path . DIRECTORY_SEPARATOR . $child;
                $queue[] = ['path' => $childPath, 'depth' => $depth + 1];
            }
        }
    }
}

// --- 使用示範 ---
$totalFiles = 0;
$totalDirs = 0;
$totalSize = 0;

traverseDirDfs('/var/www/project', function(string $path, bool $isDir) use (&$totalFiles, &$totalDirs, &$totalSize) {
    if ($isDir) {
        $totalDirs++;
    } else {
        $totalFiles++;
        $totalSize += filesize($path);
    }
    // 可選:即時輸出、過濾、收集...
    // echo ($isDir ? '[D]' : '[F]') . " $path\n";
});

echo "總計: $totalDirs 個目錄, $totalFiles 個檔案, " . formatBytes($totalSize) . "\n";

function formatBytes(int $bytes): string
{
    $units = ['B', 'KB', 'MB', 'GB', 'TB'];
    $i = 0;
    while ($bytes >= 1024 && $i < count($units)-1) {
        $bytes /= 1024;
        $i++;
    }
    return round($bytes, 2) . ' ' . $units[$i];
}
?>

方案二:SPL 迭代器 —— 面向對象、標準庫、功能豐富 (推薦日常使用)

PHP 內建 RecursiveDirectoryIterator + RecursiveIteratorIterator 是**標準庫級**的非遞歸遍歷實現 (底層 C 實現迭代器模式,非 PHP 代碼遞歸)。

<?php
$root = '/var/www/project';

// 1. 基礎遞歸迭代器 (自動處理遞歸,但內部仍用棧)
$dirIter = new RecursiveDirectoryIterator($root, 
    RecursiveDirectoryIterator::SKIP_DOTS // 自動跳過 . 和 ..
);
$recursiveIter = new RecursiveIteratorIterator($dirIter, 
    RecursiveIteratorIterator::SELF_FIRST // 先返回目錄再返回文件 (預設 CHILD_FIRST)
);

// 2. 過濾器鏈 (組合模式,極其強大)
$filter = new RegexIterator($recursiveIter, '/\.php$/i'); // 只找 .php
// 或多條件
$filter = new CallbackFilterIterator($recursiveIter, function($current, $key, $iterator) {
    return $current->isFile() && $current->getSize() > 1024 * 100; // > 100KB
});

// 3. 遍歷
foreach ($filter as $fileInfo) {
    /** @var SplFileInfo $fileInfo */
    echo "{$fileInfo->getPathname()} ({$fileInfo->getSize()} bytes)\n";
}

// 4. 限制深度
$depthLimited = new LimitIterator($recursiveIter, 0, 1000); // 不直接支援深度限制,需自定義 Filter
// 自定義深度限制迭代器
class DepthFilterIterator extends FilterIterator {
    private int $maxDepth;
    public function __construct(Iterator $iterator, int $maxDepth) {
        parent::__construct($iterator);
        $this->maxDepth = $maxDepth;
    }
    public function accept(): bool {
        return $this->getInnerIterator()->getDepth() <= $this->maxDepth;
    }
}
$limited = new DepthFilterIterator($recursiveIter, 3); // 只遍歷 3 層
foreach ($limited as $file) { /* ... */ }
?>

SPL 迭代器優勢

  • **標準庫、無依賴、C 級效能**
  • **豐富過濾器**:RegexIterator、CallbackFilterIterator、FilesystemIterator、GlobIterator
  • **SplFileInfo 物件**:直接提供 getSize()、getMTime()、getExtension()、isReadable() 等豐富方法
  • **可組合**:裝飾者模式疊加多層過濾

方案三:Generator 生成器 —— 記憶體極致優化、惰性求值、可中斷 (現代 PHP 首選)

PHP 5.5+ **Generator** 讓遍歷變成**惰性序列**:一次只產生一個結果,**記憶體 O(1)**,支援 break、return 提前結束、可組合管道處理。

<?php
/**
 * 非遞歸目錄遍歷 Generator (DFS)
 * @param string $rootDir
 * @param int $maxDepth
 * @return Generator
 */
function dirWalker(string $rootDir, int $maxDepth = -1): Generator
{
    $rootDir = rtrim($rootDir, '/\\');
    $stack = [new SplFileInfo($rootDir)];
    $depthMap = [$rootDir => 0]; // 記錄深度

    while (!empty($stack)) {
        $current = array_pop($stack);
        $path = $current->getPathname();
        $depth = $depthMap[$path] ?? 0;

        if ($maxDepth >= 0 && $depth > $maxDepth) continue;

        yield $current; // 惰性產出

        if ($current->isDir()) {
            // 讀取子項 (FilesystemIterator 自動跳過 . ..)
            $children = new FilesystemIterator($path, FilesystemIterator::SKIP_DOTS);
            // 反轉順序保持原始順序 (DFS)
            $childArray = iterator_to_array($children);
            $childArray = array_reverse($childArray);
            
            foreach ($childArray as $child) {
                $childPath = $child->getPathname();
                $depthMap[$childPath] = $depth + 1;
                $stack[] = $child;
            }
        }
    }
}

/**
 * BFS 版 Generator (使用 SplQueue)
 */
function dirWalkerBfs(string $rootDir, int $maxDepth = -1): Generator
{
    $queue = new SplQueue();
    $queue->enqueue(new SplFileInfo($rootDir));
    $depthMap = [$rootDir => 0];

    while (!$queue->isEmpty()) {
        $current = $queue->dequeue();
        $path = $current->getPathname();
        $depth = $depthMap[$path] ?? 0;

        if ($maxDepth >= 0 && $depth > $maxDepth) continue;

        yield $current;

        if ($current->isDir()) {
            $children = new FilesystemIterator($path, FilesystemIterator::SKIP_DOTS);
            foreach ($children as $child) {
                $childPath = $child->getPathname();
                $depthMap[$childPath] = $depth + 1;
                $queue->enqueue($child);
            }
        }
    }
}

// ==================== 使用示範:記憶體友好、管道處理 ====================
// 1. 只找前 10 個 .log 檔案 (惰性,找到即停止,不掃描全盤)
$count = 0;
foreach (dirWalker('/var/log') as $file) {
    if ($file->getExtension() === 'log') {
        echo $file->getPathname() . "\n";
        if (++$count >= 10) break; // 立即停止遍歷!
    }
}

// 2. 管道式處理:找 >1MB 的 .php 檔 → 讀取首行 → 輸出
$pipeline = dirWalker('/var/www/project')
    ->filter(fn($f) => $f->isFile() && $f->getExtension() === 'php')
    ->filter(fn($f) => $f->getSize() > 1024*1024)
    ->map(fn($f) => [
        'path' => $f->getPathname(),
        'size' => $f->getSize(),
        'first_line' => trim((new SplFileObject($f->getPathname()))->fgets())
    ]);

foreach ($pipeline as $info) {
    print_r($info);
}

// 3. 併發處理 (需配合並發庫如 amphp/parallel 或 進程分叉)
?>

三大方案深度對比

維度手動堆疊SPL 迭代器Generator
實現層級用戶態 PHP 代碼C 級內建類用戶態 PHP (yield)
記憶體佔用O(深度) 堆疊陣列O(深度) 內部棧**O(1)** 惰性產出
可中斷/暫停手動控制循環困難 (需 break 外層)**原生支援 break/return**
過濾/轉換手寫邏輯裝飾者模式組合**管道式 filter/map/reduce**
深度控制簡單變量控制需自定義 FilterIterator簡單變量控制
檔案資訊獲取手動 stat/lstat**SplFileInfo 物件直取****SplFileInfo 物件直取**
效能 (大量文件)良好優秀 (C 級)優秀 (無陣列構建)
學習曲線低中 (需懂迭代器模式)中 (需懂 Generator)
推薦場景
教學、極簡腳本、需精細控制堆疊邏輯、無 SPL 環境 (極罕見)
日常業務開發、複雜過濾、需 SplFileInfo 方法、團隊熟悉 SPL
**現代 PHP 首選**:大數據集、記憶體敏感、管道處理、可中斷、函數式風格

進階技巧:避開 stat 系統調用風暴

遍歷超大目錄 (百萬級文件) 時,is_dir()、filesize()、filemtime() 每次都觸發系統調用。優化策略:

  1. FilesystemIterator::CURRENT_AS_FILEINFO:迭代器直接返回 SplFileInfo,**複用同一 stat 結果**
  2. 只讀取目錄項名稱:scandir() / readdir() 不觸發 stat,後續按需 stat()
  3. Linux 專用:fscandir (需擴展) 或 exec('find ...') 繞過 PHP 層

結語

**遞歸遍歷目錄是反模式**。現代 PHP 專案應:

  1. **首選 Generator + SplFileInfo** —— 記憶體常數級、惰性、管道式、可中斷、代碼優雅
  2. **次選 SPL 迭代器鏈** —— 功能豐富、C 級效能、標準庫零依賴
  3. **手動堆疊** —— 僅用於教學、極特殊邏輯、或無 SPL 環境

掌握非遞歸遍歷,不僅解決棧溢出,更打開了**惰性流處理、管道轉換、併發分發**的大門,是 PHP 進階工程師的必備技能。

copyright © 萬盛學電腦網 all rights reserved