1

私はツリーデータ構造を持っています。通常の挿入および削除関数に加えて、ツリーに存在するノードから特定の値を計算する COMPUTE 関数があります。挿入関数と削除関数はツリーに影響します。ただし、COMPUTE 関数はツリーを変更しません。COMPUTE 関数には独自の内部キューがあり、これらのキューにノードを追加および削除します。ここでは、compute 関数の簡略化された疑似コードを示します。

class tree{
    vector<int> value;
    tree * children
}

tree::COMPUTE(vector<int> inputValue)
{
    Set currentSet;
    Set nextSet
    currentSet.add(root);

    foreach (node in currentSet)
    {
        if(node has children)
            foreach(childNode of node)
            {
                if(CONDITION_SATISFIED(childNode))
                    add childNode to nextSet;
            }
        else
            output childNode
    }


}

そのため、COMPUTE 関数は単純にツリーを再帰し、ノードを独自の内部セット データ構造に追加して、いくつかの計算を行います。

ここで、COMPUTE 関数をマルチスレッド化したいと考えています。ツリーを変更しないので、これは簡単に実行できると思います。各スレッドは独自の値を与え、独自の COMPUTE 出力を取得します。コードは C++ で記述されています。

私の質問はこれです：

私はこのようにそれを呼び出す場合：

void * threadRoutine
{
    tree.COMPUTE(thisThreadVal);
}

int main()
{
    tree myTree();

    //Insertion Code here

    call N threads each with different parameters but the same tree.
}

私はこれが正しいとは思わない。これは、すべてのスレッドが同じツリー オブジェクトの同じメンバー関数を呼び出すためです。そのため、COMPUTE メソッドで使用されるセットのような内部データ構造はマングルされます。

ツリーのメンバー関数としてではなく、ツリーの外に計算関数を記述する必要があると思います。これが正しいかどうか誰か教えてください。

ところで: 誰かが興味を持っている場合に備えて、私が使用する正確なツリーはカバー ツリーと呼ばれます。これは、最近傍クエリを見つけるために使用される比較的新しいデータ構造です。

4

2 に答える 2

2

採用されたアプローチはCOMPUTE、使用されるセットがローカルまたはヒープ内のセットである限り、複数の呼び出しに対して安全ですが、それらへのローカルポインターまたは参照がそのようなポインターまたは参照のみです-したがって、それらはお互いの邪魔にならないようにしてください。

（それ以外の場合はスレッドセーフになる可能性がありますが、それを証明するのははるかに複雑になります）。

別のスレッドが追加または削除の作業を行っているときにこれを行うのは安全ではありません。計算は他の計算と一緒に発生しても安全ですが、変更と一緒に発生することはありません。それが起こる可能性がある場合は、ある種の同期が必要です。または、考えられるすべての操作をまとめて考慮し、それらをすべてスレッドセーフにする必要があります。

関数がメンバー関数か外部かはまったく関係ありません。

于 2012-08-27T09:06:56.527 に答える
-1

後

if(node has children)

新しいスレッドを作成するだけです。保護するミューテックスを追加するnextSet

于 2012-08-27T09:11:04.247 に答える