3 ms·
In this case, the useful skill is scanning that wall of text to extract the small nugget of useful information: For small N, finding something in an associatio
by jimbokun 16y ago
In this case, the useful skill is scanning that wall of text to extract the small nugget of useful information:
For small N, finding something in an association list can be faster than finding the same thing in a hash table.
Naggum also could have run some quick bench marks and figured out at what size N hash tables become a better choice (depending on the nature of the keys, etc. etc.), in less time than he spent berating the intelligence of the questioner.
- jules 16y agoI doubt he is right for any N. Association lists require on average N+1 memory accesses. Small hash tables require 1 memory access. Only in edge cases like looking up a long string in an alist consisting of one short string he's right.
- reynolds 16y agoThat nugget of useful information is also explained (in a lot more detail) in one of the first chapters of the "Introduction to Algorithms" book. When I was working through the book (and I still am to some extent), it was basically beat into my brain that some algorithms with worse performance could perform better than faster algorithms for a small enough n.