Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- from random import randint
- from time import time
- import matplotlib.pyplot as plt
- def stupid_search(arr, target):
- ...
- def binary_search(arr, target):
- ...
- VALUE_MAX = 100000
- SIZE_MAX = 1000
- SIZE_STEP = 50
- MEASURE_ITERS = 3000
- def generate_input(size):
- ...
- def test_correctness():
- print('\n>>> Проверка корректности\n')
- for size in range(1, 10 + 1):
- print('Размер массива: {}'.format(size))
- arr = generate_input(size)
- for i in range(MEASURE_ITERS):
- target = randint(1, VALUE_MAX)
- if stupid_search(arr, target) != binary_search(arr, target):
- print(' Неправильный ответ при arr = {}, target = {}'.format(arr, target))
- return False
- return True
- def measure_time(func, arr, target):
- start = time()
- func(arr, target)
- return time() - start
- MSEC_PER_SEC = 1000
- def test_performance():
- print('\n>>> Тестирование производительности\n')
- xs = []
- ys_stupid = []
- ys_smart = []
- for size in range(SIZE_STEP, SIZE_MAX + SIZE_STEP, SIZE_STEP):
- print('Размер массива: {}'.format(size))
- arr = generate_input(size)
- elapsed_stupid = 0
- elapsed_smart = 0
- for i in range(MEASURE_ITERS):
- target = randint(1, VALUE_MAX)
- elapsed_stupid += measure_time(stupid_search, arr, target)
- elapsed_smart += measure_time(binary_search, arr, target)
- y_stupid = elapsed_stupid / MEASURE_ITERS * MSEC_PER_SEC
- y_smart = elapsed_smart / MEASURE_ITERS * MSEC_PER_SEC
- print(' Глупый поиск: {:.3f} мс'.format(y_stupid))
- print(' Двоичный поиск: {:.3f} мс'.format(y_smart))
- xs.append(size)
- ys_stupid.append(y_stupid)
- ys_smart.append(y_smart)
- plt.rc('font', family='Verdana', weight='normal')
- plt.plot(xs, ys_stupid, label='Глупый поиск')
- plt.plot(xs, ys_smart, label='Двоичный поиск')
- plt.legend()
- plt.xlabel('Размер массива')
- plt.ylabel('Время (миллисекунды)')
- plt.show()
- if test_correctness():
- test_performance()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement