遍历树时使用线程
我想加快穿越树的过程。 以下是节点的示例:
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上进行门控非常重要:
当然,不要忘记,如果问题实际上是使机器的I / O能力饱和,那么没有多少处理器并行性会造成损害。 如果您正在填充游泳池,则在同一个水龙头中添加更多软管不会增加通过该水龙头的流量。
如果要并行遍历树,则必须:
如果你得到“奇怪的结果”,上面的一个可能不是真的。 请记住,在multithreading示例中,遍历节点的顺序是不确定的。 在宣布结果“奇怪”时你是否说明了这一点?
即使是这样:
请记住,只有当您的应用程序在单个内核上占用100%的CPU时间时,multithreading才有用。 如果CPU使用率很低(因为它在硬盘驱动器或网络之后等待),您将看不到并行运行代码的任何好处。
最近我不得不创建一个能够发现巨大树结构的算法(实际上是文件系统,但它可以是任何东西),并对每个项目执行异步操作 。 我想出了一个小型库(使用.Net TPL和并发队列构建),它能够做到这一点:
并行异步TreeWalker
上述就是C#学习教程:遍历树时使用线程分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1038701.html