7 ms·
Naggum Nugget
- exit 16y agoanother thing the world needs is people who can argue a point without an obnoxious "shut-down" mentality about it. whatever points he's making, it feels like listening to bill o'reilly make them.
- zachbeane 16y agoObtaining useful information in contexts or from people you find unpleasant is a handy skill.
- jimbokun 16y agoIn 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.
- silentbicycle 16y agoIt's good to be able to endure it when necessary, sure, but it's also good to avoid needlessly perpetuating bitterness. Is it really that hard to say, "Complex algorithms have higher constant factors, so for small values of N, 'naive' ones can still be faster. When in doubt, measure." without chewing somebody out?
- dlytle 16y agoAgreed, but being able to present useful information in a context that makes people more receptive, rather than hostile, is also a handy skill. It's easy to deliberately overlook rudeness, but it still unconsciously colors a person's responses and thoughts, which could have a negative impact on the message.
- zck 16y agoThe next reply in that conversation is by...Julian Assange (http://groups.google.com/group/comp.emacs/browse_thread/thread/3e0bf77f8868f46a/b888b276e551aad7?#b8844c1aed3c214e http://groups.google.com/group/comp.emacs/browse_thread/thre...).
- deleted 16y ago[deleted]
- StavrosK 16y agoTL:DR: O(2n^2) complexity is better than O(5000n) for small n. I believe the above to be an accurate summary.
- JoachimSchipper 16y agoPretty much, although O() notation doesn't really work with constants.
- StavrosK 16y agoI know, but it was the most concise way I could express it.
- BrandonM 16y agoIs there a problem with just leaving off the O() altogether?
- silentbicycle 16y agoRight. Big O notation usually excludes constant factors, but here, the constant factors are the point.
- davidw 16y agoI don't see him pin any actual numbers to things. It'd be interesting to see how things work out with different sized lists and hash tables.
- JabavuAdams 16y agoOuch! The cruel tutelage of Erik Naggum. I miss that guy.
- kmavm 16y agoTrue enough in 1999, and all but completely false now. For a competently implemented hash map with integer keys, hash tables start beating linear search somwhere between n = 2 and n = 4. At n = 4, you start needing more than one cacheline to do your linear search. Since a worst-case cache miss is around 300 cycles on a Nehalem, a hash function is very, very cheap price for near-certainty that you'll only probe one line of the structure. All of which makes the table-pounding tone of this post kind of funny from 11 years' hindsight. The crossover point between linear search and hashing is a result of hardware and software parameters, not rhetorical force. He was right when he wrote what he wrote, and is wrong now. Future hardware/software changes might make him right again, but might not. I've indulged in the "real programmers vs. quiche eaters" rhetorical flourish at times, too; this post is a welcome reminder of its risks. It looks better to posterity if you do the experiments, state the results, and walk away.
- hvs 16y agoAnd based on the way he worded it, he would agree with you now. His point was that you need to apply both theory AND practice and not just blindly cite theory.
- jemfinch 16y agoThere is an aspect to theory that's comforting, though. I'm sure I would sleep better at night knowing that my application was using an O(1) hash table as its map rather than an O(n) alist, even if the constant factors are higher. More hardware helps out constant factors; it doesn't do anything with quadratic algorithms.
- deleted 16y ago[deleted]
- bborud 16y agoI don't see why this should look funny 11 years in hindsight. the important part is knowing rather than assuming. and you seem to assume quite a lot.
- 16y ago
- mdemare 16y agotl;dr: Fancy algorithms are slow when n is small, and n is usually small. (Rob Pike).
- gregfjohnson 16y agoIn order to improve the performance of hash tables, why not have the buckets be something like a red-black tree instead of a linked list? (You might improve the efficiency a little by spending a bit and saying "This bucket contains a single element and here it is", or "This bucket contains multiple elements and here is the root of the red-black tree".) Then, you would get log-time search instead of linear-time search when buckets start to fill up with multiple elements.
- Psyonic 16y agoThis exists, it's just generally not done because your buckets should be small enough that linear search is fastest. From the wikipedia hash table article (http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_other_structures http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_wi...): Instead of a list, one can use any other data structure that supports the required operations. By using a self-balancing tree, for example, the theoretical worst-case time of a hash table can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g. in a real-time application), or if one expects to have many entries hashed to the same slot (e.g. if one expects extremely non-uniform or even malicious key distributions).