О курсе

Структура курса

Этот курс построен в соответствии с рабочей программой спецкурса по программированию в рамках проекта «IT-классы в московских школах».

Он состоит из трёх основных разделов:

• Язык Python
• Алгоритмы и структуры данных
• Практика программирования

Материалы выкладываются параллельно во все три раздела по мере их изучения на уроках. Некоторая часть материалов является дополнением к рассмотренному на уроках: обычно к этой категории относятся концы соответствующих подразделов.

Рекомендуется взглянуть на список полезных ссылок.

Полезные ссылки

• inf2086.ru — этот сайт
• informatics.msk.ru — довольно крупная база задач по программированию (в основном — околоспортивному)
• olympiads.ru — олимпиады по программированию
• python.org — официальный сайт языка Python
• repl.it — онлайн-среда разработки
• ideone.com — ещё одна онлайн-среда разработки
• Wikipedia — википедия (без комментариев)

Алгоритмы и структуры данных

Асимптотическая сложность

Сортировка пузырьком

Рассмотрим весьма банальную задачу сортировки массива данных: на вход дан массив данных, которые можно друг с другом сравнивать по величине; требуется построить массив, состоящий из тех же данных, расположенных в порядке неубывания (это означает, что каждый следующий элемент не меньше предыдущего).

Один из самых широкоизвестных алгоритмов сортировки — сортировка «пузырьком» (англ. bubble sort).

В предположении, что доступ к массиву осуществляется посредством переменной array, этот алгоритм может быть записан на языке Python следующим образом:

N = len(array)
for _ in range(N-1):
  for i in range(N-1):
    if array[i] > array[i+1]:
      array[i], array[i+1] = array[i+1], array[i]

Почему он работает? Это легко понять, если заметить, что один проход внутреннего цикла ставит самый большой элемент в конец массива, сводя задачу к задаче сортировки массива на единицу меньшей длины.

Сложность сортировки пузырьком

В алгоритме сортировки пузырьком фигурируют две различных нетривиальных операции: условное ветвление по результатам сравнения и обмен двух элементов массива местами.

Будем считать, что каждая из этих операций занимает единицу времени, а всё остальное (например, обслуживание счётчиков циклов) бесплатно. Тогда для массива длины \(N\) алгоритм занимает

\[ 2(N-1)^2 = 2N^2 - 4N + 1 \]

единиц времени. Заметим, что, начиная с \(N=4\), выполнено неравенство

\[ 2(N-1)^2 \geqslant N^2 \]

Также всегда выполнено неравенство

\[ 2(N-1)^2 \leqslant 2N^2 \]

То есть, начиная с некоторого \(N\), время работы алгоритма заключено между значениями выражений, пропорциональных \(N^2\). В такой ситуации говорят, что \(N^2\) является асимптотической сложностью рассматриваемого алгоритма.

В общем случае, если \( T(N) \) — (максимально возможное) время работы алгоритма на наборе данных размера \( N \), а \(f\) — некоторая функция натурального аргумента, то говорят, что:

• алгоритм обладает верхней асимптотической сложностью \( f(N) \), если существует такое положительное число \( \alpha \), что, начиная с некоторого \(N\), выполнено неравенство \( T(N) \leqslant \alpha f(N) \)
• алгоритм обладает нижней асимптотической сложностью \( f(N) \), если существует такое положительное число \( \alpha \), что, начиная с некоторого \(N\), выполнено неравенство \( T(N) \geqslant \alpha f(N) \)
• алгоритм обладает асимптотической сложностью \( f(N) \), если он обладает нижней и верхней асимптотическими сложностями \( f(N) \)

Например, про сортировку пузырьком можно сказать, что:

• она обладает верхней асимптотической сложностью \( N^2 \)
• она обладает верхней асимптотической сложностью \( 1000N^2 \)
• она обладает верхней асимптотической сложностью \( N^{1000} \)
• она обладает нижней асимптотической сложностью \( N^2 \)
• она обладает нижней асимптотической сложностью \( 1000N^2 \)
• она обладает нижней асимптотической сложностью \( N \)
• она обладает асимптотической сложностью \( N^2 \)

Часто можно встретить обозначение \(O( f(N) )\) для множества алгоритмов, обладающих асимптотической сложностью \( f(N) \).

Иногда буква \(O\) относится только к верхней асимптотической сложности: в таких ситуациях для нижней асимптотической сложности используется буква \( \Omega \) (омега большая), а для (просто) асимптотической сложности — буква \( \Theta \) (тета большая).

Нижняя оценка сложности алгоритма сортировки

Какая вообще может быть асимптотическая сложность алгоритма сортировки, подобного сортировке пузырьком?

Рассмотрим алгоритм, использующий ветвления (с произвольными условиями) и обмены (или любые другие операции над массивом), зависящие только от значений условий ветвлений (но не от информации, хранящейся в массиве). В таком алгоритме каждый входной массив однозначно задаёт последовательность результатов условий ветвлений, которая, в свою очередь, однозначно задаёт перестановку входного массива, упорядочивающую его.

Проиллюстрируем это на примере пузырька размера 3, в котором все циклы полностью раскрыты, а последнее сравнение вообще убрано (оно ни на что не влияет):

if a[0] > a[1]:
  a[0], a[1] = a[1], a[0]
  if a[1] > a[2]:
    a[0], a[1] = a[1], a[0]
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]
  else:
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]
else:
  if a[1] > a[2]:
    a[0], a[1] = a[1], a[0]
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]
  else:
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]

В этом алгоритме массив [1,2,3] приводит к последовательности результатов сравнений False, False, False. А, например, массив [3,2,1] даёт последовательность True, True, True.

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

Если \(M\) — длина наидлиннейшей такой последовательности, то всего последовательностей не больше \(2^M\). А перестановок массива длины \(N\) ровно \(N!\). Поэтому для любого алгоритма сортировки

\[ 2^M \geqslant N! \]

Продолжим это неравенство, оценив половину сомножителей \(N!\) снизу числом \(1\), а другую половину — числом \(N/2\):

\[ 2^M \geqslant N! \geqslant 1^{N/2}\cdot (N/2)^{N/2} \]

Для нечётного \(N\) это неравенство тоже выполнено (оставляем это в качестве простого упражнения). Теперь применим к неравенству двоичный логарифм:

\[ M \geqslant (N/2) ( \log_2 N - 1 ) \]

Осталось заметить, что начиная с \(N=4\)

\[ M \geqslant (N/2) ( \log_2 N - 1 ) \geqslant (1/4) N \log_2 N \]

Мы доказали, что любой алгоритм сортировки, удовлетворяющий оговоренным выше условиям, обладает (по количеству ветвлений) нижней асимптотической сложностью \(N \log_2 N\).

Контрпример

Покажем, почему требование однозначной зависимости перестановки элементов массива от последовательности значений условий ветвлений существенно.

Рассмотрим алгоритм

N = len(array)
for i in range(N):
  array[ array[i] - 1 ] = array[i]

Этот алгоритм отлично сортирует любой массив с различными числами от \(1\) до \(N\), но при этом в нём ровно одна возможная последовательность значений условий ветвлений: пустая. Он обладает асимптотической сложностью \(N\).

Квадратичные алгоритмы сортировки

На практике сортировка «пузырьком» почти не используется. Причина проста: есть существенно более эффективные алгоритмы сортировки с той же асимптотической сложностью и примерно такой же сложностью реализации.

Ниже мы рассмотрим две альтернативы пузырьку. Обе эти альтернативы разбивают массив на две части: до некоторого элемента (до — по номеру) массив отсортирован, после него — ещё нет. Шаг этих алгоритмов удлиняет отсортированный кусок на 1 элемент.

То есть устроены они так (в предположении, что переменная array связана с сортируемым массивом):

N = len(array)
for sorted_length in range(N):
  ## здесь происходят перестановки элементов, приводящие к 
  ## увеличению длины упорядоченного куска на 1

Сортировка поиском минимума

Для удлинения упорядоченной части на 1 мы ищем наименьший элемент неупорядоченной части и меняем его местами с начальным элементом неупорядоченной части:

N = len(array)
for sorted_length in range(N):
  _, min_index = min([(x, i + sorted_length) 
                      for i,x in enumerate(array[sorted_length:])])
  
  array[min_index], array[sorted_length] = (
    array[sorted_length], array[min_index]
  )

Асимптотическую сложность этого алгоритма нетрудно вычислить. Поиск минимального элемента (перебором) на каждом шагу алгоритма занимает не более \(N\) операций вида «посмотреть на элемент и что-нибудь запомнить», но и не менее \(N-sorted_length\) (в том случае, когда минимальный элемент — последний, на который мы посмотрели в процессе перебора).

Поэтому время работы алгоритма \(T(N)\) удовлетворяет неравенствам

\[ N\cdot N \geqslant T(n) \geqslant N + (N-1) + (N-2) + \ldots + 1 = \frac{N(N+1)}{2} \]

Осталось заметить, что \(N(N+1)/2 \geqslant \frac{1}{2} N^2\). Поэтому рассматриваемый нами алгоритм относится к классу квадратичных (т.е. асимптотической сложности \(N^2\)).

Сортировка вставками

Для удлинения упорядоченной части на 1 мы берём первый элемент неупорядоченной части и обменами с левым соседом ставим в то место упорядоченной части, где он должен в итоге оказаться:

N = len(array)
for sorted_length in range(N):
  for k in range(sorted_length):
    i = sorted_length - k 
    if array[i] < array[i-1]:
      array[i], array[i-1] = array[i-1], array[i]
    else:
      break

Единственной сложностью реализации этого алгоритма является обеспечения корректности индекса i внутреннего цикла. Он должен быть в пределах от \(1\) (для того, чтобы было определено array[i-1]) до \(N-1\) (для того, чтобы было определено array[i]).

Поскольку k не превышает sorted_length-1, то sorted_length-k не меньше

sorted_length - (sorted_length - 1) = 1

Также, поскольку k не меньше нуля, а sorted_length не превышает \(N-1\), то sorted_length - k тоже не превышает \(N-1\).

Асимптотическая сложность этого алгоритма ровно такая же, как и у сортировки поиском минимума: квадратичная. Доказательство в точности такое же.

Постскриптум

Среди трёх рассмотренных нами квадратичных алгоритмов (пузырёк, поиск минимума, вставки) на практике обычно можно встретить только вставки: имея одинаковую асимптотическую сложность, эти три алгоритма различаются по реальному времени работы (напомним, что асимптотическая сложность вообще не берёт в расчёт постоянные множители).

Может возникнуть естественный вопрос: «зачем вообще использовать квадратичный алгоритм сортировки, если есть алгоритмы с более низкой асимптотической сложностью?». Ответ весьма простой (хотя и состоит из двух частей):

• теория асимптотической сложности исследует лишь время работы алгоритма при достаточно большом \(N\)
• чем больше \(\alpha\), тем при большем количестве натуральных значений \(N\) выполнено неравенство \(\alpha N \log_2 N > N^2\)

Следствием любого из этих утверждений является то, что квадратичный алгоритм при достаточно маленьком \(N\) может работать быстрее линейно-логарифмического.

Считается (как результат большого количества экспериментов), что для массивов размером не более нескольких десятков элементов наиболее эффективный способ их отсортировать — применить сортировку вставками.

Быстрые алгоритмы сортировки

В этой главе мы рассмотрим два классических алгоритма сортировки с линейно-логарифмической сложностью: сортировку слиянием и сортировку разбиением.

Сортировка слиянием

Заметим сперва, что два упорядоченных массива можно соединить в один (тоже упорядоченный) следующим образом:

def merge(a,b):
  result = []

  i,j = 0,0
  while i<len(a) and j<len(b):
    if a[i] < b[j]: result.append(a[i]); i+=1
    else:           result.append(b[j]); j+=1

  result.extend(a[i:])
  result.extend(b[j:])
    
  return result

Время работы такого слияния пропорционально суммарной длине входных массивов. Этим можно воспользоваться для написания линейно-логарифмического алгоритма сортировки:

def merge_sorted(a):
  if len(a) < 2: return a[:]
  
  m = len(a)//2
  return merge(merge_sorted(a[:m]), 
               merge_sorted(a[m:]))

Доказательство того, что этот алгоритм работает, причём достаточно «быстро», можно аккуратно провести в несколько этапов.

Корректность

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

Назовём этот самый короткий среди неупорядочиваемых массивов буквой A. Заметим следующее (каждый факт тривиальным образом следует из предыдущего):

1. len(A) >= 2
2. len(A)//2 >= 1 и len(A)//2 < len(A)
3. len(A[:m]) < len(A) и len(A[m:]) < len(A), где m = len(A)//2
4. merge_sorted(A[:m]) и merge_sorted(A[m:]) упорядочены
5. merge_sorted(A) упорядочен

Осталось заметить, что пункт 5 противоречит предположению о том, что бывают неупорядочиваемые массивы. Значит, наше предположение неверно, и, следовательно, любой массив можно упорядочить при помощи рассматриваемого алгоритма.

Асимптотическая сложность

Будем рассматривать только верхнюю асимптотическую сложность (нижняя равна \(N\log N\), поскольку рассматриваемый алгоритм удовлетворяет предположениям теоремы о нижней оценке асимптотической сложности алгоритма сортировки — траектория программы зависит только от результатов ветвлений).

Обозначим \(T(N)\) максимально возможное время работы программы на массиве длины \(N\). Теперь применим полезный «трюк». Введём обозначение \(T_m(N) = \mathop{\mathrm{max}}_{n\leqslant N} T(n) \).

Верно следующее:

1. \(T(N) \leqslant T_m(N)\)
2. последовательность \(T_m\) является неубывающей

Монотонность \(T_m\) нам очень пригодится в дальнейшем. А вот \(T\) нас вообще больше не будет интересовать: очень трудно оценивать сверху последовательность, которая иногда возрастает, а иногда убывает, но «в целом возрастает». В связи с этим далее под обозначением \(T\) мы будем всегда понимать \(T_m\).

Также доопределим \(T\) на весь луч неотрицательных чисел: будем считать \(T(x) = T(\lfloor x \rfloor)\). Тогда для любого \(x\geqslant 2\) верно следующее:

\[ T(x) \leqslant 2T(x/2) + \alpha x + \beta \]

Здесь \(\alpha\) определяется реализацией алгоритма слияния merge, а \(\beta\) — накладными расходами на арифметические операции и вызовы функций в определении merge_sorted.

Применим это неравенство \(k\) раз:

\[ T(x) \leqslant 2^k T(x/2^k) + \alpha kx + \beta (1 + 2 + \ldots + 2^{k-1}) \]

Возьмём \(k=\lfloor \log x \rfloor\). Тогда:

\[ T(x) \leqslant 2^k T(1) + (2^k-1)\beta + \alpha x \log x \]

Осталось заметить, что, начиная с достаточно большого \(x\), выполнено

\[ T(x) \leqslant 2\alpha x\log x \]

Это и требовалось доказать.

Сортировка разбиением

Сортировка слиянием разбивет массив на два куска, каждый упорядочивает, затем сливает упорядоченные куски. Эффективность её работы зависит от того, насколько близко отношение длин кусков к единице.

Сортировка разбиением разбивает массив на два куска так, чтобы слияние этих кусков было тривиальным:

def partition_sorted(a):
  if len(a) < 2: return a[:]

  left, pivot, right = partition(a)

  return partition_sorted(left) + [pivot] + partition_sorted(right)

Этого можно добиться, если любой элемент left не превосходит pivot, а любой элемент right не меньше pivot. Опорный элемент pivot отделён от обеих частей для того, чтобы их размеры были строго меньше len(a).

Простейшая реализация функции partition может выглядеть так:

def partition(a):
  pivot = a[0]
  left = []
  right = []

  for x in a[1:]:
    if x <= pivot: left.append(x)
    else:         right.append(x)

  return left, pivot, right

Корректность алгоритма доказывается ровно так же, как и для сортировки слиянием. Поэтому сразу перейдём к обсуждению асимптотической сложности.

Асимптотическая сложность

Алгоритм, как нетрудно заметить, квадратичен: квадратичное поведение, например, проявляется, если ему на вход подать упорядоченный массив.

Тем не менее, среднее время работы алгоритма оказывается (как мы далее покажем) линейно-логарифмическим. Поэтому обычно делают следующее:

• выбирают опорный элемент более хитрым образом (например, псевдослучайно)
• если алгоритм таки превысил некую глубину рекурсии, перезапускают его, или же переходят к другому алгоритму сортировку

Итак, сейчас мы будем оценивать не максимально возможное время работы, а среднее. Как и раньше, обозначим \(T\) результат монотонизации (теперь среднего) времени работы.

Теперь заметим, что для любого \(n\geqslant 2\) верно

\[ T(n) \leqslant \frac{T(0)+T(n-1) + T(1)+T(n-2) + \ldots + T(n-1)+T(0)}{n} + \alpha n + \beta \]

Если ввести обозначение \(S(n)=T(0)+T(1)+\ldots+T(n)\), то получим

\[ T(n) \leqslant \frac{2}{n} S(n-1) + \alpha n + \beta \]

Применив ещё раз такое неравенство, получаем

\[ T(n) \leqslant \frac{2}{n} \left( \left(1 + \frac{2}{n-1}\right)S(n-2) + \alpha\cdot(n-1) + \beta \right) + \alpha n + \beta \]

Что эквивалентно

\[ T(n) \leqslant \frac{2(n+1)}{n(n-1)} S(n-2) + \alpha \left( n + \frac{2(n-1)}{n} \right) + \beta \frac{n+2}{n} \]

Если ещё раз применить такое же неравенство (и тривиальную оценку для члена с \(\beta\)), получится:

\[ T(n) \leqslant \frac{2(n+1)}{(n-1)(n-2)} S(n-3) + \alpha\left( n + \frac{2(n-1)}{n} + \frac{2(n+1)(n-2)}{n(n-1)} \right) + \beta\frac{n+2+4}{n} \]

Сделав так ещё много раз, получим (желающие могут аккуратно вывести рекуррентные соотношения на коэффициенты формулы):

\[ T(n) \leqslant \frac{2(n+1)}{3\cdot 2} S(1) + \alpha \left( n + \sum_{k=1}^{n-2} \frac{2(n+1)(n-k)}{(n-k+1)(n-k+2)} \right) + \beta \frac{n + (n-2)(n-1)}{n} \]

Немного увеличив числа в правой части, получаем оценку:

\[ T(n) \leqslant n(S(1)+\alpha+\beta) + 4n\alpha \left( \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \ldots + \frac{1}{n} \right) \]

Осталось оценить сумму при \(4n\alpha\). Но это — уже совершенно стандартная задача (обычно изучающаяся на уроках математики в 7 или 8 классе).

Первым делом оценим эту сумму сверху суммой, в которой на два слагаемых больше:

\[ 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} \]

Дальше заметим, что:

• первое слагаемое не превосходит единицу
• следующие два слагаемых не превосходят половину; их сумма не превосходит 1
• следующие четыре слагаемых не превосходят четверть; их сумма не превосходит 1
• и т.д.

Поэтому, если слагаемых не больше \(1+2+\ldots+2^{m-1} = 2^m-1\), то вся сумма не превосходит \(m\). Отсюда сразу следует, что сумма не превосходит \(\lceil\log (n+2)\rceil\), что, начиная с \(n=2\), не больше \(2\log n\).

Итак, мы доказали, что

\[ T(n) \leqslant n(S(1)+\alpha+\beta) + 8n\alpha\log n \]

Но нам это и нужно было.

«Быстрая» сортировка

Быстрая сортировка — это оптимизация сортировки разбиением, не требующая выделения дополнительной памяти. Её асимптотические характеристики ровно те же, что и у сортировки разбиением, но реальное время работы обычно (но не всегда!) меньше.

Разбиение происходит прямо в сортируемом массиве:

def partition_inplace(a, first, last):
  pivot = a[first]  ## можно заменить на что-нибудь более интересное

  while True:
    while a[first] < pivot: first += 1
    while a[last]  > pivot: last -= 1
    if first <= last:
      a[first], a[last] = a[last], a[first]
      first += 1; last -= 1
    if first > last:
      return last, first

Результат такого разбиения обладает следующими свойствами:

• первая компонента результата меньше второй
• первая компонента результата строго меньше входа last, а вторая — строго больше входа first
• любой элемент отрезка [first,last] с номером, не большим первой компоненты результата, не больше опорного элемента
• любой элемент этого отрезка с номером, не меньшим второй компоненты результата, не меньше опорного элемента

В терминах такого разбиения алгоритм быстрой сортировки выражается так:

def quicksort_rec(a, first, last):
  if last - first <= 0: return
  l, r = partition_inplace(a, first, last)
  quicksort_rec(a, first, l)
  quicksort_rec(a, r, last)

def quicksort(a): quicksort_rec(a, 0, len(a)-1)

В заключение отметим, что используемая разновидность разбиения (называемая разбиением Хоара), несмотря на кажущуюся простоту, весьма трудна для написания «с нуля» — слишком много свойств нужно обеспечить очень малым объёмом кода.

Существенно проще для реализации похожие схемы, в которых один из обмениваемых элементов — опорный. Впрочем, они менее эффективны.

Связные списки

Связные списки — один из наиболее простых взглядов на математическое понятие последовательности.

В математике (конечную) последовательность (элементов множества \(A\)) обычно определяют одним из двух способов:

• как нечто, сопоставляющее каждому не слишком большому натуральному числу элемент множества \(A\) (совсем формально: как отображение \(\mathbb{N}\supset[1,n]\to X\))
• как нечто, являющееся либо «пустой последовательностью», либо элементом множества \(A\), «приделанным» к последовательности (совсем формально: как начальную алгебру или же терминальную коалгебру функтора \(X\mapsto 1+A\times X\))

В информатике первому способу соответствует понятие массива. А вот второй способ соответствует как раз связному списку.

Абстрактные типы данных

Вообще говоря, когда мы говорим про какой-то тип данных, мы имеем в виду некий набор операций (интерфейс) с некоторыми правилами их композиции и некоторым набором свойств, которые от этих операций ожидаются.

Например, выражая какой-нибудь алгоритм в терминах массивов, мы обычно используем следующие операции:

• создать массив заданных длины и содержания
• узнать длину массива
• посмотреть на значение такого-то элемента массива
• изменить значение такого-то элемента массива
• (иногда) добавить в массив новый элемент
• (иногда) удалить из массива такой-то элемент

От них мы ожидаем весьма много различных свойств. В частности:

• если номер элемента меньше длины массива, то изменение этого элемента на значение x с последующим просмотром этого элемента выдаст своим результатом x
• если добавить в массив новый элемент, его длина увеличится на 1
• верхняя асимптотическая сложность просмотра элемента массива — (неотрицательная) степень логарифма длины массива

Полный список свойств приводить не будем: он весьма длинный.

Идея такого подхода в следующем: после того, как выписаны все операции и их свойства (набор операций и свойств называется абстрактным типом данных), можно рассматривать конкретные реализации этих операций. Если алгоритм написан в терминах операций абстрактного типа данных, то он будет работать для любой конкретной реализации.

Заметим, что в любом языке программирования большинство встроенных типов данных являются абстрактными: они определяются именно операциями и свойствами, а не конкретной реализацией.

Связные списки

Связный список как абстрактный тип данных существенно более прост, чем массив. Его можно описать следующим набором операций:

empty()     # выход: пустой связный список
join(a,l)   # входы: что угодно, связный список; выход: непустой связный список
is_empty(l) # вход: связный список; выход: булево значение
head(l)     # вход: непустой связный список; выход: что-то
tail(l)     # вход: непустой связный список; выход: связный список

Эти операции должны обладать следующими свойствами:

is_empty(empty()) == True
is_empty(join(a,l)) == False
head(join(a,l)) == a
tail(join(a,l)) == l

Под == в этих свойствах понимается не встроенная в Python эквивалентность, а «идеализированная». В Python она может быть приближена выражением вида id(foo) == id(bar).

Также желательно, чтобы асимптотическая сложность всех этих операций была константой (ну или хотя бы степенью логарифма длины списка).

Внимательный читатель может заметить, что на первый взгляд интерфейс связных списков и его свойства совпадают с таковыми у типа «опциональная пара». Это почти так! Единственное различие: типы входов и выходов head и join.

Ещё более внимательный читатель может заметить, что указанных свойств, вообще говоря, недостаточно для предсказуемого поведения: is_empty, например, может очищать поданный ему на вход список. И второе его применение к этому же списку выдаст True. Поэтому нужно дополнительно потребовать, чтобы все вышеописанные функции не имели побочных эффектов. Формально это означает, что добавление вызовов этих функций в произвольные места произвольной программы с произвольными входами не меняет наблюдаемое поведение этой программы (если игнорировать вопрос расхода вычислительных ресурсов).

Изоморфизм массивов и связных списков

Массивы и связные списки, являясь представлениями одной и той же математической концепции — последовательности, — могут быть преобразованы друг в друга:

def list_to_array(l):
  a = []
  
  while not is_empty(l):
    h, l = head(l), tail(l)
    a.append(h)

  return a


def array_to_list(a):
  l = empty()

  ## Обратите внимание на то, что список заполняется в обратном порядке!
  for x in reversed(a):
    l = join(x,l)

  return l

Отметим, что в этих преобразованиях нетривиальным образом участвуют все 5 операций интерфейса связных списков.

Типичные алгоритмы на связных списках

Длина списка:

def list_length(l):
  result = 0

  while not is_empty(l):
    l = tail(l)
    result += 1

  return result

Разворот списка:

def list_reverse(l):
  result = empty()

  while not is_empty(l):
    h, l = head(l), tail(l)
    result = join(h, result)

  return result

Применение функции к каждому элементу:

def list_map(l, f):
  result = empty()

  l = list_reverse(l)
  while not is_empty(l):
    h, l = head(l), tail(l)
    result = join(f(h), result)

  return result

Отсев всех элементов, не удовлетворяющих условию:

def list_filter(l, p):
  result = empty()

  l = list_reverse(l)
  while not is_empty(l):
    h, l = head(l), tail(l)
    if p(h): result = join(h, result)

  return result

Слияние двух списков:

def list_concat(l1, l2):
  result = l2
  
  l = list_reverse(l1)
  while not is_empty(l):
    h, l = head(l), tail(l)
    result = join(h, result)

  return result

Проверка двух списков на равенство:

def list_equal(l1, l2):
  while not is_empty(l1):
    if is_empty(l2): return False
    h1, l1 = head(l1), tail(l1)
    h2, l2 = head(l2), tail(l2)
    if h1 != h2: return False

  return is_empty(l2)

Редукция списка

Все эти алгоритмы (с некоторыми оговорками) являются частными случаями следующего:

def reduce(l, init, update):
  result = init

  while not is_empty(l):
    h, l = head(l), tail(l)
    result = update(result, h)

  return result

А именно:

def list_length(l): return reduce(l, 0, lambda s,x: s+1)

def list_reverse(l): return reduce(l, empty(), lambda s,x: join(x,s))

def list_map(l, f):
  return reduce(list_reverse(l), empty(), lambda s,x: join(f(x),s))

def list_filter(l, p):
  return reduce(list_reverse(l), empty(), lambda s,x: join(x,s) if p(x) else s)

def list_concat(l1, l2):
  return reduce(list_reverse(l1), l2, lambda s,x: join(x,s))

## Вот эта вот функция не эквивалентна вышеприведённому аналогу 
## вычислительной сложностью лучшего случая (да и выглядит страшнее).
def list_equal(l1, l2):
  def step(s,x):
    if len(s) == 0: return []
    
    l = s[0]
    if is_empty(l): return []
    if x != head(l): return []
    return [tail(l)]

  result = reduce(l1, [l2], step)
  if len(result) == 0: return False
  return is_empty(result[0])

Функция reduce по-научному называется левой свёрткой списков.

Слияние упорядоченных списоков

Это было одним из домашних заданий:

def list_merge(l1, l2):
  result = empty()

  while not (is_empty(l1) or is_empty(l2)):
    h1, t1 = head(l1), tail(l1)
    h2, t2 = head(l2), tail(l2)

    if h1 < h2: result = join(h1, result); l1 = t1
    else:       result = join(h2, result); l2 = t2

  result = list_reverse(result)
  result = list_concat(result, l1)
  result = list_concat(result, l2)
  return result  

Как нетрудно видеть, код почти аналогичен слиянию упорядоченных массивов. Только без «указателей».

Несколько конкретных реализаций связных списков

Здесь мы приведём несколько распространённых кодировок связных списков. Необходимо понимать хотя бы первую из них: остальные приведены для расширения кругозора.

Будем идти от простых к сложным (последние две кодировки интересны тем, что в них не используется вообще ни одной встроенной в язык операции, помимо констант True и False и оператора вызова функции).

Кодировка №1

Вложенные пары:

def empty():     return None
def join(x,l):   return (x,l)
def is_empty(l): return l == None
def head(l):     return l[0]
def tail(l):     return l[1]

Кодировка №2

Словарик:

def empty():     return {}
def join(x,l):   return { "head": x, "tail": l }
def is_empty(l): return len(l) == 0
def head(l):     return l["head"]
def tail(l):     return l["tail"]

Кодировка №3

Объект:

## иерархия -- чисто "для галочки" (она дальше не используется)
class List: pass
class Empty(List): pass
class Node(List):
  def __init__(self, head, tail):
    self.head = head
    self.tail = tail

def empty():     return Empty()
def join(x,l):   return Node(x,l)
def is_empty(l): return isinstance(l,Empty)
def head(l):     return l.head
def tail(l):     return l.tail

Кодировка №4

Ленивые вложенные пары:

def empty():     return lambda: None
def join(x,l):   return lambda: (x,l)
def is_empty(l): return l() == None
def head(l):     return l()[0]
def tail(l):     return l()[1]

Особенностью этой кодировки является возможность моделировать бесконечные списки. Например:

# единицы
ones = lambda: (1, ones)

# целые числа, начиная с заданного
beginning_from = lambda x: lambda: (x, beginning_from(x+1))

# натуральные числа
nats = beginning_from(0)

Впрочем, общаться с ними при помощи алгоритмов, описанных выше, почти невозможно.

Кодировка №5

Катаморфизм (кодировка Чёрча):

def empty():     return lambda z,s: z
def join(x,l):   return lambda z,s: s(x, l(z,s))
def is_empty(l): return l(True, lambda x,r: False)
def head(l):     return l(None, lambda x,r: x)
def tail(l):     return lambda z,s: l(lambda _: z, lambda x,r: lambda u: u(x, r(s))) (lambda a,b: b)

Списки кодируются т.н. правой свёрткой по ним:

def foldr(l,z,s):
  if is_empty(l): return z
  return s(head(l), foldr(tail(l),z,s))
## join(a_1, join(a_2, ... join(a_n, empty()) ... ))
## преобразуется в
## s(a_1, s(a_2, ... s(a_n, z) ... ))

Особенностью этой кодировки является очень неэффективный tail при аппликативном порядке вычисления формул (принятом в большинстве языков программирования, в том числе — в Python).

Также в Python такая кодировка довольно быстро упирается в ограничение глубины рекурсии.

Если интересно, как этот tail работает, то вот так:

# здесь join условно обозначен точкой-с-запятой (;), а empty() -- буквой E
# лямбда-выражения (lambda x1,x2,...,xn: y) кратко обозначены (\x1,x2,...,xn:y)
tail(1;2;3;4;E)(z,s) = 
## далее x&r = \u:u(x,r(s))
(1&2&3&4&(\_: z)             ) (\a,b:b) =       
(1&2&3&(\u:u(4, z))          ) (\a,b:b) =
(1&2&(\u:u(3, s(4, z)))      ) (\a,b:b) =
(1&(\u:u(2, s(3, s(4, z))))  ) (\a,b:b) =
(\u:u(1, s(2, s(3, s(4, z))))) (\a,b:b) =
s(2, s(3, s(4, z)))

Более элементарная кодировка tail может выглядеть так:

def fst(p): return p(lambda a,b:a)
def snd(p): return p(lambda a,b:b)
def tail(l): return snd(l(lambda u: u(empty(), empty()), 
                          lambda x,r: lambda u: u(join(x,fst(r)), fst(r))))

Кодировка №6

Терминальная коалгебра (кодировка Скотта):

def empty():     return lambda z,s: z
def join(x,l):   return lambda z,s: s(x,l)
def is_empty(l): return l(True, lambda x,xs: False)
def head(l):     return l(None, lambda x,xs: x)
def tail(l):     return l(None, lambda x,xs: xs)

Списки кодируются оператором деструктурирования (ветвления по структуре):

def destruct(l,z,s):
  if is_empty(l): return z
  return s(head(l), tail(l))

В этой кодировке (как и в кодировке №4) присутствуют бесконечные списки:

ones = lambda z,s: s(1,ones) 

beginning_from = lambda x: lambda z,s: s(x, beginning_from(x+1))

Стек и очередь

Рассмотрим следующий интерфейс:

empty()  ## выход: контейнер
put(c,x) ## входы: контейнер, что угодно
take(c)  ## вход: контейнер, выход: что-то
size(c)  ## вход: контейнер, выход: натуральное число

со следующим набором свойств:

empty() не имеет побочных эффектов
# это означает, что если в алгоритм добавить произвольное количество 
# подобных вызовов, результат работы алгоритма не изменится

size(empty()) == 0

size(c) не имеет побочных эффектов

# если предварительно сделать a = size(c); put(c,x), то
size(c) == a+1

# если size(c) > 0 и предварительно сделать a = size(c); take(c), то
size(c) == a-1

# для произвольного массива a, его копии b и пустого массива r,
# при начальном условии c = empty()
# и произвольной сбалансированной последовательности операций
# r.append(take(c)) и put(c, a.pop())
sorted(b) == sorted(r)

В последнем свойстве под сбалансированностью понимается, что перед любым take выполнено size(c) > 0, а после последней операции выполнено size(c) == 0.

Будем называть вышеописанный абстрактный тип данных мешком.

Внимательный читатель заметит, что функция sorted не работает для произвольного массива: далеко не всё, что угодно, можно сравнивать между собой. В связи с этим договоримся, что мы рассматриваем «идеализированную» версию sorted.

Стек и очередь

Если для любого массива a и любого подходящего c программа

b = []
for x in a: put(c,x)
for _ in range(len(a)): b.append(take(c))

приводит к тому, что a == b, то соответствующий мешок называется очередью (или FIFO: First In First Out).

Если же для любого a такая программа приводит к a == list(reversed(b)), то соответствующий мешок называется стеком (или LIFO: Last In First Out).

Для стека более традиционны названия операций push (вместо put) и pop (вместо take).

Иммутабельные версии

Вообще говоря, все вышеописанные свойства всё равно не слишком хорошо описывают стек/очередь/мешок. Например, следующая версия «стека» удовлетворяет всем вышеперечисленным свойствам:

STACKS = []
def empty(): n = len(STACKS); STACKS.append((n,[])); return STACKS[-1]
def size(c): return len(c[1])
def put(c,x): c[1].append(x)
def take(c): 
  for i, s in STACKS: if i != c[0]: s.clear()
  return c[1].pop()

но при этом обладает весьма неожиданным поведением (и сомнительной применимостью).

Поэтому вместо того, чтобы аккуратно определять мутабельность (это очень сложно), дадим иммутабельную версию стека/очереди/мешка.

# интерфейс
i_empty()
i_size(c)
i_put(c,x)
i_take(c)

# свойства
все функции не имеют побочных эффектов

i_size(i_empty()) == 0

size(i_put(c,x)) == size(c) + 1

# если size(c) > 0, то
size(i_take(c)[0]) == size(c) - 1

# для произвольного массива a, его копии b и пустого массива r,
# при начальном условии c = i_empty()
# и произвольной сбалансированной последовательности операций
# c, x = i_take(c); r.append(x) 
# и 
# c = i_put(c, a.pop())
sorted(b) == sorted(r)

# плюс для стека/очереди нужно ещё одно свойство 
# (аналогичное таковому для мутабельных версий)

А для мутабельной просто потребуем, чтобы она своим поведением была эквивалента следующей:

def empty(): return [i_empty()]
def size(c): return i_size(c[0])
def put(c,x): c[0] = i_put(c[0], x)
def take(c): c[0], x = i_take(c[0]); return x

Реализации стека

Будем использовать классические названия push и pop.

Массив

def empty():   return []
def size(c):   return len(c)
def push(c,x): c.append(x)
def pop(c):    return c.pop()

Связный список

def i_empty():   return (0, empty_list())
def i_size(c):   return c[0]
def i_push(c,x): return (c[0]+1, join(x, c[1]))
def i_pop(c):    return (c[0]-1, tail(c[1])), head(c[1])

Классические применения стека

Вычисление формул

Рассмотрим следующую функцию:

def evaluate_rec(formula):
  if type(formula) == tuple:
    op = formula[0]
    l = evaluate_rec(formula[1])
    r = evaluate_rec(formula[2])

    if op == '+': return l+r
    if op == '-': return l-r
    if op == '*': return l*r

  return formula

Она вычисляет значения формул вида ('+', 1, ('*', ('-', 2, 3) ('+', 4, 5))) (более традиционно такая формула записывается \(1+(2-3)\cdot(4+5)\)).

Стеки позволяют записать алгоритм вычисления такой формулы без использования рекурсии:

def evaluate(formula):
  formula_stack = empty()
  operator_stack = empty()

  push(formula_stack, formula)
  while True:
    top = pop(formula_stack)

    if type(top) == tuple:
      push(operator_stack, top[0])
      push(formula_stack, top[2])
      push(formula_stack, top[1])
    else:
      if size(operator_stack) == 0: return top
      op = pop(operator_stack)

      if type(op) == str:
        push(operator_stack, (op, top))
      else:
        if op[0] == '+': value = op[1] + top
        if op[0] == '-': value = op[1] - top
        if op[0] == '*': value = op[1] * top
        push(formula_stack, value)

Этот алгоритм работает следующим образом: есть стек формул и стек операций. Первый изначально содержит формулу, которую требуется вычислить, второй — пустой.

На каждом шагу достаётся элемент из стека формул.

• Если это (неатомарная) формула, то она разбирается на операцию и подформулы: операция переносится в стек операций, подформулы кладутся обратно в стек формул.
• Если же это число, а стек операций пустой, то это число — ответ.
• Если стек операций не пуст, оттуда достаётся операция, в которую подставляется наше число. Результат подстановки кладётся в стек операций или же в стек формул в зависимости от того, является ли он числом или же недовычисленной операцией.

В данном случае мы кодируем частично вычисленные операции парами вида (название операции, её первый вход).

Если рассматривать процедуру вычисления формулы как обход соответствующего графа в глубину, то стек формул — это текущий фронт, а стек операций — текущий путь от начала.

Ещё один способ вычисления формул

Единственной сложностью предыдущего алгоритма была необходимость как-то кодировать частично вычисленные операции. Сейчас мы приведём альтернативный (также двухстековый) алгоритм, в некотором смысле двойстенный предыдущему:

def evaluate(formula):
  value_stack = empty()
  command_stack = empty()

  push(command_stack, formula)
  while size(command_stack) > 0:
    top = pop(command_stack)

    if type(top) == tuple:
      push(command_stack, top[0])
      push(command_stack, top[1])
      push(command_stack, top[2])
    elif type(top) == str:
      a = pop(value_stack)
      b = pop(value_stack)
      if top == '+': value = a+b
      if top == '-': value = a-b
      if top == '*': value = a*b
      push(value_stack, value)
    else:
      push(value_stack, top)

  return pop(value_stack)

В этом алгоритме мы имеем дело с преобразователями стека, которые в рамках этого алгоритма мы будем называть командами. Каждая команда каким-то образом меняет стек значений.

В частности, формулы мы отождествляем с командами, кладущими в стек значений своё значение. А операции — с командами, забирающими из стека значений свои входы и кладущими туда свой результат (на этих входах).

Нетрудно видеть, что команда, соответствующая формуле (op, a, b), эквивалентна последовательности команд b, a, op. Собственно, именно эта эквивалентность и используется алгоритмом для вычисления значения формулы.

Реализация механизма вызова функций

Попробуйте запустить следующий код:

def foo():
  a = 3
  a += bar(2, a)
  return a

def bar(x, y):
  b = (5+x)*y
  b += baz(b)
  return b

def baz(x):
  return x/0

foo()

Вы получите сообщение об ошибке вроде следующего

Traceback (most recent call last):
  File "??????.py", line 14, in <module>
    foo()
  File "??????.py", line 3, in foo
    a += bar(2, a)
  File "??????.py", line 8, in bar
    b += baz(b)
  File "??????.py", line 12, in baz
    return x/0
ZeroDivisionError: division by zero

Это — текущее содержимое стека вызовов на момент ошибки.

Стек вызовов — стек, в который операции вызова функций записывают «адрес возврата» — место программы (и текущее состояние исполнителя), куда нужно вернуться по завершении работы соответствующей функции.

В качестве иллюстрации покажем пример простейшего интерпретатора языка с присваиваниями и вызовами функций. В качестве программы этот язык будет принимать питоновский список «команд».

Например, аналогом вышеприведённой программы будет следующее:

[
  ("call", 2),             ## строчка 0
  ("stop",),               ## строчка 1
  ("set", "a", 3),         ## строчка 2: def foo()
  ("call", 6, 2, "a"),     ## строчка 3
  ("add", "a", "_result"), ## строчка 4
  ("return", "a"),         ## строчка 5
  ("set", "b", 5),         ## строчка 6: def bar(x, y)
  ("add", "b", "_0"),      ## строчка 7
  ("mul", "b", "_1"),      ## строчка 8
  ("call", 12, "b"),       ## строчка 9
  ("add", "b", "_result"), ## строчка 10
  ("return", "b"),         ## строчка 11
  ("set", "temp", "_0"),   ## строчка 12: def baz(x)
  ("div", "temp", 0),      ## строчка 13
  ("return", "temp"),      ## строчка 14
]

Сам интерпретатор может быть устроен так:

def interpret(program):
  stack     = []
  variables = {}
  line      = 0

  while 0 <= line < len(program):
    command = program[line]
    op = command[0]

    if op in COMMANDS:
      line = COMMANDS[op](stack, variables, line, command[1:])
    else:
      raise RuntimeError("Unknown command: " + op)

def evaluate(variables, literal):
  if literal in variables: return variables[literal]
  return literal

def command_set(stack, variables, line, args):
  variables[args[0]] = evaluate(variables, args[1])
  return line + 1

def command_add(stack, variables, line, args):
  variables[args[0]] += evaluate(variables, args[1])
  return line + 1

def command_mul(stack, variables, line, args):
  variables[args[0]] *= evaluate(variables, args[1])
  return line + 1

def command_div(stack, variables, line, args):
  variables[args[0]] /= evaluate(variables, args[1])
  return line + 1

def command_stop(stack, variables, line, args):
  return -1 

def command_call(stack, variables, line, args):
  old_variables = { v:variables[v] for v in variables }
  
  stack.append( (old_variables, line) )
  variables.clear()

  for i, arg in enumerate(args[1:]):
    variables["_"+str(i)] = evaluate(old_variables, arg)

  return args[0]

def command_return(stack, variables, line, args):
  result = None if len(args) < 1 else evaluate(variables, args[0])

  old_variables, line = stack.pop()
  variables.clear()
  
  for v in old_variables:
    variables[v] = old_variables[v]

  variables["_result"] = result

  return line+1


COMMANDS = {
  "call":   command_call,
  "stop":   command_stop,
  "set":    command_set,
  "add":    command_add,
  "mul":    command_mul,
  "div":    command_div,
  "return": command_return,
}

Обход «в глубину»

Предположим, что мы имеем дело со связным (ориентированным) графом, который нужно полностью обойти (формально говоря, перечислить все его вершины).

Стандартный способ обохода описан в древнегреческих мифах:

def traverse(graph, start, callback = None):
  path    = [start]
  visited = set()
  
  while path:
    current_place = path[-1]
    visited.add(current_place)

    ## можно что-нибудь сделать в вершине, если нужно
    if callback: callback(current_place)

    ## функция neighbors выдаёт список соседей указанной вершины
    to_visit = [n for n in neigbors(graph,current_place)
                  if  n not in visited]
    
    if to_visit: path.append(to_visit[0])
    else:        path.pop()

  return visited

Нетрудно увидеть здесь стек:

def traverse(graph, start, callback = None):
  path = empty()
  push(path, start)

  visited = set()
  
  while path:
    current_place = pop(path)
    push(path, current_place)
    visited.add(current_place)

    if callback: callback(current_place)

    to_visit = [n for n in neigbors(graph, current_place)
                  if  n not in visited]
    
    if to_visit: push(path,to_visit[0])
    else:        pop(path)

  return visited

Теперь перейдём к более современной версии того же обхода (к сожалению, автор не в курсе, знали ли её древние греки), основанную на другой идеологии, которая имеет полезные обобщения.

Фронтовой обход

Будем действовать следующим методом: на каждом шаге храним фронт — множество соседей тех вершин, в которых мы уже были. Если фронт непуст, забираем из него любую вершину, а вместо неё добавляем всех её непосещённых соседей. Этот алгоритм выражается так:

def traverse(graph, start, callback = None):
  front = empty()
  put(front, start)

  visited = set()

  while size(front) > 0:
    vertex = take(front)
    if vertex in visited: continue
    visited.add(vertex)
    
    if callback: callback(vertex)
    
    for n in neighbors(graph, vertex): put(front, n)

  return visited

Этот алгоритм, как можно видеть, выражается в терминах операций над произвольным мешком. От выбора реализации мешка зависит порядок обхода.

Обход «в глубину» получается, если мешок является стеком. Оставим доказательство этого утверждения в качестве простого упражнения на метод математической индукции.

Реализации очереди

Массив

Наиболее простая реализация очереди может выглядеть так:

def empty():   return []
def size(c):   return len(c)
def put(c,x):  c.append(x)
def take(c):   return c.pop(0)

Эта реализация плоха тем, что операция «забрать элемент» линейна по размеру очереди.

Циклическая очередь

При сколько-нибудь больших размерах очереди более эффективна следующая реализация:

MAX_CAPACITY = 100

def empty():  return [0, 0, [None] * MAX_CAPACITY]
def size(c):  return (c[1] - c[0]) % len(c[2])

def put(c,x):
  _, right, array = c

  if size(c) == len(array) - 1:
    raise RuntimeError("Max capacity exceeded")
  
  array[right] = x
  c[1] = (right + 1) % len(array)
  

def take(c):
  left, _, array = c

  if size(c) == 0:
    raise RuntimeError("Queue is empty")

  c[0] = (left + 1) % len(array)
  return array[left]

Расширяемая циклическая очередь

Как нетрудно видеть, предыдущая реалзиация имеет ограниченную вместимость. Это можно легко исправить альтернативным put:

def put(c,x):
  _, right, array = c

  array[right] = x
  c[1] = (right + 1) % len(array)

  if size(c) < len(array) - 1: return

  new_queue = [0, 0, [None] * (len(array)*2)]

  while size(c) > 0: put(new_queue, take(c))

  for i, _ in enumerate(c): c[i] = new_queue[i]

Классические применения очереди

Запаздывание в однопроходных алгоритмах

Рассмотрим типичную задачу из ЕГЭ: найти максимальное произведение пары элементов входного массива (все элементы — целые положительные числа), порядковые номера которых различаются хотя бы на 6, делящееся на 15.

Вот — каноническое её решение:

def process(sequence):
  queue = empty()
  maxima = [0] * 15
  answer = 0

  for x in sequence:
    put(queue, x)
    if size(queue) <= 6: continue

    y = take(queue)
    mod = y % 15
    maxima[mod] = max(maxima[mod], y)

    candidates = [ x * maxima[m]
                   for m in range(15)
                   if (m * x) % 15 == 0 ]

    if len(candidates) > 0: answer = max(answer, max(candidates))


  return answer

Общий вид этого алгоритма следующий:

def process(sequence, delay, init_state, update_a, update_b):
  queue = empty()
  a, b = init_state()

  for x in sequence:
    put(queue, x)
    if size(queue) <= delay: continue

    a = update_a(a, take(queue))
    b = update_b(a, b, x)
  
  return b

Это — разновидность редукции списка, в которой состояние делится на две компоненты, одна из которых обновляется с отставанием от другой.

По-научному такая редукция (а точнее, некоторое её обобщение) называется зигохистоморфизмом списка. Обычная же редукция называется катаморфизмом списка, а полуторакомпонентная редукция с отставанием, равным 0, называется зигоморфизмом списка.

Если быть более точным, то классические ката-, зиго- и прочие …морфизмы относятся к «правым» свёрткам: они обрабатывают список с конца. Впрочем, левая и правая свёртки очень тесно связаны: одну можно получить из другой, например, разворотом списка.

Обход «в ширину»

Недостатком обхода в глубину является чрезвычайный оппортунизм, следствием которого является, например, невозможность (потенциально) полного обхода бесконечных графов. Поэтому часто используется обход в ширину, перебирающий вершины в порядке возрастания расстояния от них до начальной.

Чтобы получить обход в ширину, достаточно в вышеприведённом фронтовом обходе взять в качестве мешка очередь.

Бинарный поиск

Задача эффективного поиска данных, хранящихся в массиве, существенно упрощается, если данные в массиве расположены не произвольно, а упорядочены (для определённости — по неубыванию).

Простейшая разновидность бинарного поиска

Для начала поставим простую задачу: есть упорядоченный массив haystack и некий объект needle (на который единственное ограничение — должна быть возможность сравнивать его с элементами массива при помощи операций больше/меньше). Нужно найти границу между элементами, строго меньшими needle, и элементами, большими или равными ему.

Для удобства будем считать len(haystack) == N и мысленно пронумеруем все границы между элементами массива (а также — слева и справа от них) числами от 0 до N. Заметим, что для любого x (в пределах от 0 до N-1) граница с номером x находится непосредственно левее элемента с номером x.

Рассмотрим следующий алгоритм:

def binsearch(haystack, needle):
    left  = 0
    right = len(haystack)
  
    while right > left:
        mid = (left + right) // 2
        if haystack[mid] < needle:  left = mid + 1
        else:                      right = mid

    return left

Очевидно, что если этот алгоритм завершил работу, то его результатом как раз является искомая граница. Поэтому единственный важный вопрос, связанный ним: «а всегда ли заканчивается цикл?» Ответ на этот вопрос утвердительный по следующим соображениям:

1. Если right>left, то mid<right.
2. При этом m+1>left.
3. Отсюда следует, что на каждом шаге разность right-left уменьшается хотя бы на 1. Поэтому всегда оставаться положительной она не может.

Теперь поймём, насколько бинарный поиск эффективнее полного перебора. Для этого нужно заметить, что разность right-left на каждом шагу уменьшается не меньше, чем в два раза. Поэтому количество шагов, требующееся для завершения работы алгоритма на массиве размера n не превосходит ни одно целое k, для которого 2**k > n.

В частности, увеличение количества данных в два раза влечёт увеличение времени работы не больше чем на время выполнения одного шага алгоритма (если оставить за рамками модели наблюдающееся на практике увеличение времени доступа к элементу массива с увеличением размера массива, то время выполнения одного шага не зависит от размера массива).

Например, массив размера миллиард элементов будет обработан бинарным поиском не дольше чем за 30 шагов. Нетрудно заметить, что 30 шагов, в каждом из которых не более двух сравнений и ещё чуть-чуть арифметики, существенно приятнее, чем миллиард сравнений при поиске полным перебором.

Наконец, отметим, что результат работы этого алгоритма совпадает с рангом элемента needle — количеством элементов массива haystack, меньших needle.

Поиск по ключу

На практике вышеизложенные задачи поиска почти не встречаются: обычно мы ищем не положение «Василия Ивановича Чапаева номер паспорта 1234 567890» в массиве людей, упорядоченном по ФИО и номеру паспорта, а номер паспорта человека по имени «Василий Иванович Чапаев».

Те данные, которые мы подаём на вход процедуре поиска, традиционно называются ключом поиска (вспомните терминологию, связанную с типом данных «словарь»). В примере с Василием Ивановичем ключом поиска является ФИО. Отображение, сопоставляющее единице данных соответствющий ей ключ, называется ключевой функцией.

Ниже приведена версия процедуры бинарного поиска, принимающая на вход ключевую функцию. При этом преполагается, что массив haystack упорядочен по ключу.

def binsearch_key(haystack, needle, key):
    left  = 0
    right = len(haystack)
  
    while right > left:
        mid = (left + right) // 2
        if key(haystack[mid]) < needle:  left = mid + 1
        else:                           right = mid

    return left

И заодно приведём пример использования (с тем самым Василием Ивановичем):

def name(human): return human[0]+' '+human[1]+' '+human[2]

## все совпадения с реальными людьми случайны!
people = [
    ('Чапаев',  'Василий', 'Иванович', 1234, 567890),
    ('Сидоров', 'Иван',    'Петрович', 3210, 456789),
    ('Нектов',  'Некто',   'Нектович', 1111, 111112),
]

sorted_people = sorted(people, key=name)

index = binsearch_key(sorted_people, 'Чапаев Василий Иванович', name)

print('Номер паспорта Василия Ивановича:', *sorted_people[index][3:])

Функция вместо массива

Вообще говоря, в бинарном поиске можно вместо массива использовать любую монотонную функцию. Как, например, в следующем примере:

def binsearch_fn(haystack, needle):
    fn, left, right  = haystack
  
    while right > left:
        mid = (left + right) // 2
        if fn(mid) < needle:  left = mid + 1
        else:                right = mid

    return left

## эта функция вычисляет верхний целочисленный корень числа бинарным поиском
def root(n):
    return binsearch_fn( (lambda x: x*x, 0, n), n )

Что интересно, обе ранее рассмотренные разновидности бинарного поиска тривиально выражаются при помощи этой:

def binsearch(haystack, needle):
    def get(x): return haystack[x]
    return binsearch_fn( (get, 0, len(haystack)), needle )

def binsearch_key(haystack, needle, key):
    def get(x): return key(haystack[x])
    return binsearch_fn( (get, 0, len(haystack)), needle )

Деревья поиска

Предположим, что у нас есть числовой массив, и нам требуется уметь быстро отвечать на вопрос вида «чему равна сумма всех чисел с номера a до номера b?» Наивный способ

def segment_sum(array, a, b):
    return sum(array[a:b+1])

имеет время работы, пропорциональное разности b-a. Эта разность может быть того же порядка, что и размер массива. Поэтому на практике такая ситуация оказывается малоудовлетворительной (для массива размером порядка миллиона элементов за секунду можно обработать максимум порядка тысячи запросов).

Есть классический трюк: можео заранее вычислить префиксные суммы массива

def prefix_sums(array):
    result = []

    for x in array: result.append(result[-1] + x)

    return result

Тогда сумму чисел на отрезке можно вычислить как разность двух таких сумм:

def segment_sum_prefix(prefix_sums_array, a, b):
    return prefix_sums_array[b+1] - prefix_sums_array[a]

Но сумма — далеко не единственная операция, которую приходится считать на отрезках массива. Не менее часто встречается необходимость считать, например, максимумы и минимумы. Для них вышеописанный трюк не проходит: у них нет аналога разности.

Именно для решения этой проблемы и используются деревья поиска.

Простейшее дерево

Сперва поставим задачу. Предположим, что определена ассоциативная функция combine, принимающая на вход массив и работающая за время, зависящее только от длины входного массива (но не от его содержимого).

Ассоциативность в данном случае означает, что

combine([combine(subarray) for subarray in array])

совпадает с

combine([x for subarray in array for x in subarray])

Нам нужно предобработать массив таким образом, чтобы можно было получать результат функции

def segment_value(array,a,b):
    return combine(array[a:b+1])

за время, с точностью до логарифмического множителя не зависящее от a, b или же размера массива array.

Будем для любого натурального K, большего 1, называть K-деревом результат работы следующей функции:

def make_tree(array):
    level = array[:]

    levels = [level]

    while len(level) >= K:
        level = [combine(level[i:i+K]) for i in range(0, len(level), K)]
        levels.append(level)

    return levels

Например, если определить combine = sum и K=2, то

make_tree([1,2,3,4,5,6,7,8]) == [
  [1,2,3,4,5,6,7,8],
  [3,  7,  11, 15],
  [10,     26],
  [36]
]

Теперь, наконец, мы можем решить нашу задачу при помощи следующей функции:

def tree_segment_value(tree, a, b):
    N = len(tree)

    if N == 0: return combine([])

    return tree_segment_value_rec(tree, a, b, N-1, 0, K**(N-1))


def tree_segment_value_rec(tree, a, b, level, start, size):
    to_combine = []

    for i in range(start, min(start+K, len(tree[level]))):
        if (i + 1)*size <= a: continue
        if i      *size >  b: break
        if i*size >= a and (i+1)*size-1 <= b: 
            to_combine.append(tree[level][i])
        else:
            to_combine.append(
              tree_segment_value_rec(tree, a, b, level-1, i * K, size // K)
            )
    
    return combine(to_combine)

Интересно, что эту функцию можно (хотя и не очень просто) реализовать без использования рекурсии или каких бы то ни было её замен (типа явного стека). Соответствующую реализацию оставим в качестве упражнения для читателя.

Остаётся вопрос о времени работы этой функции. Заметим следующее:

• за один цикл происходит не более двух рекуррентных вызовов
• если произошло два рекуррентных вызова, то в рамках каждого из них ни один из циклов (имеется в виду не только цикл непосредственно вызванной функции, но циклы всех её потомков) не может сделать два рекуррентных вызова
• каждый цикл имеет время работы, пропорциональное сумме K и времени работы combine на не более чем K-элементном массиве

Учитывая всё вышеперичисленное, получаем, что время работы не превосходит (помноженное на некоторую константу) удвоенное произведение количества уровней дерева и суммы K и времени работы combine на не более чем K-элементом массиве. Что не превосходит (помноженный на константу) K-ричный логарифм количества элементов исходного массива. Что и требовалось.

Дерево отрезков

Вообще говоря, подобная предобработка может быть применена не только к обычному массиву (выдающему элементы по их порядковым номерам), а к любому ассоциативному массиву (выдающему элементы по «ключам»), множество ключей которого упорядочено (т.е. ключи можно сравнивать между собой).

Единственное отличие: теперь вместе со значением combine в дереве придётся хранить ещё и отрезок — минимальное и максимальное значения ключей элементов, к которым этот combine применён.

Также следует позаботиться о том, чтобы массив был отсортирован по ключам: функция tree_segment_value (и дальнейшее рассуждение об асимптотической сложности) явно использует сортированность массива.

Конкретную реализацию дерева отрезков для ассоциативного массива оставим в качестве упражнения для читателя.

Розовые кусты

Недостатком вышеприведённой модели дерева (набор «уровней») является её статичность: она не поддерживает эффективное добавление новых элементов. Конечно, существуют относительно простые методы, позволяющие «научить» произвольную статическую структуру данных эффективному добавлению новых элементов, но они накладывают дополнительные ограничения на combine (например, динамизация, описанная в ресурсе по ссылке, требует коммутативности).

Поэтому сейчас мы рассмотрим другую модель, несколько более гибкую. А именно, деревом будем называть список деревьев, спаренный с некоторым набором данных.

Например, вышеприведённое дерево сумм для последовательности целых чисел от 1 до 8 в такой модели может выглядеть так:

(36, [
  (10, [
    (3, [
      (1, []),
      (2, []),
    ]),
    (7, [
      (3, []),
      (4, []),
    ]),
  ]),
  (26, [
    (11, [
      (5, []),
      (6, []),
    ]),
    (15, [
      (7, []),
      (8, []),
    ]),
  ]),
])

Традиционное название для такой модели — «розовый куст» (rose tree).

Очень часто встречаются специализации и модификации этой модели для конкретных размеров списков. Например, бинарное дерево обычно определяется так:

• это либо «пустое значение»
• либо пара бинарных деревьев, агрегированная с набором данных

Как нетрудно заметить, если в вышеприведённый розовый куст вставить «пустые значения»:

(36, [
  (10, [
    (3, [
      (1, [None, None]),
      (2, [None, None]),
    ]),
    (7, [
      (3, [None, None]),
      (4, [None, None]),
    ]),
  ]),
  (26, [
    (11, [
      (5, [None, None]),
      (6, [None, None]),
    ]),
    (15, [
      (7, [None, None]),
      (8, [None, None]),
    ]),
  ]),
])

то получится как раз нечто, что можно рассмативать как бинарное дерево.

Добавление элементов

Будем пользоваться следующим внутренним представлением

def tree_segment(tree):    return tree[0]
def tree_value(tree):      return tree[1]
def tree_children(tree):   return tree[2]
def make_leaf(key, value): return ( (key, key), combine([value]), [] )
def make_branch(trees):
  segments = [ tree_segment(tree) for tree in trees ]
  
  left  = min([segment[0] for segment in segments])
  right = max([segment[1] for segment in segments])
  ## при должной аккуратности можно заменить на 
  ## left  = segments[0][0]
  ## right = segments[-1][1]

  value = combine([ tree_value(tree) for tree in trees ])
  
  return ( (left, right), value, trees[:] )

def tree_segment_value(tree, a, b):
  ta, tb = tree_segment(tree)
  if a <= ta and tb <= b: return tree_value(tree)

  to_combine = []

  for child in tree_children(tree):
    ta, tb = tree_segment(child)
    if tb < a: continue
    if ta > b: break
    if a <= ta and tb <= b: to_combine.append(tree_value(child))
    else: to_combine.append(tree_segment_value(child, a, b))

  return combine(to_combine)

Для добавления элемента мы реализуем иммутабельный интерфейс (напомним, что этот термин означает, что добавление не изменяет существующее дерево, а на его основе создаёт новое):

def tree_put(tree, key, value):
  if tree == None: return make_leaf(key, value)
  
  children = tree_children(tree)

  if len(children) == 0: ## лист
    new_leaf = make_leaf(key, value)

    tree_key = tree_segment(tree)[0]
    if key < tree_key: return make_branch([new_leaf, tree])
    if key > tree_key: return make_branch([tree, new_leaf])
    return new_leaf

  i = 0
  while i < len(children):
    if tree_segment(children[i])[0] > key: break
    i += 1
  if i > 0: i -= 1
  
  return make_branch(
    children[:i] + [tree_put(children[i], key, value)] + children[i+1:]
  )

Такой способ добавления всегда создаёт бинарные деревья. У него есть два существенных недостатка:

• при неудачном стечении обстоятельств (например, добавляемые данные упорядочены по возрастанию их ключей) высота дерева пропорциональна количеству данных
• не используется потенциальная возможность веток иметь больше поддеревьев, чем два

В связи с этим мы покажем ещё один способ добавления элементов, избавленный от обоих из этих недостатков:

MAX_SIZE = 4  ## некая константа, большая 2
def is_leaf(tree): return len(tree_children(tree)) == 0

def tree_put_rec(tree, key, value):  ## возвращает одно или два дерева
  if tree == None: return [make_branch([make_leaf(key, value)])]
  
  children = tree_children(tree)

  i = 0
  while i < len(children):
    if tree_segment(children[i])[0] > key: break
    i += 1
  if i > 0: i -= 1

  left_children = children[:i]
  right_children = children[i+1:]

  child = children[i]
  if is_leaf(child):
    new_leaf = make_leaf(key, value)

    child_key = tree_segment(child)[0]
    if   child_key < key: mid_children = [child, new_leaf]
    elif child_key > key: mid_children = [new_leaf, child]
    else:                 mid_children = [new_leaf]
  else:
    mid_children = tree_put_rec(child, key, value)
  
  new_children = left_children + mid_children + right_children
  N = len(new_children)
  if N > MAX_SIZE: to_wrap = [new_children[:N//2], new_children[N//2:]]
  else:            to_wrap = [new_children]

  return [make_branch(subtrees) for subtrees in to_wrap]

def tree_put(tree, key, value):
  new_trees = tree_put_rec(tree, key, value)
  
  if len(new_trees) < 2: return new_trees[0]
  return make_branch(new_trees)

Этот способ добавления называется «B-деревом». Альтернативный способ получить дерево с логарифмической относительно количества хранимых данных высотой представлен в следующем разделе.

Для того, чтобы посмотреть вживую на эти деревья, можно воспользоваться следующим простым способом визуализации:

def print_tree(tree, indent = 0):
  if tree == None: print()

  print(' '*indent + str(tree_segment(tree)) + ' -> ' + str(tree_value(tree)))
  for child in tree_children(tree):
    print_tree(child, indent + 2)


t = None
combine = sum

for v, k in enumerate([5,7,2,1,3,6,2,7]):
  t = tree_put(t, k, v)

print_tree(t)

Балансировка Адельсон-Вельского и Ландиса

Исторически первая разновидность самобалансирующихся деревьев поиска была в 1962-м году предложена советскими математиками Г.М. Адельсон-Вельским и Е.М. Ландисом. В настоящее время на практике она почти не используется (поскольку очень сильно проигрывает в производительности алгоритмам, учитывающим наличие в современных ЭВМ большого и быстрого кэша). Здесь она присутствует исключительно из-за требований рабочей программы курса (а также — по той причине, что задача анализа высоты такого дерева представляет самостоятельный математический интерес).

Начнём с более классической (но всю эту идеологию можно применять и к построенным в предыдущем разделе бинарным «кустам отрезков») реализации бинарных деревьев: вместо того, чтобы для каждого из деревьев хранить отрезок ключей, обслуживаемый этим деревом, мы будем в каждой ветке хранить «разделяющее значение» — нечто, большее любого ключа левого поддерева, и не превышающее любого ключа правого поддерева (в этой идеологии можно продвинуться дальше и хранить данные с ключами прямо в узлах, сохраняя то же свойство — ключ в узле должен разделять ключи левого и правого поддереьвев).

Выглядит это примерно так:

## Служебные функции
def leaf(key, value): return (key, value)
def is_leaf(tree): return len(tree) == 2

def branch(separator, left, right, inv=False):
    if inv: left, right = right, left
    return (separator, left, right)

def children(tree, inv):
    if inv: return tree[2], tree[1]
    return tree[1], tree[2]


## Основной интерфейс
def empty(): return None

def put(tree, key, value):
    if tree == None: return leaf(key, value)

    tree_key = tree[0]
    inv = key < tree_key

    if is_leaf(tree):
        new_leaf = leaf(key, value)
        if key == tree_key: return new_leaf
        
        if inv: key = tree_key 
        return branch(key, tree, new_leaf, inv)
   
    left, right = children(tree, inv)
    
    return branch(tree_key, left, put(right, key, value), inv)

def get(tree, key):
    if tree == None: return None

    tree_key = tree[0]

    if is_leaf(tree):
        if tree_key == key: return tree[1]
        return None

    _, right = children(tree, key < tree_key)

    return get(right, key)

Деревья Адельсон-Вельского и Ландиса отличаются от «наивных» бинарных деревьев следующим:

• в каждом узле хранится высота дерева (длина самого длинного пути от этого узла до листа)
• в функции добавления элементов применяется дополнительная балансировка, обеспечивающая не превышающую 1 разность высот поддеревьев любого узла

Получается примерно следующее:

## Служебные функции
def leaf(key, value): return (key, value)
def is_leaf(tree): return len(tree) == 2

def branch(separator, left, right, inv=False):
    if inv: left, right = right, left
    return (separator, left, right, 1 + max(height(left), height(right)))

def children(tree, inv):
    if inv: return tree[2], tree[1]
    return tree[1], tree[2]

def height(tree):
    if tree == None: return 0
    if is_leaf(tree): return 1
    return tree[3]


## AVL-утилиты
def reassoc(tree, inv):
    l, r   = children(tree, inv)
    rl, rr = children(r, inv)
    return branch(r[0], branch(tree[0], l, rl, inv), rr, inv)

def avl(tree, inv):
    l, r = children(tree, inv)

    if height(r) - height(l) < 2: return tree

    rl, rr = children(r, inv)
    if height(rl) - height(rr) == 1: r = reassoc(r, not inv)
    
    return reassoc(branch(tree[0], l, r, inv), inv)


## Основной интерфейс
def empty(): return None

def put(tree, key, value):
    if tree == None: return leaf(key, value)

    tree_key = tree[0]
    inv = key < tree_key

    if is_leaf(tree):
        new_leaf = leaf(key, value)
        if key == tree_key: return new_leaf
        
        if inv: key = tree_key 
        return branch(key, tree, new_leaf, inv)
   
    left, right = children(tree, inv)
    
    return avl(branch(tree_key, left, put(right, key, value), inv), inv)
##         ^^^ <-- единственное отличие!

def get(tree, key):
    if tree == None: return None

    tree_key = tree[0]

    if is_leaf(tree):
        if tree_key == key: return tree[1]
        return None

    _, right = children(tree, key < tree_key)

    return get(right, key)

Отметим, что в оригинальном алгоритме предлагалось в каждом узле хранить не высоту, а разность высот поддеревьев. Но алгоритм при этом был чуть сложнее для понимания.

Анализ высоты AVL-деревьев

Пусть \(m(h)\) — минимальное количество элементов в дереве высоты \(h\).

Тогда, очевидно, \(m\) монотонно, и для \(h\geqslant2\) верно соотношение

\[ m(h) = m(h-1) + m(h-2) \]

Учитывая, что \(m(1) = 1\) и \(m(2) = 2\), получаем (согласно явной формуле для чисел Фибоначчи)

\[ m(h) = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{h} + \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{h} \]

что весьма близко (отличается не более чем на 1) к первому слагаемому правой части

\[ \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{h} \]

Учитывая, что при хранении \(N\) элементов выполняется неравенство

\[ N \geqslant m(h) \geqslant \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{h} - 1 \]

получаем, что

\[ h \leqslant \frac{1}{\log(1+\sqrt{5})-1}\log(N\sqrt{5}) \]

Такой оценки нам вполне достаточно.

Данные в узлах

Вместо разделяющего значения можно в узлах хранить данные, ключ которых использовать как разделяющее значение.

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

Впрочем, удаление элементов мы и не обсуждали по банальной причине:

• обычно проще не удалять элемент физически из дерева, а всего лишь помечать его как удалённый
• если через такое дерево проходит очень большое количество элементов (то приходя в него, то уходя из него), и требуется сохранять ограниченный размер дерева, можно изредка его перестраивать: например, если количество помеченных элементов составляет половину (или какую-либо иную долю) его размера

Итак, без лишних слов (AVL-дерево в 26 строчек):

def height(tree): return 0 if tree == None else tree[4]

def branch(key, value, l, r, inv = False): 
  if inv: l, r = r, l
  return (key, value, l, r, 1 + max(height(l), height(r)))

## AVL-часть остаётся прежней
def children(tree, inv): return (tree[3], tree[2]) if inv else (tree[2], tree[3])
  
def reassoc(tree, inv):
    l, r   = children(tree, inv)
    rl, rr = children(r, inv)
    return branch(r[0], r[1], branch(tree[0], tree[1], l, rl, inv), rr, inv)

def avl(tree, inv):
    l, r = children(tree, inv)

    if height(r) - height(l) < 2: return tree

    rl, rr = children(r, inv)
    if height(rl) - height(rr) == 1: r = reassoc(r, not inv)
    
    return reassoc(branch(tree[0], tree[1], l, r, inv), inv)

## А вот само дерево поиска упрощается
def empty(): return None

def put(tree, key, value):
    if tree == None:   return branch(key, value, None, None)
    if tree[0] == key: return branch(key, value, tree[2], tree[3])

    inv = key < tree[0]
   
    left, right = children(tree, inv)
    
    return avl(branch(tree[0], tree[1], left, put(right, key, value), inv), inv)

def get(tree, key):
    if tree == None: return None
    if key == tree[0]: return tree[1]
    
    return get(children(tree, key < tree[0])[1], key)

Хеш-таблицы

Деревья поиска обладают не слишком высокой плотностью расположения данных в памяти: в лучшем случае они представляют собой набор массивов-уровней, но при этом в них проблематично добавлять новые элементы.

Наиболее же гибкие разновидности деревьев состоят из большого количества блоков маленького размера, расположенных в памяти где повезёт.

При этом архитектура современных ЭВМ не рассчитана на частые операции доступа к большому количеству различных участков памяти: если суммарная длина этих участков больше размера кэша процессора, приходится периодически перекладывать данные из оперативной памяти в кэш, что весьма временезатратно.

Поэтому чем локальнее расположены данные, тем быстрее можно с ними работать.

Идеальная с этой точки зрения структура данных — массив. Хеш-таблицы представляют собой некую модификацию идеи массива, позволяющую использовать массив в качестве эффективного ассоциативного контейнера для довольно широкого спектра видов ключей.

Хеш-функции

Массивы с точки зрения математики — модели для отображений \([0,N) \rightarrow X\), где \([0,N)\) — множество натуральных чисел от \(0\) до \(N\).

Ассоциативные контейнеры — модели для отображений \(K \rightarrow 1+V\).

Массив можно превратить в ассоциативный контейнер, выбрав некоторую функцию \(h: K \rightarrow [0, N)\) и взяв \(X = 1+V\):

def new(size): return [None]*size

def put(array, key, value):
  array[h(key)] = [value]

def get(array, key):
  result = array[h(key)]

  if result == None: raise KeyError  ## тот самый элемент множества 1

  return result[0]

Это — наиболее примитивная версия хеш-таблицы. Та самая функция \(h\), преобразующая ключи в индексы массива, традиционно называется хеш-функцией. Обычно от хеш-функции (в аспекте реализации хеш-таблиц) требуются две вещи:

• высокая скорость работы
• относительно равномерное распределение значений

Но, независимо от качества хеш-функции, обычно приходится иметь дело с ситуацией, когда разные ключи имеют одно и то же значение хеш-функции. Такие ситуации традиционно называются коллизиями. И с ними нужно что-то делать (впрочем, отказывать в хранении — тоже иногда вполне разумная политика; как и в некоторых случаях — перезаписывать уже хранящиеся в таблице данные).

Сначала мы обсудим один из способов эффективного хеширования, а затем — способы разрешения конфликтов.

Полиномиальные хеши последовательностей

Допустим, что мы умеем каким-то образом элементам множества \(A\) сопоставлять целые числа. Научимся сопоставлять целые числа последовательностям таких элементов так, чтобы наиболее распространённые операции над последовательностями соответствовали каким-то простым операциям над соответствующими этим последовательностям числами.

Для простоты будем считать, что в последовательности находятся не элементы множества \(A\), а соответствующие этим элементам числа.

Полиномиальным хешем последовательности \(a_1, a_2, \ldots a_n\) относительно параметров \(a_0\), \(d\) и \(N\) назовём значение выражения

\[ H(a) = (a_0 d^{n} + a_1 d^{n-1} + a_2 d^{n-2} + a_3 d^{n-3} + \ldots + a_n d^{0}) \bmod N \]

Для \(N=2^{32}\) очень популярны значения параметров \(d=31\) и \(a_0=7\).

Главная особенность полиномиальных хешей — возможность быстрой их конкатенации: если \(a\) и \(b\) — две последовательности, то

\[ H(ab) = ((H(a) - a_0)d^{|b|} + H(b)) \bmod N \]

где \(|b|\) — длина последовательности \(b\).

Нетрудно заметить, что сложность такой операции: логарифм длины последовательности \(b\), поскольку возведение в степень по фиксированному модулю — как раз логарифмическая операция.

Хеш-таблицы со списками кандидатов

Появится после окончания срока сдачи домашнего задания.

Хеш-таблицы с неточным расположением данных

Появится после окончания срока сдачи домашнего задания.

Практика программирования

Работа с файлами

Некоторые свойства файлов

Трудно дать достаточно всеобъемлющее определение того, что именно называется словом «файл». Вместо этого перечислим некоторые свойства, которыми файлы обладают:

• у каждого файла есть хотя бы одно имя
• файл может позволять записывать в него данные
• файл может позволять считывать из него данные

При этом, например, не гарантируется, что:

• данные, записанные в файл, можно из него как-либо считать
• две подряд идущие попытки считать данные из файла дадут один и тот же результат

Связано это с тем, что операционные системы обычно позволяют произвольной программе изображать из себя файл.

Общие принципы работы с файлами

Для того, чтобы получить возможность работы с файлом, нужно запросить у операционной системы к нему доступ. Для этого нужно имя файла и режим работы с ним. Режим обычно классифицируется по двум «осям».

Первая — направление:

• чтение
• запись
• дозапись

Вторая — тип файла:

• текстовый
• бинарный

Между текстовым и бинарным режимом есть существенные различия под Windows: текстовый режим производит автоматическое преобразование последовательности символов «возврат каретки, следующая строчка» из файла в одиночный символ «следующая строчка». Связано это с тем, что традиционно в программах принято обозначать переход на следующую строчку текста одним символом ('\n'), а под Windows традиционное окончание строчек в текстовых файлах состоит из двух символов ('\r\n').

В Python есть второе (менее существенное) различие: бинарный режим выдаёт данные как элемент типа bytes (иммутабельный массив байт), а текстовый режим выдаёт данные как элемент типа str.

Работа с файлами в Python

Для того, чтобы получить доступ к файлу, используется функция open. Её первый вход — имя файла. Её второй вход — режим работы. Обычно это одно из следующего:

• 'r' или 'rb' — чтение в текстовом/бинарном режиме
• 'w' или 'wb' — запись в текстовом/бинарном режиме
• 'a' или 'ab' — дозапись в текстовом/бинарном режиме
• 'r+', 'r+b', 'w+', 'w+b', 'a+', 'a+b' — чтение И запись

Чтение выдаёт ошибку, если файл с таким названием не существует. Режимы записи/дозаписи пытается файл создать. Также режим записи стирает старое содержимое файла (если для этого файла вообще определено понятие «содержимое»).

Режимы «с плюсом» отличаются от таковых «без плюса» только дополнительной возможностью записи/чтения. В остальном они ведут себя так же, как и соответствующие режимы «без плюса».

Функция open возвращает объект, посредством которого можно производить действия с файлом. Самые полезные:

• метод read — считывает данные из файла
• метод write — записывает данные в файл
• метод close — завершает работу с файлом («закрывает» его)

Обратите внимание, что программа не может одновременно иметь слишком много открытых файлов. Поэтому их необходимо закрывать сразу по завершении работы. Лучше это делать не вручную, а автоматически, при помощи конструкции:

with open(...) as f:
  какой-то код

Это следует писать вместо:

f = open(...)
какой-то код
f.close()

Первая конструкция работает даже если на участке (какой-то код) присутствует return или возникают исключения.

Сравните две эквивалентных функции (складывающие все числа из указанного файла):

def short_sum(filename):
  with open(filename, 'r') as f:
    return sum([int(x) for x in f.read().split()])

def long_sum(filename):
  f = open(filename, 'r')
  try:
    result = sum([int(x) for x in f.read().split()])
  except:
    f.close()
    raise

  f.close()
  return result

Ещё полезная особенность: объект, возвращённый функцией open, можно использовать как последовательность всех строчек файла. Вот, например, программа, которая считывает из файла названия других файлов, в каждый из которых записывает количество считанных файлов:

with open('files_list', 'r') as f:
  filenames = [name for line in f 
                    for name in [line.strip()]
                    if  name]

for filename in filenames:
  with open(filename, 'w') as f:
    f.write(str(len(filenames)))

Стандартные файлы

В подавляющем большинстве ОС каждой запущенной программе по умолчанию предоставляются три (уже открытых) файла — т.н. стандартный вход, стандартный выход, стандартный поток ошибок. В Python они доступны посредством переменных sys.stdin, sys.stdout, sys.stderr модуля sys.

Такие функции, как input и print работают как раз с этими файлами (впрочем у print можно и поменять используемый файл на произвольный).

Например, input (почти) эквивалентен следующему определению:

import sys

def input(prompt):
    sys.stdout.write(prompt)
    sys.stdout.flush()
    line = sys.stdin.readline()
    if len(line) > 0 and line[-1] == '\n': return line[:-1]
    return line

Тонкий момент: часто реальный input для удобства пользователя работает со стандартным входом не напрямую, как показано в этом примере, а через библиотеку readline, добавляющую к командной строке возможность навигации.

Пример бинарного формата

В отличие от текстовых файлов, содержимое которых (обычно) регламентируется стандартом Unicode, бинарные файлы имеют совершенно произвольную внутреннюю структуру. Чаще всего они начинаются с «метки» — нескольких байт, по которым можно понять, какой именно стандарт регламентирует дальнейшее содержимое. В случае отсутствия такой метки внутри файла в качестве метки может выступать часть названия (чаще всего выделенная слева точкой).

В качестве примера бинарного формата рассмотрим растровый формат TGA (если быть более точным, TGA второго типа).

Файл в формате TGA начинается с 18-байтового заголовка, за которым следует идентификатор изображения (произвольная информация; например, название, дата создания, координаты места фотографии, электронная подпись), за которым следуют цвета пикселей.

Заголовок устроен так (побайтово):

1. Длина (в байтах) идентификатора.
2. Ноль.
3. Два.
4. Ноль.
5. Ноль.
6. Ноль.
7. Ноль.
8. Ноль.
9. Младший байт горизонтальной координаты начала изображения.
10. Старший байт горизонтальной координаты начала изображения.
11. Младший байт вертикальной координаты начала изображения.
12. Старший байт вертикальной координаты начала изображения.
13. Младший байт ширины изображения.
14. Старший байт ширины изображения.
15. Младший байт высоты изображения.
16. Старший байт высоты изображения.
17. Количество бит в пикселе (16, 24 или 32).
18. Битовое поле.

Младшие 4 бита 18-го байта — ширина альфа канала (для 24-битных изображений это 0, для 32-битных это 8). Пятый бит — ноль. Шестой бит отвечает за ориентацию изображения. Ноль в шестом бите означает, что строчки изображения начинаются с самой нижней. Единица — с самой верхней. Старшие два бита — нули.

Пиксели хранятся построчно, слева направо. В 24-битном формате каждый пиксель задаётся тремя байтами: интенсивностями синей, зелёной и красной компонент соответственно. В 32-битном формате к ним добавляется четвёртый байт — значение альфа-канала.

Для того, чтобы работать с TGA-изображениями, можно, например, использовать следующий (максимально упрощённый) интерфейс:

def create_image(width, height):
    return (width, [(0,0,0)]*(width*height))

def image_width(image):
    width, pixels = image
    return width

def image_height(image):
    width, pixels = image
    return len(pixels) // width

def put_pixel(image, x, y, r, g, b):
    width, pixels = image
    pixels[width*y + x] = (r,g,b)

def write_image_tga(image, filename):
    width, pixels = image
    height = image_height(image)

    header = bytes([
        0, 0, 2,
        0, 0, 0, 0, 0,
        0, 0, 0, 0,
        width  % 256, width  // 256,
        height % 256, height // 256,
        24, 0
    ])

    with open(filename, 'wb') as f:
        f.write(header)
        for r,g,b in pixels:
            f.write( bytes([b,g,r]) )

Обратим внимание на то, что TGA-специфична здесь лишь последняя функция. Остальные четыре просто предоставляют некоторый способ работы с растровым изображением. Именно в терминах этих четырёх функций мы будем вести изложение материала в следующем разделе.

Алгоритм Брезенхема

Уравнение прямой на плоскости

Напомним, что прямая на плоскости — это множество всевозможных точек, координаты \(x,y\) которых удовлетворяют уравнению вида

\[Ax+By+C=0\]

для каких-то \(A,B,C\) (\(A\) и \(B\) не должны быть одновременно равны нулю).

У этого уравнения есть очень простой геометрический смысл. Пусть \(X,Y\) — произвольная точка прямой. Тогда \(C=-AX-BY\). Поэтому уравнение можно переписать в виде

\[A(x-X)+B(y-Y)=0\]

Слева (в предположении ортонормированности системы координат) — скалярное произведение вектора с координатами \(A,B\) и направляющего вектора прямой. Равенство скалярного произведения нулю — перпендикулярность. То есть уравнение прямой дословно говорит о том, что прямая — множество всех точек, радиус-вектор которых (относительно некоторой фиксированной точки) перпендикулярен некоторому фиксированному вектору.

Коэффициенты \(A\) и \(B\) легко вычислить, если знать координаты каких-нибудь двух точек на прямой. Если прямая проходит через точки \(x_0,y_0\) и \(x_1,y_1\), то можно взять

\[ A = y_1 - y_0;\qquad B = x_0 - x_1 \]

или любые другие числа, пропорциональные этой паре.

Изображение прямой

Для того, чтобы изобразить прямую на растровом изображении, нужно пометить все пиксели, достаточно близкие к этой прямой (из-за того, что растровое изображение представляет собой целочисленную решётку, уравнению прямой точно удовлетворяет довольно мало пикселей).

В качестве критерия близости пикселя к прямой можно использовать результат его подстановки в левую часть рассмотренного выше уравнения прямой: этот результат является (если вспомнить геометрический смысл скалярного произведения) расстоянием от пикселя до прямой (нормированным величиной \(\sqrt{A^2+B^2}\)).

Именно такой критерий использует алгоритм Брезенхема, строящий отрезок между парой заданных точек. Этот алгоритм (точнее, одну из многочисленных его вариаций) можно грубо описать так:

1. Выбираем два перпендикулярных напраления, направленных от начальной точки отрезка в сторону конечной. Например, вправо и вверх.
2. Закрашиваем начальный пиксель.
3. Создаём переменную, хранящую значение левой части уравнения для текущего пикселя. Её начальное значение — ноль.
4. Пока мы не попали в конечную точку, делаем шаг в одном из выбранных в пункте 1 направлений в зависимости от знака переменной из пункта 3 (или её близости к нулю). Соответствующим образом обновляем эту переменную и красим текущий пиксель.

Основное достоинство этого алгоритма — он вообще не использует никакой арифметики, кроме сложения и сравнения с нулём.

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

def mark_pixel(image, x, y):
    put_pixel(image, x, y, 255, 255, 255)

def draw_line(image, x0, y0, x1, y1):
    y = y0
    error = 0
    A = y1-y0
    B = x0-x1

    for x in range(x0, x1+1):
        mark_pixel(image, x, y)
        
        while error > 0:
            y += 1
            error += B
            mark_pixel(image, x, y)
        
        x += 1
        error += A
    
    mark_pixel(image, x, y)

Вторая реализация более полноценна и работает всегда:

def sign(x):
    if x > 0: return 1
    if x < 0: return -1
    return 0

def draw_line(image, x0, y0, x1, y1):
    x,y = x0,y0
    error = 0
    
    A = y1-y0
    B = x0-x1
    dx, dy = -sign(B), sign(A)

    while x != x1 or y != y1:
        mark_pixel(image, x, y)

        ex = error + A*dx
        ey = error + B*dy

        if abs(ex) < abs(ey):
            x    += dx
            error = ex
        else:
            y    += dy
            error = ey

    mark_pixel(image, x, y)