我正在使用字典来累积键的出现次数,因此,核心操作是编写一个键值对,其中值是前一个值加一或如果没有前一值则仅加一。但是,这需要两个单独的字典操作(读取和写入),而我只能执行一个(AddOrUpdate
)。
我注意到并发字典支持AddOrUpdate
但普通泛型Dictionary
似乎不支持。
因此,对可变整数的引用字典更快。但是,这会引入不必要的引用,这意味着堆分配和写入障碍。所以我猜可能会做得更好,但如果不Dictionary
从头开始重写,我看不到如何做。我对吗?
我正在使用字典来累积键的出现次数,因此,核心操作是编写一个键值对,其中值是前一个值加一或如果没有前一值则仅加一。但是,这需要两个单独的字典操作(读取和写入),而我只能执行一个(AddOrUpdate
)。
我注意到并发字典支持AddOrUpdate
但普通泛型Dictionary
似乎不支持。
因此,对可变整数的引用字典更快。但是,这会引入不必要的引用,这意味着堆分配和写入障碍。所以我猜可能会做得更好,但如果不Dictionary
从头开始重写,我看不到如何做。我对吗?
你可以这样做:
private class Counter
{
public string Key { get ; set ; }
public int Frequency { get ; set ; }
}
...
Dictionary<string,Counter> frequencyTable = new Dictionary<string,Counter>() ;
...
string someKey = GetKeyToLookup() ;
Counter item = null ;
bool hit = frequencyTable.TryGetValue( someKey,out item ) ;
if ( !hit )
{
item = new Counter{ Key=someKey,Frequency=0 } ;
}
++ item.Frequency ;
如果这还不够好,为什么还要自己写?使用高性能C5 集合库。它是免费的(实际上最初是由微软资助的),建立在微软的System.Collections.Generic
界面之上,并且它的字典、集合和包支持FindOrAdd()
语义。
正如 Jim Mischel 所提到的 - 不可能进行单一查找来更改字典的项目值。
ConcurrentDictionary.AddOrUpdate
方法执行多个查找操作(反映的来源):
public TValue AddOrUpdate(TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory)
{
TValue local2;
if (key == null)
{
throw new ArgumentNullException("key");
}
if (updateValueFactory == null)
{
throw new ArgumentNullException("updateValueFactory");
}
do
{
TValue local3;
while (this.TryGetValue(key, out local3))
{
TValue newValue = updateValueFactory(key, local3);
if (this.TryUpdate(key, newValue, local3))
{
return newValue;
}
}
}
while (!this.TryAddInternal(key, addValue, false, true, out local2));
return local2;
}
我用并发字典和简单字典进行了性能测试:
IDictionary 的 AddOrUpdate 扩展:
public static class DictionaryExtensions
{
public static void AddOrUpdate<TKey, TValue>(this IDictionary<TKey, TValue> dict, TKey key, TValue initValue, Func<TKey, TValue, TValue> updateFunc)
{
TValue value;
value = dict.TryGetValue(key, out value) ? updateFunc(key, value) : initValue;
dict[key] = value;
}
}
测试:
static void Main(string[] args)
{
const int dictLength = 100000;
const int testCount = 1000000;
var cdict = new ConcurrentDictionary<string, int>(GetRandomData(dictLength));
var dict = GetRandomData(dictLength).ToDictionary(x => x.Key, x => x.Value);
var stopwatch = new Stopwatch();
stopwatch.Start();
foreach (var pair in GetRandomData(testCount))
cdict.AddOrUpdate(pair.Key, 1, (x, y) => y+1);
stopwatch.Stop();
Console.WriteLine("Concurrent dictionary: {0}", stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
foreach (var pair in GetRandomData(testCount))
dict.AddOrUpdate(pair.Key, 1, (x, y) => y+1);
stopwatch.Stop();
Console.WriteLine("Dictionary: {0}", stopwatch.ElapsedMilliseconds);
Console.ReadLine();
}
static IEnumerable<KeyValuePair<string, int>> GetRandomData(int count)
{
const int constSeed = 100;
var randGenerator = new Random(constSeed);
return Enumerable.Range(0, count).Select((x, ind) => new KeyValuePair<string, int>(randGenerator.Next().ToString() + "_" + ind, randGenerator.Next()));
}
在我的环境中测试结果(毫秒):
ConcurrentDictionary: 2504
Dictionary: 1351
如果您使用引用类型,则字典更新不需要多次查找:
假设您有一个Dictionary<string, Foo>
, 其中Foo
是一个引用类型并包含一个Count
属性:
void UpdateCount(string key)
{
Foo f;
if (dict.TryGetValue(key, out f))
{
// do the update
++f.Count;
}
else
{
dict[key] = 1;
}
}
如果您的值是值类型……那么,您必须处理值类型语义。这包括必须进行两次查找。
也就是说,字典查找非常快。如果这给您带来了问题,那么您必须要计算很多次。