Tag Archives: Computing

Computer Algorithms: Data Compression with Bitmaps

algorithms, PHP, , , , , , , , , , , , , , ,

Overview

In my previous post we saw how to compress data consisting of very long runs of repeating elements. This type of compression is known as “run-length encoding” and can be very handy when transferring data with no loss. The problem is that the data must follow a specific format. Thus the string “aaaaaaaabbbbbbbb” can be compressed as “a8b8”. Now a string with length 16 can be compressed as a string with length 4, which is 25% of its initial length without loosing any information. There will be a problem in case the characters (elements) were dispersed in a different way. What would happen if the characters are the same, but they don’t form long runs? What if the string was “abababababababab”? The same length, the same characters, but we cannot use run-length encoding! Indeed using this algorithm we’ll get at best the same string.

In this case, however, we can see another fact. The string consists of too many repeating elements, although not arranged one after another. We can compress this string with a bitmap. This means that we can save the positions of the occurrences of a given element with a sequence of bits, which can be easily converted into a decimal value. In the example above the string “abababababababab” can be compressed as “1010101010101010”, which is 43690 in decimals, and even better AAAA in hexadecimal. Thus the long string can be compressed. When decompressing (decoding) the message we can convert again from decimal/hexadecimal into binary and match the occurrences of the characters. Well, the example above is too simple, but let’s say only one of the characters is repeating and the rest of the string consists of different characters like this: “abacadaeafagahai”. Then we can use bitmap only for the character “a” – “1010101010101010” and compress it as “AAAA bcdefghi”. As you can see all the example strings are exactly 16 characters and that is a limitation. To use bitmaps with variable length of the data is a bit tricky and it is not always easy (if possible) to decompress it.

Bitmap Compression
Basically bitmap compression saves the positions of an element that is repeated very often in the message!

Continue reading Computer Algorithms: Data Compression with Bitmaps →

Computer Algorithms: Linear Search in Sorted Lists

algorithms, javascript, PHP, , , , , , , , , , , , ,

Overview

The expression “linear search in sorted lists” itself sounds strange. Why should we use this algorithm for sorted lists when there are lots of other algorithms that are far more effective? As I mentioned in

my previous post the sequential search is very ineffective in most of the cases and it is primary used for unordered lists. Indeed sometimes it is more useful first to sort the data and then use a faster algorithm like the binary search. On the other hand the analysis shows that for lists with less than ten items the linear search is much faster than the binary search. Although, for instance, binary search is more effective on sorted lists, sequential search can be a better solution in some specific cases with minor changes. The problem is that when developers hear the expression “sorted list” they directly choose an algorithm different from the linear search. Perhaps the problem lays in the way we understand what an ordered list is?

What is a sorted list?

We used to think that this list (1, 1, 2, 3, 5, 8, 13) is sorted. Actually we think so because it is … sorted, but the list (3, 13, 1, 3, 3.14, 1.5, -1) is also sorted, except that we don’t know how. Thus we can think that any array is sorted, although it is not always obvious how. There are basically two cases when sequential search can be very useful. First when the list is very short or when we know in advance that there are some values that are very frequently searched. Continue reading Computer Algorithms: Linear Search in Sorted Lists →

Computer Algorithms: Sequential Search

algorithms, javascript, PHP, , , , , , , , , , , , , , , , ,

Overview

This is the easiest to implement and the most frequently used search algorithm in practice. Unfortunately the sequential search is also the most ineffective searching algorithm. However, it is so commonly used that it is appropriate to consider several ways to optimize it. In general the sequential search, also called linear search, is the method of consecutively check every value in a list until we find the desired one.

Basic Implementation

The most natural approach is to loop through the list until we find the desired value. Here’s an implementation on PHP using FOR loop, something that can be easily written into any other computer language.

This is really the most ineffective implementation. There are two big mistakes in this code. First of all we calculate the length of the list on every iteration of the array, and secondly after we find the desired element, we don’t break the loop, but continue to loop through the array.

Forward Linear Search

Yes, if the element is repeated without the “break” we can find its last occurrence, but if not the loop will iterate over the end of the array with no practical value.

Optimization of the forward sequential search

… and javascript:

Optimized forward linear search

Even with this little optimization the algorithm remains ineffective. As we can see, on every iteration we have two conditional expressions. First we check whether we’ve reached the end of the list, and then we check whether the current element equals to the searched element. So the question is can we reduce the number of the conditional expressions?

Searching in reverse order

Yes, we can reduce the number of comparison instructions from the forward approach of the linear search algorithm by using reverse order searching. Although it seems to be pretty much the same by reversing the order of the search we can discard one of the conditional expressions.

Note that we need to adjust index because of $index—expression.

Indeed here we have only one conditional expression, but the problem is that this implementation is correct ONLY when the element exists in the list, which is not always true. If the element doesn’t appears into the list, then this code can lead to an infinite loop. OK, but how can we stop the loop even when the list doesn’t contain the desired value? The answer is, by adding the searched value to the list.

Sentinel

The above problem can be solved by inserting the desired item as a sentinel value. Thus we’re sure that the list contains the value, so the loop will stop for sure even if at the beginning the value didn’t appear to be part of the list.

Using setinel in sequential search

This approach can be used to overcome the problem of the reverse linear search approach from the previous section.

Complexity

As I said at the beginning of this post this is one of the most ineffective searching algorithms. Of course the best case is when the searched value is at the very beginning of the list. Thus on the first comparison we can find it. On the other hand the worst case is when the element is located at the very end of the list. Assuming that we don’t know where the element is and the possibility to be anywhere in the list is absolutely equal, then the complexity of this algorithm is O(n).

Different cases

We must remember, however, that the algorithm’s complexity can vary depending on whether the element occurs once.

Is it so ineffective?

Sequential search can be very slow compared to binary search on an ordered list. But actually this is not quite true. Sequential search can be faster than binary search for small arrays, but it is assumed that for n < 8 the sequential search is faster.

Application

The linear search is really very simple to implement and most web developers go to the forward implementation, which is the most ineffective one. On the other hand this algorithm is quite useful when we search in an unordered list. Yes, searching in an ordered list is something that can dramatically change the search algorithm. Actually searching and sorting algorithms are often used together.

A typical case is pulling something from a database, usually in form of a list and then search for some value in it. Unfortunately in most of the cases the database orders the returned result set and yet most of the developers perform a consecutive search over the list. Yet again when the list is ordered it is better to use binary search instead of sequential search.
Let’s say we have a CSV file containing the usernames and the names of our users.

Username,Name
jamesbond007,James Bond
jsmith,John Smith
...

Now we fetch these values into an array.

// work case
$arr = array(
    array('name' =&gt; 'James Bond', 'username' =&gt; 'jamesbond007'),
    array('name' =&gt; 'John Smith', 'username' =&gt; 'jsmith')
);

Now using sequential search …

// using a sentinel
$x = 'jsmith';
$arr[] = array('username' =&gt; $x, 'name' =&gt; '');
$index = 0;

while ($arr[$index++]['username'] != $x);

if ($index &lt; count($arr)) {
    echo "Hello, {$arr[$index-1]['name']}";
} else {
    echo "Hi, guest!";
}

Object Cloning and Passing by Reference in PHP

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

In PHP everything’s a reference! I’ve heard it so many times in my practice. No, these words are too strong! Let’s see some examples.

Passing by reference in PHP can be tricky!
Some developers think that everything's passed by reference in PHP.

Passing Parameters by Reference

Clearly when we pass parameters to a function it’s not by reference. How to check this? Well, like this.

function f($param)
{
	$param++;
}
 
$a = 5;
f($a);
 
echo $a;

Now the value of $a equals 5. If it were passed by reference, it would be 6. With a little change of the code we can get it.

function f(&$param)
{
	$param++;
}
 
$a = 5;
f($a);
 
echo $a;

Now the variable’s value is 6.

So far, so good. Now what about copying objects?
Continue reading Object Cloning and Passing by Reference in PHP →

Does JavaScript undefined Equals undefined?

javascript, , , , , , , , , , , , ,

Weird JS

Does "undefined" equals "undefined"?
Does JavaScript "undefined" equals "undefined"?

As you know sometimes JavaScript can be weird. Let’s see the following example and let’s try to answer the question: does “undefined” equals “undefined”. What do I mean?

First take a look at the following code.

var a;
var b = undefined;
 
// alerts "false"
alert(b == a);

Both a and b are undefined, but they are NOT equal. Now let’s see where it can become a problem.

We have an object with one member variable that is not defined.

var f1 = function()
{
	this.myvar;
};
 
var obj1 = new f1();

Now you’d like to know whether the object “b” has the property “myvar”. There are lots of examples online, but what’s the right way?
Continue reading Does JavaScript undefined Equals undefined? →