Алгоритмы неформально. Инструкция для начинающих питонистов - [28]
Подсчет шагов
Вместо затрат времени в секундах более надежной метрикой быстродействия алгоритма оказывается количество шагов, необходимых для выполнения алгоритма. Количество шагов в алгоритме — характеристика самого алгоритма, не зависит от архитектуры оборудования, а иногда даже от языка программирования. В листинге 4.3 приведен код сортировки методом вставки из листингов 4.1 и 4.2 с добавлением нескольких строк с командой stepcounter+=1. Счетчик шагов увеличивается каждый раз, когда мы берем со старой полки новую папку для вставки, при каждом сравнении этой папки с другой папкой на новой полке и при каждой вставке папки на новой полке.
Листинг 4.3. Код сортировки методом вставки со счетчиком шагов
def insert_cabinet(cabinet,to_insert):
check_location = len(cabinet) - 1
insert_location = 0
global stepcounter
while(check_location >= 0):
stepcounter += 1
if to_insert > cabinet[check_location]:
insert_location = check_location + 1
check_location = - 1
check_location = check_location - 1
stepcounter += 1
cabinet.insert(insert_location,to_insert)
return(cabinet)
def insertion_sort(cabinet):
newcabinet = []
global stepcounter
while len(cabinet) > 0:
stepcounter += 1
to_insert = cabinet.pop(0)
newcabinet = insert_cabinet(newcabinet,to_insert)
return(newcabinet)
cabinet = [8,4,6,1,2,5,3,7]
stepcounter = 0
sortedcabinet = insertion_sort(cabinet)
print(stepcounter)
В данном случае при выполнении этого кода мы видим, что для реализации сортировки методом вставки для списка длиной 8 выполняются 36 шагов. Попробуем выполнить сортировку методом вставки для списков другой длины и посмотрим, сколько шагов для этого потребуется.
Для этого напишем функцию, которая подсчитывает шаги, необходимые для сортировки методом вставки для несортированных списков разной длины. Вместо того чтобы записывать каждый несортированный список вручную, мы воспользуемся простым списковым включением в Python для генерирования случайного списка любой заданной длины. Для упрощения генерирования случайных списков в Python можно импортировать модуль Python random. Пример создания случайного несортированного списка длины 10:
import random
size_of_cabinet = 10
cabinet = [int(1000 * random.random()) for i in range(size_of_cabinet)]
Наша функция просто генерирует список заданной длины, выполняет код сортировки методом вставки и возвращает итоговое найденное значение для stepcounter.
def check_steps(size_of_cabinet):
cabinet = [int(1000 * random.random()) for i in range(size_of_cabinet)]
global stepcounter
stepcounter = 0
sortedcabinet = insertion_sort(cabinet)
return(stepcounter)
Создадим список всех чисел от 1 до 100 и проверим, сколько шагов потребуется для сортировки списка каждой длины:
random.seed(5040)
xs = list(range(1,100))
ys = [check_steps(x) for x in xs]
print(ys)
В этом коде сначала вызывается функция random.seed(). Этот вызов не является необходимым, но гарантирует, что при выполнении того же кода вы получите такие же результаты. Как видите, мы определяем набор значений для x, хранящийся в xs, и набор значений для y, хранящийся в ys. Значения x просто представляют собой числа от 1 до 100, а значения y — количества шагов, необходимые для сортировки случайно сгенерированных списков каждого размера, соответствующего x. Взглянув на вывод, вы увидите, сколько шагов потребуется сортировке методом вставки для случайно сгенерированных списков длины 1, 2, 3... 99. График зависимости между длиной списка и количеством шагов сортировки строится фрагментом, приведенным ниже. Для построения графика импортируется пакет matplotlib.pyplot.
import matplotlib.pyplot as plt
plt.plot(xs,ys)
plt.title('Steps Required for Insertion Sort for Random Cabinets')
plt.xlabel('Number of Files in Random Cabinet')
plt.ylabel('Steps Required to Sort Cabinet by Insertion Sort')
plt.show()
Результат показан на рис. 4.1. Как видите, выходная кривая получается неровной — иногда более длинный список сортируется за меньшее количество шагов, чем короткий. Причина в том, что все списки генерируются случайным образом. Время от времени код генерирования случайных списков создает список, который
Рис. 4.1. Количество шагов при сортировке методом вставки
слишком легко упорядочивается и быстро обрабатывается сортировкой методом вставки (поскольку он уже частично отсортирован), а иногда создаются списки, которые труднее обработать быстро — все зависит исключительно от случайности. По той же причине может оказаться, что вывод на вашем компьютере отличается от приведенного здесь, если вы не инициализировали генератор случайных чисел тем же значением, но в целом форма графика останется той же.
Сравнение с известными функциями
Забудем об искусственной неровности рис. 4.1, проанализируем общую форму кривой и попробуем проанализировать скорость ее роста. На интервале между x = 1 и x = 10 количество шагов растет довольно медленно. После этого кривая постепенно набирает крутизну и становится более неровной. Между x = 90 и x = 100 скорость роста становится очень заметной.
Можно сказать, что с ростом длины списка кривая постепенно становится более крутой, но и это описание не настолько точное, как нам хотелось бы. Иногда нарастающую скорость роста называют экспоненциальной. Имеем ли мы дело с экспоненциальным ростом в данном случае? Строго говоря, существует
