Thread overview | |||||||
---|---|---|---|---|---|---|---|
|
January 27, 2011 A few improvements to SortedRange | ||||
---|---|---|---|---|
| ||||
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. https://github.com/D-Programming-Language/phobos/commit/b6aabf2044001ea61af15834dcec5855680cf209 http://d-programming-language.org/cutting-edge/phobos/std_range.html#SearchPolicy http://d-programming-language.org/cutting-edge/phobos/std_range.html#SortedRange Andrei |
January 27, 2011 Re: A few improvements to SortedRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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
|
January 27, 2011 Re: A few improvements to SortedRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | 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
|
January 28, 2011 Re: A few improvements to SortedRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 2011-01-27 19:22, Andrei Alexandrescu wrote: > 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. > > https://github.com/D-Programming-Language/phobos/commit/b6aabf2044001ea61af15834dcec5855680cf209 > > > http://d-programming-language.org/cutting-edge/phobos/std_range.html#SearchPolicy > > > http://d-programming-language.org/cutting-edge/phobos/std_range.html#SortedRange > > > > Andrei When I view that page in Firefox 4 I get this error in a dialog window: "The language of this website could not be determined automatically. Please indicate the main language: (ISO 639-1)" In Internet Explorer I get: "Hyphenator.js says: An Error occurred: 'window.prompt(...)' is null or not an object" -- /Jacob Carlborg |
January 28, 2011 Re: A few improvements to SortedRange | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jacob Carlborg | On 1/28/11 7:27 AM, Jacob Carlborg wrote:
> On 2011-01-27 19:22, Andrei Alexandrescu wrote:
>> 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.
>>
>> https://github.com/D-Programming-Language/phobos/commit/b6aabf2044001ea61af15834dcec5855680cf209
>>
>>
>>
>> http://d-programming-language.org/cutting-edge/phobos/std_range.html#SearchPolicy
>>
>>
>>
>> http://d-programming-language.org/cutting-edge/phobos/std_range.html#SortedRange
>>
>>
>>
>>
>> Andrei
>
> When I view that page in Firefox 4 I get this error in a dialog window:
>
> "The language of this website could not be determined automatically.
> Please indicate the main language: (ISO 639-1)"
>
> In Internet Explorer I get:
>
> "Hyphenator.js says:
> An Error occurred:
> 'window.prompt(...)' is null or not an object"
>
Yah, I added experimental hyphenation. Looks much better, but I forgot how to set the language. Removed for now.
Andrei
|
Copyright © 1999-2021 by the D Language Foundation