0001 from random import randrange 0002 from timeit import Timer 0003 from sys import stdout 0004 0005 ############################################################################### 0006 def show(L): print sum(L), '/', len(L), ':', L; return 0007 0008 ############################################################################### 0009 def reverse_1(L): # reverse a list in manner of CALL-BY-RANK 0010 lo, hi = 0, len(L)-1 # starting from the first and the last element 0011 while lo < hi: # for each pair of symmetric elements 0012 L[lo], L[hi] = L[hi], L[lo] # swap them and 0013 lo, hi = lo+1, hi-1 # consider the next pair 0014 return L 0015 0016 def reverse_1_test(n): reverse_1([ randrange(n) for i in range(n) ]); return 0017 0018 ############################################################################### 0019 def reverse_2(L): # reverse a list in manner of CALL-BY-POSITION 0020 for i in range( len(L) ): # for each i in [0, n) 0021 L.insert(i, L.pop()) # move the last element to position i 0022 return L 0023 0024 def reverse_2_test(n): reverse_2([ randrange(n) for i in range(n) ]); return 0025 0026 ############################################################################### 0027 if __name__ == '__main__': 0028 n = 13 0029 L = [ randrange(n) for i in range(n) ]; show(L) # create a random list of size n 0030 L = reverse_1(L); show(L) # reverse it using algorithm #1 0031 L = reverse_2(L); show(L) # reverse it using algorithm #2 0032 L.sort(); show(L) # and sort it for verification 0033 print('\n\t i n T1 T1/n T2 T2/n/n\n' + 64*'=') 0034 for i in range(18): # for each i in [0, 18) (it slows down on typical PC for i more than 18) 0035 n = 2**i; print('\t2^%2d = %6d :' %(i, n)), # test the two algorithms with a list of size n = 2^i 0036 t = 1000*Timer('__main__.reverse_1_test(__main__.n)', 'import __main__').timeit(1); print('%8.1f %10.4f' %(t, t/n)), 0037 t = 1000*Timer('__main__.reverse_2_test(__main__.n)', 'import __main__').timeit(1); print('%8.1f %10.4f' %(t, t/n/n*1000)) 0038 stdout.flush()