c# - 遍历树时使用线程

Question

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

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

我遍历 try 的方式是这样的:

    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

Answer 1

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

TPL 的工作方式不是为问题分配线程，而是将问题分解为“任务”，然后让 TPL 负责确定如何在可用工作线程池中并行处理工作。只需为树的每个子分支创建一个任务；这些任务可以反过来为它们的子分支产生它们自己的任务。 TPL 将从池中分配线程，直到处理器饱和。

因此，让 TPL 知道您的任务是在 CPU 上还是在 I/O 上被控制是很重要的:

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

• 如果单个任务是 I/O 绑定(bind)的，那么您可以在创建任务时使用 LongRunning 选项来向 TPL 指示该任务不应消耗整个核心；其他任务应该轮到那个核心。

• 如果看起来是这种情况，您有许多 I/O 绑定(bind)任务，那么您应该考虑改用TaskCompletionSource，因为它允许更有效地使用“延续”回调。还可以考虑使用 C# 5 的新 async/await 功能来安排延续；它提供了一种更愉快的方式来编写异步代码。

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