.Net - Fastest way to sum a collection of numeric values

Question

I have a method which summarizes a collection of decimal values using a method similar to this...

Dim _amountCollection as New List(Of Decimal)
_amountCollection.Add(145.12D)
_amountCollection.Add(11.32D)
_amountCollection.Add(6547.07D)

Dim _totalAmount as Decimal

For Each _individualAmount as Decimal in _amountCollection
  _totalAmount += _individualAmount
Next

In the actual code, there are usually more members in the amount collection, and there are at least 50 individual amount collections that need to be summed in a total operation.

This recalculation of total amount gets called often (at least once, and then again for each collection content change), and is showing up in profile traces as consuming between 2-5% of the total operation time. I am looking to see if anyone has an idea of how to speed this summation operation up, or if this is just the fastest its going to get.

Caching is not realistic in this case, because the amounts must be recalculated.

**EDIT For Ravadre and Joel - The total amount is stored at the class level (each amount collection and sum are contained in a class instance)

Any ideas?

Answer 1

That is about as fast as it is going to get given the fact that you are using a List(Of T).

Others have suggested that you use the Sum extension method - this will not improve performance as its implementation is identical to your current solution to the problem:

<Extension> _
Public Shared Function Sum(ByVal source As IEnumerable(Of Decimal)) As Decimal
    If (source Is Nothing) Then
        Throw Error.ArgumentNull("source")
    End If
    Dim num As Decimal = 0
    Dim num2 As Decimal
    For Each num2 In source
        num = (num + num2)
    Next
    Return num
End Function

Answer 2

What about totalAmount = amountCollection.Sum() ?

Answer 3

Your other alternative is using for loop, you wouldn't have to create an enumerator, but practically there's no significant boost anyway (as far as I know).

Why you can't cache the result? If you cache total ammount, and for each change of one of your elements, modify amount using the same value (and eventually compute all each 10 modifications for synch). So when one of the elements is changed from 2.5 to 3.6, you just add 1.1 to your total amount. Why this won't work in your case?

Answer 4

It's not clear to me how you expect to add up a list of numbers faster than adding each one in turn!

However, using decimals to do arithmetic is probably much, much, much slower than using a floating-point type, so if you don't actually need the precision, I suggest switching.

Answer 5

there are at least 50 individual amount collections that need to be summed in a total operation.

What about caching the sums from each individual collection? Then when a collection changes you only have to sum up that collection and the cached totals.

Answer 6

Try subclassing List(Of Decimal), expose a TotalSum property. Each time Add() is called, increment by the insterted value. That'll keep you from having to iterate through the list to get the sum.

Edit: After trying, it would be better to implement IList(Of Decimal) because List's methods not being virtual. Something along the lines of this (Yes, I know it's C#...)

public class DecimalSumList : IList<decimal>
{
    readonly IList<decimal> _allValues = new List<decimal>();
    decimal _totalSum;
    public decimal TotalSum { get { return _totalSum; } }
    public void Add(decimal item)
    {
        _totalSum += item;
        _allValues.Add(item);
    }

    public void CopyTo(decimal[] array, int arrayIndex)
    {
        _allValues.CopyTo(array, arrayIndex);
    }

    bool ICollection<decimal>.Remove(decimal item)
    {
        _totalSum -= item;
        return _allValues.Remove(item);
    }

    public int Count
    {
        get { return _allValues.Count; }
    }

    public bool IsReadOnly
    {
        get { throw new NotImplementedException(); }
    }

    public void Remove(decimal item)
    {
        _totalSum -= item;
        _allValues.Remove(item);
    }
    public void Clear()
    {
        _totalSum = 0;
        _allValues.Clear();
    }

    public bool Contains(decimal item)
    {
        return _allValues.Contains(item);
    }

    public IEnumerator<decimal> GetEnumerator()
    {
        return _allValues.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public int IndexOf(decimal item)
    {
        return _allValues.IndexOf(item);
    }

    public void Insert(int index, decimal item)
    {
        _totalSum += item;
        _allValues.Insert(index,item);
    }

    public void RemoveAt(int index)
    {
        _totalSum -= _allValues[index];
        _allValues.RemoveAt(index);
    }

    public decimal this[int index]
    {
        get { return _allValues[index]; }
        set { _allValues[index] = value; }
    }
}

Answer 7

2-5% of your total profile trace time just isn't that much.

Even if you cut the execution time of this method in half, you will have saved at most a few percent of your total runtime.

Your best bet is probably to look elsewhere first.

Answer 8

If you don't want to implement a version of IList/IDictionary as statenjason suggested you could create a wrapper :

Public Class TotalDictionaryWrapper
        Private innerDictionary As IDictionary(Of Integer, Decimal)
        Private m_total As Decimal = 0D
        
        Public Sub New(ByVal dictionary As IDictionary(Of Integer, Decimal))
            Me.innerDictionary = dictionary
        End Sub
        
        Public ReadOnly Property Total() As [Decimal]
            Get
                Return Me.m_total
            End Get
        End Property
        
        Public Sub Add(ByVal key As Integer, ByVal value As Decimal)
            Me.innerDictionary.Add(key, value)
            m_total += value
        End Sub
        
        Public Sub Remove(ByVal key As String)
            Dim toRemove As Decimal = Me.innerDictionary(key)
            Me.innerDictionary.Remove(key)
            Me.m_total -= toRemove
        End Sub
        
        Public Sub Update(ByVal key As Integer, ByVal newValue As Decimal)
            Dim oldValue As Decimal = Me.innerDictionary(key)
            Me.innerDictionary(key) = newValue
            Me.m_total -= oldValue
            Me.m_total += newValue
        End Sub
        
        Other methods..

    End Class

Answer 9

If these are currency values, consider using scaled integers. For 2 decimal places, you store the # of pennies instead of the number of dollars, then divide by 100 when you need to output the result. For 5 decimal places, your variables internally use the original number * 100000. This should improve both performance and accuracy, especially if you're doing any division.