On Sunday, 15 February 2015 at 19:04:57 UTC, Meta wrote:
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.?
Where is the lang. scpec. saying that "in" must only be used if
the complexity is O this O that ? (seriously show me the link...)
It's understandable that phobos respects this consensus, but
please don't deactivate opIn_r for the users..."in" makes sense
in many contexts.
