Find on sorted range slower?

Tofu Ninja via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Thu Aug 6 22:01:39 PDT 2015


On Friday, 7 August 2015 at 04:23:21 UTC, Ali Çehreli wrote:
> Do you want to see SortedRange 1700 times faster? ;)
>
> On 08/06/2015 05:35 PM, Tofu Ninja wrote:> void main()
>
> >          auto temp = assumeSorted(a).find(f);
>
> SortedRange does not have a find() member. What happens is, it 
> goes to find() algorithm. Replace that line with
>
>         auto temp = assumeSorted(a).equalRange(f);
>         writefln("found: %s", temp.front);
>
> New result:
>
> found: 102400000
> found: 102400000
> Sorted	83235
> Regular	141392157
> Ratio	0.000588682
>
> Ali

Hmm.... I feel like I have read on the forums like a million 
times that certain parts of std.algorithm was specialized for 
sorted ranges, I guess that was just talk...

Still does not really explain why find is slower on the 
assumeSorted version.


More information about the Digitalmars-d-learn mailing list