More proof that algorithms matter

Image via Wikipedia

In my piece on Programming Pearls a few days ago, I said I had been inspired to try a different, and hopefully faster, algorithm to manage a linked list.

Well, I did, and then I improved on it a second time by not deleting the array between scans of the memory map of a program being tested – simply reusing the allocated space and using a guard entry to mark the current ‘high tide’ of the chain in the array.

The resulting code is still very slow on the Pentium III box I am testing it on: but there is slow and there is slow: this particular slow is about 100 times faster than the simple/naive algorithm I started off with.

Related articles

• In continued praise of “Programming Pearls” (cartesianproduct.wordpress.com)
• Data Structure Performances – Lists (mirkobronzi.wordpress.com)
• Dynamic Programming – LtU Classic Archives (lambda-the-ultimate.org)