On Thu, 16 Dec 2010 04:52:53 +0300, Craig Black <[email protected]>
wrote:
On my computer, the custom sort algorithm performs almost 40 percent
better than the Phobos one. I provided this in case anyone wanted to
improve the phobos algorithm. I only benchmarked this with DMD. I
would be curious to know how it performs with GDC.
Benchmarks! Love them. They will show whatever you want them to. For
example I see that customSort is of different complexity and much slower
than phobos' sort. =)
void quickSort(A, alias L)(A a, int p, int r)
{
if (p >= r) return;
if(p + 7 > r) return insertionSort!(A, L)(a, p, r);
auto x = a[r];
And here is why. Quicksort is quite famous for being O(n^2) worst case
(for sorted data). Your straightforward, simple (and less generic, I must
say) implementation shines for random data, but performs terribly for
ordered data. Phobos' sort isn't really plain quicksort so it is slower
for random data (yet still of the same complexity as your code best case),
but it is pretty fast for ordered data.
I wonder though, what exactly makes std.algorithm.sort twice slower for
random data... overhead of ranges? more complex logic/more code?
--
Using Opera's revolutionary email client: http://www.opera.com/mail/
