[Patches] [ python-Patches-587076 ] Adaptive stable mergesort
noreply@sourceforge.net
noreply@sourceforge.net
Fri, 26 Jul 2002 10:52:52 -0700
Patches item #587076, was opened at 2002-07-26 11: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: Tim Peters (tim_one)
Date: 2002-07-26 13:52
Message:
Logged In: YES
user_id=31435
Numbers from Marc-Andre Lemburg, "AMD Athlon
1.2GHz/Linux/gcc".
samplesort
i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort
15 32768 0.07 0.00 0.01 0.09 0.01 0.03
0.01 0.08
16 65536 0.18 0.02 0.02 0.19 0.03 0.07
0.02 0.20
17 131072 0.43 0.05 0.04 0.46 0.05 0.18
0.05 0.48
18 262144 0.99 0.09 0.10 1.04 0.13 0.40
0.09 1.11
19 524288 2.23 0.19 0.21 2.32 0.24 0.83
0.20 2.46
20 1048576 4.96 0.40 0.40 5.41 0.47 1.72
0.40 5.46
samplesort again (run twice by mistake)
i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort
15 32768 0.08 0.01 0.01 0.09 0.01 0.03
0.00 0.09
16 65536 0.20 0.02 0.01 0.20 0.03 0.07
0.02 0.20
17 131072 0.46 0.06 0.02 0.45 0.05 0.20
0.04 0.49
18 262144 0.99 0.09 0.10 1.09 0.11 0.40
0.12 1.12
19 524288 2.33 0.20 0.20 2.30 0.24 0.83
0.19 2.47
20 1048576 4.89 0.40 0.41 5.37 0.48 1.71
0.38 6.22
timsort
i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort
15 32768 0.08 0.01 0.01 0.01 0.01 0.03
0.00 0.02
16 65536 0.17 0.02 0.02 0.02 0.02 0.07
0.02 0.06
17 131072 0.41 0.05 0.04 0.05 0.04 0.16
0.04 0.09
18 262144 0.95 0.10 0.10 0.10 0.10 0.33
0.10 0.20
19 524288 2.17 0.20 0.21 0.20 0.21 0.66
0.20 0.44
20 1048576 4.85 0.42 0.40 0.41 0.41 1.37
0.41 0.84
----------------------------------------------------------------------
Comment By: Kevin Jacobs (jacobs99)
Date: 2002-07-26 12:54
Message:
Logged In: YES
user_id=459565
Intel 1266 MHz Penguin III x2 (Dual processor)
512KB cache
Linux 2.4.19-pre1-ac2
gcc 3.1 20020205
samplesort:
i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort
15 32768 0.07 0.00 0.01 0.06 0.01 0.02 0.00 0.07
16 65536 0.16 0.02 0.01 0.15 0.01 0.06 0.02 0.17
17 131072 0.37 0.04 0.04 0.35 0.04 0.15 0.03 0.38
18 262144 0.84 0.07 0.08 0.80 0.09 0.31 0.07 0.86
19 524288 1.89 0.16 0.15 1.78 0.19 0.66 0.15 1.92
20 1048576 4.12 0.33 0.31 4.07 0.37 1.34 0.31
4.22
timsort:
i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort
15 32768 0.07 0.01 0.00 0.01 0.01 0.03 0.01 0.01
16 65536 0.17 0.01 0.02 0.01 0.02 0.06 0.02 0.04
17 131072 0.37 0.04 0.03 0.04 0.04 0.13 0.04 0.08
18 262144 0.84 0.07 0.07 0.08 0.08 0.27 0.07 0.16
19 524288 1.89 0.16 0.15 0.15 0.17 0.55 0.15 0.33
20 1048576 4.16 0.32 0.31 0.31 0.32 1.14 0.31
0.66
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2002-07-26 12:30
Message:
Logged In: YES
user_id=31435
Wow! Thanks, Neil! That's impressive, even if I say so
myself <wink>.
----------------------------------------------------------------------
Comment By: Neil Schemenauer (nascheme)
Date: 2002-07-26 12: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