3

次の問題に対するエレガントで高性能なソリューションを探しています。

リンクされたリストは 256 個あります。

  • 各リストには、並べ替え順序を定義するために使用される整数を保持する同じタイプのオブジェクトが含まれています。
  • すべてのリストのすべての番号は一意です
  • 個々のリストは、これらの番号で昇順にソートされます

元の 256 個のリンク リストのすべてのオブジェクトから単一の昇順リストを作成するにはどうすればよいでしょうか? 私はそれを力ずくでやりたくないので、他にもいくつかのアイデアがありますが、これは標準的で最適な解決策がある問題の1つに思えます。

4

4 に答える 4

3

256 個のリンクされたリストのそれぞれの「最上位」項目を保持する優先キューを使用できます。この「最上位」の項目は、結果リストに挿入される予定の項目です。このようにして、優先度キューから最小の要素を取り出し、それを結果のキューに挿入し、その次の要素を優先度キューに挿入できます。

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())
于 2008-10-02T13:00:59.913 に答える
1

個々のリストが既に並べ替えられている場合は、マージ アルゴリズムを直接適用します。要するに、すべてのヘッドを比較して最小のものを選び、そのリストから取り出して、出力リストにプッシュします。すべてのソース リストが空になるまで繰り返します。

編集: Konrad の優先キュー (ヒープ) の使用は、はるかに洗練されたスケーラブルなソリューションですが、おそらく 256 個の入力リストは非常に少ないため、単純な比較がより高速になる可能性があります。

于 2008-10-02T13:02:05.837 に答える
0

これらのリストの長さはわかりませんが、すべて同時に RAM に収まると思います。私が最初に試みることは、それらをすべて一緒に追加し、私の環境の組み込みの並べ替えルーチンを呼び出すことであり、それが許容できるパフォーマンスをもたらすかどうかを確認します. 実装は簡単で、テストに時間はかかりません。それでも許容できるパフォーマンスが得られない場合は、Konrad Rudolph による優先キューのマージを使用します。

于 2008-10-26T04:18:05.547 に答える
0

各リストをその上のリスト 128 とマージするだけです。(結果として 128 個のリストが作成されます)
次に、各リストを 64 個上のリストとマージします。(結果として 64 個のリストが作成されます)
次に、各リストをその上の 32 個のリストとマージします。(結果として 32 個のリストが作成されます)
次に、各リストをその上の 16 個のリストとマージします。(結果として 16 個のリストが作成されます)
次に、各リストをその上のリスト 8 とマージします。(結果として 8 つのリストが作成されます)
次に、各リストをその上のリスト 4 とマージします。(結果として 4 つのリストが作成されます)
次に、各リストをその上のリスト 2 とマージします。(結果として 2 つのリストが作成されます)
次に、各リストをその上のリスト 1 とマージします。(結果として 1 つのリストが生成されます)
(上記にはループを使用できます)。

于 2008-10-26T04:04:33.640 に答える