1

我有一个树数据结构。除了正常的插入和删除函数之外，我还有一个 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 输出。代码是用 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 回答