From d5f4359458877fd2e36d82f71e2c2f86ad50b251 Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Fri, 2 Aug 2002 05:46:09 +0000 Subject: 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 . 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 --- Lib/test/sortperf.py | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) 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:] -- cgit v0.12