Tag Archives: Mathematics

Beginning Algorithm Complexity and Estimation

micro tutorial, PHP, , , , , , , , , , , , , , , , ,

Which is the Fastest Program?


When a programmer sees a chunk of code he tends to evaluate it in a rather intuitive manner and to qualify it as “elegant” or not. This is quite easy, because it’s subjective and nobody knows what exactly elegant means. However behind this there is a powerful mathematical approach of measuring a program effectiveness.

It’s a pity that most of the developers still think of the big O notation as something from the university classes, but unusual in the practice and they barely use it their job. But before describing the big O notation, let me start from something really simple.

Let’s have the following example (note that all the examples are in PHP):

$n = 100;
$s = 0;
 
for ($i = 0; $i < $n; $i++) {
	for ($j = 0; $j < $n; $j++) {
		$s++;	
	}	
}

As you can see there are two assignments and two nested loops. This is really a widely used example from any algorithm book.

Constants, Languages, Compilers

First of all the time to assign a value to a variable, to compare two values and to increment a variable is constant. It depends on the computer resources, the compiler or the language, but it’s constant on one machine if you compare two chunks of code. Now we can see that these operations take (add) constant time to the program, and we can assume this time is respectively a, b, c, d, e, f, g, h, i.

$n = 100; 	// a
$s = 0;		// b
$i = 0; 	// c
$i < $n; 	// d
$i++;		// e
$j = 0; 	// f
$j < $n;	// g
$j++;		// h
$s++;		// i

What Matters?

Actually the most important thing here is the value of n. By assigning greater values to n the more time will take the program to run. As we can see from the following table by multiplying the value of n by 10, the time became 100 times more.

n		time
10		0.00002
100		0.002
...		...

What happens in fact is that we can sum all these values.

a + b + c + n*d + n*e + n*(f + n*g + n*h + n*i)

and by substituting:

a + b + c = k
d + e + n = l
g + h + i = m

the result is:

m*n² + l*n + k

Conclusion

Here the most important thing is the degree of n, because it can change dramatically the program time consumption depending on the n value. Thus this chunk has a quadratic complexity or O(n²).

Of course there are constants, but in the practice they are not so important. Take a look at these two functions:

f = 2*n²
g = 200*n

OK, for n = 1 the first one will be faster, but as n increments the second function becomes to be faster and faster, thus after a given value of n the second function is really the fastest!

PHP: What is More Powerful Than list()

micro tutorial, PHP, , , , , , , , , , , , , , ,

First of all list() is not an unknown method in the PHP community, where almost every PHP developer knows what it does. The pity is that it has, perhaps, remained useless, although there is hidden power in it!

What is list()?

Let’s assume you’ve two variables and one array with two elements:

$arr = array(1, 2);
$a = $arr[0];
$b = $arr[1];
// now a == 1, and b == 2

Maybe the easiest way to assign to the first variable the value of the first element of the array, and to the second variable the value of the second element of the array is to use list():

list($a, $b) = array(1, 2);
// again a == 1, and b == 2

Note that you can do the same with as many variables/array elements you want.

The funny thing is that nobody use it, while I see at least one perfect usage. You can think of a typical admin panel of any web system. For sure any developer has programmed the typical table page containing a list of “things” and a paging to switch the result set page. It’s like the posts page from the WordPress admin panel, or a search result page in Google, where you’ve one page of results and at the bottom – a number of pages where you can go to another page of the search results.

What I’ve seen in almost every project is that typically the developers prefer to set the results for the page into one list returned from one method and the count of the entire result set is returned by another method.

Thus most of the times there are two methods, performing most commonly a database queries. Something like – getList($offset, $limit) and getCount() where the first one returns the page and the second one returns the count of the result set.

This will result into two methods, two calls and two lines of code:

function getList($offset, $limit)
{
	...
	// although the entire result set contains
	// 5 elements by limiting it from the parameters
	// only three are returned
	return $list; // where $list = array('title1', 'title2', 'title3');	
}
 
function getCount()
{
	...
	// here's returned the count
	// of the entire result set
	return $count; // where $count = 5;	
}
 
$list  = getList(0, 3);
$count = getCount();

What actually you can do is to perform both queries in one method, perhaps called getItems($offset, $limit) where the returned value is an array containing both the list of results and the count:

function getItems($offset, $limit)
{
	...
	return array('list' => $list, 'count' => $count);
}

And finally when calling this method to list() that into the two variables – single lined.

list($list, $count) = getItems(0, 3);

Friday Algorithms: JavaScript Bubble Sort

algorithms, javascript, micro tutorial, web development, , , , , , , , , , ,

Bubble Sort

Unsorted Array

This is one of the most slowest algorithms for sorting, but it’s extremely well known because of its easy to implement nature. However as I wrote past Fridays there are lots of sorting algorithms which are really fast, like the quicksort or mergesort. In the case of bubble sort the nature of the algorithm is described in its name. The smaller element goes to the top (beginning) of the array as a bubble goes to the top of the water.

There is a cool animation showing how bubble sort works in compare to the quick sort and you can practically see how slow is bubble sort because of all the comparing.

QuickSort vs. BubbleSort

Pseudo Code

Actually what I’d like to show you is how you can move from pseudo code to code in practice. Here’s the pseudo code from Wikipedia.

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length(A) - 2 inclusive do:
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        swapped := true
      end if
    end for
  while swapped
end procedure

JavaScript Source

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
 
function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}
 
bubbleSort(a);
console.log(a);

As a result you’ve a sorted array!

Sorted Array

Friday Algorithms: JavaScript Merge Sort

algorithms, javascript, web development, , , , , , , ,

Merge Sort

This week I’m going to cover one very popular sorting algorithm – the merge sort. It’s very intuitive and simple as it’s described in Wikipedia:

  • If the list is of length 0 or 1, then it is already sorted. Otherwise:
  • Divide the unsorted list into two sublists of about half the size.
  • Sort each sublist recursively by re-applying merge sort.
  • Merge the two sublists back into one sorted list.

Here’s the Source

(JavaScript)

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
 
function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;
 
    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);
 
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right)
{
    var result = [];
 
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}
 
console.log(mergeSort(a));

It’s interesting to see what happens in the Firebug’s console:

[34, 203, 3, 746] [200, 984, 198, 764, 9]
 
[34, 203] [3, 746]
 
[34] [203]
 
[3] [746]
 
[200, 984] [198, 764, 9]
 
[200] [984]
 
[198] [764, 9]
 
[764] [9]
 
[3, 9, 34, 198, 200, 203, 746, 764, 984]

Actually the tricky part in this algorithm is the merge function – it does all the work.

Friday Algorithms: Sorting a Set of Integers – Far Quicker than Quicksort!

algorithms, javascript, web development, , , , , , , ,

Yes! It’s really really fast, and it’s far quicker than the quicksort algorithm, which is considered as the fastest sorting algorithm in practice. However how it’s possible to be faster than the quicksort, which is the fastest algorithm?! Is that true? Actually it’s true, but only in few cases. It works with integers, you’ve to know the first and the last element from that set and you’ve to be sure that every element is unique

Imagine you’ve a set of numbers all of them greater than 1 and lesser than 1000. Of course you’re not suppose to have all of the integers between 1 and 1000, but only few of them – think of 500 numbers between 1 and 1000! Here’s important to note – that this is only an example, you can have far more than only few numbers between 1 and 1000 – what about the numbers between 1 and 1,000,000 – this is a big set, isn’t it.

The question is – if there are so many constraints, why should I use that algorithm instead of quicksort, or another sorting algorithm, that works with everything. The answer is clear – yes, you’d prefer quicksort if you’ve to sort some arbitrary data, but when it comes to integers, and you’ve, let’s say, 1,000,000 integers, my advice is – use this algorithm!

Sorting the Set

1. First Pass

First we have an unsorted array, but we know the minimum and maximum of the set.

an unsorted array of integers

On the first pass initialize an empty array with as many elements, as they are between the first and the last element of the set – for a set between 1 and 1000 – that will be an array with 1000 elements – each of which will be a zero in the beginning.

temporary array with 0 on every element

Than loop trough the set and for every element in the set – you should put a 1 on it’s place

sort a set - first pass

Now we have an array of 0 and 1.

2. Second Pass

After the first pass, you’d guess what you’ve to do – loop trough the second array and print the keys of the elements different from 0 – those that are 1.

a sorted set of integers

Now the array is sorted!

Source Code

var a = [34, 203, 3, 746, 200, 984, 198, 764];
 
function setSort(arr)
{
    var t = [], len = arr.length;
    for (var i = 0; i < 1000; i++) {
        t[i] = 0;
    }
 
    for (i = 0; i < len; i++) {
        t[arr[i]] = 1;
    }
 
    for (i = 0; i < 1000; i++) {
        if (1 == t[i]) {
            console.log(i);
        }
    }
}
 
setSort(a);

Now that you’ve seen that algorithm, perhaps you’d guess that it’s no so difficult to change from integers to any other set, and once again I should say that in many cases this is the best algorithm for sorting! Very often quicksort is preferred, but not always there isn’t something faster!