0

要件は次のとおりです。

  1. 並べ替えに使用される Priority 整数に加えて一意の ID を含む、複数のプロパティを持つオブジェクトを格納します。
  2. 優先度の値が重複します。
  3. ID（つまり、辞書/ハッシュテーブルキー）によるオブジェクトの検索/存在のチェックはO（1）です。
  4. Priority による「上位 10 項目」の取得は、できるだけ速く行う必要があります。私の仮定では、これは、ディクショナリ/ハッシュ テーブル内の項目への参照を保持する個別の List / LinkedList が必要であることを意味します。その場合、アイテムが追加または削除されたとき、またはアイテムの Priority 値が変更されたときはいつでも、この List / LinkedList を維持する必要があります。
  5. アイテムの追加/削除、またはアイテムの優先度の変更時にアイテムを再ソートすることは、可能な限り高速です。

どのデータ構造を使用しますか? .NET には既に存在しますか? それともカスタムビルドする必要がありますか？私は後者に傾いています。

4

1 に答える 1

2

SortedListは、シーケンシャル アクセスと O(log n) 検索を提供します。これは、提供されている .NET コレクションで実行できる最善の方法です。

これを行う必要があるときは、優先キューと辞書を組み合わせました。それは次のように見えました：

var myqueue = new PriorityQueue<DataType>();
var myDictionary = new Dictionary<KeyType, PriorityQueueNode<DataType>>();

アイテムを挿入するたびに、それをキューに挿入し、PriorityQueueNode. 私はそれを辞書に入れました。

これにより、O(1) の検索と O(log n) の挿入が可能になりました。私が使用したバイナリ ヒープ プライオリティ キューではなくペアリング ヒープを使用すると、償却された O(1) 挿入を取得できます。

上位 k 個のアイテムを取得するのは O(n log k) です。ここで、n は優先キュー内のアイテムの数です。そのためにヒープ選択を使用しました。ヒープの選択については、理論と実践の出会いで少し書きました。アイテムがすでにヒープにあることを考慮すると、最小ヒープでの選択に最適なアルゴリズムに基づく手法を使用して、O(k) で実行できるはずです。可能だと思いますが、やったことはありません。

私はヒープベースのプライオリティ キューを持っています。ソースはhttp://mischel.com/pubs/priqueue.zipにあります。残念ながら、私が書いた記事はオンラインではもう入手できません。しかし、私 (jim AT mischel.com) に電子メールを送り、この投稿について言及していただければ、掘り下げられるかどうかを確認します。

ただし、辞書と優先キューを組み合わせたコードはもうありません。ごめん。

コメントの質問への回答

プライオリティ キューが必要か、リスト/リンク リストが必要かは、その使用方法とコレクション内のアイテムの数によって異なります。線形リストを使用する場合、追加と変更の優先度は O(n) です。キーで削除する場合、削除は O(1) です。削除する前にアイテムを見つける必要があるため、優先度による削除は O(n) です。しかし、上位 k 個のアイテムを見つけるのは簡単です。最初の k 個のアイテムを取得します。

バイナリ ヒープ優先度キューでは、挿入、削除、および変更の優先度は O(log n) です。上位 k 個のアイテムを取得するのは O(k) ですが、実際には線形リストよりも遅くなります。常にトップ 10 が必要であることがわかっている場合は、それらを検索して別のリストにキャッシュすることができます。そうすれば、ほとんどの場合、それらをすばやく返すことができます。優先順位を追加、削除、または変更するたびにダーティ フラグを設定して、次に誰かが要求したときにトップ 10 リストを再生成するようにします。

ペアリング ヒープは、探しているものである可能性が非常に高いです。O（1）の償却時間で追加および削除します。優先度を変更することはそれほど悪いことではありません (リンクされたウィキペディアの記事と元の論文 [上にリンクされている] を参照してください)。削除は O(log n) です。トップ 10 を見つけるための最悪のケースは O(n log k) ですが、アイテムをキャッシュして、ヒープが変更された場合にのみトップ 10 を再生成することができます。k が定数であるか、最大 k がアイテムの総数のわずかな割合である場合、キャッシュのアイデアは最適に機能します。

いくつかのプライオリティ キューの実装を持つC5 Generic Collection Libraryをご覧ください。私はそれを使用していませんが、それについて良いことを聞いています。

それは実際には、コレクション内にあるアイテムの数と、変更の頻度と上位 10 のリクエストの頻度に依存します。線形リストでの操作のコストには、多くのアイテム (おそらく数千) は必要ありません。本当にあなたを殺すために。また、上位 10 のリストを簡単にキャッシュして、必要に応じて再作成できるため、コレクションのサイズが大きくなった場合、他の操作にかかるプライオリティ キューの低コストは非常に魅力的です。

考えてみると、操作の組み合わせを考えると、これSortedListが必要な場合があります。上位 10 項目の取得は非常に高速です。使い方は簡単です。プロトタイプを作成して、十分なパフォーマンスが得られるかどうかを確認してみませんか?

于 2013-09-12T00:03:57.797 に答える