3

C# は、プライオリティ キューのネイティブ実装を提供しません。

Stackoverflow では、この種の問題に対する一般的な答えはPower Collectionsを使用することです。

私はそれを進める必要がありますか、それとも欠点はありますか?

4

1 に答える 1

9

パワー コレクションは、.NET フレームワークには (まだ) 存在しない、一般的に使用されるデータ構造のいくつかの優れた実装を実際に提供します。このオプションを使用しても問題はありませんが、このアプローチには重大な欠陥があることを指摘したいと思います。

OrderedMultiDictionary (および他のすべての Power Collection クラス) は、赤黒ツリーを使用して、キーと値のペアの順序付きバッグを作成します。プライオリティ キューの場合、RB ツリーは劣ったデータ構造になる傾向があります。優先度の値は整数にハッシュ可能であると仮定しています。

理由は簡単です。Dictionary は、O(1) で特定の優先度の値にすぐにジャンプできます。そこでは、特殊なデータ構造を使用して、その優先度の値 (キュー) を格納できます。

テスト

私の主張を確認するために、3 つの異なるアイデアに基づいて優先キュー構造を比較する簡単なベンチマークを作成しました。

  1. Power Collections OrderedMultiDictionary
  2. 並べ替えられた辞書
  3. 辞書

2 番目のオプションは、BST として内部的に実装されるSortedDictionaryを使用します。3 番目のオプションでは、O(1) ルックアップを使用した単純な Dictionary を使用します。

Y 軸に示すさまざまな数の要素と、X 軸に示すさまざまな数の異なる値でテストしました。特定の組み合わせの結果は、値の 3x3 マトリックスとして表示されます。最初の行はオプション 1 (OrdererdMultiDictionary、2 番目は SortedDictionary、3 番目は Dictionary) を示します。これら 3 行のそれぞれの最初の値は、それぞれの数の値をキューに入れるのにかかった時間を示し、2 番目は列挙するのにかかった時間を示します。すべての値に対して、3 回目はすべての値を再びキューから取り出す時間です。

すべての時間は log 2です。値 10 は 2^10ms = 1 秒を示しますが、絶対値の重要性は低くなります。要素の数は 2 倍になります。つまり、構造が O(n) のように動作する場合、時間は毎回 1 ずつ増加します。

水平方向では、個別の値の数が列ごとに 32 倍されます。したがって、最初の列 (同じ値が何度も挿入されている) は、値を保持する内部データ構造のパフォーマンスを示します。

使用するマシンは、16 GB と SSD を搭載した i7 です。

          |           1        |          32        |        1024        |       32768        |     1048576        |

       128
          | -4.9 / -4.3 /  n/a | -4.7 / -4.1 /  n/a | -4.8 / -2.9 /  n/a | -4.9 / -2.9 /  n/a | -4.9 / -2.9 /  n/a |
          | -7.5 / -6.1 / -5.3 | -6.5 / -5.7 / -5.1 | -4.7 / -4.9 / -4.3 | -4.6 / -4.7 / -4.2 | -4.6 / -4.8 / -4.2 |
          | -7.5 / -7.6 / -6.6 | -6.8 / -7.3 / -6.3 | -5.9 / -5.9 / -3.0 | -6.2 / -6.4 / -2.8 | -6.2 / -6.3 / -2.8 |


       256
          | -3.8 / -3.2 /  n/a | -3.7 / -3.1 /  n/a | -3.7 / -2.2 /  n/a | -3.8 / -1.8 /  n/a | -3.7 / -1.8 /  n/a |
          | -6.8 / -5.5 / -4.4 | -5.8 / -5.4 / -4.2 | -3.8 / -4.3 / -3.4 | -3.5 / -4.1 / -3.2 | -3.5 / -4.1 / -3.1 |
          | -6.6 / -6.9 / -5.7 | -6.1 / -6.7 / -5.7 | -5.5 / -5.3 / -1.8 | -5.3 / -5.0 / -0.9 | -5.3 / -5.6 / -1.0 |


       512
          | -2.7 / -2.1 /  n/a | -2.5 / -2.1 /  n/a | -2.5 / -1.5 /  n/a | -2.6 / -0.7 /  n/a | -2.6 / -0.7 /  n/a |
          | -5.9 / -5.2 / -3.4 | -4.9 / -5.0 / -3.3 | -3.2 / -4.2 / -2.6 | -2.4 / -3.2 / -2.1 | -2.3 / -3.2 / -2.0 |
          | -5.7 / -6.1 / -4.9 | -5.2 / -6.1 / -4.8 | -4.8 / -5.0 / -1.7 | -4.3 / -4.0 /  1.0 | -4.4 / -4.7 /  1.0 |


      1024
          | -1.6 / -1.0 /  n/a | -1.4 / -1.0 /  n/a | -1.4 / -0.7 /  n/a | -1.5 /  0.4 /  n/a | -1.5 /  0.3 /  n/a |
          | -4.9 / -4.7 / -2.4 | -4.1 / -4.5 / -2.3 | -2.6 / -4.0 / -1.8 | -1.2 / -2.3 / -1.0 | -1.2 / -2.3 / -0.9 |
          | -4.7 / -5.4 / -3.9 | -4.4 / -5.3 / -3.8 | -4.1 / -4.6 / -1.6 | -3.3 / -3.0 /  2.9 | -3.5 / -3.8 /  3.0 |


      2048
          | -0.4 /  0.1 /  n/a | -0.3 /  0.1 /  n/a | -0.3 /  0.3 /  n/a | -0.3 /  1.5 /  n/a | -0.5 /  1.4 /  n/a |
          | -4.0 / -4.1 / -1.4 | -3.2 / -4.0 / -1.3 | -1.7 / -3.5 / -0.9 | -0.2 / -1.4 /  0.1 | -0.2 / -1.3 /  0.1 |
          | -3.8 / -4.5 / -2.9 | -3.5 / -4.4 / -2.9 | -3.2 / -3.9 / -1.0 | -2.5 / -2.0 /  4.9 | -2.4 / -2.1 /  4.9 |


      4096
          |  0.7 /  1.2 /  n/a |  0.8 /  1.2 /  n/a |  0.9 /  1.3 /  n/a |  0.8 /  2.8 /  n/a |  0.6 /  2.9 /  n/a |
          | -3.0 / -3.2 / -0.4 | -2.2 / -3.3 / -0.3 | -0.8 / -3.0 /  0.1 |  0.9 / -0.4 /  1.1 |  0.9 / -0.2 /  1.2 |
          | -2.9 / -3.5 / -1.9 | -2.6 / -3.5 / -1.9 | -2.3 / -3.2 / -0.9 | -1.6 / -1.1 /  6.6 | -1.3 / -1.1 /  6.9 |


      8192
          |  1.8 /  2.8 /  n/a |  1.9 /  3.0 /  n/a |  2.0 /  3.0 /  n/a |  1.9 /  4.0 /  n/a |  1.8 /  4.1 /  n/a |
          | -2.0 / -2.4 /  0.6 | -1.3 / -2.4 /  0.7 |  0.1 / -2.2 /  1.1 |  1.8 /  0.4 /  2.1 |  2.1 /  0.9 /  2.3 |
          | -1.9 / -2.6 / -1.0 | -1.6 / -2.5 / -0.9 | -1.4 / -2.4 / -0.3 | -0.6 / -0.3 /  8.0 | -0.5 /  0.1 /  8.9 |


     16384
          |  2.9 /  3.7 /  n/a |  3.0 /  3.6 /  n/a |  3.1 /  3.8 /  n/a |  3.1 /  4.6 /  n/a |  3.0 /  5.2 /  n/a |
          | -1.0 / -1.5 /  1.6 | -0.3 / -1.5 /  1.7 |  1.1 / -1.4 /  2.0 |  2.4 /  0.7 /  2.9 |  3.2 /  1.9 /  3.6 |
          | -0.9 / -1.6 /  0.0 | -0.6 / -1.6 /  0.1 | -0.5 / -1.5 /  0.4 |  0.0 / -0.1 /  8.0 |  0.6 /  1.2 / 10.9 |


     32768
          |  4.0 /  5.0 /  n/a |  4.1 /  5.0 /  n/a |  4.3 /  5.0 /  n/a |  4.2 /  5.5 /  n/a |  4.1 /  6.4 /  n/a |
          | -0.1 / -0.5 /  2.6 |  0.7 / -0.5 /  2.7 |  2.0 / -0.5 /  3.1 |  3.1 /  0.9 /  3.8 |  4.3 /  3.0 /  4.8 |
          |  0.1 / -0.6 /  1.0 |  0.4 / -0.6 /  1.1 |  0.5 / -0.5 /  1.3 |  0.9 /  0.4 /  8.0 |  1.6 /  2.3 / 12.9 |


     65536
          |  5.2 /  6.6 /  n/a |  5.4 /  6.4 /  n/a |  5.5 /  6.4 /  n/a |  5.5 /  6.8 /  n/a |  5.4 /  7.4 /  n/a |
          |  1.0 /  0.4 /  3.6 |  1.8 /  0.5 /  3.7 |  3.0 /  0.4 /  4.1 |  4.2 /  1.9 /  4.9 |  5.5 /  4.2 /  6.0 |
          |  1.1 /  0.4 /  2.0 |  1.4 /  0.4 /  2.1 |  1.5 /  0.5 /  2.4 |  2.0 /  1.4 /  9.8 |  3.2 /  3.4 / 14.8 |


    131072
          |  6.5 /  7.8 /  n/a |  6.6 /  7.6 /  n/a |  6.8 /  7.4 /  n/a |  6.9 /  7.7 /  n/a |  6.8 /  8.6 /  n/a |
          |  2.0 /  1.4 /  4.6 |  2.9 /  1.4 /  4.8 |  4.1 /  1.5 /  5.2 |  5.2 /  2.4 /  5.8 |  6.8 /  5.4 /  7.0 |
          |  2.1 /  1.4 /  3.1 |  2.4 /  1.4 /  3.1 |  2.5 /  1.5 /  3.3 |  3.0 /  2.0 /  9.9 |  4.4 /  4.6 / 16.6 |


    262144
          |  7.5 /  8.9 /  n/a |  7.6 /  8.9 /  n/a |  7.8 /  8.6 /  n/a |  8.0 /  8.8 /  n/a |  8.2 /  9.6 /  n/a |
          |  3.0 /  2.4 /  5.6 |  3.9 /  2.4 /  5.7 |  5.1 /  2.4 /  6.1 |  6.1 /  2.9 /  6.7 |  8.1 /  6.4 /  8.1 |
          |  3.1 /  2.5 /  4.1 |  3.3 /  2.4 /  4.1 |  3.5 /  2.4 /  4.2 |  4.7 /  3.6 /  9.9 |  5.7 /  5.8 / 18.2 |


    524288
          |  8.6 / 10.0 /  n/a |  8.8 / 10.0 /  n/a |  9.0 /  9.6 /  n/a |  9.4 /  9.7 /  n/a |  9.3 / 10.4 /  n/a |
          |  4.0 /  3.4 /  6.6 |  4.9 /  3.4 /  6.7 |  6.1 /  3.4 /  7.1 |  7.0 /  3.7 /  7.6 |  8.9 /  7.0 /  8.8 |
          |  4.1 /  3.5 /  5.0 |  4.4 /  3.4 /  5.1 |  4.5 /  3.4 /  5.2 |  4.9 /  3.6 /  9.9 |  6.8 /  6.5 / 19.2 |


   1048576
          |  9.7 / 11.0 /  n/a |  9.9 / 11.1 /  n/a | 10.2 / 10.7 /  n/a | 10.7 / 10.7 /  n/a | 10.7 / 11.2 /  n/a |
          |  5.0 /  4.4 /  7.5 |  5.9 /  4.4 /  7.7 |  7.1 /  4.4 /  8.1 |  8.0 /  4.6 /  8.5 |  9.7 /  7.3 /  9.8 |
          |  5.1 /  4.4 /  n/a |  5.3 /  4.4 /  n/a |  5.5 /  4.4 /  n/a |  5.9 /  4.6 /  n/a |  7.7 /  6.8 /  n/a |


   2097152
          | 10.8 / 12.0 /  n/a | 11.0 / 12.1 /  n/a | 11.3 / 11.8 /  n/a | 12.1 / 11.8 /  n/a | 12.0 / 12.1 /  n/a |
          |  6.0 /  5.4 /  8.5 |  7.0 /  5.4 /  8.7 |  8.1 /  5.4 /  9.1 |  9.0 /  5.6 /  9.5 | 10.6 /  7.6 / 10.3 |
          |  6.1 /  5.4 /  n/a |  6.4 /  5.4 /  n/a |  6.6 /  5.4 /  n/a |  6.9 /  5.6 /  n/a |  8.8 /  7.2 /  n/a |


   4194304
          | 11.9 / 13.0 /  n/a | 12.0 / 13.1 /  n/a | 12.5 / 12.9 /  n/a | 13.3 / 12.8 /  n/a | 13.2 / 13.0 /  n/a |
          |  7.0 /  6.4 /  9.5 |  8.0 /  6.4 /  9.7 |  9.2 /  6.4 / 10.1 | 10.1 /  6.5 / 10.5 | 11.6 /  8.0 / 11.1 |
          |  7.1 /  6.4 /  n/a |  7.3 /  6.4 /  n/a |  7.6 /  6.4 /  n/a |  8.0 /  6.5 /  n/a |  9.9 /  7.7 /  n/a |


   8388608
          |  n/a /  n/a /  n/a |  n/a /  n/a /  n/a | 13.7 / 14.1 /  n/a | 14.5 / 13.8 /  n/a | 14.4 / 13.9 /  n/a |
          |  8.0 /  7.4 / 10.5 |  9.0 /  7.4 / 10.7 | 10.2 /  7.4 / 11.1 | 11.1 /  7.5 / 11.5 | 12.6 /  8.5 / 12.0 |
          |  8.1 /  7.4 /  n/a |  8.4 /  7.4 /  n/a |  8.6 /  7.4 /  n/a |  9.1 /  7.5 /  n/a | 10.8 /  8.3 /  n/a |


 16777216
         |  n/a /  n/a /  n/a |  n/a /  n/a /  n/a |  n/a /  n/a /  n/a |  n/a /  n/a /  n/a |  n/a /  n/a /  n/a |
         |  9.0 /  8.4 / 11.6 | 10.0 /  8.4 / 11.7 | 11.2 /  8.4 / 12.1 | 12.2 /  8.4 / 12.5 | 13.6 /  9.1 / 12.9 |
         |  9.1 /  8.4 /  n/a |  9.3 /  8.4 /  n/a |  9.6 /  8.4 /  n/a | 10.1 /  8.4 /  n/a | 11.9 /  9.0 /  n/a |

テストの欠陥

値が 100 未満のすべての行は表示されませんでした。これは、実際には重要ではなく、ウォーミングアップと見なすことができるためです。

すべてのテストは 1 回だけ実行され、平滑化は行われていないため、どちらの方向にもスパイクが発生する可能性があります。10000 を超える値のテストは、少なくとも短いスパイクを除外するためにかなり長い時間実行されました。ベンチマーク全体を数回繰り返しましたが、差は 10% 以内でした。

データ構造が、保持できると予想される適切な量の要素で初期化されていません。これは、部分的には、より大きなセットでのメモリ消費が原因でした。

これを実装する合理的な方法がまだ見つからないため、OMD Dequeuing の値はありません。これについて何か助けていただければ幸いです。

結果

結果は、より大きな値に対してかなり一貫しています。

  1. バケット数 (個別の値の数) が小さい場合、オプション 2 または 3 ベースのアプローチはどちらも、エンキュー時に OMD よりも数倍高速であり、列挙時にはさらに高速です。デキューの比較はありません。
  2. バケット数が多い場合、OMD は遅くなりませんが、オプション 2+3 は遅くなります (係数 10)。最終的に、オプション 2 はエンキューでわずかに劣りますが、それでも列挙は非常に高速です。オプション 3 (単純な辞書) は両方に勝っています。
  3. ただし、オプション 3 は、大量のバケット数のデキューがひどくなり、明らかに使い物にならなくなります。これは、SortedDictionary に存在しない最小キーの永久検索によるものです。

メモリ使用量に関して、OMD はオプション 2 および 3 よりも数倍多くのメモリを使用し、500 万を超える値に対して一貫して OutOfMemory 例外をスローしました。オプション 3 は、オプション 2 よりも著しく少ないメモリを使用しました。各テストの後、完全なガベージ コレクションが強制されました。

結論として、キューの SortedDictionary を使用することをお勧めします。これは、Power Collection で使用された RB ツリー アプローチと同じくらい高速であり、メモリの使用量が少ない傾向があるためです。明確な優先順位の値が少ない場合、利点は大きくなります。もちろん、これは大量のデータを扱う場合にのみ重要です。

ソースコード

SortedDictionary のソース コードを追加します。詳細については、http://pastebin.com/J4snVYzbを参照してください。

public class PriorityQueue<TK, TV>
{
    private readonly SortedDictionary<TK, Queue<TV>> _D = new SortedDictionary<TK, Queue<TV>> ();

    public void Enqueue (TK key, TV value)
    {
        Queue<TV> list;
        if (!_D.TryGetValue (key, out list)) {
            list = new Queue<TV> ();
            _D.Add (key, list);
        }
        list.Enqueue (value);
        Count++;
    }

    public int Count
    {
        get;
        private set;
    }

    public TV Dequeue ()
    {
        var first = _D.First ();
        var item = first.Value.Dequeue ();
        if (!first.Value.Any ()) {
            _D.Remove (first.Key);
        }
        return item;
    }

    public IEnumerable<TV> Values
    {
        get
        {
            var keys = _D.Keys.ToArray ();
            foreach (var key in keys) {
                foreach (var item in _D[key]) {
                    yield return item;
                }
            }
        }
    }
}
于 2013-03-28T14:10:55.340 に答える