Front page | perl.perl5.porters |
Postings from September 2013
On Thu Sep 12 05:54:17 2013, nicholas wrote: > On Fri, Sep 06, 2013 at 02:59:44PM -0400, John P. Linderman wrote: > > > Part of the reason, I think, was that v5.6 and earlier's sort was > a > > > quicksort, and hence not a stable sort. > > > > Stability was definitely a feature, but my best argument to Jarkko > was that > > far too many common sequences (organ pipe, sawtooth, etc.) went > quadratic, > > and Peter Mcilroy's merge sort did a particularly nice job on > sequences > > with pre-existing order (linear time on sorted input). > > > > The only sequences (that I could think of, anyway) where it was > clear that > > qsort would outperform merge sort were those containing many > repetitions of > > a small number (k) of keys. Qsort's "fat pivot" guaranteed that > only k > > passes would be required, where merge sort might need log N. > > The bit that keeps bugging me is "how many people know that their data > is > usually going to be in a particular form that qsort favours"? > > In that, the amount of use cases where it's correct to specify qsort > instead > of mergesort are small, the amount of effort needed to determine this > is > high, and the gain itself is small? > > In which case, seems that choosing a specific sort algorithm is not > the > first place to look at optimising. But would it be possible for perl to detect datasets that work better with qsort? Or (most likely) would the time the detection takes outweigh the benefits? -- Father Chrysostomos --- via perlbug: queue: perl5 status: open https://rt.perl.org:443/rt3/Ticket/Display.html?id=119635Thread Previous | Thread Next