home *** CD-ROM | disk | FTP | other *** search
/ PC World 2001 April / PCWorld_2001-04_cd.bin / Software / TemaCD / webclean / !!!python!!! / BeOpen-Python-2.0.exe / SORTPERF.PY < prev    next >
Encoding:
Python Source  |  2000-09-28  |  3.7 KB  |  143 lines
  1. """Sort performance test.
  2.  
  3. See main() for command line syntax.
  4. See tabulate() for output format.
  5.  
  6. """
  7.  
  8. import sys
  9. import time
  10. import whrandom
  11. import marshal
  12. import tempfile
  13. import operator
  14. import os
  15.  
  16. td = tempfile.gettempdir()
  17.  
  18. def randrange(n):
  19.     """Return a random shuffle of range(n)."""
  20.     fn = os.path.join(td, "rr%06d" % n)
  21.     try:
  22.         fp = open(fn, "rb")
  23.     except IOError:
  24.         result = []
  25.         for i in range(n):
  26.             result.append(whrandom.random())
  27.         try:
  28.             try:
  29.                 fp = open(fn, "wb")
  30.                 marshal.dump(result, fp)
  31.                 fp.close()
  32.                 fp = None
  33.             finally:
  34.                 if fp:
  35.                     try:
  36.                         os.unlink(fn)
  37.                     except os.error:
  38.                         pass
  39.         except IOError, msg:
  40.             print "can't write", fn, ":", msg
  41.     else:
  42.         result = marshal.load(fp)
  43.         fp.close()
  44.         ##assert len(result) == n
  45.         # Shuffle it a bit...
  46.         for i in range(10):
  47.             i = whrandom.randint(0, n-1)
  48.             temp = result[:i]
  49.             del result[:i]
  50.             temp.reverse()
  51.             result[len(result):] = temp
  52.             del temp
  53.     return result
  54.  
  55. def fl():
  56.     sys.stdout.flush()
  57.  
  58. def doit(L):
  59.     t0 = time.clock()
  60.     L.sort()
  61.     t1 = time.clock()
  62.     print "%6.2f" % (t1-t0),
  63.     fl()
  64.  
  65. def tabulate(r):
  66.     """Tabulate sort speed for lists of various sizes.
  67.  
  68.     The sizes are 2**i for i in r (the argument, a list).
  69.  
  70.     The output displays i, 2**i, and the time to sort arrays of 2**i
  71.     floating point numbers with the following properties:
  72.  
  73.     *sort: random data
  74.     \sort: descending data
  75.     /sort: ascending data
  76.     ~sort: many duplicates
  77.     -sort: all equal
  78.     !sort: worst case scenario
  79.  
  80.     """
  81.     cases = ("*sort", "\\sort", "/sort", "~sort", "-sort", "!sort")
  82.     fmt = ("%2s %6s" + " %6s"*len(cases))
  83.     print fmt % (("i", "2**i") + cases)
  84.     for i in r:
  85.         n = 1<<i
  86.         L = randrange(n)
  87.         ##assert len(L) == n
  88.         print "%2d %6d" % (i, n),
  89.         fl()
  90.         doit(L) # *sort
  91.         L.reverse()
  92.         doit(L) # \sort
  93.         doit(L) # /sort
  94.         if n > 4:
  95.             del L[4:]
  96.             L = L*(n/4)
  97.             L = map(lambda x: --x, L)
  98.         doit(L) # ~sort
  99.         del L
  100.         L = map(abs, [-0.5]*n)
  101.         doit(L) # -sort
  102.         L = range(n/2-1, -1, -1)
  103.         L[len(L):] = range(n/2)
  104.         doit(L) # !sort
  105.         print
  106.  
  107. def main():
  108.     """Main program when invoked as a script.
  109.  
  110.     One argument: tabulate a single row.
  111.     Two arguments: tabulate a range (inclusive).
  112.     Extra arguments are used to seed the random generator.
  113.  
  114.     """
  115.     import string
  116.     # default range (inclusive)
  117.     k1 = 15
  118.     k2 = 19
  119.     if sys.argv[1:]:
  120.         # one argument: single point
  121.         k1 = k2 = string.atoi(sys.argv[1])
  122.         if sys.argv[2:]:
  123.             # two arguments: specify range
  124.             k2 = string.atoi(sys.argv[2])
  125.             if sys.argv[3:]:
  126.                 # derive random seed from remaining arguments
  127.                 x, y, z = 0, 0, 0
  128.                 for a in sys.argv[3:]:
  129.                     h = hash(a)
  130.                     h, d = divmod(h, 256)
  131.                     h = h & 0xffffff
  132.                     x = (x^h^d) & 255
  133.                     h = h>>8
  134.                     y = (y^h^d) & 255
  135.                     h = h>>8
  136.                     z = (z^h^d) & 255
  137.                 whrandom.seed(x, y, z)
  138.     r = range(k1, k2+1)                 # include the end point
  139.     tabulate(r)
  140.  
  141. if __name__ == '__main__':
  142.     main()
  143.