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