Two dimensional array sum in C#/Linq

Question

I have a two dimensional array of integers. I would like to write an optimized and fast code to sum all the columns of the two dimensional array.

Any thoughts how I might be able to do this using LINQ/PLINQ/TASK parallelization ?

Ex:

private int[,] m_indexes = new int[6,4]  { {367, 40, 74, 15},
                                           {535, 226, 74, 15}, 
                                           {368, 313, 74, 15},
                                           {197, 316, 74, 15}, 
                                           {27, 226, 74, 15},
                                           {194, 41, 74, 15} };

Actually..in real example... the size of the array is int[60,350]. I need to sum all the columns, then group few columns together to find the min and max in the total of those columns. — Chili Manku
– Chili Manku, Commented Sep 12, 2011 at 20:27
Gabe - Not familiar will Parallel.For. I see Jason has given examples for Parallel.Foreach, and Linq. Going to benchmark and explore implementations further. Thanks all. — Chili Manku
– Chili Manku, Commented Sep 12, 2011 at 20:36
Instead of Parallel.ForEach(Enumerable.Range(0, 4), ...) you could use Parallel.For(0, 4, ...). This gives more opportunity for optimization because the number of columns are known at the outset. — Gabe
– Gabe, Commented Sep 13, 2011 at 8:19

jason · Accepted Answer · 2011-09-12 20:36:14Z

6

The simplest parallel implementation:

 int[,] m_indexes = new int[6, 4]  { {367, 40, 74, 15},
                                     {535, 226, 74, 15}, 
                                     {368, 313, 74, 15},
                                     {197, 316, 74, 15}, 
                                     {27, 226, 74, 15},
                                     {194, 41, 74, 15} };
 var columns  = Enumerable.Range(0, 4);
 int[] sums = new int[4];
 Parallel.ForEach(columns, column => {
     int sum = 0;
     for (int i = 0; i < 6; i++) {
         sum += m_indexes[i, column];
     }
            sums[column] = sum;
 });

This code can obviously be "generalized" (use m_indexes.GetLength(0) and m_indexes.GetLength(1)).

LINQ:

var sums = columns.Select(
    column => {
        int sum = 0;
        for (int i = 0; i < 6; i++) {
            sum += m_indexes[i, column];
         } return sum; 
    }
).ToArray();

Be sure to profile on real-world data here if you truly need to optimize for performance here.

Also, if you truly care about optimizing for performance, try to load up your array so that you summing across rows. You'll get better locality for cache performance that way.

edited Sep 12, 2011 at 20:36

answered Sep 12, 2011 at 20:30

jason

243k35 gold badges436 silver badges532 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

xanatos Over a year ago

(to the OP) But you should benchmark it before using it :-) For small arrays, the time spent synchronizing the threads is often > the time you gain.

Bala R Over a year ago

var columns = Enumerable.Range(0, 4); could be var columns = Enumerable.Range(0, m_indexes.GetLength(1)); for extensibility.

Chili Manku Over a year ago

Thanks Jason. Going to explore the implementation and benchmark. Will implement accordingly. Thanks again.

jason Over a year ago

@Chili Manku: Please read my last paragraph that I just edited in.

Y.A.P. · Accepted Answer · 2011-09-12 20:37:24Z

1

Or maybe without for's :

List<List<int>> m_indexes = new List<List<int>>()  { new List<int>(){367, 40, 74, 15},
new List<int>(){535, 226, 74, 15}, 
new List<int>(){368, 313, 74, 15},
new List<int>(){197, 316, 74, 15}, 
new List<int>(){27, 226, 74, 15},
new List<int>(){194, 41, 74, 15} };

var res = m_indexes.Select(x => x.Sum()).Sum();

answered Sep 12, 2011 at 20:37

Y.A.P.

5385 silver badges12 bronze badges

Comments

driis · Accepted Answer · 2011-09-12 20:38:31Z

1

Straightforward LINQ way:

var columnSums = m_indexes.OfType<int>().Select((x,i) => new { x, col = i % m_indexes.GetLength(1) } )
    .GroupBy(x => x.col)
    .Select(x => new { Column = x.Key, Sum = x.Sum(g => g.x) });

It might not be worth it to parallelize. If you need to access the array by index, you spend some cycles on bounds checking, so, as always with performance, do measure it.

edited Sep 12, 2011 at 20:38

answered Sep 12, 2011 at 20:27

driis

165k46 gold badges272 silver badges345 bronze badges

1 Comment

jason Over a year ago

Meh. The JITter could very likely optimize the bounds checking away.

Collectives™ on Stack Overflow

Two dimensional array sum in C#/Linq

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related