How to calculate the sum of a huge range filtered by a predicate in LINQ

Question

I am trying to test the performance of three solutions for the Problem 1 from projecteuler.net by passing an int.MaxValue instead of 1000.

First solution:

    long sum = SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15);
    Console.WriteLine(sum);

Where SumDivisibleBy is:

public static long SumDivisibleBy(int k, int n = int.MaxValue)
{
    long m = n / k;
    return k * (m * (m + 1) / 2);
}

is faster (about 27 seconds) than

second solution:

    long sum = 0;
    for (int i = 0; i < int.MaxValue; i++)
    {
        if (i % 3 == 0 || i % 5 == 0)
        {
            sum += (long)i;
        }
    }
    Console.WriteLine(sum);

The third solution (which is an elegant one in my opinion) is:

    Console.WriteLine(Enumerable.Range(1, 999)
                                .Where(x => x % 3 == 0 || x % 5 == 0)
                                .Sum());

but I cannot achieve this (for testing performance purpose):

    Console.WriteLine(Enumerable.Range(1, int.MaxValue)
                                    .Where(x => x % 3 == 0 || x % 5 == 0)
                                    .Sum());

because it gives me an OverflowException which is natural because of the nature of int Sum(this IEnumerable<int> source).

My question is this:

How can I upcast the int Sum(this IEnumerable<int> source) to the long Sum(this IEnumerable<long> source) in the code below:

    Console.WriteLine(Enumerable.Range(1, int.MaxValue)
                                    .Where(x => x % 3 == 0 || x % 5 == 0)
                                    .Sum());

Using LinqPad i do not see any error message. Code in solution 3 has been executed in 0.072 sec. — Maciej Los, Jan 08 '15 at 10:16
1. You should not output to the console within the stopwatch measurement. 2. You should run test code in a loop of as many iterations as possible to perform in a reasonable amount of time and then divide by number of iterations to get more accurate times. — Danny Varod, Jan 08 '15 at 10:20
@T.Glatzer It does not. You can not call `Sum` on an `IEnumerable`. — Rotem, Jan 08 '15 at 10:23

score 3 · Accepted Answer · edited May 23 '17 at 11:57

3

Try projecting the filtered sequence of ints to a sequence of longs:

.Where(x => x % 3 == 0 || x % 5 == 0)
.Select(x => (long)x)
.Sum()

Note that .Cast<long>() looks more elegant but won't work for this kind of conversion.

edited May 23 '17 at 11:57

Community

1
1

answered Jan 08 '15 at 10:15

Ani

111,048
26
262
307

Alternatively, `.Select(i => i)` will also work, making the cast implicit. – Rotem Jan 08 '15 at 10:20
2

The Compiler would also determine `var sum = Enum.Sum(i => (long)i)` as Int64, which would hide the select. But I did not test it in runtime. – TGlatzer Jan 08 '15 at 10:31
@T.Glatzer great hint! It works: `Console.WriteLine(Enumerable.Range(1, int.MaxValue).Where(x => x % 3 == 0 || x % 5 == 0).Sum(x => (long)x));`. That's even better and ...elegant :) – Andritchi Alexei Jan 08 '15 at 11:30

score 2 · Answer 2 · answered Jan 08 '15 at 10:15

You could extend the Enumerable class like below:

public static class MyExtensions
{
    public static IEnumerable<long> Range(long start, long count)
    {
        for (long i = start; i < start + count; i++)
        {
            yield return i;
        }
    } 
}

This way you could make use of Sum method without having any issue, like below:

MyExtensions.Range(1, int.MaxValue)
            .Where(x => x % 3 == 0 || x % 5 == 0)
            .Sum());

score 0 · Answer 3 · answered Jan 08 '15 at 13:45

0

Just for information... I tested all recommended solutions (LinqPad) and checked the time of execution.

Method 1) conversion with Select - time: 1:23.360s (mid)

.Select(x => (long)x)

Method 2) Extension method - time: 02:06.768s (slow)

MyExtensions.Range(1, int.MaxValue)
            .Where(x => x % 3 == 0 || x % 5 == 0)
            .Sum());

Method 3) suggested by T.Glatzer in comment to Ani's solution - time: 00:54.567 (quick)

Enumerable.Range(1, int.MaxValue).Where(x=> x%3==0 || x%5==0).Sum(x=>(long)x);

Conclusion:
Each method is much, much slower than your SumDivisibleBy function, so what are the benefits of Linq solutions other than elegant code? None.

Note: i do not tested it in other areas such as memory usage, CPU usage, etc.

answered Jan 08 '15 at 13:45

Maciej Los

8,468
1
20
35

You are absolutely right, and yes I know that `SumDivisibleBy` is much faster than other (because in case of SumDivisibleBy we have O(1) complexity but in methods with LINQ we have O(n)). My question was quite specific about **upcasting** the `.Sum()` from `int` to `long` (because I wasn't able to test for performance with an `int.MaxValue`), I **didn't ask** about benefits of one method to another. – Andritchi Alexei Jan 08 '15 at 15:23
@AndritchiAlexei, i know what you were asking about, that's why i added on the begining of my answer: "*just for information*". Cheers, Maciej – Maciej Los Jan 08 '15 at 22:30

How to calculate the sum of a huge range filtered by a predicate in LINQ

3 Answers3