C＃提高稀疏矩阵行和列计算总的并行性能 [英] C# Improve parallel performance of Sparse Matrix Row and Column Total Calculations

问题描述

我有一个包含约1亿非零元素的稀疏矩阵：

I have a sparse matrix containing roughly 100 million non-zero elements:

// [Row][Column][Element]
public IDictionary<int, IDictionary<int, decimal>> MyMatrix { get; private set; }

获取每行的总和是非常快的：

Getting the sum of each row is very fast:

private void RowSum()
{
    var rowTotals = new ConcurrentDictionary<int, decimal>();

    Parallel.ForEach(MyMatrix, (row) =>
    {
         rowTotals.TryAdd(row.Key, row.Value.Sum(x => x.Value));
    });
}

获取每列的总和慢得多：

Getting the sum of each column is much slower:

private void ColumnSum()
{
   var columnTotals = new ConcurrentDictionary<int, decimal>();

   Parallel.ForEach(MyMatrix, (row) =>
   {
        foreach (var column in row.Value)
        {
            columnTotals.AddOrUpdate(column.Key, column.Value, 
                 (key, old) => old + column.Value);
        }
   });
}

为使列计算速度更快，我可以创建一个[专栏] [行] [元]矩阵，但是这将增加一倍RAM要求。有什么方法或数据结构将允许该列计算，以尽可能快作为该行的计算，而不RAM翻倍？

To make column calculations faster, I could create a [Column][Row][Element] matrix, but that would double the RAM requirement. Is there any approach or data structure that would allow for the column calculations to be as fast as the row calculations, without doubling the ram?

推荐答案

什么可能会发生的是，没有为集中 ConcurrentDictionary 争。如果是这样的话，你可以尝试 Parallel.ForEach 的 localInit 超载，给每个任务一批自己的本地（和非竞争）词典，然后在最后汇总成中央词典：

What could be happening is that there is contention for the centralized ConcurrentDictionary. If this is the case, you could try the localInit overload of Parallel.ForEach, to give each Task batch its own local (and uncontended) Dictionary, which is then aggregated into the central dictionary at the end:

var columnTotals = new ConcurrentDictionary<int, decimal>();

Parallel.ForEach(MyMatrix,
    // Each Task gets own dictionary
    () => new Dictionary<int, decimal>(),
    (row, state, colTots) =>
    {
        foreach (var column in row.Value)
        {
            if (!colTots.ContainsKey(column.Key))
            {
                colTots[column.Key] = column.Value;
            }
            else
            {
                colTots[column.Key] += column.Value;
            }
        }
        return colTots;
    },
    colTots =>
    {
        // Aggregate the dictionaries
        foreach (var column in colTots)
        {
            columnTotals.AddOrUpdate(column.Key, column.Value, 
                (key, old) => old + column.Value);
        }
    });

修改

有些时序（在100000点¯x100000空间10M填充元素）

Some timings (10M populated elements in a 100000 x 100000 space)

• 您RowSum 425ms


• 您ColumnSum 7774ms


• localInit ColumnSum 3324ms

所以还是要比较慢的命令行之和，但看起来像一个合理的改进。

So still an order of magnitude slower than the row sums, but looks like a reasonable improvement.

（也是在我的字典使用错误）

(Was also bug in my Dictionary usage)

这篇关于C＃提高稀疏矩阵行和列计算总的并行性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！