Алгоритмы неформально. Инструкция для начинающих питонистов - [29]
import math
import numpy as np
random.seed(5040)
xs = list(range(1,100))
ys = [check_steps(x) for x in xs]
ys_exp = [math.exp(x) for x in xs]
plt.plot(xs,ys)
axes = plt.gca()
axes.set_ylim([np.min(ys),np.max(ys) + 140])
plt.plot(xs,ys_exp)
plt.title('Comparing Insertion Sort to the Exponential Function')
plt.xlabel('Number of Files in Random Cabinet')
plt.ylabel('Steps Required to Sort Cabinet')
plt.show()
Как и прежде, мы определяем xs как список всех чисел от 1 до 100, а ys — как количество шагов, необходимое для сортировки случайно сгенерированных списков размера, соответствующего каждому x. Вдобавок определяется переменная ys_exp, которая содержит значение ex для каждого из значений, хранящихся в xs. Затем значения ys и ys_exp наносятся на один график. В результате мы видим, как количество шагов, требуемых для сортировки списка, соотносится с настоящим экспоненциальным ростом.
При выполнении этого кода будет получен график, как на рис. 4.2.
Рис. 4.2. Сравнение количества шагов при сортировке методом вставки с экспоненциальной функцией
Мы видим, что настоящая кривая экспоненциального роста устремляется к бесконечности в левой части графика. Хотя кривая количества шагов сортировки методом вставки растет в нарастающем темпе, ускорение даже близко не стоит с настоящим экспоненциальным ростом. Если нанести на график другие функции, скорость роста которых тоже может называться экспоненциальной, 2x или 10 x, то вы увидите, что все эти функции растут намного быстрее нашей кривой количества шагов. Если кривая количества шагов сортировки методом вставки отстает от экспоненциального роста, то какой скорости роста соответствует? Попробуем нанести на тот же график еще несколько функций. В следующем фрагменте вместе с функцией количества шагов сортировки методом вставки строятся графики функций y = x, y = x1,5, y = x 2 и y = x 3:
random.seed(5040)
xs = list(range(1,100))
ys = [check_steps(x) for x in xs]
xs_exp = [math.exp(x) for x in xs]
xs_squared = [x**2 for x in xs]
xs_threehalves = [x**1.5 for x in xs]
xs_cubed = [x**3 for x in xs]
plt.plot(xs,ys)
axes = plt.gca()
axes.set_ylim([np.min(ys),np.max(ys) + 140])
plt.plot(xs,xs_exp)
plt.plot(xs,xs)
plt.plot(xs,xs_squared)
plt.plot(xs,xs_cubed)
plt.plot(xs,xs_threehalves)
plt.title('Comparing Insertion Sort to Other Growth Rates')
plt.xlabel('Number of Files in Random Cabinet')
plt.ylabel('Steps Required to Sort Cabinet')
plt.show()
Результат показан на рис. 4.3.
Рис. 4.3. Сравнение количества шагов сортировки методом вставки с другими скоростями роста
На рис. 4.3 представлены три скорости роста помимо зазубренной кривой, характеризующей количество шагов, необходимых для сортировки методом вставки. Как видно из графика, экспоненциальная кривая растет быстрее всех, а следующая за ней кубическая кривая почти не видна на графике, поскольку тоже растет очень быстро. Функция y = x растет очень медленно по сравнению с другими; она видна в самой нижней части графика.
К кривой количества шагов ближе всего функции y = x 2 и y = x1,5. Пока не очевидно, какая из них ближе к нашей кривой, так что мы не можем что-либо с уверенностью утверждать относительно скорости роста. Но после создания графика можно выдавать утверждения наподобие «сортировка списка из n элементов требует количества шагов приблизительно в диапазоне от n1,5 до n2». Это более точная и обоснованная формулировка, чем «со скоростью взмаха комариного крыла» или «около 0,002 секунды на моем конкретном ноутбуке этим утром».
Повышение теоретической точности
Чтобы добиться еще большей точности, следует тщательно проанализировать количество шагов, необходимых для сортировки методом вставки. Еще раз представим, что у вас имеется новый несортированный список из n элементов. В табл. 4.1 подсчитываются все шаги сортировки методом вставки.
Таблица 4.1. Подсчет шагов при сортировке методом вставки
Описание действий
Количество шагов, необходимых для снятия папки со старой полки
Максимальное количество шагов, необходимых для сравнения с другими папками
Количество шагов, необходимых для вставки папки на новую полку
Взять первую папку со старой полки и поставить ее на (пустую) новую полку
1
0 (нет папок для сравнения)
1
Взять вторую папку со старой полки и поставить ее на новую полку (на которой сейчас стоит одна папка)
1
1 (есть одна папка для сравнения, необходимо выполнить сравнение с ней)
1
Взять третью папку со старой полки и поставить ее на новую полку (на которой сейчас стоят две папки)
1
2 или менее (есть две папки для сравнения, необходимо выполнить сравнение от 1 до всех папок)
1
Взять четвертую папку со старой полки и поставить ее на новую полку (на которой сейчас стоят три папки)
