diff options
| author | Tim Peters <tim.peters@gmail.com> | 2002-08-10 03:04:33 (GMT) |
|---|---|---|
| committer | Tim Peters <tim.peters@gmail.com> | 2002-08-10 03:04:33 (GMT) |
| commit | b80595f44af906922d2a016d1556af5bb6a50158 (patch) | |
| tree | 5d6e89dfb6c31306b80d89db364362e3c06ce2c6 | |
| parent | dd8ddacd94175774dfc1fae8c437e08fe87d178f (diff) | |
| download | cpython-b80595f44af906922d2a016d1556af5bb6a50158.zip cpython-b80595f44af906922d2a016d1556af5bb6a50158.tar.gz cpython-b80595f44af906922d2a016d1556af5bb6a50158.tar.bz2 | |
The samplesort-vs-mergesort #-of-comparisons comparisons were captured
before %sort was introduced. Redid them (the numbers change, but the
conclusions don't). Also did the samplesort counts with the released
2.2.1, as they're slightly different under the last CVS 2.3 samplesort
(some higher, some lower -- CVS had been changed to stop doing the
special-case business on recursive samplesort calls).
| -rw-r--r-- | Objects/listsort.txt | 48 |
1 files changed, 24 insertions, 24 deletions
diff --git a/Objects/listsort.txt b/Objects/listsort.txt index 906b803..545ce51 100644 --- a/Objects/listsort.txt +++ b/Objects/listsort.txt @@ -95,31 +95,31 @@ Comparison with Python's Samplesort Hybrid below that, it's either astronomically lucky, or is finding exploitable structure in the data. - n lg(n!) *sort 3sort +sort ~sort !sort -------- ------- ------ -------- ------- ------- -------- - 32768 444255 453084 453604 32908 130484 469132 samplesort - 449235 33019 33016 188720 65534 timsort - 0.86% 1273.77% -0.33% -30.86% 615.86% %ch from timsort + n lg(n!) *sort 3sort +sort %sort ~sort !sort +------- ------- ------ -------- ------- ------ ------- -------- + 32768 444255 453096 453614 32908 452871 130491 469141 old + 449235 33019 33016 51328 188720 65534 new + 0.86% 1273.80% -0.33% 782.31% -30.85% 615.87% %ch from new - 65536 954037 973111 970464 65686 260019 1004597 - 963924 65767 65802 377634 131070 - 0.95% 1375.61% -0.18% -31.15% 666.46% + 65536 954037 972699 981940 65686 973104 260029 1004607 + 963714 65824 65809 103409 377634 131070 + 0.93% 1391.77% -0.19% 841.02% -31.14% 666.47% - 131072 2039137 2100019 2102708 131232 555035 2161268 - 2058863 131422 131363 755476 262142 - 2.00% 1499.97% -0.10% -26.53% 724.46% + 131072 2039137 2101881 2091491 131232 2092894 554790 2161379 + 2059092 131413 131362 209130 755476 262142 + 2.08% 1491.54% -0.10% 900.76% -26.56% 724.51% - 262144 4340409 4461471 4442796 262314 1107826 4584316 - 4380148 262446 262466 1511174 524286 - 1.86% 1592.84% -0.06% -26.69% 774.39% + 262144 4340409 4464460 4403233 262314 4445884 1107842 4584560 + 4380687 262440 262460 421998 1511174 524286 + 1.91% 1577.81% -0.06% 953.53% -26.69% 774.44% - 524288 9205096 9448146 9368681 524468 2218562 9691553 - 9285454 524576 524626 3022584 1048574 - 1.75% 1685.95% -0.03% -26.60% 824.26% + 524288 9205096 9453356 9408463 524468 9441930 2218577 9692015 + 9285709 524581 524634 848590 3022584 1048574 + 1.81% 1693.52% -0.03% 1012.66% -26.60% 824.30% -1048576 19458756 19950541 20307955 1048766 4430616 20433371 - 19621100 1048854 1048933 6045418 2097150 - 1.68% 1836.20% -0.02% -26.71% 874.34% +1048576 19458756 19950272 19838588 1048766 19912134 4430649 20434212 + 19621118 1048960 1048942 1715806 6045418 2097150 + 1.68% 1791.26% -0.02% 1060.51% -26.71% 874.38% Discussion of cases: @@ -132,10 +132,10 @@ Comparison with Python's Samplesort Hybrid quicksort does about 39% more compares than the limit, and the median-of-3 variant about 19% more. - 3sort and !sort: No contest; there's structure in this data, but not of - the specific kinds samplesort special-cases. Note that structure in !sort - wasn't put there on purpose -- it was crafted as a worst case for a - previous quicksort implementation. That timsort nails it came as a + 3sort, %sort, and !sort: No contest; there's structure in this data, but + not of the specific kinds samplesort special-cases. Note that structure + in !sort wasn't put there on purpose -- it was crafted as a worst case for + a previous quicksort implementation. That timsort nails it came as a surprise to me (although it's obvious in retrospect). +sort: samplesort special-cases this data, and does a few less compares |