#!/usr/bin/env python ### cache_friends_plot.py -- Plot output of cache_friends_test. # argv[] is the list of programs; for each there is a .out file. from sys import stdin, argv from os import system from math import log, e, floor, ceil from reportlab.pdfgen import canvas from reportlab.lib.pagesizes import letter, A4 from reportlab.lib.units import inch from random import random ## read_one_run -- Read three lines of test output that look like this: # size: 2097152 alloc: 0.000057 randomize: 0.232545 # 1 2 3 7 9 10 12 13 13 16 17 18 21 24 24 24 27 30 31 33 34 36 ... # pages of 1022: 5.709841 # # Return a dict with int size (called n), floats alloc, randomize and time, # and strings output and longname. # If end of file, just return None. def read_one_run( f ): line = f.readline().rstrip() if line == "": return None result = {} parts = line.split() assert parts[0] == "size:" result[ "n" ] = int( parts[1] ) assert parts[2] == "alloc:" result[ "alloc" ] = float( parts[3] ) assert parts[4] == "randomize:" result[ "randomize" ] = float( parts[5] ) result[ "output" ] = f.readline().strip() line = f.readline().rstrip() left,right = line.split( ":" ) result[ "longname" ] = left.strip() result[ "time" ] = float( right ) return result ## read_one_out_file -- Read all runs in a file. # Check longname consistency. # Return longname, and a dict indexed by n. def read_one_out_file( filename ): longname = None results = {} f = open( filename ) while True: run = read_one_run( f ) if not run: break if longname == None: longname = run[ "longname" ] else: assert longname == run[ "longname" ] results[ run[ "n" ] ] = run return longname, results ## read_program_outputs -- Read .out files for all programs. # Return list of longnames, dict indexed by longname. def read_program_outputs( program_names ): longnames = [] results = {} for prog in program_names: longname, prog_result = read_one_out_file( prog + ".out" ) longnames.append( longname ) results[ longname ] = prog_result return longnames, results def random_RGB(): r = random() g = random() b = random() while True: t = r*2 + g*3 + b if t > 2.99 and t < 3.01: break r = min( r * 3 / t, 1 ) g = min( g * 3 / t, 1 ) b = min( b * 3 / t, 1 ) return r, g, b def plot_results( longnames, results ): output_file = "graph.pdf" # pageCompression = 0 to make text in the output readable. # set to 1 in rl_config.py. c = canvas.Canvas( output_file, pagesize=letter ) width, height = letter #keep for later # choose some colors c.setStrokeColorRGB(0,0,0) c.setFillColorRGB(0,0,0) c.setFont("Helvetica", 14 ) c.drawString( 1 * inch, 10 * inch, "Heapsort Arrangement Timing Comparison" ) c.setFont("Helvetica", 11 ) c.drawString( 1 * inch, 9.5 * inch, "Some nice smaller text here." ) # # Set the origin in the middle of the page: # c.translate( 8.5 * inch / 2, 11 * inch / 2 ) # Scale so that range of the graph is about +/- 5: # NOTE: THIS MEANS LINE WIDTHS AND FONTS AREN'T IN POINTS ANY MORE. # scale = .7 * inch scale = 1 c.scale( scale, scale ) point = 1 / scale left_edge = 1.5 * inch right_edge = 7.5 * inch bottom_edge = 2 * inch top_edge = 8 * inch # Draw the axes: def log_scale( min, max ): for base in 2, 10: minlog = int( floor( log( min, base ) ) ) maxlog = int( ceil( log( max, base ) ) ) if maxlog - minlog <= 10: break return base, minlog, maxlog ns = all_ns( results ) minn, maxn = ns[0], ns[-1] xbase, min_log_n, max_log_n = log_scale( minn, maxn ) left_edge_n = xbase ** min_log_n right_edge_n = xbase ** max_log_n def scalex( x, minx, maxx ): return left_edge + ( right_edge - left_edge ) * ( x - minx ) / ( maxx - minx ) # Draw and label the X axis: c.setLineWidth( 1 * point ) c.line( left_edge, bottom_edge, right_edge, bottom_edge ) c.setFont("Helvetica", 10 * point ) c.setLineWidth( .25 * point ) ticks = [] names = [] for pwr in xrange( min_log_n, max_log_n + 1 ): ticks.append( pwr ) names.append( str(xbase) + "^" + str(pwr) ) for i in range( len( ticks ) ): x, name = ticks[i], names[i] x = scalex( x, min_log_n, max_log_n ) c.line( x, bottom_edge -.1 * inch, x, bottom_edge - .0 * inch ) printexp( c, x, bottom_edge -.3 * inch, name, "Helvetica", 10 * point ) c.setFont("Helvetica", 12 * point ) printexp( c, (left_edge+right_edge)*.5, bottom_edge -.3 * inch - 25 * point, "n = number of elements sorted", "Helvetica", 12 * point ) # Figure out what's going on with the y axis: def t_over_n_fn( name, n, stuff ): return stuff["time"] / ( float(n) ) t_over_n_fn.label = "run time per element" def t_over_n_lg_n_fn( name, n, stuff ): return stuff["time"] / ( n * log( n, 2 ) ) t_over_n_lg_n_fn.label = "run time / n lg n" y_fn = t_over_n_lg_n_fn ys = sort_map( flatten_results( results ), y_fn ) min_lg_y = int( floor( log( ys[0], 2 ) ) ) # miny = 2.0**min_lg_y miny = 0.0 # This is a linear scale, let's start at zero. max_lg_y = int( ceil( log( ys[-1], 2 ) ) ) maxy = 2.0**max_lg_y def scaley( y, miny, maxy ): return bottom_edge + (top_edge-bottom_edge) * ( y-miny ) / ( maxy - miny ) # Draw and label the Y axis: c.setLineWidth( 1 * point ) c.line( left_edge, bottom_edge, left_edge, top_edge ) c.setFont("Helvetica", 10 * point ) c.setLineWidth( .25 * point ) ticks = [] names = [] # Don't divide too finely or labels overlap: for lg in xrange( max( min_lg_y, max_lg_y - 5 ), max_lg_y + 1 ): ticks.append( 2.0**lg ) names.append( "2^" + str(lg) ) for i in range( len( ticks ) ): y, name = ticks[i], names[i] y = scaley( y, miny, maxy ) c.line( left_edge - .1*inch, y, left_edge - .0 * inch, y ) printexp( c, left_edge -.3 * inch, y, name, "Helvetica", 10 * point ) c.setFont("Helvetica", 12 * point ) c.saveState() c.translate( left_edge - .3 * inch - 25 * point, (top_edge+bottom_edge) *.5 ) c.rotate(90) printexp( c, 0, 0, y_fn.label, "Helvetica", 12 * point ) c.restoreState() # Draw the graph lines: textx = left_edge + .5 * inch texty = top_edge min_t_over_n_lg_n = 1000 max_t_over_n_lg_n = -1000 c.setLineWidth( 1 * point ) # These colors are picked from the 2D space where ( 2r + 3g + b ) == 3. colors = [ # ( 0, 1, 0 ), Bright green isn't distinct on printers. ( 0, .67, 1 ), # aqua ( .5, .67, 0 ), # olive ( .5, .33, 1 ), # lavender ( 1, .33, 0 ), # orange ( 1, 0, 1 ), # magenta ( .17, .78, .32 ), # med green -- ?? ( .33, .56, .66 ), # teal ( .67, .44, .34 ), # brown ( .83, .22, .68 ), # purple ( .5, .5, .5 ) # gray ] for i, name in enumerate( longnames ): result = results[ name ] r, g, b = colors[ i ] c.setStrokeColorRGB( r, g, b ) c.setFillColorRGB( r, g, b ) c.drawString( textx, texty, name ) texty -= 15 * point n = minn t = result[ n ][ "time" ] prevx = scalex( log( n, xbase ), min_log_n, max_log_n ) prevy = scaley( y_fn( name, n, result[n] ), miny, maxy ) t_over_n_lg_n = t / float(n * log( n, 2 )) min_t_over_n_lg_n = min( min_t_over_n_lg_n, t_over_n_lg_n ) max_t_over_n_lg_n = max( max_t_over_n_lg_n, t_over_n_lg_n ) for n in ns[ 1: ]: if not n in result: continue t = result[ n ][ "time" ] x = scalex( log( n, xbase ), min_log_n, max_log_n ) y = scaley( y_fn( name, n, result[n] ), miny, maxy ) c.line( prevx, prevy, x, y ) t_over_n_lg_n = t / float(n * log( n, 2 )) min_t_over_n_lg_n = min( min_t_over_n_lg_n, t_over_n_lg_n ) max_t_over_n_lg_n = max( max_t_over_n_lg_n, t_over_n_lg_n ) prevx, prevy = x, y # Draw dashed lines with constant t/n lg n. # This was useful when the y axis was t/lg n instead of t/n lg n. # c.saveState() # c.setDash( 4, 4 ) # c.setStrokeColorRGB( 0, 0, 0 ) # c.setLineWidth( .25 * point ) # for i in xrange( 5 ): # t_over_n_lg_n = ( min_t_over_n_lg_n * .9 * (4-i) # + max_t_over_n_lg_n * 1.05 * i ) * .25 # lefty = scaley( t_over_n_lg_n * min_lg_n, miny, maxy ) # righty = scaley( t_over_n_lg_n * max_lg_n, miny, maxy ) # c.line( left_edge, lefty, right_edge, righty ) # c.restoreState() c.showPage() c.save() system( "open " + output_file ) ## printexp() -- Print a string, centered on (x,y), with levels ^ of ^ superscripts. # ("exp" was originally for exponentials.) # def printexp( c, x, y, name, fontname, fontsize ): width = c.stringWidth( name.replace('^',''), fontname, fontsize ) pieces = name.split( '^' ) jump = fontsize * .5 y -= ( len(pieces) - 1 ) * jump * .5 x -= width / 2 for piece in pieces: c.drawString( x, y, piece ) x += c.stringWidth( piece, fontname, fontsize ) y += jump def all_ns( results ): return sort_map( flatten_results( results ), lambda name, n, stuff: n ) def flatten_results( results ): for name, result in results.iteritems(): for n, stuff in result.iteritems(): yield name, n, stuff def sort_map( it, fn ): values = [ fn( name, n, stuff ) for name, n, stuff in it ] values.sort() return values def all_ratios( results ): return sort_map( flatten_results( results ), lambda( name, n, stuff ): stuff["time"]/float(n) ) def print_results( longnames, results ): column = 79 / ( len(longnames) + 1 ) fmt = "%" + str(column-1) + "s" ffmt = "%" + str(column-1) + ".2f" print fmt % "n", for name in longnames: print fmt % name, print ns = all_ns( results ) for n in ns: print ffmt % log( n, 2 ), for name in longnames: time = results[ name ][ n ][ "time" ] print ffmt % log( time, 2 ), print longnames, results = read_program_outputs( argv[1:] ) # print_results( longnames, results ) plot_results( longnames, results )