在C#中优化稀疏点积

Question

我正在尝试计算两个非常稀疏的关联数组的点积.数组包含ID和值,因此只应对两个数组共有的ID进行计算,例如

[(1, 0.5), (3, 0.7), (12, 1.3)] * [(2, 0.4), (3, 2.3), (12, 4.7)] = (0.7 * 2.3) + (1.3 * 4.7)

我的实现(称之为dict)目前使用Dictionaries,但它的速度太慢了.

double dot_product(IDictionary<int, double> arr1, IDictionary<int, double> arr2)
  {
     double res = 0;
     double val2;
     foreach (KeyValuePair<int, double> p in arr1)
        if (arr2.TryGetValue(p.Key, out val2))
           res += p.Value * val2;
     return res;
  }

完整数组每个都有大约500,000个条目,而稀疏数组每个只有几十到几百个条目.

我做了一些玩具版点产品的实验.首先,我试图将两个双阵列相乘,看看我能得到的最终速度(让我们称之为" 平坦 ").

然后我尝试使用int[] ID数组和double[] 值数组更改关联数组乘法的实现,在两个ID数组上一起移动并在它们相等时相乘(让我们称之为" double ").

然后,我尝试使用F5或Ctrl- 运行所有三个版本的调试或发布F5.结果如下:

debug F5:    dict: 5.29s double: 4.18s (79% of dict) flat: 0.99s (19% of dict, 24% of double)
debug ^F5:   dict: 5.23s double: 4.19s (80% of dict) flat: 0.98s (19% of dict, 23% of double)
release F5:  dict: 5.29s double: 3.08s (58% of dict) flat: 0.81s (15% of dict, 26% of double)
release ^F5: dict: 4.62s double: 1.22s (26% of dict) flat: 0.29s ( 6% of dict, 24% of double)

我不明白这些结果.
为什么版本中的字典版本F5不像double和flat版本那样优化？
为什么在版本^ F5版本中只略微优化,而其他两个版本经过大量优化？

此外,由于将我的代码转换为"双"方案意味着很多工作 - 你有什么建议如何优化字典？

谢谢!
哈

Answer 1

谢谢大家。我决定将代码转换为在排序数组上使用并行行走（“double”方法），使用正确的包装器不会像我担心的那样花费太多时间来转换。显然，JIT/编译器优化对于泛型的效果不如对于数组的效果好。