0

約 15,000 のノードを使用して、それらから階層を構築しようとしています。ノードは決してソート可能ではなく、それぞれが無限の数の子を持つことができますが、親は常に子の前に関数に供給されます。私が持っているコードは N の値が小さい場合に機能しますが、N > 2,000 の場合、サーバーでの最大実行時間を超えてしまいます。これを行うためのより良い方法があるかどうかはわかりませんが、ここに私が持っているものがあります：

function insertNode(&$treeNode, $insertNode) {
    if($insertNode['DEPTH'] <= $treeNode['DEPTH']) return false; 
    if($treeNode['ID'] == $insertNode['PARENT_ID']) {
        $treeNode['CHILDREN'][] = $insertNode;
        $treeNode['CHILD_COUNT']++;
        return true;
    }
    else {
        foreach($treeNode['CHILDREN'] as $key=>$value) {
            $found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
            if($found) {
                $treeNode['CHILD_COUNT']++;
                return true;
            }
        }
    }
}

現時点での私の最善の解決策は、再帰を数千ノードに相当する深さの構築に制限し、Javascript で、ツリーが完全に完成するまで各下位ノードのスクリプトを呼び出すことです。ただし、すべてを一度に実行できるようにしたいのですが。

4

1 に答える 1

0

私は自分でそれを理解しました。キーは次のとおりです。

親は常に、子供より先に関数にフィードされます

私が使用していた SQL クエリ ( Oracle CONNECT BY) は、すべての子 (およびそのすべての子) を直接の祖先の直後に出力しました。たとえば、データセット:

|id|parent_id|
|A-|---------|
|C-|-----A---|
|Bb|-----B---|
|B-|-----A---|

クエリによって次のように配信されます。

|id|parent_id|
|A-|---------|
|B-|-----A---|
|Bb|-----B---|
|C-|-----A---|

クエリのすべての行を順番に循環し、各行に対して再帰挿入関数を呼び出していました。各関数呼び出し内でforeach、行の親が見つかるまで、ツリー内の現在のノードのすべての子に対して再帰呼び出しを行うループを使用していました。

foreach($treeNode['CHILDREN'] as $key=>$value) {
    $found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
    if($found) {
        $treeNode['CHILD_COUNT']++;
        return true;
    }
}

しかし、すべての子の親は常にその深さの最後に挿入された項目であったため (その深さを循環した最後の行だったため)、親はツリーの右端のブランチの右端の子であることが保証されていました。ループは不要だっただけでなく、実際に私ができる最悪のことでした。つまり、子を左から右に循環させていましたが、親は常に右端の分岐の右端の子であり、関数がループする最後の項目でした。通過してトラバースします。（あれは何O(N^2)？） タイムアウトだったのも不思議ではありません。

を切り取り、代わりにコールにforeach置き換えました。end()

$lastChild = $treeNode['CHILDREN'];
end($lastChild);
$key = key($lastChild);
$found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
if($found) {
    $treeNode['CHILD_COUNT']++;
    return true;
}

これにより、関数が行ごとに再帰的に自分自身を呼び出す回数が指数関数的に削減されるため、実行時間が大幅に短縮されました。N=15,000 で約 6 秒で機能するようになりました (以前は N=2,000 という低さで 30 秒に制限されていました)。ノード数の上限や JS による遅延読み込みは必要ありません。

于 2013-08-01T18:13:02.563 に答える