Накопление подпоследовательностей последовательности с использованием C#/Linq

Question

Я пытаюсь найти лучший способ обработки последовательности чисел на основе следующего требования: значение sequence[i] это сумма его собственной стоимости плюс накопление от sequence[0] в sequence[i-1],

Например: если последовательность представляет собой список

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

выходной результат должен быть

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

Я знаю способ грубой силы, который использует несколько итераций, но мне интересно, должно быть какое-то лучшее решение (возможно, с LINQ).

Answer 1

Предполагая, что у вас есть доступ к 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;
});

Answer 2

Моя версия, которая является модификацией того, что я положил в комментарии, и возвращает IEnumerable, а не List, но ToList() это уладит.

Должно быть довольно эффективным. А кто не любит пользоваться 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);
}

Основным преимуществом этого является то, что он выполняет только один цикл над входным массивом. и если вы на самом деле не используете весь возвращенный материал (то есть вы смотрите только на первые три), то остальные не будут вычисляться. Потенциально полезен в длинных списках и т. Д. То же самое будет сказано о вещах, подобных ответу Криса Доггетта, но не обо всех, кто здесь использует linq.

Answer 3

Используйте относительно неизвестную перегрузку Select, которая позволяет увидеть индекс:

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

Answer 4

Версия не LINQ, просто чтобы отличаться:

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;
}

Answer 5

Я создал универсальный (с большим количеством вариантов) метод расширения, основанный на операторе сканирования APL (аналогично тому, как Aggregate по сути, оператор сокращения APL), который возвращает промежуточные результаты последовательности операций:

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;
    }
}

Который затем может быть использован как:

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

Answer 6

Вот еще один способ, похожий на один из постов, но этот отдельный:

// 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

Если мы переключаемся на int64, используем 10 000 000 в качестве верхней границы и читаем окончательный накопленный результат, код выполняется примерно за 450 миллисекунд на Corei5 с окончательным выводом:

50000005000000

Кстати, для верхней границы 1 000 000 выполнение составляет около 40 миллисекунд, поэтому увеличение размера на 10 увеличило время на 10.