遍历树时使用线程

Question

我想加快遍历树的过程.以下是节点的示例:

    class Node
    {
        public List<Node> Children { get; set; }
        public int SompeProperty { get; set; }
        public String SomeOtherProperty { get; set; }
    }

我遍历尝试的方式如下:

    static void TraverseTree(Node ParentNode)
    {
        if (ParentNode.Children == null)
            return;

        foreach (var child in ParentNode.Children)
        {
            TraverseTree(child);               
        }
    }

该ParentNode.Children方法大约需要1毫秒,因为Node表示文件或目录.我只是用这个节点的例子来说明我的观点.

因此,如果您考虑一下,如果第一个节点有4个子节点,并且每个子节点都有10000000个后代,那么如果我们在separeate线程中利用并行编程来遍历这4个子节点中的每一个,我们可以提高此遍历的速度.如果那就是情景那么我会采取这种方法.但如果我事先不知道树的结构怎么能这样做呢？

我一直在考虑:

1)开始遍历树,将具有子节点的前10个节点放在堆栈上,然后在单独的线程上开始遍历每个节点.

2)做类似的事情:

    static void TraverseTree(Node ParentNode)
    {
        if (ParentNode.Children == null)
            return;

        foreach (var child in ParentNode.Children)
        {
            ThreadPool.QueueUserWorkItem(new WaitCallback((x) =>
            {                    
                TraverseTree(child);   
            }), null);                            
        }
    }

这通常会给我带来奇怪的结果,但速度要快得多.

---

结果

使用任务将算法的速度提高了约40%,结果如下:

使用以下算法扫描我的整个C:\驱动器大约需要5.81秒:

        //directoryPath  = "C:\"
    var now = DateTime.Now;

        Task<List<ScanItem>> t1 = new Task<List<ScanItem>>(() =>
        {
            return GetAllFilesInDirectory(directoryPath);
        });

        t1.Start();

        t1.Wait();

        var done = DateTime.Now-now;  // done = 5.81 average

使用以下算法扫描我的整个C:\驱动器大约需要3.01秒:

        //directoryPath  = "C:\"  
        var now = DateTime.Now;


        // get all directories in my c: drive it should only contain directories
        var directories = Directory.GetDirectories(directoryPath);

        // directories = 17 directories:  inetpub, MSOCache, PrefLogs, ProgramFiles, ProgramFiles (x86) etc...

        Task<List<ScanItem>>[] myTasks = new Task<List<ScanItem>>[directories.Length];

        // create a task fore each directory in the c:\ drive
        for (int k = 0; k < myTasks.Length; k++)
        {
            var currentDir = directories[k];
            myTasks[k] = new Task<List<ScanItem>>(() =>
            {
                return GetAllFilesInDirectory(currentDir);
            });                
        }

        // start all the tasks
        for (int k = 0; k < myTasks.Length; k++)
            myTasks[k].Start();


        Task.WaitAll(myTasks); // wait for all tasks to finish

        var done = now - DateTime.Now;  // average about 3.01 seconds

如果我遍历列表,第一个算法返回318,222文件和目录(这是正确的数字).第二个算法返回318,195这是非常接近我不明白为什么虽然...

我在一台有8个内核的计算机上测试它.也许如果我在使用一个任务拥有2个内核的计算机上运行它可能比创建所有这17个任务更快.

如果你想知道我用什么算法快速获取文件,请查看/sf/answers/50692911/

Answer 1

使用任务并行库,而不是滚动自己的并行代码.它非常适合解决这类问题.

TPL的工作方式不是为问题分配线程,而是将问题分解为"任务",让TPL负责确定如何在可用工作池之间并行化工作.只需为树的每个子分支创建一个任务; 这些任务可以反过来为他们的子分支产生他们自己的任务.TPL将从池中分配线程,直到处理器饱和.

因此,让TPL了解您的任务是否将在CPU或I/O上进行门控非常重要:

• 如果任务是CPU绑定的,则TPL将为每个CPU分配一个池化线程,并使其他任务等待,直到有可用核心为止; 最大化吞吐量并使所有处理器饱和.这正是你想要的:如果你买了一台带有四个处理器并且其中两个处于空闲状态的机器,那么你支付了两个你没有使用的核心.

• 如果单个任务是I/O绑定,那么您可以LongRunning在创建任务时使用该选项,以向TPL指示此任务不应占用整个核心; 其他任务应该转向核心.

• 如果看起来像是这样,那么你有许多 I/O绑定任务,那么你应该考虑使用TaskCompletionSource,因为这样可以更有效地使用"continuation"回调.还要考虑使用async/awaitC#5 的新功能来安排延续; 它提供了一种更愉快的编写异步代码的方法.

当然,不要忘记,如果问题实际上是使机器的I/O能力饱和,那么没有多少处理器并行性会造成损害.如果您正在填充游泳池,则在同一个水龙头中添加更多软管不会增加通过该水龙头的流量.