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

这是受 Mare Infinitus 的回答启发的。假设您的cache变量现在是 aDictionary<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 中减少一半的 hash-and-find-bucket 操作。我自己对这些东西进行了基准测试，而 Dictionary 并没有人们想象的那么快。

不幸的是，内置字典不支持这一点。甚至没有解决方法。

您可以实现自己的哈希表并自己执行此操作。撇开法律问题不谈，您可以从 Dictionary 的实现开始并添加 GetAndUpdateOrCreate 方法。

于 2012-06-10T21:12:15.727 回答
2

您当然可以将 Pairs 存储在字典中！

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 回答