1

我想加快遍历树的过程。下面是一个节点示例:

    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 个后代,那么如果我们利用并行编程在单独的线程中遍历这 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 个任务更快。

如果您想知道我使用什么算法来快速获取文件,请查看https://stackoverflow.com/a/724184/637142

4

4 回答 4

13

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

TPL 的工作方式不是您将线程分配给问题,您只需将问题分解为“任务”,然后让 TPL 负责找出如何在可用工作人员池中并行化工作。只需为树的每个子分支创建一个任务;这些任务又可以为它们的子分支产生自己的任务。TPL 将从池中分配线程,直到处理器饱和。

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

  • 如果任务受 CPU 限制,则 TPL 将为每个 CPU 分配一个池线程,并让其他任务等待直到有可用内核;最大化吞吐量并使所有处理器饱和。这正是你想要的:如果你买了一台有四个处理器的机器,其中两个是空闲的,那么你为两个不使用的内核付费。

  • 如果单个任务是 I/O 绑定的,那么您可以LongRunning在创建任务时使用该选项向 TPL 指示该任务不应消耗整个内核;其他任务应该在这个核心上轮流完成。

  • 如果看起来确实如此,您有许多I/O 绑定任务,那么您应该考虑使用TaskCompletionSource,因为这样可以更有效地使用“继续”回调。还可以考虑使用 C# 5 的新async/await特性来安排延续;它提供了一种更愉快的方式来编写异步代码。

当然,不要忘记,如果问题实际上是机器的 I/O 能力饱和,那么再多的处理器并行性也不会产生影响。如果您正在为游泳池注水,向同一个水龙头添加更多软管不会增加通过该水龙头的流量。

于 2012-04-05T16:38:08.457 回答
2

如果要并行遍历树,则必须:

  • 对树进行分区,以保证单独的线程在树的不同部分工作(例如,从根开始,您可以将后代节点分配给新线程,直到达到最大程度的并行性。
  • 确保您的树结构通常可以被多个线程安全地遍历(即遍历不会导致树实现中的状态更改副作用)。
  • 确保在遍历期间没有线程更新树。

如果您得到“奇怪的结果”,则上述其中一项可能不正确。请记住,在多线程示例中,遍历节点的顺序是不确定的。您在宣布结果“奇怪”时是否考虑了这一点?

即使是这样:

  • 在目录示例中,您很可能最终会遇到 IO 争用限制了多线程方法的有效性
  • 遍历内存中的节点往往会将事物踢出缓存,从而降低使用多线程的投资回报(错误共享)。
于 2012-04-05T16:19:46.730 回答
2

请记住,仅当您的应用程序在单核上占用 100% 的 CPU 时间时,多线程才有用;如果 CPU 使用率很低(因为它在硬盘驱动器或网络之后等待),您将看不到并行运行代码的任何好处。

于 2012-04-05T16:29:12.427 回答
-1

最近我不得不创建一个算法,它能够发现一个巨大的树结构(实际上是文件系统,但它可以是任何东西)并对每个项目执行异步操作。我想出了一个能够做到这一点的小型库(使用 .Net TPL 和并发队列构建):

  • 并行发现一棵大树
  • 父项总是在子项之前处理
  • 资源使用取决于给定的最大并行度,而不是树大小
  • 异步工作

并行异步 TreeWalker

于 2016-07-24T19:33:09.017 回答