Re: LINQ - Как получить частичные суммы ряда? - .NET

Есит ряд:

1, 2, 3, 4, ..... n

Надо через LINQ получить из него ряд частичных сумм:

1, 3, 6, 10, ... m

Как это сделать?

Здравствуйте, Northrop, Вы писали:

N>Есит ряд:

N>1, 2, 3, 4, ..... n

N>Надо через LINQ получить из него ряд частичных сумм:

N>1, 3, 6, 10, ... m

N>Как это сделать?

На F# без проблем:

let nums = [ 1; 2; 3; 4 ]
let sums = nums |> List.scan_left (+) 0 |> List.tl

Чем бы заменить scan в Linq...

Здравствуйте, Northrop, Вы писали:

N>Есит ряд:
N>1, 2, 3, 4, ..... n

N>Надо через LINQ получить из него ряд частичных сумм:
N>1, 3, 6, 10, ... m

var sum = 0;
var numbers = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var partialSums = numbers.Select(item => { sum += item; return sum; });

Здравствуйте, Qbit86, Вы писали:

Q>var sum = 0;
Q>var numbers = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Q>var partialSums = numbers.Select(item => { sum += item; return sum; });

Можно кривее и без mutable closure:

var scan = src.Aggregate(new List<int> { 0 }, (l, x) => { l.Add(l[l.Count-1] + x); return l; });

Здравствуйте, Пельмешко, Вы писали:

П>На F# без проблем:

П>

П>let nums = [ 1; 2; 3; 4 ]
П>let sums = nums |> List.scan_left (+) 0 |> List.tl
П>

П>Чем бы заменить scan в Linq...

Реализовать:

public static class ScanExtensions
{
    public static IEnumerable<TResult> ScanLeft<T, TResult>(
        this IEnumerable<T> items, 
        Func<TResult, T, TResult> func, 
        TResult start)
    {
        TResult accum = start;
        foreach(var item in items)
        {
            accum = func(accum, item);
            yield return accum;
        }
    }
    
    public static IEnumerable<int> ScanLeft(
        this IEnumerable<int> items, 
        int start)
    {
        return items.ScanLeft((x, accum) => accum + x, start);
    }
    
    public static IEnumerable<int> ScanLeft0(
        this IEnumerable<int> items)
    {
        return items.ScanLeft(0);
    }
}

И использовать:

var sums = new [] { 1, 2, 3, 4, 5 }.ScanLeft0();

С Уважением, Andir!

using( RSDN@Home 1.2.0 alpha 4 rev. 1233 ) { /* Работаем */ }

Здравствуйте, Northrop, Вы писали:

N>Есит ряд:

N>1, 2, 3, 4, ..... n

N>Надо через LINQ получить из него ряд частичных сумм:

N>1, 3, 6, 10, ... m

N>Как это сделать?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var m = 50;
            var ll = Enumerable.Range(1, 100);
            Func<int, bool> ff = (i) => (i % 3 == 0 && i < m) ? true : false;
            var sum = ll.Where(x => ff(x)).Sum();

            Console.WriteLine(sum);

        }
    }
}

Здравствуйте, Northrop, Вы писали:

N>Есит ряд:

N>1, 2, 3, 4, ..... n

N>Надо через LINQ получить из него ряд частичных сумм:

N>1, 3, 6, 10, ... m

N>Как это сделать?
самый красивый вариант

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
           
            var sum = 0;
            var ss = Enumerable.Range(1, 100).Select(x => { sum += x; return sum; });
            ss.ToList().ForEach(x => Console.WriteLine(x));

        }
    }
}

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Northrop, Вы писали:

N>>Есит ряд:

N>>1, 2, 3, 4, ..... n

N>>Надо через LINQ получить из него ряд частичных сумм:

N>>1, 3, 6, 10, ... m

N>>Как это сделать?
А>самый красивый вариант
А>

А>using System;
А>using System.Collections.Generic;
А>using System.Linq;
А>using System.Text;

А>namespace ConsoleApplication2
А>{
А>    class Program
А>    {
А>        static void Main(string[] args)
А>        {
           
А>            var sum = 0;
А>            var ss = Enumerable.Range(1, 100).Select(x => { sum += x; return sum; });
А>            ss.ToList().ForEach(x => Console.WriteLine(x));

А>        }
А>    }
А>}

А>

Спасибо, то что надо!

Здравствуйте, Northrop, Вы писали:

N>Есит ряд:

N>1, 2, 3, 4, ..... n

N>Надо через LINQ получить из него ряд частичных сумм:

N>1, 3, 6, 10, ... m

N>Как это сделать?

Может быть задачу можно решить проще если применить хитрость. Например для описанного случая это будет

var nums = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
var sums = nums.Select(n => n * (n + 1) / 2);

А если всё-же общий случай, то придтся немного помудрить.
Вполне через Linq но не совсем быстро, ибо суммируем много раз одно и тоже.

private static IEnumerable<int> GetNumbers()
{
    int i = 1;
    while (true)
    {
        yield return i++;
    }
}

var nums = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
var sums = GetNumbers().Take(nums.Length).Select(x => nums.Take(x).Aggregate(0,(a, b) => a + b));

Здравствуйте, Аноним, Вы писали:

А>самый красивый вариант

Да уж...

        static void Main(string[] args)
        {
            // исходный код, только вывод убрал
            int size = 50000000;
            var sum = 0;
            DateTime Start = DateTime.Now;
            var ss = Enumerable.Range(1, size).Select(x => { sum += x; return sum; });
            List<int> s = ss.ToList();
            DateTime End = DateTime.Now;
            TimeSpan time = End - Start;
            Console.WriteLine(time);
            
            // а теперь попробуем по-простому
            Start = DateTime.Now;
            int[] array = new int[size];
            array[0] = 0;
            for (int i = 1; i < size; i++)
                array[i] = array[i - 1] + i;

            End = DateTime.Now;
            time = End - Start;
            Console.WriteLine(time);

Athlon 4200+, VS 2008 SP1, Release

00:00:02.5156250
00:00:00.2968750

Почти 6-кратный проигрыш!

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Да уж...

[ поскипано ]

PD>Почти 6-кратный проигрыш!

Некошерно как-то мерить DateTime'ом, да и не особо эквивалентный код

Не забывайте, что от ленивости может быть бенефит, а так же может нельзя переиспользовать массив исходных данных (массив ли там вообще на входе?), смотря какая задача там у топикстартера

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;

namespace ConsoleApp
{
  public static class Program
  {
    public static string Test(
      int iterCount, params Func<string>[] tests)
    {
      if (tests == null)
        throw new ArgumentNullException("tests");

      var thread = Thread.CurrentThread;
      var oldPriority = thread.Priority;
      var timer = new Stopwatch();
      var buf = new StringBuilder();

      try
      {
        // прогревочный круг :D
        foreach (var test in tests) test();

        thread.Priority = ThreadPriority.Highest;

        int n = 1;
        foreach (var test in tests)
        {
          timer.Start();

          string name = null;
          for (int i=0; i < iterCount; i++) name = test();

          timer.Stop();

          buf.AppendFormat(
            "Test #{0} {1,16}: {2} ({3} ms)\n", n++,
            name, timer.Elapsed, timer.ElapsedMilliseconds);

          timer.Reset();
        }
      }
      finally { thread.Priority = oldPriority; }

      return buf.ToString();
    }

    static void Main()
    {
      const int Size = 50000;

      string result = Test(1000,
        () => {
          int sum = 0;
          var ss = Enumerable.Range(1, Size)
            .Select(x => { sum += x; return sum; }).ToList();
          return "Linq";
        },

        () => {
          var xx = Enumerable.Range(1, Size)
            .Aggregate(new List<int> { 0 },
              (l, x) => { l.Add(l[l.Count-1] + x); return l; });

          return "Linq2";
        },

        () => {
          var xx = new List<int>();
          Enumerable.Range(1, Size).Aggregate(
            (a, x) => { xx.Add(x); return a; });

          return "Linq3";
        },

        () => {
          int[] array = new int[Size];
          for (int i = 1; i < array.Length; i++) // use length-based loop!
            array[i] = array[i-1] + i;

          return "Imperative";
        },
        
        () => {
          int[] array = new int[Size],
                scan  = new int[Size];

          for(int i = 0; i < array.Length; i++) array[i] = i;

          int sum = 0;
          for(int i = 0; i < scan.Length; i++)
          {
            sum += array[i];
            scan[i] = sum;
          }

          return "Imper.(честнее)";
        });

      Console.WriteLine(result);
    }
  }
}

Test #1             Linq: 00:00:02.8320702 (2832 ms)
Test #2            Linq2: 00:00:02.2512573 (2251 ms)
Test #3            Linq3: 00:00:01.7357650 (1735 ms)
Test #4       Imperative: 00:00:00.3250726 (325 ms)
Test #5  Imper.(честнее): 00:00:00.5843982 (584 ms)

Athlon X2 3800+

p.s. Раньше ради интереса гонял тесты, linq всегда проигрывал в 2-3 раза эквивалентному eager-коду на циклах.
Не удивительно, сколько там вызовов делегатов с замыканиями, интерфейсных вызовов IEnumerable<T> и т.п...

Здравствуйте, Пельмешко, Вы писали:

Простите, чушь в третьем случае написал, вот так правильно:

        () => {
          var xx = new List<int> { 0 };
          Enumerable.Range(1, Size).Aggregate(
            (a, x) => { int s = a+x; xx.Add(s); return s; });

          return "Linq3";
        },

Результата это не меняет, у меня даже меньше вышло, хотя это скорее всего из-за погрешности:

Test #1             Linq: 00:00:02.8420874 (2842 ms)
Test #2            Linq2: 00:00:02.2010004 (2201 ms)
Test #3            Linq3: 00:00:01.7111976 (1711 ms)
Test #4       Imperative: 00:00:00.3063548 (306 ms)
Test #5  Imper.(честнее): 00:00:00.5250748 (525 ms)

Кстати, третий случай быстрее потому что там не генерится скрытый класс для замыкания, target'ом делегата становится сам List<int> xx.
То есть доступ к нему в лямбде будет не this.xx.Add(), а просто this.Add()

Здравствуйте, Пельмешко, Вы писали:

П>Кстати, третий случай быстрее потому что там не генерится скрытый класс для замыкания, target'ом делегата становится сам List<int> xx.
П>То есть доступ к нему в лямбде будет не this.xx.Add(), а просто this.Add()

А если ещё capacity подсказать списку, то выходит ещё интереснее

Test #3            Linq3: 00:00:01.3988305 (1398 ms)

Здравствуйте, Аноним, Вы писали:

А>самый красивый вариант

тогда уж так:

А>

А>            var sum = 0;
А>            var ss = Enumerable.Range(1, 100).Select(x => sum += x);
А>

так по-любому красивее

Здравствуйте, Пельмешко, Вы писали:

П>Здравствуйте, Пельмешко, Вы писали:

П>Простите, чушь в третьем случае написал, вот так правильно:
П>

П>        () => {
П>          var xx = new List<int> { 0 };
П>          Enumerable.Range(1, Size).Aggregate(
П>            (a, x) => { int s = a+x; xx.Add(s); return s; });

П>          return "Linq3";
П>        },
П>

П>Результата это не меняет, у меня даже меньше вышло, хотя это скорее всего из-за погрешности:
П>

П>Test #1             Linq: 00:00:02.8420874 (2842 ms)
П>Test #2            Linq2: 00:00:02.2010004 (2201 ms)
П>Test #3            Linq3: 00:00:01.7111976 (1711 ms)
П>Test #4       Imperative: 00:00:00.3063548 (306 ms)
П>Test #5  Imper.(честнее): 00:00:00.5250748 (525 ms)
П>

П>Кстати, третий случай быстрее потому что там не генерится скрытый класс для замыкания, target'ом делегата становится сам List<int> xx.
П>То есть доступ к нему в лямбде будет не this.xx.Add(), а просто this.Add()

а зачем List<int> юзать?

Здравствуйте, Пельмешко, Вы писали:

PD>>Почти 6-кратный проигрыш!

П>Некошерно как-то мерить DateTime'ом

При тех значениях (десятые доли секунды) , что GetTickCount, что QueryPerfomanceCounter — один черт. Разрешение GetTickCount — 0.015 сек. Ну не в 6 раз, так в 5.95 раз

П> () => {
П> int[] array = new int[Size],
П> scan = new int[Size];

П> for(int i = 0; i < array.Length; i++) array[i] = i;

П> int sum = 0;
П> for(int i = 0; i < scan.Length; i++)
П> {
П> sum += array[i];
П> scan[i] = sum;
П> }

П> return "Imper.(честнее)";

Хм, а почему же честнее ? Завел ты непонятно зачем еще один массив, да еще со значениями array[i] = i. Не обижайся, но за такие массивы я школьникам втык делал. Ибо незачем такие массивы заводить. Я бы еще понял, если бы array[]= SomeHardFunction(i), тут еще можно подискутировать, вычислять ее каждый раз или предварительно просчитать и в массив. А array[i] = i — ИМХО безобразие.

А если честнее потому, что это более соответствует тому, что генерируется LinQ — то мне до этого и дела нет. Задача поставлена ясно

////////////////////////////////////////////////////
Есит ряд:

1, 2, 3, 4, ..... n

Надо через LINQ получить из него ряд частичных сумм:

1, 3, 6, 10, ... m

////////////////////////////////////////////////////

Вот я и сделал этот ряд частичных сумм, и пусть мне кто-то докажет обратное. И если при этом LinQ или кто-то еще должен соорудить какие-то еще массивы или иные контейнеры — меня это не касается. Я свое дело сделал и так.

П>Не удивительно, сколько там вызовов делегатов с замыканиями, интерфейсных вызовов IEnumerable<T> и т.п...

Не удивительно. Удивительно другое — несмотря на это, находятся желающие его использовать в ситуации, когда простой императивный код занимает 3 строчки и работает в 6 раз быстрее. Вот скажи на милость (или пусть топикстартер скажет) — зачем он ему в этой задаче понадобился ???

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Не удивительно. Удивительно другое — несмотря на это, находятся желающие его использовать в ситуации, когда простой императивный код занимает 3 строчки и работает в 6 раз быстрее. Вот скажи на милость (или пусть топикстартер скажет) — зачем он ему в этой задаче понадобился ???

Ну например ему может понадобится найти максимальную из четных сумм, которые меньше заданного числа...
или еще как-то скомбинировать результирующую последовательность с другими операциями.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А если честнее потому, что это более соответствует тому, что генерируется LinQ — то мне до этого и дела нет. Задача поставлена ясно

Вы меня простите ради Бога, каюсь, в этом я ошибался конечно, почему то решил, что топикстартер привёл ряд вида 1,2,3...n в качестве примера, я именно ожидал что у него там SomeHardFunction(i), думал задача реальная, откуда-то ряд берётся... А надо было лишь получше прочитать, извините...

PD>Не удивительно. Удивительно другое — несмотря на это, находятся желающие его использовать в ситуации, когда простой императивный код занимает 3 строчки и работает в 6 раз быстрее. Вот скажи на милость (или пусть топикстартер скажет) — зачем он ему в этой задаче понадобился ???

Не знаю

Чисто академический интерес, наверное, или любовь к декларативности

Разве это не прекрасно?

let sums = { 0 .. n } |> Seq.scan (+) 0

Здравствуйте, Пельмешко, Вы писали:

П>Не знаю :) Чисто академический интерес, наверное, или любовь к декларативности :)
П>Разве это не прекрасно? :shuffle:
П>

let sums = { 0 .. n } |> Seq.scan (+) 0

Ящитаю — прекрасно.

Здравствуйте, Пельмешко, Вы писали:

П>Разве это не прекрасно?

П>

П>let sums = { 0 .. n } |> Seq.scan (+) 0
П>

Прекрасно, но при условии, что это работает на абстрактной машине

	От:	Northrop
	Дата:	06.09.09 17:12
	Оценка:

От:	Пельмешко	blog
Дата:	06.09.09 17:46
Оценка:

От:	Qbit86	https://twitter.com/qbit86
Дата:	06.09.09 17:53
Оценка:

От:	Пельмешко	blog
Дата:	06.09.09 18:00
Оценка:

От:	Andir	http://twitter.com/AndirNotes
Дата:	06.09.09 18:33
Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	07.09.09 11:35
Оценка: