Accumulation of subsequences of a sequence using C

问题:

I'm trying to find a better way of processing a sequence of numbers based on the following requirement: the value of sequence[i] is the sum of its own value plus the accumulation from sequence[0] to sequence[i-1].

For example: if the sequence is a list

List<double> list = new List<double> { 10.0, 20.0, 30.0, 40.0 };

the output result should be

list[0] = 10.0
list[1] = 20.0 + 10.0
list[2] = 30.0 + 10.0 + 20.0
list[3] = 40.0 + 10.0 + 20.0 + 30.0

I know the brute force way which uses multiple iterations, but I wonder there must be some better solution (maybe with LINQ).

回答1:

Assuming you have access to LINQ:

using System.Linq;

List<int> numbers = new List<int> {10, 20, 30, 40};
List<int> runningTotals = new List<int>(numbers.Count);

numbers.Aggregate(0, (sum, value) => {
    sum += value; 
    runningTotals.Add(sum); 
    return sum;
});

回答2:

My version which is a modification of what I put in comments and returns an IEnumerable rather than a List but a ToList() will sort that out.

Should be pretty efficient. And who doesn't like using yield return? ;-)

public IEnumerable<double> GetCumulativeSequence (IEnumerable<double> input)
{
    var runningTotal = 0.0;
    foreach (double current in input)
    {
        runningTotal+=current;
        yield return runningTotal;
    }
}

void Main()
{
    List<double> list = new List<double> { 10.0, 20.0, 30.0, 40.0 };
    var foo = GetCumulativeSequence(list);
}

Main advantage of this is that it only does one loop over the input array. and if you don't actually use all of the stuff returned (ie you only look at the first three) then it won't calculate the rest. Potentially useful in longer lists, etc. The same will be said of things like Chris Doggett's answer but not all those here using linq.

回答3:

Use the relatively-unknown overload of Select that lets you see the index:

var result = list.Select((val, index) => list.Take(index + 1).Sum())

回答4:

A non-LINQ version, just to be different:

List<double> GetSums(List<double> values)
{
   List<double> sums = new List<double>();
   double total = 0;
   foreach(double d in values)
   {
      total += d;
      sums.Add(total);
   }
   return sums;
}

回答5:

Here is another way similar to one of the posts, but this one is self-contained:

// C#
Enumerable.Range(1, 100)
.Aggregate(new List<int>{0},
  (acc, x) => { acc.Add(acc.Last() + x); return acc; })
.Dump(); // Dump using LINQPad; ans: 5050

If we switch to int64, and use 10,000,000 as the upper bound, and read the final accumulated result, the code executes in about 450 milli-seconds on a Corei5 with a final output of:

50000005000000

Incidentally, for an upper bound of 1,000,000 the execution is about 40 milli-seconds, so increasing the size by 10 increased the time by 10.

回答6:

I built a general purpose (with lots of variations) extension method based on the APL scan operator (analogous to how Aggregate is essentially the APL reduce operator) that returns the intermediate results of the sequence of operations:

public static IEnumerable<TResult> Scan<T, TResult>(this IEnumerable<T> src, TResult seed, Func<TResult, T, TResult> combine) {
    foreach (var s in src) {
        seed = combine(seed, s);
        yield return seed;
    }
}

Which can then be used like:

var ans = list.Scan(0.0, (a, d) => a+d).ToList();