On Sunday, 15 February 2015 at 18:45:45 UTC, bearophile wrote:
Meta:
Oh, whoops. I mixed up average-case complexity with
worst-case. Although, isn't lookup O(n) in the worst case for
hash tables?
D associative arrays used to be O(1) amortized and O(n ln n) in
worst case. Now they are O(1) amortized and O(n) worst case.
And for an adversary it's not too much hard to find and hit
that O(n) case.
Bye,
bearophile
Hmm, if that's the case, then the logic for not allowing "in" for
arrays and other collections seems to be quite weak. However,
what if the AA implementation is changed again so that lookup is
worst-case O(n*logn)? Should we then again disable "in" for
arrays, etc.?
