A few improvements to SortedRange
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Thu Jan 27 11:22:51 PST 2011
On 1/27/11 12:43 PM, bearophile wrote:
> Andrei:
>
>> I just committed a few improvements to phobos' SortedRange, notably
>> adding various search policies and improving the existing routines.
>> These changes will be rolled out in the next dmd release. Until then,
>> feel free to suggest any improvements.
>
> That SearchPolicy will be enough for maniacs too (it just lacks optional galloping sound effects), very good Andrei :-)
>
> Bye,
> bearophile
In fact I implemented it because many large-scale algorithms (such as
n-way merge or intersection) use galloping search as a primitive. One
nice perk is that having galloping search available allowed me to
improve equalRange, which is often of use in casual applications.
Right now equalRange is arguably better than all other implementations
I've seen because once it found one element that's inside the equal
range, it performs galloping searches to the left and to the right to
find the limits of that range. Other implementations I've seen use
straight binary search for finding those limits, which I think is
inferior because most often the limits of the equal range are close to
the found point.
Andrei
More information about the Digitalmars-d-announce
mailing list