"It's probably premature optimization to use an AVL tree in place of an ordinary binary tree, or even an alist."
Yeah that makes sense, thanks for bringing that up. The constants will probably drown out anything else for small structures.
---
"A hash table has an _expected_ constant lookup time. But it might be as bad as O(number of fields)."
Let me rephrase. A node has a statically constant, small number of fields. Who cares what the time complexity of lookup is?
"He blows all his O(log n) complexities by putting in an expected O(1) lookup for all his field manipulations."
I think you mean O(k) not O(1)? Since k is not n and exactly 4, which is a small number, it's not clear this is a problem.
---
May I suggest referring to the post or idea or implementation rather than to 'the guy'? I'm also finding your use of words like 'disgusting' distracting. (unless you're really feeling flamey :)
Yeah, it is distracting and I'm sorry about that. Similarly, I'm sorry to publicly snipe, 'cause I really do admire folks who make an effort to learn by doing, and better yet, write up their experiences.
But "disgust" was the word I wanted. I can't point at his choice and say "this is all wrong". Instead, I point at it and claim that it "smells" wrong to me, I'd never do it that way, bad taste, etc. Then I tried to argue about why my taste is offended.
Regarding O(1) versus O(k), I actually wrote "expected O(1)". That is, _expected_ constant time, versus guaranteed constant time. Though your point that the number of fields is a constant, 4, is certainly true.
