Monday, 4 March 2013

Binary Linked Hashes - which one would YOU choose ?

Reading comments on Hacker News about the performance of linked lists and hash tables got me going down another rabbit hole...

Take this example from Stack Overflow about  Binary Trees vs. Linked Lists vs. Hash Tables
From the answers, it seems there is a standard trade-off
  • Binary Trees
    • medium complexity to implement (assuming you can't get them from a library)
    • inserts are O(logN)
    • lookups are O(logN)
  • Linked lists (unsorted)
    • low complexity to implement
    • inserts are O(1)
    • lookups are O(N)
  • Hash tables
    • high complexity to implement
    • inserts are O(1) on average
    • lookups are O(1) on average
and of course you know what O(logN) and O(N) and O(1) mean...

So when you're pairing with the dev and going through the code ( because all testers need to know code ) then when you find out he's using a linked list you can point out the error of his ways...

or maybe not. 
Writing this post reminded me about Alan Page and his blog posts and article about  the 5 Orders of Ignorance:

The 2nd order of ignorance is lack of awareness. You have 2OI when you are unaware of what you don’t know. "

But having read this post you've levelled up and know of things that you don't know ( you're welcome ) and decide to tackle it by doing a Google and find a book such as the (in)famous SICP - ( Structure and Interpretation of Computer Programs ) or Introduction to Algorithms ( especially the Third edition which covers van Emde Boas trees !! )

Or maybe not.
Is this a rabbit hole worth going down ?
Any readers of this blog familiar with algorithms and data structures ?  Have you found it useful in your  work ?

1 comment:

Erik Davis said...

Phil, you just brought back a lot of memories. I loved studying data structure when I was a CS major (in the 90's), but when I changed majors and eventually got into testing, I lost most of it. I haven't worked anywhere yet where I looked at code mat all, so I haven't needed to see any of my now long lost knowledge. I wouldn't mind picking bits of it back up though.