[Patches] [ python-Patches-587076 ] Adaptive stable mergesort

[noreply@sourceforge.net]

Patches item #587076, was opened at 2002-07-26 15:51
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=587076&group_id=5470

Category: Core (C code)
Group: Python 2.3
Status: Open
Resolution: None
Priority: 5
Submitted By: Tim Peters (tim_one)
Assigned to: Nobody/Anonymous (nobody)
Summary: Adaptive stable mergesort

Initial Comment:
This adds method list.msort([compare]).

Lib/test/sortperf.py is already a sort performance 
test.  To run it on exactly the same data I used, run it 
via

python -O sortperf.py 15 20 1

That will time the current samplesort (even after this 
patch).  After getting stable numbers for that, change 
sortperf's doit() to say L.msort() instead of L.sort(), 
and you'll time the mergesort instead.

CAUTION:  To save time across many runs, sortperf 
saves the random floats it generates, into temp files.  
If those temp files already exist when sortperf starts, 
it reads them up instead of generating new numbers.  
As a result, it's important in the above to pass "1" as 
the last argument the *first* time you run sortperf -- 
that forces the random # generator into the same 
state it was when I used it.

This patch also gives lists a new list.hsort() method, 
which is a weak heapsort I gave up on.  Time it if you 
want to see how bad an excellent sort can get <wink>.


----------------------------------------------------------------------

>Comment By: Neil Schemenauer (nascheme)
Date: 2002-07-26 16:23

Message:
Logged In: YES 
user_id=35752

AMD 1.4 Ghz Athon CPU
  L1 I Cache: 64K (64 bytes/line), D cache 64K (64 bytes/line)
  L2 Cache: 256K (64 bytes/line)
Linux 2.4.19-pre10-ac1
gcc 2.95.4

samplesort:
 i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort
 !sort
15   32768   0.06   0.01   0.01   0.07   0.01   0.03   0.01
  0.07
16   65536   0.16   0.02   0.02   0.15   0.02   0.07   0.02
  0.17
17  131072   0.37   0.03   0.03   0.39   0.04   0.16   0.04
  0.41
18  262144   0.84   0.07   0.08   0.87   0.10   0.34   0.07
  0.93
19  524288   1.89   0.16   0.16   1.97   0.21   0.70   0.16
  2.08
20 1048576   4.20   0.33   0.34   4.55   0.41   1.45   0.34
  4.61

timsort:
 i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort
 !sort
15   32768   0.06   0.00   0.01   0.01   0.01   0.03   0.00
  0.01
16   65536   0.14   0.02   0.02   0.02   0.02   0.06   0.02
  0.04
17  131072   0.35   0.04   0.04   0.04   0.04   0.12   0.04
  0.08
18  262144   0.79   0.08   0.08   0.09   0.09   0.27   0.09
  0.16
19  524288   1.79   0.17   0.17   0.18   0.17   0.54   0.17
  0.33
20 1048576   3.96   0.35   0.34   0.34   0.36   1.12   0.34
  0.70


----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=587076&group_id=5470