3

特定のプライオリティ キューを作成しています。その構造は次のようにする必要があります。

Priority(<int>)    Data(List<Object>)
1                  a, b, g, h
3                  c, d, j
4                  k
10                 e, f, i

特定の優先度のリストが存在するかどうかを効率的に見つける必要があります。そうでない場合は、リストを作成してメッセージを追加します。そうでない場合は、メッセージを既存のリストに追加します。

私は赤黒木を書きましたが、これはやり過ぎのようで、最速の解決策ではないかもしれません。また、優先順位によってメッセージを簡単に取得できないという欠点もあります。これは、書き込みが完了したら実行できるようにする必要があります。

Dictionary について考えてみたのですが、間違っていなければ「__というキーが存在する場合はそれに対応する値を与え、そうでなければ null を与える」という単純な方法はありません。または、何か不足していますか？

編集

私の現在の実装は、32 個の固定リストを持つことです。３２ビットフラグに該当リストを追加し、該当ビットをセットする。De Bruijn のアルゴリズムを使用して LSB を取得します。これは効率的ですが、緩和したい他の複雑さを追加しています。

4

3 に答える 3

3

SortedDictionary がジョブを埋めます。リストを条件付きで検索するには、TryGetValue() を使用するだけです。

于 2011-05-14T11:16:47.493 に答える
3

Dictionaryうーん、下層のコンテナーとして何が問題なのですか? rb-tree では O(log n) ではなく、平均して O(1) アクセス/挿入時間が得られます。必要に応じてラップするだけDictionaryです。たとえば、次のようになります。

internal public class PriorityQueue<TValue> 
{
    private Dictionary<int, List<TValue>> mDict;

    // only Add, TryGetValue shown...
    public void Add(int pPriority, TValue pInput) 
    {
        List<TValue> tTmp;
        if (mDict.TryGetValue(pPriority, tTmp)) 
        {
            tTmp.Add(pInput);
        } 
        else 
        {
            mDict.Add(pPriority, new List<TValue>{ pInput });
        }
    }

    public bool TryGetValue(int pPriority, out List<TValue>) 
    {
        // obvious...
    }
}
于 2011-05-14T11:28:46.370 に答える
3

多分あなたは使うべきですDictionary<int,List<object>>

public void Add(int priority,object data)
{
    if(dictionary.ContainsKey(priority))
       dictionary[priority].Add(data);
    else
       dictionary.Add(priority,new List<object>{data});
}
于 2011-05-14T11:18:23.383 に答える