http://github.com/heineman/LearningAlgorithms.
5 Ұнайды
программах используются три свободно распространяемые библиотеки Python, которые необходимо скачать и установить самостоятельно2:
• NumPy (https://www.numpy.org) версии 1.19.5;
• SciPy (https://www.scipy.org) версии 1.6.0;
• NetworkX (https://networkx.org) версии 2.5.
NumPy и SciPy — одни из самых популярных свободных библиотек с огромным сообществом. Я их использую, чтобы измерить фактическую производительность алгоритмов. NetworkX — большой сборник эффективных алгоритмов для работы с графами,
2 Ұнайды
Встроенные же функции, например max(), — часть самого интерпретатора: пока такая функция обрабатывает объект, не нужно ничего дополнительно интерпретировать. Поэтому встроенные функции всегда быстрее тех, что написаны на Python8. Следует заметить, что во всех случаях реализация одного и того же алгоритма должна приводить к одинаковому изменению быстродействия при изменении размера данных — например, при удвоении N время работы и largest(), и max() тоже удваивается как в наихудшем, так и в наилучшем случае.
1 Ұнайды
Пример 1.3. Другой способ найти наибольшее значение в списке A
def alternate(A):
for v in A: ❶
for x in A:
if v < x: ❷
break
else:
return v ❸
return None ❹
❶ Для каждого v из A рассмотрим все x из A и сравним их.
❷ Если v меньше какого-то x, можно больше не сравнивать: это не максимум.
❸ Если мы просмотрели все x, так ни разу и не выполнив break, значит, v — это максимум и его можно уже возвращать.
❹ До этого места выполнение дойдет только при пустом A. В таком случае вернем специальный объект Python — None.
Пример 1.2. Правильная функция, которая находит наибольшее значение в списке
def largest(A):
my_max = A[0] ❶
for idx in range(1, len(A)): ❷
if my_max < A[idx]:
my_max = A[idx] ❸
return my_max
❶ Сделаем my_max равным начальному элементу списка (он доступен по индексу 0).
❷ Переменная idx принимает целочисленные значения от 1 до len(A)-1 включительно, не достигая len(A).
❸ Если в A по индексу idx стоит большее значение, обновить my_max.
Если x больше, чем y, можно задать убывающую последовательность от x до y, не включая y, с помощью range(x,y,–1). Если сделать список из range(1,7), list(range(1,7)) даст [1,2,3,4,5,6]. Соответственно, list(range(5,0,–1)) даст [5,4,3,2,1], а если дополнительно задать шаг — приращение последовательности — list(range(1,10,2)) даст [1,3,5,7,9]: разность между соседними элементами будет равна 2.
работает flawed()
Эта реализация алгоритма содержит ошибку: предполагается, что в A есть хотя бы одно неотрицательное число. Вызов flawed([–5,–3,–11]) вернет 0, что неправильно. Часто вместо нуля пытаются использовать «наименьшее возможное число», примерно так: my_max = float('-inf'). Этот подход также небезупречен, потому что для пустого списка A = [] он вернет -inf, которого там не было. Недочет надо исправить.
NumPy (https://www.numpy.org) версии 1.19.5;
• SciPy (https://www.scipy.org) версии 1.6.0;
• NetworkX (https://networkx.org) версии 2.5.
NumPy и SciPy — одни из самых популярных свободных библиотек с огромным сообществом. Я их использую, чтобы измерить фактическую производительность алгоритмов. NetworkX — большой сборник эффективных алгоритмов для работы с графами, он нам понадобится в главе 7; там же есть удобная готовая структура данных, реализующая граф. Средства этих библиотек позволят не изобретать очередное колесо, если в этом нет нужды. Если они не установлены, не беда: примеры написаны так, что смогут работать и без них, нужные функции также есть в репозитории.
Python — интерпретируемый язык программирования: написанная программа транслируется в промежуточное представление, называемое байт-кодом, а при выполнении программы запускается интерпретатор Python, который читает, интерпретирует и выполняет инструкции байт-кода. Встроенные же функции, например max(), — часть самого интерпретатора: пока такая функция обрабатывает объект, не нужно ничего дополнительно интерпретировать. Поэтому встроенные функции всегда быстрее тех, что написаны на Python8. Следует заметить, что во всех случаях реализация одного и того же алгоритма должна приводить к одинаковому изменению быстродействия при изменении размера данных — например, при удвоении N время работы и largest(), и max() тоже удваивается как в наихудшем, так и в наилучшем случае.
В книге будут появляться таблицы с подсчетом количества выполненных действий и затраченного времени наподобие табл. 1.2, где измерялось количество сравнений >. Строки таких таблиц соответствуют различным объемам входных данных. Если просмотреть таблицу сверху вниз, становится понятно, как растут показания в каждом столбце по мере удвоения размера данных.
Подсчет количества сравнений показывает, как работают функции largest() и alternate(). При удвоении N количество сравнений в largest() удваивается, а в alternate() — увеличивается вчетверо. Это поведение вполне стабильно, и несложно предсказать, как оба алгоритма поведут себя на данных большего размера. На рис. 1.5 показано, что количество сравнений в функции alternate() (отмечено по оси Y с левой стороны) довольно точно соответствует ее производительности (затраченное время отмечено по оси Y с правой стороны).