3

何億回も呼び出される関数にキャッシュを実装しています。キャッシュサイズは数千万アイテムです。現在Dictionary、を使用して実装されており、その中のルックアップにはかなりの時間がかかります。

値だけでなく、のペア全体への参照を取得することは可能Dictionaryですか？そのため、値が存在するかどうかを確認し、単一のルックアップを使用して存在する場合はそれを確認します（場合によっては更新します）。

現在、私はこのようなものを持っています：

int val;
if (cache.TryGetValue(key, out val))
    if (val < newVal) cache[key] = newVal;
    else return val;
else
    cache.Add(key, newVal);

私はこれを手に入れたいです：

Pair pair = cache.GetPair(key);
if (pair != null)
    if (pair.Value < newVal) pair.Value = newVal;
    else return pair.Value;
else
    cache.Add(key, newVal);

これを可能にする代替のデータ構造があれば、私もそれについて聞いてうれしいです。

前もって感謝します！

4

3 に答える 3

4

これは、マーレ・インフィニタスの答えに触発されています。変数cacheがaになったとすると、次のように記述された場所にDictionary<string, int>変更できます。Dictionary<string, MutableInt32>MutableInt32

// wraps an int that may change
class MutableInt32
{
  public int Value;
}

次に、コードを次のように変更できます

MutableInt32 val;
if (cache.TryGetValue(key, out val))
  if (val.Value < newVal) val.Value = newVal;
  else ...
于 2012-06-10T21:40:23.477 に答える
2

ディクショナリ内のハッシュおよび検索バケット操作の数を半分に削減できるという点で、あなたのアイデアは優れています。私はそのようなものを自分でベンチマークしました、そして辞書は人々が考えるほど速くはありません。

残念ながら、組み込みの辞書はこれをサポートしていません。回避策すらありません。

独自のハッシュテーブルを実装して、これを自分で行うことができます。法的な問題はさておき、Dictionaryの実装から始めて、GetAndUpdateOrCreateメソッドを追加できます。

于 2012-06-10T21:12:15.727 に答える
2

もちろん、ペアを辞書に保存することもできます。

public class KeyValueTuple
{
    private string key;
    private int value;

    public KeyValueTuple(string key, int value)
    { 
        this.key = key;
        this.value = value;
    }
}

public class BigDataCache
{
    private Dictionary<string, KeyValueTuple> cache;

    public BigDataCache()
    {
        cache = new Dictionary<string, KeyValueTuple>();

        cache.Add("entry1", new KeyValueTuple("entry1", 1));
        cache.Add("entry2", new KeyValueTuple("entry2", 2));
        cache.Add("entry3", new KeyValueTuple("entry3", 3));
    }

    public KeyValueTuple GetTuple(string key)
    {
        KeyValueTuple value = null;

        if (cache.TryGetValue(key, out value))
        {
            return value;
        }

        return null;
    }
}

public void SomeMethod()
{
    BigDataCache d = new BigDataCache();

    var value1 = d.GetTuple("entry1");
    var value2 = d.GetTuple("entryNotValid");
}
于 2012-06-10T21:18:34.987 に答える