Find on sorted range slower?

Tofu Ninja via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Thu Aug 6 17:35:56 PDT 2015


void main()
{
	auto a = new int[100*1024*1024];
	for(int i = 0; i < 100*1024*1024; i++)
	{
		a[i] = i;
	}

	enum f = 100*1024*1000;

	StopWatch sw;
	{
		sw.start();
		auto temp = assumeSorted(a).find(f);
		sw.stop();
	}
	auto t1 = sw.peek();

	sw.reset();

	{
		sw.start();
		auto temp = a.find(f);
		sw.stop();
	}
	auto t2 = sw.peek();

	writeln("Sorted\t", t1.length);
	writeln("Regular\t", t2.length);
	writeln("Ratio\t", float(t1.length)/ float(t2.length));
}


I am getting the assumeSorted version to be about 3x slower than 
the regular find, that seems very counter intuitive. Anyone know 
why this would be, seems like a very odd thing to happen. I 
expected the assumeSorted to be faster, expect it to do a binary 
search, instead if a linear one.




More information about the Digitalmars-d-learn mailing list