Advertisement
hxrussia

Задание для 7-го класса ОЗШ, 28.03.2017

Mar 28th, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.38 KB | None | 0 0
  1. import sys
  2. from random import randint
  3. from time import time
  4.  
  5. import matplotlib.pyplot as plt
  6.  
  7.  
  8. def stupid_search(arr, target):
  9.     ...
  10.    
  11.  
  12. def binary_search(arr, target):
  13.     ...
  14.  
  15.  
  16. VALUE_MAX = 100000
  17. SIZE_MAX = 1000
  18. SIZE_STEP = 50
  19. MEASURE_ITERS = 3000
  20.  
  21.  
  22. def generate_input(size):
  23.     ...
  24.  
  25.  
  26. def test_correctness():
  27.     print('\n>>> Проверка корректности\n')
  28.    
  29.     for size in range(1, 10 + 1):
  30.         print('Размер массива: {}'.format(size))
  31.         arr = generate_input(size)
  32.        
  33.         for i in range(MEASURE_ITERS):
  34.             target = randint(1, VALUE_MAX)
  35.            
  36.             if stupid_search(arr, target) != binary_search(arr, target):
  37.                 print('  Неправильный ответ при arr = {}, target = {}'.format(arr, target))
  38.                 return False
  39.     return True
  40.  
  41.  
  42. def measure_time(func, arr, target):
  43.     start = time()
  44.     func(arr, target)
  45.     return time() - start
  46.  
  47.  
  48. MSEC_PER_SEC = 1000
  49.  
  50.  
  51. def test_performance():
  52.     print('\n>>> Тестирование производительности\n')
  53.    
  54.     xs = []
  55.     ys_stupid = []
  56.     ys_smart = []
  57.     for size in range(SIZE_STEP, SIZE_MAX + SIZE_STEP, SIZE_STEP):
  58.         print('Размер массива: {}'.format(size))
  59.         arr = generate_input(size)
  60.        
  61.         elapsed_stupid = 0
  62.         elapsed_smart = 0
  63.         for i in range(MEASURE_ITERS):
  64.             target = randint(1, VALUE_MAX)
  65.            
  66.             elapsed_stupid += measure_time(stupid_search, arr, target)
  67.             elapsed_smart += measure_time(binary_search, arr, target)
  68.         y_stupid = elapsed_stupid / MEASURE_ITERS * MSEC_PER_SEC
  69.         y_smart = elapsed_smart / MEASURE_ITERS * MSEC_PER_SEC
  70.         print('  Глупый поиск: {:.3f} мс'.format(y_stupid))
  71.         print('  Двоичный поиск: {:.3f} мс'.format(y_smart))
  72.        
  73.         xs.append(size)
  74.         ys_stupid.append(y_stupid)
  75.         ys_smart.append(y_smart)
  76.          
  77.     plt.rc('font', family='Verdana', weight='normal')
  78.     plt.plot(xs, ys_stupid, label='Глупый поиск')
  79.     plt.plot(xs, ys_smart, label='Двоичный поиск')
  80.     plt.legend()
  81.     plt.xlabel('Размер массива')
  82.     plt.ylabel('Время (миллисекунды)')
  83.     plt.show()
  84.  
  85.  
  86. if test_correctness():
  87.     test_performance()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement