Speed Up Your Searches

Usually, in Computer Science classes, sorting algorithms are studied in depth. The reason is quite simple: they are widely used and can be applied to several contexts. Moreover they represent a good way to introduce the concept of computational complexity.

In the real world, one of the reasons to sort items is for searching. On a large set of data, finding an item by scanning every element to see if it matches can be a very slow operation. If the array is sorted by a key, we can perform binary search in order to lower complexity on worst case from O(N) to O(log N). This is a good improvement on large set of data, isn't it? Now, what if I say that I can lower the computational complexity to O(1)?

No Magic, Just Some Math

A small phone book as a hash table (image by Jorge Stolfi)

The trick is to find a way (or an algorithm, if you prefer) to convert the key (that can be a number, a string or whatever) into an index that directly refers to the desired information. This "way" is called hash function and the data structure hash table.

There are hundreds of articles about how hash tables works under the hood and at least the same number of implementations. In many high level languages hash tables are available even as built-in types, often called associative arrays, dictionaries or maps.

Hash tables are widely used when the data set is huge and high response speed is needed. For example, in some RDBMS, indexes are implemented with hash tables. In addition, unlike arrays, you are not forced to have object of the same size stored into hash tables, so the used space (in memory or disk) is optimized and this also affects the average speed of a search.

All That Glitters Is Not Gold

Unfortunately there are some drawbacks with hash tables; the two biggest are both related to the hash function: speed and collisions. The speed issue is related to the execution time of the hash function itself and it's critical when the hash table doesn't contain so much data, so the cost of the linear search in the medium case may be comparable with execution of the hash function.

The collision is a more subtle problem: the hash function may produce the same output for different keys and exist various ways to store different data in this case but they all take some time, reducing the performances of the hash table.

The good news is that many implementations let you choose to use the built-in hash function or provide your own, so, if the speed is a critical requirement of your project, you can create a hash function that better fits your needs.

Conclusions

Hash tables are a very powerful and flexible data structure that can increase the speed of your searches on a huge set of data.

If you are wondering which hash table implementation I use in C, the answer is GLib Hash Table.

algorithms, development Thursday, July 31, 2014 No comments

Algorithms in the Real World

Image by en:User:RolandH

If you are here, I suppose you're familiar with algorithms. Probably your job consists in creating them. What you should know is that every sequence of operations that we accomplish is an algorithm.

What students learn in Computer Science classes is to create generic algorithms (such as the quicksort graphically explained in the image on the left). Then, when they start to work, new specific algorithms must be created.

Nowadays, especially with the advent of the so called Internet of Things, special purpose algorithms are everywhere -  and the control we have on them is very limited. Take a look to the following TED talk:



Surprised about the "Flash Crash of 2:45"? Well, if at Wall Street a software is able to make decisions based on few data, an algorithm that analyzes big data can surely vote in a board of directors, right?

algorithms, TED Saturday, May 31, 2014 No comments

The Month Lengths Problem

The first time I've heard of this problem, I was 14.

At school, during the math class, we started to learn the basics of programming using a language called L2P (no, you won't find it on Wikipedia and, no, it's not worth learning it).

Anyway, this is, more or less, the problem the teacher gave us to solve:

Write a function that returns the number of days of a month in a given year.

Plain Solutions

Any solution must start with the management of February.

if (month == 2) {
        if (!(year % 100) && (year % 400))
                days = 28;
        else if (!(year % 4))
                days = 29;
        else
                days = 28;
}

Once we have done with the most troublesome month, one solution can involve an array of twelve integers filled at design time with the right numbers. This is probably the way that I'd solve it today but I don't think the teacher would have liked it.

Another good solution is to check first the months with 30 days since they are only four: April, June, September and November.

if ((month == 4) || (month == 6) || (month == 9) || (month == 11))
        days = 30;
else
        days = 31;

Obviously the above solution can be rewritten, in a more readable way, with a switch statement. I'll leave it to you as homework ;-)

Well, you can say that the above code is the solution to the problem. And, when I was 14, I was convinced too. But the teacher was not satisfied. She had another solution.

C'mon, Show Me How Smart You Are

The management of February was the same, but for other months the code was a little tricky.

if (((month < 8) && !(month % 2)) || ((month > 8) && (month % 2)))
        days = 30;
else
        days = 31;

Have you understood the logic behind this? Basically, the months with 30 days are:

• the even ones between March and July and
• the odd ones after August.

You can tell this if you think deeply about the numbers (like a math teacher is supposed to do). But is this a good solution? No, it isn't. And probably it's the worst.

Keep It Simple, Schoolteacher

It has at least two weaknesses: performances and readability. Speaking about the execution speed, two comparisons and two modules are definitely slower than four comparisons.

But the biggest issue is the second: you don't have to show me that you are a good programmer. If you write code that is not easily understandable, you will never be a good member for a development team where everyone should be able to modify each others code.

So, dear teacher, you have been rejected in Computer Science.

A Final Confession

OK, I confess. I've been a little too trenchant. The teacher's solution is not so bad. It has a big quality: the spur to think different, to explore different solutions. Because only comparing different things you can choose the best one.

algorithms, development, personal Monday, April 07, 2014 No comments