今日は、任意の深さのグラフをトラバースして、それを単一の列挙可能なものにフラット化するメソッドを実装する予定でした。代わりに、私は最初に少し検索して、これを見つけました：
public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector)
{
foreach (T item in enumerable)
{
yield return item;
IEnumerable<T> seqRecurse = recursivePropertySelector(item);
if (seqRecurse == null) continue;
foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector))
{
yield return itemRecurse;
}
}
}
理論的にはこれは良さそうに見えますが、実際には、同等の手書きコードを使用してグラフを調べ、必要なことをすべて実行するよりも、パフォーマンスが大幅に低下することがわかりました。これは、このメソッドでは、返されるすべてのアイテムについて、スタックが任意の深さのレベルまで巻き戻される必要があるためだと思います。
また、再帰が排除されれば、このメソッドははるかに効率的に実行されると思います。また、再帰を排除するのがあまり得意ではありません。
再帰を排除するためにこのメソッドを書き直す方法を知っている人はいますか？
助けてくれてありがとう。
編集：すべての詳細な回答をありがとうございました。元のソリューションとEricのソリューションのベンチマークを試しましたが、列挙子メソッドを使用せず、代わりにラムダを再帰的にトラバースしました。奇妙なことに、ラムダ再帰は他の2つのメソッドのいずれよりも大幅に高速です。
class Node
{
public List<Node> ChildNodes { get; set; }
public Node()
{
ChildNodes = new List<Node>();
}
}
class Foo
{
public static void Main(String[] args)
{
var nodes = new List<Node>();
for(int i = 0; i < 100; i++)
{
var nodeA = new Node();
nodes.Add(nodeA);
for (int j = 0; j < 100; j++)
{
var nodeB = new Node();
nodeA.ChildNodes.Add(nodeB);
for (int k = 0; k < 100; k++)
{
var nodeC = new Node();
nodeB.ChildNodes.Add(nodeC);
for(int l = 0; l < 12; l++)
{
var nodeD = new Node();
nodeC.ChildNodes.Add(nodeD);
}
}
}
}
nodes.TraverseOld(node => node.ChildNodes).ToList();
nodes.TraverseNew(node => node.ChildNodes).ToList();
var watch = Stopwatch.StartNew();
nodes.TraverseOld(node => node.ChildNodes).ToList();
watch.Stop();
var recursiveTraversalTime = watch.ElapsedMilliseconds;
watch.Restart();
nodes.TraverseNew(node => node.ChildNodes).ToList();
watch.Stop();
var noRecursionTraversalTime = watch.ElapsedMilliseconds;
Action<Node> visitNode = null;
visitNode = node =>
{
foreach (var child in node.ChildNodes)
visitNode(child);
};
watch.Restart();
foreach(var node in nodes)
visitNode(node);
watch.Stop();
var lambdaRecursionTime = watch.ElapsedMilliseconds;
}
}
TraverseOldが元のメソッドであるのに対し、TraverseNewはEricのメソッドであり、明らかにラムダはラムダです。
私のマシンでは、TraverseOldは10127ミリ秒、TraverseNewは3038ミリ秒、ラムダ再帰は1181ミリ秒かかります。
これは、列挙子メソッド（yield returnを使用）が即時実行とは対照的に3倍の時間がかかる可能性があるという典型的なものですか？それともここで何か他のことが起こっていますか？