0

私は QueueList テーブルを持っています:

{Id, Queue_Instance_ID, Parent_Queue_Instance_ID, Child_Queue_Instance_ID}

これをに詰め込む最も効率的な方法は何LinkedList<QueueList>ですか? より低くできると思いますo(n^2)か？

4

2 に答える 2

4

O(n) は O(n^2) より優れていますよね？;)

親と子の ID は、実際にはリスト内の前と次の ID であると想定しています。

辞書で簡単に調べられるように、まず項目を辞書に入れますQueueInstanceId。このループでは、最初のアイテムも見つけます。次に、アイテムをリンクされたリストに追加し、辞書を使用して次のアイテムを取得します。C# での例:

Dictionary<int, QueueList> lookup = new Dictionary<int, QueueList>();
QueueList first = null;
foreach (QueueList item in source) {
    lookup.Add(item.QueueInstanceId, item);
    if (item.ParentQueueInstanceId == -1) {
        first = item;
    }
}
LinkedList<QueueList> list = new LinkedList<QueueList>();
do {
    list.AddLast(first);
} while (lookup.TryGetValue(first.ChildQueueInstanceId, out first));

ディクショナリに項目を追加してキーで取得するのは O(1) 操作であり、各ループはソース リストの長さであるため、すべて O(n) 操作です。

于 2009-04-09T03:24:31.907 に答える
0

これについて少し考えてみると、O(n) 時間で実行できますが、オーバーヘッドが追加される余分なものが必要になります。（続いている））。

優れたハッシュテーブルを構築できるように、ある種のユニバーサル ハッシュ スキームを使用できます。基本的に、インスタンス ID でハッシュします。

-各キューを取得し、二重にリンクされた何らかのノードにスローします。- 各ノードをハッシュテーブルに挿入します。- 挿入するときは、親および/または子がハッシュテーブルにあるかどうかを確認し、それに応じてリンクします。_ 完了したら、先頭から開始し (最初のパスで把握できるはずです)、リストをたどって LinkedList に追加するか、結果の二重リンク リストを使用します。

これには O(n) のパスが 1 つ必要で、ハッシュテーブルの初期化には O(n) が必要で、挿入は O(1) です。

あなたに残された問題は、それらの結果をもたらす適切なハッシュテーブルの実装を選択することです。

また、予想される結果の数がわからないため、メモリのオーバーヘッドを考慮する必要があります。うまくいけば、記憶に留めておくのに十分です。

SQL クエリ ベースのソリューションがあるとは知りませんが、私の SQL 知識は非常に限られています。

お役に立てれば！

于 2009-04-09T03:19:44.647 に答える