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)