php - PHPで最も深いファイルパスを取得する

Question

ファイルパスを持つ配列から最も深いパスを持つ要素を取得する方法を知っている人はいますか? これが奇妙に聞こえる場合は、次の配列を想像してください。

/a/b
/a
/1/2/3/4
/1/2
/1/2/3/5
/a/b/c/d/e

私が取得したいものは次のとおりです。

/1/2/3/4
/1/2/3/5
/a/b/c/d/e

配列全体を何度も反復する必要のない最速の方法は何か疑問に思っています。言語は PHP (5.2) です。

Answer 1

あなたの明確化に続いて、これがそれを行う機能です。見つかった「最も深いパス」の配列を保持し、各パスをそれと比較します。最良のシナリオは O(n) (すべてのパスが最大パスのサブパスである場合) であり、最悪のシナリオは O(n ² ) (すべてのパスが完全に異なる場合) です。

continue 2「外側のループを続ける」という意味であることに注意してください。

<?php

function getDeepestPaths($array)
{
    $deepestPaths = array();
    foreach ($array as $path)
    {
        $pathLength = strlen($path);
        // look for all the paths we consider the longest
        // (note how we're using references to the array members)
        foreach ($deepestPaths as &$deepPath)
        {
            $deepPathLength = strlen($deepPath);
            // if $path is prefixed by $deepPath, this means that $path is
            // deeper, so we replace $deepPath with $path
            if (substr($path, 0, $deepPathLength) == $deepPath)
            {
                $deepPath = $path;
                continue 2;
            }
            // otherwise, if $deepPath is prefixed by $path, this means that
            // $path is shallower; so we should stop looking
            else if (substr($deepPath, 0, $pathLength) == $path)
            {
                continue 2;
            }
        }
        // $path matches nothing currently in $deepestPaths, so we should
        // add it to the array
        $deepestPaths[] = $path;
    }
    return $deepestPaths;
}

$paths = array('/a/b', '/a', '/1/2/3/4', '/1/2', '/1/2/3/5', '/a/b/c/d/e');
print_r(getDeepestPaths($paths));

?>

フォルダー名がスラッシュで終わっていない場合は、2 つifの s で追加のチェックを行う必要があります。より深いパスのプレフィックスの隣の文字がスラッシュであること/foo/barを確認します。よりも「深いパス」/foo/b（そしてそれを置き換えます）。

if (substr($path, 0, $deepPathLength) == $deepPath && $path[$deepPathLength] == '/')
if (substr($deepPath, 0, $path) == $path && $deepPath[$path] == '/')

Answer 2

$aPathes = array(
    '/a/b',
    '/a',
    '/1/2/3/4',
    '/1/2',
    '/1/2/3/5',
    '/a/b/c/d/e'
);

function getDepth($sPath) {
    return substr_count($sPath, '/');
}
$aPathDepths = array_map('getDepth', $aPathes);
arsort($aPathDepths);
foreach ($aPathDepths as $iKey => $iDepth) {
    echo $aPathes[$iKey] . "\n";
}

この例も参照してください。

===更新===

$aUsed = array();
foreach ($aPathes as $sPath) {
    foreach ($aUsed as $iIndex => $sUsed) {
        if (substr($sUsed, 0, strlen($sPath)) == $sPath || substr($sPath, 0, strlen($sUsed)) == $sUsed) {
            if (strlen($sUsed) < strlen($sPath)) {
                array_splice($aUsed, $iIndex, 1);
                $aUsed[] = $sPath;
            }
            continue 2;
        }
    }
    $aUsed[] = $sPath;
}

この例も参照してください。

Answer 3

「スペル」が常に同じであることを保証できる場合 (つまり、「/a/bc/d」対 /a/b\ /c/d)、単純な文字列比較を実行して、文字列の 1 つが他の文字列に完全に含まれています。それが true の場合、文字列を破棄します。両方向で比較する必要があることに注意してください。