Consistency

Baz via Digitalmars-d digitalmars-d at puremagic.com
Sun Feb 15 12:59:32 PST 2015


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.



More information about the Digitalmars-d mailing list