2

.NET 2.0（はい、2.0）アプリケーションに階層データを入力しようとしていますが、現在のアップグレードはテーブルから外れています（したがって、LINQ、LINQ Bridgeなどはありません）。

このクラス構造に階層データを取り込むためのより良い方法があるかどうか疑問に思いましたか？これを達成するためのはるかに良い方法があると私はかなり確信しています。

これを行うための良い方法を見るのは本当に素晴らしいことです。誰かが.NET2.0の方法を示す時間があり、別の方法がある場合は、.NET4.0以降でそれを行うのは素晴らしいことです。

ノードタイプ構造の例を次に示します。

using System.Collections.Generic;

public class ExampleNode
{

private int _id;

private Nullable<int> _parentId;


private int _depth;

private List<ExampleNode> _children = new List<ExampleNode>();

public ExampleNode()
{
}

public virtual int ApplicationNumber {
    get { return _id; }
    set { _id = value; }
}

public virtual Nullable<int> ParentId {
    get { return _parentId; }
    set { _parentId = value; }
}


public virtual int Depth {
    get { return _depth; }
    set { _depth = value; }
}


public virtual List<ExampleNode> Children {
    get { return _children; }
    set { _children = value; }
}
}

これは、ノード構造を設定するために使用されている関数の例です。これを行うのは最善の方法ではないようで、孫タイプのデータを入力しない可能性があります。深さは、階層内のレベルとしてストアドプロシージャから返されます（レベル0のアイテムはトップレベルであり、ノードがトップレベルノードの子である場合はレベル1であり、トップレベルノードの孫はレベルです） 2など）

public List<ExampleNode> GetNodes()
{
// This may not be optimal.

List<ExampleNode> nodeList = new List<ExampleNode>();
Dictionary<int, ExampleNode> nodeDictionary = new Dictionary<int, ExampleNode>();

using (SqlDataReader reader = SqlHelper.ExecuteReader(ConfigurationManager.ConnectionStrings("SqlServer").ConnectionString, CommandType.StoredProcedure, "proc_GetNodeStructure", new SqlParameter("@UserId", userId), new SqlParameter("@NodeTypeId", nodeType))) {
    while (reader.Read) {
        ExampleNode nodeInstance = new ExampleNode();

        nodeInstance.Id = Convert.ToInt32(reader("Id"));
        nodeInstance.Depth = Convert.ToInt32(reader("Depth"));


        if (!Information.IsDBNull(reader("ParentId"))) {
            nodeInstance.ParentId = Convert.ToInt64(reader("ParentId"));
        }

        // Add to list
        nodeList.Add(nodeInstance);

        // Add to dictionary
        nodeDictionary.Add(nodeInstance.Id, nodeInstance);

    }
}

foreach (ExampleNode item in nodeList) {
    if (item.ParentId.HasValue) {
        nodeDictionary(item.ParentId).Children.Add(item);
    }

}

for (int i = nodeList.Count - 1; i >= 0; i += -1) {
    if (nodeList(i).Depth > 0) {
        nodeList.RemoveAt(i);
    }
}

return nodeList;
}
4

2 に答える 2

2

私が正しく理解していれば、あなたは

  1. ノードをリストと辞書にまとめます
  2. リストを繰り返し処理し、辞書を介して親子関係を調整します
  3. 正の深さを持つノードをリストから削除します

...これにより、階層構造の最上位ノードを含むリストが残ります。あなたのアルゴリズムは私には正しいようです。

最初の2つの操作は、ノード数に対する時間と空間のO（n）の複雑さです。これは、かなり良いことです。

あなたがしている唯一の本当に非効率的なことは、ステップ3でリストから要素を削除することです。基になるストレージはベクトルであるため、残りのすべての要素をコピーする必要があるため、リストの先頭から要素を削除するとコストがかかります。リストを逆方向に繰り返すことで、このようなコピーの量を最小限に抑えようとしています。リストの後半が親ノードで、前半分が子ノードであると想像してください。子ノードを削除するときはいつでも、子ノードが削除されるたびに元のリストサイズの半分をコピーする必要があります。これはO（n ^ 2）の振る舞いに近づきます。

したがって、ステップ3では、時間内にパフォーマンスを向上させたい場合、少なくとも2つの選択肢があります。

  1. 深さ==0である最初の要素のみを含む2番目のリストを作成します。
  2. 代わりにリンクリストを使用して、削除が最大O（n）のパフォーマンスではなくO（1）になるようにします。

最初のオプションのコードは次のとおりです。

...

List<ExampleNode> roots = new List<ExampleNode>();
for (int i = 0; i < nodeList.Count; i ++) { 
    if (nodeList[i].Depth == 0) { 
        roots.Add(nodeList[i]);
    }
} 
return roots;

手順1または2でルートノードの数を数え、2番目のリストを初期化して、その容量がルートノードの数と等しくなるようにすることで、さらに時間を節約できる可能性があります。これにより、リストに要素を追加しているときに、基になるリストベクトルの不要な割り当てとコピーを防ぐことができます。 

List<ExampleNode> roots = new List<ExampleNode>(rootCount);

nodeList同じことが最初の;にも当てはまります。クエリから返されるレコードの数がわかるまで、その構築を遅らせることができます。

于 2012-07-09T03:17:24.027 に答える
0

NHibernateを使用するのはどうですか？.net 2 plusで動作するため、先に進むこともできます。

于 2012-07-09T01:24:20.840 に答える