@David. I did not read carefully enough your answer. You are talking about hash maps, I was thinking about tree-based maps.
[DAL:] This is precisely my point. When you talk generically about "maps" I assume you refer to the generic concept not a particular implementation. So when you say things like "maps are slow" or "maps are log(n)" I completely disagree. On principal. It is not the generic container class that has a performance characteristic, it is the implementation which does. This is true even when you start to add qualifiers like 'tree based' ... what kind of tree ? it could be a tree with say 10 branches per node, that would have different characteristics then a binary tree. It could be a hash map with a linear list for overflows, or a tree for overflows or any number of variations. Even then, optimizations "under the hood" can make even the best educated guesses wildly wrong. I would estimate that in my years of performance analysis that my first guess as to either what the performance of an algorithm would be, once implemented in actual real optimized code, or looking at a complex system, what part was the major performance bottleneck is wrong more often than right. Maybe that makes me very bad at guessing ... but in my opinion it means that reality is usually more subtle than it looks at first. -David
_______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
