提高通用字典性能的方法

我有一个Dictinary<int, int>，它填充了〜5Mio记录。提高通用字典性能的方法

考虑到我希望改进的数据量，性能相当不错。我不关心数据总体，我主要关心的是数据检索。

我做的第一件事 - 我将值类型从decimal更改为int，这使我获得了两倍的性能提升。

然后我试图通过将非通用IntComparer到字典的构造函数如下交易“一般性词语”飞车：

public class IntegerComparer : IEqualityComparer<int> 
    { 
     public bool Equals(int x, int y) 
     { 
      return x == y; 
     } 

     public int GetHashCode(int obj) 
     { 
      return obj; 
     } 
    }

但无济于事，性能得到了20％的下降。 SortedDictionary放慢了10倍的速度（虽然没有多少希望）。想知道如何改善性能可以做些什么？

这里只是衡量性能综合测试：

var d = new Dictionary<int, int>(); 
      for (var i = 0; i < 5000000; i++) 
      { 
       d.Add(i, i + 5); 
      } 



     var r = new Random(); 

     var s = new Stopwatch(); 
     s.Start(); 

     for (var i = 0; i < 100000; i++) 
     { 
      var r0 = Enumerable.Range(1, 255).Select(t => r.Next(5000000)); 
      var values = r0.Select(t => d[t]).ToList(); 
     } 

     s.Stop(); 
     MessageBox.Show(s.ElapsedMilliseconds.ToString());

来源

2015-04-02 Dmitry

你为什么exptect该数组自定义比较器的结果比使用“int”的默认比较器的结果更好？也许你在优化错误的东西，你如何访问字典，为什么？它存储什么？你有足够的记忆吗？ – 2015-04-02 09:51:08

如果你真的想要通过编写你自己的哈希表来实现更好的性能。内置的字典中有一些不是严格需要的开销。当我上次做到这一点时，我认为我做了5倍加速。这是很多测试和调整工作。另一方面，我有一个小的数据集。你的CPU不适合CPU高速缓存，所以内存访问可能使其他所有东西都变得渺茫。 – usr 2015-04-02 09:56:17

@usr你不止一次这样做过？ ...;） – Carsten 2015-04-02 09:57:00

正如评论指出测试存在严重缺陷...

如果您将看到指数最高为5,000,0000那么数组将是最高性能的选项。我试着快速重写你的测试以消除一些错误。可能会有错误，编写准确的基准测试是困难的。

static void Main(string[] args) 
    { 
     var loopLength = 100000000; 

     var d = new Dictionary<int, int>(); 
     for (var i = 0; i < 5000000; i++) 
     { 
      d.Add(i, i + 5); 
     } 
     var ignore = d[7]; 

     var a = new int[5000000]; 
     for (var i = 0; i < 5000000; i++) 
     { 
      a[i] = i + 5; 
     } 
     ignore = a[7]; 

     var s = new Stopwatch(); 
     var x = 1; 
     s.Start(); 

     for (var i = 0; i < loopLength; i++) 
     { 
      x = (x * 1664525 + 1013904223) & (4194303); 
      var y = d[x]; 
     } 

     s.Stop(); 
     Console.WriteLine(s.ElapsedMilliseconds); 
     s.Reset(); 
     x = 1; 
     s.Start(); 
     for (var i = 0; i < loopLength; i++) 
     { 
      x = (x * 1664525 + 1013904223) & (4194303); 
      var y = a[x]; 
     } 

     s.Stop(); 
     Console.WriteLine(s.ElapsedMilliseconds); 
     Console.ReadKey(true); 
    }

X系数从维基百科的线性同余发生器文章借用

我的结果：

这使得超过12倍的速度更快

来源

2015-04-02 10:36:53

这一切都非常有意义。 – Dmitry 2015-04-02 10:43:26

你的测试并不是很好。你也在测量'Random.Next'。你也在比较苹果和橘子。使用'array [7]'与dict [7]'不同。前者访问第八个元素，后者是键7的值。 – 2015-04-02 10:43:27

@TimSchmelter，我知道，我试图删除它是为了移除'randomTime'。它需要非顺序访问才能避免缓存/流水线优化。不知道如何避开它 – 2015-04-02 10:45:13

提高通用字典性能的方法

回答

相关问题