我想加快遍历树的过程。下面是一个节点示例:
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