diff options
| author | Tim Peters <tim.peters@gmail.com> | 2002-08-02 05:46:09 (GMT) |
|---|---|---|
| committer | Tim Peters <tim.peters@gmail.com> | 2002-08-02 05:46:09 (GMT) |
| commit | d5f4359458877fd2e36d82f71e2c2f86ad50b251 (patch) | |
| tree | 21544ece38184e47b8e365a7929d78cb5cde3b8f | |
| parent | fe51c6d66e0fbf6a142036bee2c448bd7fe8fefc (diff) | |
| download | cpython-d5f4359458877fd2e36d82f71e2c2f86ad50b251.zip cpython-d5f4359458877fd2e36d82f71e2c2f86ad50b251.tar.gz cpython-d5f4359458877fd2e36d82f71e2c2f86ad50b251.tar.bz2 | |
New test %sort. This takes a sorted list, picks 1% of the list positions
at random, and replaces the elements at those positions with new random
values. I was pleasantly surprised by how fast this goes! It's hard to
conceive of an algorithm that could special-case for this effectively.
Plus it's exactly what happens if a burst of gamma rays corrupts your
sorted database on disk <wink>.
i 2**i *sort ... %sort
15 32768 0.18 ... 0.03
16 65536 0.24 ... 0.04
17 131072 0.53 ... 0.08
18 262144 1.17 ... 0.16
19 524288 2.56 ... 0.35
20 1048576 5.54 ... 0.77
| -rw-r--r-- | Lib/test/sortperf.py | 8 |
1 files changed, 7 insertions, 1 deletions
diff --git a/Lib/test/sortperf.py b/Lib/test/sortperf.py index 86b38ba..cc83ee4 100644 --- a/Lib/test/sortperf.py +++ b/Lib/test/sortperf.py @@ -76,12 +76,13 @@ def tabulate(r): /sort: ascending data 3sort: ascending, then 3 random exchanges +sort: ascending, then 10 random at the end + %sort: ascending, then randomly replace 1% of the elements w/ random values ~sort: many duplicates =sort: all equal !sort: worst case scenario """ - cases = tuple([ch + "sort" for ch in r"*\/3+~=!"]) + cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"]) fmt = ("%2s %7s" + " %6s"*len(cases)) print fmt % (("i", "2**i") + cases) for i in r: @@ -106,6 +107,11 @@ def tabulate(r): L[-10:] = [random.random() for dummy in range(10)] doit(L) # +sort + # Replace 1% of the elements at random. + for dummy in xrange(n // 100): + L[random.randrange(n)] = random.random() + doit(L) # %sort + # Arrange for lots of duplicates. if n > 4: del L[4:] |