Friends in need
Random Quote
I always turn right because then I can't go wrong.
- Toby Tanser

Simplicity versus performance

Though I love the simplicity and beauty (and laziness by the programmer) in many of the code implementations out there, I think that you have to rethink some of the solutions a little bit more before you call it a day. Just because you always return the correct answer does not mean that you have solved the problem. Sometimes you have to walk that extra mile and rethink your solution.

I will elaborate around this with some trivial problems and compare some implementations (in Java) to solve these problems. All these solutions returns correct results, but some of them will have low performance for large input values. In these examples we will take advantage of some mathematical formulas, when implementing solutions.

First problem

You are asked to sum the integers from 1 to 123456.

Solutions to first problem

What do you, as a programmer, do? One way to solve the problem is this

    static long sumAllIntegersFromOneToN_naive(final long n) {
        // Naive and correct the old fashioned way.
        long sum = 0;
        for (long i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }

or if you use the Java 8 Stream functionality

    static long sumAllIntegersFromOneToN_still_naive(final long n) {
        // Naive and correct with Java 8 streams.
        return LongStream.rangeClosed(1, n).sum();
    }

Good! You solved the problem and can start with your next task. But is this really the best you could do? It is nice and simple code, but for large input values, it will be extremely inefficient calculations.

Since there are well-known mathematical formulas for summing up integers, why not use them in your solution.

    static long sumAllIntegersFromOneToN_rethought(final long n) {
        // Using the mathematics. The sum of all integers from 1 to n equals n*(n+1)/2.
        return n * (n + 1) / 2;
    }

Perhaps not so simple and elegant as the Stream implementation, but much more efficient.

Second problem

You are asked to sum the integers from 12345 to 98765.

Solutions to second problem

Okay, once again the Java 8 Stream can deliver beautiful code

    static long sumAllIntegersFromMToN_naive(final long m, final long n) {
        // Naive and correct with Java 8 streams.
        return LongStream.rangeClosed(m, n).sum();
    }

Problem solved, but what if the input arguments are 123 and 1234567? The stream API will have to work hard to calculate the result.

You can still use the solutions to the first problem, when solving this second problem. So, for example

    static long sumAllIntegersFromMToN_rethought(final long m, final long n) {
        // Using the mathematics.
        return sumAllIntegersFromOneToN_rethought(n) - sumAllIntegersFromOneToN_rethought(m - 1);
    }

Still simple, but clearly better performance.

Third problem

You are asked to sum the odd integers from 1 to 123456.

Solutions to third problem

A simple and elegant first attempt

    static long sumAllOddIntegersFrom1ToN_naive(final long n) {
        // Naive and correct with Java 8 streams.
        final LongPredicate isOdd = i -> i % 2 == 1;
        return LongStream.rangeClosed(1, n).filter(isOdd).sum();
    }

Compare it to the solution where we take advantage of the mathematics

    static long sumAllOddIntegersFrom1ToN_rethought(final long n) {
        // Using the mathematics. The sum of all odd integers from 1 to n equals ((n+1)/2)^2.
        final long numberOfOddIntegersToAdd = (n + 1) / 2;
        return numberOfOddIntegersToAdd * numberOfOddIntegersToAdd;
    }

Fourth problem

You are asked to sum the odd integers from 12345 to 98765.

Solutions to fourth problem

Still very elegant (and inefficient)

    static long sumAllOddIntegersFromMToN_naive(final long m, final long n) {
        // Naive and correct with Java 8 streams.
        final LongPredicate isOdd = i -> i % 2 == 1;
        return LongStream.rangeClosed(m, n).filter(isOdd).sum();
    }

A more efficient solution can look like

    static long sumAllOddIntegersFromMToN_rethought(final long m, final long n) {
        // Using the mathematics. The sum of all odd integers from 1 to n equals ((n+1)/2)^2.
        return sumAllOddIntegersFrom1ToN_rethought(n) - sumAllOddIntegersFrom1ToN_rethought(m - 1);
    }

Conclusions/summary

We love simple and beautiful code, but sometimes an elegant solution may be too naive. There may be inefficiency in your solution, but with just a little extra research you may find that there are mathematical formulas or something else, that will turn your inefficient elegant solution into an efficient (still elegant) solution.

And remember that the sky is no limit!

First published by Anders Gustafson in August 2016