ツリーをたどるプロセスを高速化したいと思います。ノードの例を次に示します。
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.ChildrenNode はファイルまたはディレクトリを表すため、このメソッドには約 1 ミリ秒かかります。このノードの例を使用して、要点をよりよく説明しました。
したがって、最初のノードに 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);
}
}
これはしばしば奇妙な結果をもたらしますが、かなり高速です。
結果
task を使用すると、アルゴリズムの速度が約 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 個のファイルとディレクトリを返します (これが正しい数です)。2番目のアルゴリズムは318,195を返しますが、これは非常に近いですが、理由はわかりません...
これを 8 コアのコンピューターでテストしています。おそらく、1 つのタスクを使用して 2 つのコアを備えたコンピューターでこれを実行する場所は、この 17 のタスクすべてを作成するよりも高速になる可能性があります。
ファイルを高速で取得するために使用するアルゴリズムを知りたい場合は、https://stackoverflow.com/a/724184/637142をご覧ください