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 :-)

Different approaches to dump and load objects using Python. Perfomance analysis.

The previous post gave you an example demonstrating the usage of json format to store an object's value. 

We have several ways to store/load (or serialize and deserialize) data that we collect during the launch of our application. 

At the moment we have several ways how to do that. First of all we should think about what we will do with that data? Will we load it back inside our application? Will we send it to another application (that could be written using another programming language, not especially Python)? Should we store data in the format that could be understood by a human, so that the stored data had a readable format?

What approaches might we have if we used Python?

1. JSON (http://json.org/)
2. XML (http://www.w3.org/XML/) 
3. YAML (http://yaml.org/ and RFC is here)
4. Pickle (Python 2 Docs, Python 3 Docs)

JSON, XML and YAML can be used to store information in human-readable format, and this data format can be uploaded using all modern programming languages. Pickle is a Python-specific module. An advantage of this module is that we can dump more complicated objects than standard data structures and types without any issues and special methods inside our classes that will convert instances of our classes into the format that is applicable to be dumped into XML, JSON or YAML formats.
So, it is the time to look at each bullet in a bit more detail.

First of all we should keep in mind that for serialization and deserialization we should have simple approach that allows us to store and load our data (simple variables, collections, objects) without any problems. We will have a look at implementations of modules with both dump and load functions.

JSON 

This format is supported by Python standard module (module description for Python 3.X). As you may see from documentation, the functionality provided in this module is pretty simple. It allows to serialize and deserialize an object into a string or a stream. The list of the possible types that can be encoded/decoded with this value includes: Several collection types: dict, list and tuple, String types like string and unicode string, Numeric types like int, long and float, Boolean values such as True and False, and of course None.
This library provides both dump function and load function. So, JSON is chosen for our experiment.

XML

XML support in Python is implemented in several modules. Full information can be found here. As I haven't found any applicable modules with the required functionality, I suggest that for our experiment we try to write our own module for serialization or deserialization, based on Expat module. But it is not the purpose of this article, so we will not use XML for this experiment.

YAML

Module PyYAML can be used for working with this markup language. It provides simple functions to dump and load information. Correlation with JSON is available here and with XML - here. This module has both dump and load functions, so we will use it for our experiment.

Pickle

Pickle is a standard module that allows to use serialization and deserialization processes for an object. It converts objects hierarchy in byte stream aka 'Pickling' operation and restore the objects hierarchy from byte stream aka 'Unpickling' process. This format is compared with JSON in the following article for Python 3.X
Since Pickle is a standard module, it also contains both dump function and load function, and we will use this module as part of our experiment.