home *** CD-ROM | disk | FTP | other *** search
/ Freelog 33 / Freelog033.iso / Progr / Python-2.2.1.exe / SORTPERF.PY < prev    next >
Encoding:
Python Source  |  2001-02-09  |  3.6 KB  |  142 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.     # default range (inclusive)
  116.     k1 = 15
  117.     k2 = 19
  118.     if sys.argv[1:]:
  119.         # one argument: single point
  120.         k1 = k2 = int(sys.argv[1])
  121.         if sys.argv[2:]:
  122.             # two arguments: specify range
  123.             k2 = int(sys.argv[2])
  124.             if sys.argv[3:]:
  125.                 # derive random seed from remaining arguments
  126.                 x, y, z = 0, 0, 0
  127.                 for a in sys.argv[3:]:
  128.                     h = hash(a)
  129.                     h, d = divmod(h, 256)
  130.                     h = h & 0xffffff
  131.                     x = (x^h^d) & 255
  132.                     h = h>>8
  133.                     y = (y^h^d) & 255
  134.                     h = h>>8
  135.                     z = (z^h^d) & 255
  136.                 whrandom.seed(x, y, z)
  137.     r = range(k1, k2+1)                 # include the end point
  138.     tabulate(r)
  139.  
  140. if __name__ == '__main__':
  141.     main()
  142.