More proof that algorithms matter

Diagram of deleting a node from a singly linke... — 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.

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)

Related articles

Rate this:

Share this:

Like this:

Related