0

これらの相対リンクを分割するための最良の解決策は何ですか

folder-1/folder-2/item-a.txt
folder-1/folder-2/item-b.txt
folder-1/folder-3/item-c.txt
folder-1/folder-3/item-a.txt
folder-1/item-f.txt
folder-1/folder-2
folder-1/folder-3
folder-1
item-b.txt
item-g.txt

PHP配列に？

$testArray = array(
    "folder-1/" => array(
        "folder-2" => array(
            "item-a.txt",
            "item-b.txt"
        ),
        "folder-3" => array(
            "item-a.txt",
            "item-c.txt"
        ),
        "item-f.txt"
    ),
    "item-b.txt",
    "item-g.txt",
);
4

1 に答える 1

2

最も深いパスの深さdとパスの数を考えると、ルックアップが一定である場合 (PHP の場合)、最悪の場合の O (nk) で非常に簡単に実行できます。

$root = array();

foreach ($I as $i) {
    $d =& $root;
    $P = explode("/", $i);

    foreach ($P as $p) {
        if (!array_key_exists($p, $d))
            $d[$p] = array();

        $d =& $d[$p];
    }
}

親ディレクトリが子ディレクトリの前に確実に表示されるように入力をソートして前処理することで、これをさらに最適化できます。

次に、次の各エントリを追加する必要があることを確認します (したがって、array_key_exists-条件は冗長です)。次に、「カーソル」をどこに配置するかを知るための賢い方法が必要です$r。このコードはもう少し複雑になる可能性があります。

また、どの時点で前処理とナビゲーションのコストが$r一般的な時間の複雑さを改善するのか完全にはわかりません。

于 2014-06-16T00:19:31.150 に答える