Originally Posted by watchout
O(1) (for lookup) is only average case for your typical hash table implementation, and that only if the key-hashes follow the perfect distribution that the hash-function designer thought to be universal.
|
You might have a point if you can show that hash collisions occur more frequently in the global environment than they would in your small table, taking into account the difference in the amount of allocated hash buckets. Personally, I don't think that's the case.
|
Worst case is O(n). Reality will be somewhere in between, especially since best case O(1) = average case O(1) should give you a hint on why the O-notation is not always the perfect method to judge the performance of an algorithm.
|
I don't see a problem with the O-notation here.
|
This however... is wrong. In the specific way that you did not correctly guess what performance difference I observed. [...] I reran my bench when writing this post and found that the performance of the global table has significantly improved (it's still not completely the same as an empty table though, about 2-5% off *cough*), I apologize for this. I just should have rerun the bench when writing my previous post.
|
Unfortunately, I can only
guess at what testing you're doing without looking at the code. A 2-5% difference seems small enough to be caused by some form of noise.
|
It [the number of entries in the global environment] used to be much bigger - so big actually that my client locked up and disconnected before finishing counting.
|
Iterating over a table with one million string keys and incrementing a counter each iteration takes slightly over 0.3s using lua on my laptop. It's possible that WoW's Lua implementation, or your PC (or both) are slower than what I'm testing against; on the other hand, I doubt the difference is much greater than 1:10. Extrapolating on that, it'd take at least several million entries to freeze your client long enough to force a disconnect. The most obvious conclusion is that your counting code did something other than
just count entries.