3

各オブジェクトがその親を指す単方向のオブジェクト ツリーがあります。オブジェクトが与えられたら、オブジェクトのコレクションとして、その子孫のサブツリー全体を取得する必要があります。オブジェクトは実際にはどのデータ構造にもありませんが、すべてのオブジェクトのコレクションを簡単に取得できます。

素朴なアプローチは、バッチ内の各オブジェクトを調べ、指定されたオブジェクトが祖先であるかどうかを確認し、それを脇に置いておくことです。これはあまり効率的ではありません... O(N*N) のオーバーヘッドが発生します。ここで、N はオブジェクトの数です。

別のアプローチは再帰的なものです。つまり、オブジェクトの直接の子を検索し、次のレベルのプロセスを繰り返します。残念ながら、ツリーは単方向です...子への直接的なアプローチはありません。これは、以前のアプローチよりもわずかにコストが低くなります。

私の質問: ここで見落としている効率的なアルゴリズムはありますか?

ありがとう、

ユヴァル=8-)

4

4 に答える 4

3

データベースは同じように機能するので、データベースが行うことを行います。親から子のリストにマップするハッシュテーブルを作成します。それにはO(n)が必要です。次に、そのハッシュテーブルを使用すると、ルックアップとクエリがより効率的になる可能性があります。

于 2008-10-16T16:19:58.050 に答える
3

他の人が述べたように、オブジェクトのハッシュテーブル/マップをそれらの (直接の) 子のリストに構築します。

そこから、「ターゲット オブジェクト」の直接の子のリストを簡単に検索し、リスト内の各オブジェクトに対してプロセスを繰り返すことができます。

これは、再帰の代わりにキューを使用して、Javaでジェネリックを使用してそれを行った方法です。

public static Set<Node> findDescendants(List<Node> allNodes, Node thisNode) {

    // keep a map of Nodes to a List of that Node's direct children
    Map<Node, List<Node>> map = new HashMap<Node, List<Node>>();

    // populate the map - this is O(n) since we examine each and every node
    // in the list
    for (Node n : allNodes) {

        Node parent = n.getParent();
        if (parent != null) {

            List<Node> children = map.get(parent);
            if (children == null) {
                // instantiate list
                children = new ArrayList<Node>();
                map.put(parent, children);
            }
            children.add(n);
        }
    }


    // now, create a collection of thisNode's children (of all levels)
    Set<Node> allChildren = new HashSet<Node>();

    // keep a "queue" of nodes to look at
    List<Node> nodesToExamine = new ArrayList<Node>();
    nodesToExamine.add(thisNode);

    while (nodesToExamine.isEmpty() == false) {
        // pop a node off the queue
        Node node = nodesToExamine.remove(0);

        List<Node> children = map.get(node);
        if (children != null) {
            for (Node c : children) {
                allChildren.add(c);
                nodesToExamine.add(c);
            }
        }
    }

    return allChildren;
}

予想される実行時間は、正しい計算方法を覚えていれば、O(n) から O(2n) の間です。リスト内のすべてのノードに加えて、ノードのすべての子孫を見つけるためのいくつかの操作が保証されます。最悪の場合 (ルート ノードでアルゴリズムを実行する場合)、すべてのノードが表示されます。リストを2回。

于 2008-10-16T17:05:58.767 に答える
0

あなたの質問は少し抽象的ですが、ネストされたセット(スクロールダウン、mysql 固有すぎるかもしれません) が選択肢になるかもしれません。読み取り操作は非常に高速ですが、変更は非常に複雑です (平均してツリーの半分を変更する必要があります)。

ただし、データ構造を変更する機能が必要です。そして、構造を変更できれば、子オブジェクトへの参照を追加することもできると思います。構造を変更できない場合、あなたのアイデアよりも速いものはないと思います。

于 2008-10-16T16:17:39.193 に答える
0

オブジェクトが直接の子を指しているツリーを構築することは、特に将来のルックアップを行う必要がある場合に、おそらく最良のアプローチです。ツリーの構築は、元のツリーの高さに大きく依存します。最大で O(n^2) かかります。

ツリーを構築している間に、ハッシュテーブルを構築します。ハッシュテーブルは、特定のオブジェクトの将来の検索を高速化します (O(1) 対 O(n))。

于 2008-10-16T17:00:11.620 に答える