| |||||||||||||
Worst case performance and "impossibly unlikely" conditionsWorst case performance and "impossibly unlikely" conditionsPosted Jan 13, 2012 20:16 UTC (Fri) by rgmoore (✭ supporter ✭, #75)In reply to: Worst case performance and "impossibly unlikely" conditions by cmccabe Parent article: Denial of service via hash collisions
As I understand it, Perl switched to a random pivot at the same time they moved from quicksort to merge sort as their default algorithm. But that still has some potential problems. After all, if quicksort and merge sort are both O(NlogN), then which one is faster depends on implementation details, not algorithmic complexity. Adding extra processor cycles to pick the pivot may slow the whole thing down to the point that it loses its average case speed advantage over merge sort. And it seems like using a random pivot would exacerbate the problem with quicksort not being a stable sort. Not only would items that compare the same not be guaranteed to stay in the same order after the sort, they wouldn't even be guaranteed to be in the same order if you sort the same list twice. I guess you already accepted that when you chose an unstable sort algorithm, but it still seems weird.
(Log in to post comments)
Worst case performance and "impossibly unlikely" conditions Posted Jan 13, 2012 20:49 UTC (Fri) by joey (subscriber, #328) [Link]
Perl's sort does sort the same list the same way twice, despite being unstable. If the pivot is chosen randomly, it must be pseudorandom with a seed of the input list.
To test this I used code like this, which exercises the instability of the sort:
perl -MData::Dumper -e 'print Dumper sort { $a->[0] <=> $b->[1] } ([1,1],[2,3],[1,2],[2,1],[2,4])'
perl -le 'sub c { $a->[0] <=> $b->[1] } @l=([1,1],[2,3],[1,2],[2,1],[2,4]); print sort(\&c, @l) == sort(&c, @l)'
Worst case performance and "impossibly unlikely" conditions Posted Jan 13, 2012 23:20 UTC (Fri) by rgmoore (✭ supporter ✭, #75) [Link] That's because they changed the default sort to merge sort, which is stable, starting in 5.8. If you want to test whether their quicksort is stable from run to run over the same data, you'd need to
|
|||||||||||||