Накопление подпоследовательностей последовательности с использованием 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

Я создал универсальный (с большим количеством вариантов) метод расширения, основанный на операторе сканирования 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 5

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

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

Answer 6

Версия не 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;
}