автордың кітабынан сөз тіркестері  Алгоритмы. С примерами на Python

Джордж Хайнеман

http://github.com/heineman/LearningAlgorithms.

программах используются три свободно распространяемые библиотеки 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 — большой сборник эффективных алгоритмов для работы с графами,

Пример 1.6. Поиск двух наибольших значений A с помощью турнирного дерева

def tournament_two(A):

N = len(A)

winner = [None] * (N-1) ❶

loser = [None] * (N-1)

prior = [-1] * (N-1) ❷

idx = 0

for i in range(0, N, 2): ❸

if A[i] < A[i+1]:

winner[idx] = A[i+1]

loser[idx] = A[i]

else:

winner[idx] = A[i]

loser[idx] = A[i+1]

idx += 1

m = 0 ❹

while idx < N-1:

if winner[m] < winner[m+1]: ❺

winner[idx] = winner[m+1]

loser[idx] = winner[m]

prior[idx] = m+1

else:

winner[idx] = winner[m]

loser[idx] = winner[m+1]

prior[idx] = m

m += 2 ❻

idx += 1

largest = winner[m]

second = loser[m] ❼

m = prior[m]

while m >= 0:

if second < loser[m]: ❽

second = loser[m]

m = prior[m]

return (largest, second)

❶ В этих списках мы станем хранить индексы победителей и проигравших в игре, которых будет N – 1.

❷ Когда значение в позиции m проходит на очередной тур, в prior[m] записывается позиция этого значения в предыдущем туре. Для первого тура такой информации нет, поэтому в начале этого списка хранится -1.

❸ Первый тур состоит из N / 2 игр, то есть требует N / 2 сравнений на «меньше» в парах «победитель — проигравший».

❹ Игры победителей во всех следующих турах с записью позиции выигравшего в каждой игре.

❺ Еще N / 2 – 1 сравнение.

❻ Увеличим m на 2 — это игра двух следующих победителей. Когда idx достигнет N – 1, в winner[m] окажется наибольшее значение.

❼ Первый кандидат на второе место; надо еще проверить остальных проигравших чемпиону, возможно, они больше подходят для второго места.

❽ Не больше log2(N) – 1 дополнительное сравнение на «меньше».

def sorting_two(A):

return tuple(sorted(A, reverse=True)[:2]) ❶

def double_two(A):

my_max = max(A) ❷

copy = list(A)

copy.remove(my_max) ❸

return (my_max, max(copy)) ❹

def mutable_two(A):

idx = max(range(len(A)), key=A.__getitem__) ❺

my_max = A[idx] ❻

del A[idx]

second = max(A) ❼

A.insert(idx, my_max) ❽

return (my_max, second)

❶ Создать из A новый отсортированный список и вернуть первые два его элемента.

❷ Использовать встроенную функцию max() и найти максимум.

❸ Создать дубликат списка A и удалить из него этот максимум.

❹ Вернуть кортеж из сходного максимума и максимума в урезанной копии.

❺ Трюк Python, который позволяет найти индекс наибольшего значения, а не само наибольшее значение.

❻ Запомнить максимум my_max и удалить его из A.

❼ Найти еще один max() в усеченном списке.

❽ Вставить максимальное значение my_max на место.

Трюк ❺ работает так. Как и все операции с объектами в Python, операция индексирования (то есть квадратные скобки) имеет эквивалентный ей метод — .__getitem__(). Параметр key=функция в функции max(последовательность) означает, что максимум будет вычисляться не в исходной последовательности элемент0, элемент1…, а в последовательности функция(элемент0), функция(элемент1)…, а в качестве результата функция вернет некоторый элементm. В нашем примере элементы — это 0, 1… m… len(A)-1, то есть индексы всех объектов в A, а максимум вычисляется среди A.__getitiem__(0), A.__getitiem__(1)…, то есть среди A[0], A[1]…, а возвращается при этом индекс m.

def largest_two(A):

my_max,second = A[:2] ❶

if my_max < second:

my_max,second = second,my_max

for idx in range(2, len(A)):

if my_max < A[idx]: ❷

my_max,second = A[idx],my_max

elif second < A[idx]: ❸

second = A[idx]

return (my_max, second)

Встроенные же функции, например max(), — часть самого интерпретатора: пока такая функция обрабатывает объект, не нужно ничего дополнительно интерпретировать. Поэтому встроенные функции всегда быстрее тех, что написаны на Python8. Следует заметить, что во всех случаях реализация одного и того же алгоритма должна приводить к одинаковому изменению быстродействия при изменении размера данных — например, при удвоении N время работы и largest(), и max() тоже удваивается как в наихудшем, так и в наилучшем случае.

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

Python-выражение range(x,y) вычисляет последовательность целых чисел от x до y (не включая y). Если 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.

Эта реализация алгоритма содержит ошибку: предполагается, что в A есть хотя бы одно неотрицательное число. Вызов flawed([–5,–3,–11]) вернет 0, что неправильно. Часто вместо нуля пытаются использовать «наименьшее возможное число», примерно так: my_max = float('-inf'). Этот подход также небезупречен, потому что для пустого списка A = [] он вернет -inf, которого там не было. Недочет надо исправить

def flawed(A):

my_max = 0 ❶

for v in A: ❷

if my_max < v:

my_max = v ❸

return my_max