2

C# オブジェクトに再帰的なデータ構造があります。

オブジェクトには「パーツ」の集まりがあります。各パーツにはパーツのコレクションもあります。等々。構造は、理論的には永遠に入れ子になる可能性があります。

object
--> Part
--> Part
  --> Part
  --> Part
    --> Part
  --> Part
--> Part

この構造内のすべてのパーツの数を取得したいと考えています。だから、すべての枝と葉。(上記の例では、全部で 7 つのパーツがあります。)

カウンターを初期化し、ツリーを再帰することなくこれを行う方法はありますか? 確かにこれを行うことはできますが、遅くてやり過ぎのようです。より良い/簡単な方法はありますか?

4

4 に答える 4

5

カウントまたはその他の種類の集計のために、再帰的なデータ構造を処理する自然な方法は、再帰関数を使用することです。

class Part {
    IEnumerable<Part> SubParts {get;set;}
    public int TotalParts {
        get {
            return 1 + SubParts.Sum(p => p.TotalParts);
            //     ^                       ^
            //     |                       |
            // Add one for this part       |
            //                             |
            //         Use LINQ to aggregate counts recursively
        }
    }
}

この関数は、下位レベルのパーツが上位レベルのパーツ間で共有されていない、つまりパーツのグラフがツリーであると想定しています。Partこのような関数のパフォーマンスを改善する 1 つの方法は、再帰計算が 1 回だけ行われるようにするために、 の下位レベルで結果をキャッシュすることです。

キューまたはスタックを実装することで再帰を回避できますが、実装はそれほど単純ではありません。

于 2013-08-16T13:28:47.000 に答える