3

ツリーのようなデータ構造を形成するためにそれ自体を再帰する次のクラスがあります。 

public class chartObject
{
    public string name { get; set; }
    public int descendants { get; set; }
    public List<chartObject> children { get; set; }
}

ツリー内の各オブジェクトについて、その下に存在する量のオブジェクトを子孫プロパティに入力したいと思います。

構造例:

chartObject1 (descendants: 4)
└-chartObject2 (descendants: 0)
└-chartObject3 (descendants: 2)
└--chartObject4 (descendants: 1)
└---chartObject5 (descendants: 0)

これを行う最も効率的な方法は何でしょうか?

4

4 に答える 4

4

再帰式はどうですか：

children.Count + children.Sum(c => c.descendants)

これは、ツリーが不変である場合 (クラス宣言からのものではない場合)、熱心な評価 / キャッシュに適しています。可変性に直面しても効率が必要な場合は、これがはるかに難しいことがわかります。ツリーの一部が変異したときに「ダーティ」とマークすることを検討したり、ツリーの一部が変異したときにこのメトリックの再評価を強制的に「バブルアップ」させたりすることができます。

于 2012-07-24T01:23:15.077 に答える
2

これは私のために働く：

public void SetDescendants(chartObject current)
{
    foreach (var child in current.children)
    {
        SetDescendants(child);
    }
    current.descendants = current.children.Sum(x => 1 + x.descendants);
}

私はこのコードでテストしました：

var co = new chartObject()
{
    name = "chartObject1",
    children = new List<chartObject>()
    {
        new chartObject()
        {
            name = "chartObject2",
            children = new List<chartObject>() { }
        },
        new chartObject()
        {
            name = "chartObject3",
            children = new List<chartObject>()
            {
                new chartObject()
                {
                    name = "chartObject4",
                    children = new List<chartObject>()
                    {
                        new chartObject()
                        {
                            name = "chartObject5",
                            children = new List<chartObject>() { }
                        }
                    }
                }
            }
        }
    }
};

そして、結果としてこれを得ました：

結果

于 2012-07-24T01:39:40.670 に答える
1

計算を最も効率的にするには、その結果をノード自体にキャッシュします。descendantsそうしないと、プロパティが検索されるたびにカウントが再計算されます。

これを行うコストは、次のように、親チェーンまでずっとキャッシュを無効にする必要があることです。

public class chartObject
{
    private chartObject _parent;
    private int? _descCache = null;
    public string name { get; set; }
    public int descendants {
        get {
            return _descCache ?? calcDescendents();
        }
    }
    public List<chartObject> children { get; set; }
    public void AddChild(chartObject child) {
        child._parent = this;
        children.Add(child);
        chartObject tmp = this;
        while (tmp != null) {
            tmp._descCache = null;
            tmp = tmp._parent;
        }
    }
    private int calcDescendents() {
        return children.Count+children.Sum(child => child.descendants);
    }
}
于 2012-07-24T01:31:16.677 に答える
0

ツリーのすべてのノードをウォークし (最初の深さは問題ありません)、子で完了したら、「descendants プロパティを子の子孫の合計 + 子の数に設定します。ツリー構造を変更するたびにこれを行う必要があります。更新を制限できるはずです。変更された要素の親に対してのみ。

ノードが不変にされた場合、作成時にフィールドに入力できます。

補足:

  • ツリーは現状のままで変更可能です (子ノードをどこにでも簡単に追加できます)。そのため、ノードのプロパティではなく、子孫をカウントするメソッドを使用する方が安全な場合があります。
  • 計算されたプロパティint descendants { get; set; }を読み取り/書き込みにすることは、誰でもその値を任意の数値に設定できるため、混乱を招きます。読み取り専用にして、子ノードの 1 つが変更されたときに更新するかどうかを検討してください (何らかのカスタム通知メカニズムが必要です)。
  • コード スタイル - 公開することを意図したコードのクラス名は大文字にすることを検討してください (Microsoft の C# コーディング ガイドラインに従ってください)。chartObject->ChartObject
于 2012-07-24T01:34:44.743 に答える