Front page | perl.perl5.porters |
Postings from September 2013
Re: [perl #119635] deprecate and remove qsort?
Thread Previous
|
Thread Next
From:
Victor Efimov
Date:
September 7, 2013 08:18
Subject:
Re: [perl #119635] deprecate and remove qsort?
Message ID:
CAF7QZD7i4Ehwidins9yzN0Ob0n4JuDa3L4H=VrF19UmXKc-NaA@mail.gmail.com
I was able to reproduce case when qsort do 3 times less comparison than
mergesort.
However I was unable to find case when qsort faster when comparsion
function is simple, obvious this can be the case for complex comparison
functions. One also can/should use
http://en.wikipedia.org/wiki/Schwartzian_transform anyway if comparison
function is always slow, an this limits benefits of qsort.
==
use strict;
use warnings;
my @a = (1..3) x 100_000;
our $i;
sub mysub
{
++$i;
$a <=> $b;
}
my ($q, $m);
{
use sort '_quicksort';
local $i=0;
my @b = sort mysub @a;
$q = $i;
print "quicksort: $i\n";
};
{
local $i=0;
my @b = sort mysub @a;
$m = $i;
print "mergesort: $i\n";
}
print $q/$m, "\n";
__END_
quicksort: 599997
mergesort: 1746356
0.343570841225958
==
2013/9/7 John P. Linderman <jpl.jpl@gmail.com>
> All true, all valid observations. The merge sort implementation uses N
> additional *pointers* (not records), the qsort implementation sorts in
> place (unless you want stability, in which case it, too, uses another set
> of pointers, same as the merge sort implementation). I started programming
> back in the 60's, when a few kilobytes of memory was all that there was,
> and you'd do all sorts of things that would now be considered inexcusable
> to save a few bytes (like using only the last two digits of the year,
> leading to the Y2K "crisis"). I often have to remind myself that memory is
> now darn near free, but my time is more expensive every year (at least
> until AT&T "surplussed" me). If you need to worry about double the number
> of pointers, perhaps perl is not the implementation language you should be
> using. Qsort, with its divide and conquer approach, automatically ends up
> doing a lot of processing in the fastest (i.e. smallest) cache, which is
> quite ironic, since quicksort was invented when memory was monolithic, and
> caches didn't exist. But I attempted to fix that flaw in merge sort (at
> the expense of some additional stack space... it took some discipline to
> ignore that in the environment I now program in rather than one where I
> learned to program :-). My attitude now (since you didn't ask :-) is that
> space matters a whole lot less than time, and cache hits matter, because
> they have a major impact on time. And maintainability matters a lot too,
> because it relates to correctness, which really matters more than just
> about everything, which is why I wouldn't much mind qsort disappearing. I
> hope to live long enough to experience another major paradigm shift (like
> exploiting multiple processors in parallel).
>
>
> On Fri, Sep 6, 2013 at 3:34 PM, Victor Efimov <victor@vsespb.ru> wrote:
>
>>
>> 2013/9/6 John P. Linderman <jpl.jpl@gmail.com>
>>
>> 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.
>>>
>>
>> Seems memory usage can be better with qsort than with mergesort (not sure
>> about perl implementation).
>>
>> http://en.wikipedia.org/wiki/Merge_sort
>> ===
>> Merge sort's most common implementation does not sort in place;
>> therefore, the memory size of the input must be allocated for the sorted
>> output to be stored in (see below for versions that need only *n*/2
>> extra spaces).
>> ===
>>
>> http://en.wikipedia.org/wiki/Quicksort
>> ===
>> The disadvantage of the simple version above is that it requires O(*n*)
>> extra storage space, which is as bad as merge sort<http://en.wikipedia.org/wiki/Merge_sort>.
>> The additional memory allocations required can also drastically impact
>> speed and cache performance in practical implementations. There is a more
>> complex version which uses an in-place<http://en.wikipedia.org/wiki/In-place_algorithm>partition algorithm and can achieve the complete sort using O(log
>> *n*) space (not counting the input) on average (for the call stack<http://en.wikipedia.org/wiki/Call_stack>).
>> We start with a partition function:
>> ===
>>
>>
>
Thread Previous
|
Thread Next