input validation
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Thu Mar 5 16:01:34 PST 2009
Christopher Wright wrote:
> Andrei Alexandrescu wrote:
>> Steve Schveighoffer wrote:
>>> BTW, what happens if you pass a sorted list into find? Intuitively,
>>> you'd assume you can pass as assumeSorted? But you can't really do
>>> anything but linear search?
>>
>> It's up to the designer of the API. Passing a sorted forward range
>> into sort will cut the average search time in half, which does not
>> improve complexity.
>
> How does this work? find in a sorted linked list has the same expected
> runtime as in an unsorted one -- on average, 0.5 * length. Assuming that
> comparisons and iterating are equally expensive, that is. If you assume
> that comparison is more expensive, you can do better, though cheaper
> comparisons don't benefit you at all.
We're saying the same thing.
Andrei
More information about the Digitalmars-d
mailing list