1

我正在比较两种广度优先搜索算法的时间执行差异。平行和非平行。但是对于我制作的每张图，非并行版本比并行版本快 10 倍。

这是并行广度优先搜索。我不知道问题出在哪里，但我想在这个方法的某个地方：

public static int PBFS(Node start, Node end)
{
    var queue = new ConcurrentQueue<Node>();
    queue.Enqueue(start);

    while (queue.Count != 0)
    {
        bool isFinished = false;
        if (isFinished) break;

        Parallel.ForEach<Node>(queue, CurrentNode =>
        {
            if (queue.TryDequeue(out CurrentNode))
            {
                foreach (Node Child in CurrentNode.Children.Keys)
                {
                    if (Child.IsVisited == false)
                    {
                        Child.IsVisited = true; 
                        if (Child == end) { isFinished = true; return; }
                    }
                    queue.Enqueue(Child);
                }
            }  
            return;
        });
    } return 1;
}

这是非并行 BFS：

public static int BFS(Node start, Node end)
{
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(start);

    while (queue.Count != 0)
    {
        Node CurrentNode = queue.Dequeue();
        CurrentNode.IsVisited = true;

        foreach (Node Child in CurrentNode.Children.Keys)
        {
            if (Child.IsVisited == false)
            {
                Child.IsVisited = true;
                //Console.Write(Child.Name+" ");
                if (Child == end) return 1;
            }
            queue.Enqueue(Child);
        }
        // Console.WriteLine();
    }

    // Console.WriteLine();
    return 0;
}
4

2 回答 2

3

共享数据的并行化和并发需要同步。同步是昂贵的——正如你所看到的那样。 ConcurrentQueue有它自己的同步，这可能不适合您的情况。

超出 CPU 数量的并行化（这可能不会在此处发生，但它是相关的）会导致大量上下文切换——这很昂贵并且会降低并行运行的代码的生产力。即在一个问题上投入更多线程的前提往往会产生相反的效果。

如果性能是一个问题，我认为您可能希望查看不同的设计，可能是基于 Actor 的、消息传递的或生产者/消费者的，以避免共享数据并避免共享数据的同步。

于 2012-09-06T17:41:11.173 回答
1

我建议您首先编写一个并行双向 BFS：您创建两个搜索线程，一个从“箭头”的起始节点开始，另一个从目标节点开始反向，并在搜索时终止两个线程边界“相遇”。例如，在 Java 中看起来像[this]。

于 2013-03-27T12:34:02.343 回答