遍历树时使用线程
我想加快穿越树的过程。 以下是节点的示例：
class Node { public List 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> t1 = new Task<List>(() => { 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>[] myTasks = new Task<List>[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>(() => { 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
使用任务并行库 ，而不是滚动自己的并行代码。 它非常适合解决这类问题。
TPL的工作方式不是你为问题分配线程，而是简单地将问题分解为“任务”，让TPL负责确定如何在可用工作池之间并行化工作。 只需为树的每个子分支创建一个任务; 这些任务可以反过来为他们的子分支产生他们自己的任务。 TPL将从池中分配线程，直到处理器饱和。
因此，让TPL了解您的任务是否将在CPU或I / O上进行门控非常重要：
-
如果任务是CPU绑定的，那么TPL将为每个CPU分配一个池化线程，并使其他任务等待，直到有可用的核心; 最大化吞吐量并使所有处理器饱和。 这正是你想要的：如果你买了一台带有四个处理器并且其中两个处于闲置状态的机器，那么你支付了两个你没有使用的核心。
-
如果单个任务是I / O绑定，那么您可以在创建任务时使用
LongRunning选项向TPL指示此任务不应占用整个核心; 其他任务应该转向核心。 -
如果看起来像是这样，那么你有许多 I / O绑定任务，那么你应该考虑使用TaskCompletionSource ，因为这样可以更有效地使用“延续”回调。 还要考虑使用C＃5的新
async/awaitfunction来安排延续; 它提供了一种更愉快的编写异步代码的方法。
当然，不要忘记，如果问题实际上是使机器的I / O能力饱和，那么没有多少处理器并行性会造成损害。 如果您正在填充游泳池，则在同一个水龙头中添加更多软管不会增加通过该水龙头的流量。
如果要并行遍历树，则必须：
- 对树进行分区，以确保单独的线程可以在树的不同部分上工作（例如，从根开始，您可以将后代节点分配给新线程，直到达到最大并行度。
- 确保您的树结构通常可以被多个线程安全地遍历（即遍历不会导致树实现中的状态改变副作用）。
- 确保在遍历期间没有线程正在更新树。
如果你得到“奇怪的结果”，上面的一个可能不是真的。 请记住，在multithreading示例中，遍历节点的顺序是不确定的。 在宣布结果“奇怪”时你是否说明了这一点？
即使是这样：
- 在目录示例中，您最终可能会遇到IO争用限制multithreading方法的有效性
- 遍历内存节点将倾向于从缓存中解脱出来，从而降低使用多个线程的投资回报（ 错误共享 ）。
请记住，只有当您的应用程序在单个内核上占用100％的CPU时间时，multithreading才有用。 如果CPU使用率很低（因为它在硬盘驱动器或网络之后等待），您将看不到并行运行代码的任何好处。
最近我不得不创建一个能够发现巨大树结构的算法（实际上是文件系统，但它可以是任何东西），并对每个项目执行异步操作 。 我想出了一个小型库（使用.Net TPL和并发队列构建），它能够做到这一点：
- 并行发现一棵巨大的树
- 父项目始终在孩子之前处理
- 资源使用取决于给定的最大并行度，而不是树大小
- 异步工作
并行异步TreeWalker