Simple changes in an algorithm and how it can improve performance.

Everyone knows how it is important to implement something efficiently.

Today I tried to solve one algorithmic challenge from HackerRank.
Link on the challenge is: https://www.hackerrank.com/contests/w26/challenges/hard-homework
This challenge is marked as Hard, and at the moment, I am on my way to be able to solve any kind of Medium challenges without any problems. So, I didn't expected that my solution will be 100% optimal, but tomorrow we will see.

So, common rule that we know from interviews is: "if you don't know how to solve problem efficiently, try to implement the brute-force algorithm and optimize it.".

If you have no access to the challenge, the problem is to find three integers x, y and z (all numbers are positive), with sum of all of them equal to required number n and sum of sin(x), sin(y), sum(z) is maximal across all triples x, y, z. Here parameter of sin operation is an angle in radians.

The simple solution is:

static double getMaxSumOfSinsBruteForce(int n) {
    double maxSumOfSins = Double.MIN_VALUE;
    double currentSumOfSins;
    for (int x = 1; x < n - 1; x++) {
        for (int y = 1; x + y < n; y++) {
            currentSumOfSins = Math.sin(x) + Math.sin(y) + Math.sin(n-x-y);
            if (currentSumOfSins > maxSumOfSins) {
                maxSumOfSins = currentSumOfSins;
            }
        }
    }
    return maxSumOfSins;
}

We try to iterate over x from 1 to n-2. n-2 is because y and z should be positive, so both these numbers should have value that great or equal to 1. After that we try to check all possible values of y and calculate required sum of sinuses with parameters x, y and n-x-y.

Hm... it takes a good time to find a sum where n is equal to 10000... 
How we can do better? Oh, thanks to Tim Roughgarden and Algorithms specialization from Stanford on the coursera.org site (https://www.coursera.org/specializations/algorithms), for now I ask myself this question every time when I implement something that computationally intensive.

The first thing that we might notice is that in the for loop over y, on every iteration we calculate the Math.sin(x) where x is a constant inside this loop over y.

static double getMaxSumOfSinsOptV1(int n) {
    double maxSumOfSins = Double.MIN_VALUE;
    double currentSumOfSins;
    double sinOfX;
    for (int x = 1; x < n - 1; x++) {
        sinOfX = Math.sin(x);
        for (int y = 1; x + y < n; y++) {
            currentSumOfSins = sinOfX + Math.sin(y) + Math.sin(n-x-y);
            if (currentSumOfSins > maxSumOfSins) {
                maxSumOfSins = currentSumOfSins;
            }
        }
    }
    return maxSumOfSins;
}

Better? Yes!
What about performance? Still slow...

So, if we look on the solution from another angle, what we can see. Actually, in target sum of sinuses all summands are values from collection Math.sin(1), ..., Math.sin(n-2).

Next idea is to create a map which has angle as a key and value is a sinus of that angle. 

As a result we got the following:

static double getMaxSumOfSinsOptV2(int n) {
    double maxSumOfSins = Double.MIN_VALUE;
    double currentSumOfSins;
    double sinOfX;
    // pre-calculation

    Map<Integer, Double> preCalculation = new HashMap<>();
    for (int i = 1; i <= n-2; i++) {
        preCalculation.put(i, Math.sin(i));
    }
    // Common processing

    for (int x = 1; x < n - 1; x++) {
        sinOfX = preCalculation.get(x);
        for (int y = 1; x + y < n; y++) {
            currentSumOfSins = sinOfX + preCalculation.get(y) + preCalculation.get(n-x-y);
            if (currentSumOfSins > maxSumOfSins) {
                maxSumOfSins = currentSumOfSins;
            }
        }
    }
    return maxSumOfSins;
}

Performance? Much faster!

Can we do better? We can try!

According to problem description, x, y and z are positive numbers, so there values we can use as indexes in array. As a result, we no need to use map collection type here.

Let's do that!

static double getMaxSumOfSinsOptV3(int n) {
    double maxSumOfSins = Double.MIN_VALUE;
    double currentSumOfSins;
    // pre-calculation

    double[] preCalculation = new double[n];
    for (int i = 0; i < n; i++) {
        preCalculation[i] = Math.sin(i);
    }
    // Common processing

    for (int x = 1; x < n - 1; x++) {
        // At least one should be positive.

        if (preCalculation[x] >= 0) {
            for (int y = 1; x + y < n; y++) {
                currentSumOfSins = preCalculation[x] + preCalculation[y] + preCalculation[n - x - y];
                if (currentSumOfSins > maxSumOfSins) {
                    maxSumOfSins = currentSumOfSins;
                }
            }
        }
    }
    return maxSumOfSins;
}

At the end of the day, let's try to launch all four solution with the same value of n and compare results, especially performance or time to calculate the sum.

Assume we pass n that equals to 10000 to those functions

On my laptop results are:

* 10000

* BF: Calculated value: 2.739180081. Time to calculate: 19030

* O1: Calculated value: 2.739180081. Time to calculate: 12290

* O2: Calculated value: 2.739180081. Time to calculate: 995

* O3: Calculated value: 2.739180081. Time to calculate: 72

Time is in milliseconds.

As we can see, it is the same approach, but with few enhancements and final version works ~250 times faster.

Is it enough to pass the challenge on HackerRank? No... Another approach should be used, and it is an another story :-)