c# - 平行广度优先搜索

我正在比较两种广度优先搜索算法在时间执行上的差异。并行和非并行。但是对于我制作的每个图形，非并行版本都比并行版本快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;
}

最佳答案

共享数据的并行化和并发需要同步。同步很昂贵-正如您可能会看到的那样。 ConcurrentQueue有它自己的同步，这对于您的情况可能不是最佳的。

超出CPU数量的并行化（这可能在这里没有发生，但很重要）会导致很多上下文切换-代价高昂，并降低了并行运行的代码的生产率。即在问题上抛出更多线程的前提通常会产生相反的效果。

如果需要考虑性能，我认为您可能希望查看不同的设计，例如Actor-based，message-passing或producer/consumer，以避免共享数据并避免同步共享数据。

关于c# - 平行广度优先搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12305444/