customized rants from a PHP dev's viewpoint

Not long ago, the battery in my Dell XPS M1330 decided it was time to die. Apparently, I had hit the wall: my battery which would run fine for an hour and 20 minutes, just died – one day to the next. No warning signs. Nothing. What’s a geek to do? Look at Dells offers? With the cheapest, 4-cell battery coming in at 780 kr. ($156) that didn’t seem like an option. Instead, good old eBay seemed more interesting. With 800+ results for Dell M1330 batteries there was bound to be something good. Just one minor problem … pretty much all of the results are fake batteries. Which leads to the dilemma: cheap, fake battery or expensive, original battery? Well, I decided to give the Chinese fakers a chance and sent for a battery from Hong Kong, figuring that paying the total amount of 400 kr ($80) was the better option. Right I was! Haven’t had a single problem with the battery (a 9-cell, compared to my previous 6-cell) and I’m now mobile once more. All I can say is, suck it, Dell! The expensive batteries and other accessories are a sham, on a par with the printer inks that cost more than perfume.

Going with this spirit, I decided to look into replacing my iPod battery. Of late, the charge on it had been reduced from 3-4 hours to 10 minutes, not really acceptable. Buying a new iPod when the old one works just fine is also not acceptable (I’m sorry but no, I simply do not buy into the ridiculous consumerism advanced by Apple, MicroSoft and others). Some googling on the net led to the following site: ifixipodsfast.com (strange title, as that’s not the domain it’s hosted on). The videos of switching out the battery made it seems so easy that I couldn’t stop myself from purchasing a new battery from BatteriByen (at 100 kr – $20). Before I knew it, I had a knife to my iPod, trying to pry it open. Took me about 30 mins, using improper tools, then the insides of it were showing and I was looking around for something looking like a battery. A bit more time, and the iPod closed up again with just a few marks of my barbaric butchering to show that I’d been messing with the stuff Apple never wanted to see the light of day. Then today the battery arrived, along with a set of proper tools, and I could switch out the battery in about 1 minute flat. One charge later and my iPod has now been playing for a couple of hours, non-stop.

The moral of the story, you ask? Screw the vendor lock-in, go for the competitors that make the accessory you need. Don’t waste your money, support the businesses that actually give you what you want without ripping you off. Oh, and make sure you use proper tools when prying your precious hardware open.

Third in the line of posts on sorting algorithms (first was Bubble Sort and the second was Insertion Sort) is the Shell Sort. This is basically a variant of the insertion sort, with the difference that you’re sorting the array multiple times. Another way of looking at this is that the shell sort is really a second level sort, wrapped around the actual sorting algorithm. The inner algorithm here is the insertion sort but it could technically be anything, owing to what the shell sort actually does: running a number of smaller sorts, gradually sorting the array, before finally going over the whole array.

What makes the shell sort work is that you first divide the array into n smaller arrays and sort them (technically, you don’t divide the array into smaller pieces, you just operate on sub-parts of it). After this, you divide this, now half-sorted, array into n/2 arrays, sort each of these in turn. Iterate till you’re working on the whole array. The trick is that each time you sort one of the sub-parts, this also sorts the array. Because using insertion sort on an already sorted array approaches O(n), the final sort of the entire array in shell sort is much faster than the equivalent insertion sort on an unsorted array.

The Code

<?php

class ShellSort extends BaseSort
{
    public function sortFunction()
    {
        $count = count($this->store);

        $array = $this->store;
        $gap = floor($count / 3);
        do
        {
            for ($i = 0; $i < $gap; $i++)
            {
                $temp = array($array[$i]);
                for ($ii = ($i + $gap), $a = 1; $ii < $count; $ii += $gap)
                {
                    $value = $array[$ii];
                    $b = $a;
                    while ($b > 0 && $temp[$b - 1] > $value)
                    {
                        $temp[$b] = $temp[$b-1];
                        $b--;
                    }
                    $temp[$b] = $value;
                    $a++;
                }
                for ($ii = $i, $a = 0; $ii < $count; $ii += $gap)
                {
                    $array[$ii] = $temp[$a];
                    $a++;
                }
            }
        }
        while ($gap = floor($gap / 2));
        $this->store = $array;
    }
}

The difference to the insertion sort should be readily seen: the outer loop dividing the main array into smaller arrays wraps around an insertion sort.

A note on the algorithm: the sub-parts are taken from the original array by picking every n element. This means that when you move an element in the array, you move it n steps at a time. Compare this to the bubble sort, where an element is only moved one step at a time, and you can probably see why this would be a lot faster – even if the inner loop is the bubble sort.

Some notes on the code: it could obviously do with some proper variable naming – it’s the result of a couple of iterations trying to improve the efficiency. At first I had opted to run the inner insertion sort inline on the array but after getting some fairly bad results I opted for using a temporary array before reinserting the elements into the array to sort.

Results

First, the 1.000 elements:

1000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.003565 seconds. Memory used: 64464 bytes
Running ShellSort sort. Algorithm took: 0.044342 seconds. Memory used: 64376 bytes

At 1.000 elements, the shell sort is about nine times faster than insertion sort. The next test is 10.000 elements.

10000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.044411 seconds. Memory used: 665912 bytes
Running ShellSort sort. Algorithm took: 0.633066 seconds. Memory used: 665816 bytes

Still running slower than the built in PHP sort but nothing remotely close to what could be seen with insertion sort. At 10.000 elements, shell sort is running 50 times faster than insertion sort and only 15 times slower than the run at 1.000 elements. The insertion and bubble sorts were so slow that there was no point trying to run them for 100.000 elements but here it makes sense.

100000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.600952 seconds. Memory used: 6524656 bytes
Running ShellSort sort. Algorithm took: 8.780088 seconds. Memory used: 6524588 bytes

Again, adding 10 times the elements ups the execution time by 15 times – nothing like the O(n2) of the insertion sort or bubble sort.

With shell sort, we’ve reached something that would actually work in a normal environment. There’s of course no reason whatsoever to use it if the PHP sort function does the job – but if it doesn’t here’s a plausible algorithm to use. Not, as I expect to show later, as efficient as other algorithms, but definitely worth a look.

Extending my knowledge on SEO I was getting acquainted with some FireFox plugins (SEO for Firefox, yExplore, and SEOpen) when I happened upon the related search. Specifically, I did a related:http://plind.dk/ search on Google. The result? Hit #9 is ‘Suicide: Read This First‘ and #10 is ‘I had sex with my brother but I don’t feel guilty‘. I’m not quite sure I understand this …

Because I’m freelancing for my previous employer, telecommuting in effect, I’ve become a big fan of screen. I didn’t see the benefit of using the program at first, but when you’re logging into a machine with ssh and then have to log into one or two more, after that, you soon become very happy about the ability to just open another terminal window on the machine – no need to ssh again (to be fair, you could of course use a master connection for your ssh connections and then just hop through logins with multiple ssh commandlines in one go). Even better, screen lets you detach from a session, with that session still running. You can then drop your connection, come back half an hour later, re-attach to your screen session and find everything as you left it. No wonder screen is such a loved tool by so many people.

One thing has been bugging me though: one of my favourite keymappings for vim stopped working after I started using screen. Specifically, I could no longer get <S-TAB> to work: shift-tab was gone! I couldn’t see any way to get it to work and I just left it like that – annoyed that it didn’t work but not annoyed enough to really do something about it. For some strange reason, this is one of those issues that seems to have affected only me and one other user (could not find any more pages on Google, just one guy lamenting that the key-combo stopped working). The alternative is of course that everyone that ever came across this instantly knew how to fix it. Something I’m obviously not ready to accept … though I might have to.

In the end I did manage to find my fix and like so often before, I’m almost ashamed of not having thought of it before. The problem was down to screen not knowing which terminal to emulate and so the fix consists in telling screen to use xterm.

term xterm-256color

If you put the above line (assuming you’re using the 256 color version of xterm and not just xterm) into your .screenrc file, screen happily accepts shift-tab as a key-press combination (it’s actually more likely that the problem lies with how Vim interprets the input from screen. I tested the output of shift-tab and it was identical for using screen and not using screen. Vim however had no idea what was going on). If specifying the terminal in your .screenrc is not an option, you can specify it on the command line:

screen -T xterm-256color

Anyway, I needed to tell the world about this on the off-chance that someone else finds themselves in the same position. I would have loved to find the answer after two minutes on google rather than after 1 hour (there’s another gripe: googling for tips/hints/help on screen is nigh impossible using google, as you won’t get any useful results, just stuff about monitors or tv screens).

Second up in the line of sorting algorithms I’ll run through is the insertion sort algorithm. It’s fairly different from the bubblesort algorithm in that bubblesort will go through every element that you’re trying to sort and compare it with every other element (meaning, you’re looking at about n * n comparisons) while insertion sort will try to minimize the comparison by ordering the elements better. Essentially, insertion sort takes one element at a time and inserts it into another array in it’s right place. For each element, you only compare it with other elements until you find one that’s smaller than the element you’re trying to insert.

In terms of steps, this means something like:

1. Set a to value of element to insert.
2. Set x to index of last element in sorted array.
3. Compare a to sorted_array[x].
4. If a is bigger than sorted_array[x], insert a at sorted_array[x+1]. Done.
5. If a is smaller than sorted_array[x], shift value at x one place up in the sorted array and decrement x.
6. Repeat from 3 till done.

The code

It’s probably easier to figure out what’s going on by looking at the code – it’s really rather simple.

<?php
class InsertionSort extends BaseSort
{
    public function sortFunction()
    {
        $count = count($this->store);
        $result = array();
        $result[0] = $this->store[0];
        for ($i = 1; $i < $count; $i++)
        {
            $value = $this->store[$i];
            $j = $i - 1;
            while ($j >= 0)
            {
                if ($value < $result[$j])
                {
                    $result[$j+1] = $result[$j];
                    $j--;
                }
                else
                {
                    break;
                }
            }
            $result[$j+1] = $value;
        }
        $this->store = $result;
    }
}

Note: The code here makes use of the small test framework I created it Sorting algorithms: quick update.

Quick run through: first, some housekeeping. An array for the result is created, a count of the elements to sort is done and the first element in the sorted array is inserted (it will always be the same element, so better initialize it like this). Then the actual sorting takes place, looping over every element and inserting it into the results array. This is the more interesting part: the element to sort is compared to the top of the results array and if it’s smaller, the results array then gets shifted. This keeps on going till a proper place is found for the element to sort.

Results

First, a test with 1.000 elements.

1000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.003070 seconds. Memory used: 64464 bytes
Running InsertionSort sort. Algorithm took: 0.326779 seconds. Memory used: 64344 bytes

At 1.000 elements, it’s running in 3/5 the time of the bubblesort algorithm.

10000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.039953 seconds. Memory used: 665928 bytes
Running InsertionSort sort. Algorithm took: 32.702462 seconds. Memory used: 665788 bytes

Scaling up by a factor of 10 results in 100 times longer execution time. This is as expected: insertion sort should run in O(n²). The reason for this is that while insertion sort minimizes the amount of comparisons to be done compared with bubblesort, it has exactly the same problem: for every element you add that needs to be sorted you’re also adding a large number of comparisons to do, even if only half as many as for bubblesort.