Предисловие

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

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

Для того чтобы разбираться в алгоритмах, не нужно оканчивать четыре курса университета. Увы, большинство книг и материалов в Сети на эту тему рассчитаны именно на студентов: в них делается упор на математические доказательства и основные постулаты компьютерной науки. Справочники содержат пугающее количество самых разнообразных алгоритмов и бесчисленные их варианты для самых изощренных случаев. Слишком часто читатель сдается уже на первой главе такой книги. Это как читать полный английский словарь с целью подправить правописание: лучше бросить сразу. Куда полезнее взять специализированное пособие: в нем будет сто английских слов, в которых чаще всего ошибаются, а также правила, по которым слова составляются (и исключения из них). Вот так же и людям различных профессий и опыта, когда они хотят применять алгоритмы в своей работе, нужно пособие, нацеленное именно на их нужды.

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

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

Эта книга научит вас основным алгоритмам и структурам данных, принятым в computer science, — с ними ваши программы будут эффективнее. Может помочь при приеме на работу и, несомненно, послужит хорошим началом на пути изучения алгоритмов!

Цви Галиль, почетный декан Технологического института Джорджии, кафедра компьютерных наук им. Фредерика Дж. Стори, Атланта, 2021

---

Введение

Для кого эта книга

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

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

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

Если вы заглянете в сопутствующие книге исходные тексты программ, то найдете там в каждой главе файл book.py — это программа на Python, которая при запуске воспроизводит на вашем компьютере все схемы из книги (рис. В.1).

Рис. В.1. Сводка по тематическому содержанию книги

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

Исходные тексты

Все программы из книги доступны в соответствующем репозитории GitHub: http://github.com/heineman/LearningAlgorithms. Они совместимы с Python 3.4 и выше. Везде, где это было разумно, я старался следовать рекомендациям Python и оформлять системные методы наподобие __str()__ или __len__(). Примеры в книге отформатированы с отступом два пробела — так они лучше помещаются в ширину при печати; в программах репозитория используется стандартный отступ четыре пробела. Изредка в печатных примерах попадаются однострочники, например if j == lo: break.

В программах используются три свободно распространяемые библиотеки 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 — большой сборник эффективных алгоритмов для работы с графами, он нам понадобится в главе 7; там же есть удобная готовая структура данных, реализующая граф. Средства этих библиотек позволят не изобретать очередное колесо, если в этом нет нужды. Если они не установлены, не беда: примеры написаны так, что смогут работать и без них, нужные функции также есть в репозитории.

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

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

В репозитории больше 10 000 строк кода на Python, сценарии для запуска всех тестов и вычисления всех данных для таблиц в книге; можно воспроизвести также большую часть схем и графиков. Исходный текст снабжен, как это принято в Python, строками документации и тестами, причем тестовое покрытие, согласно https://coverage.readthedocs.io, составляет 95 %.

Если у вас возникнут технические вопросы или затруднения в работе примеров, свяжитесь с нами по адресу bookquestions@oreilly.com.

В общем случае все примеры кода из книги вы можете использовать в своих программах и в документации. Вам не нужно обращаться в издательство за разрешением, если вы не собираетесь воспроизводить существенные части программного кода. Если вы разрабатываете программу и используете в ней несколько фрагментов кода из книги, вам не нужно обращаться за разрешением. Но для продажи или распространения примеров из книги вам потребуется разрешение от издательства O’Reilly. Вы можете отвечать на вопросы, цитируя данную книгу или примеры из нее, но для включения существенных объемов программного кода из книги в документацию вашего продукта потребуется разрешение.

Мы рекомендуем, но не требуем добавлять ссылку на первоисточник при цитировании. Под ссылкой на первоисточник мы подразумеваем указание авторов, издательства и ISBN.

За получением разрешения на использование значительных объемов программного кода из книги обращайтесь по адресу permissions@oreilly.com.

Условные обозначения

В книге используются следующие типографические обозначения:

Курсив

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

Шрифт без засечек

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

Моноширинный шрифт

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

Полужирный шрифт

В русском переводе обозначает собственные имена алгоритмов и структур данных.

Кошачий лемур сопровождает совет или подсказку. Из всех приматов, включая человека, у кошачьего лемура самое большое суммарное поле зрения — до 280°. В тексте советы позволяют буквально расширить кругозор: в них изложена познавательная информация или описана интересная возможность Python.

Ворона сопровождает теоретические замечания. Большинство зоопсихологов сходятся на том, что вороны — очень умные птицы: они умеют решать сложные задачи и даже пользоваться предметами. В тексте примечание содержит определение термина или разъяснения важного понятия. Прежде чем читать дальше, их надо внимательно изучить.

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

Благодарности

Я считаю, что лучшее в computer science — это изучение алгоритмов. Спасибо читателям за то, что дали мне возможность поделиться своими наработками. Спасибо моей жене Дженнифер за то, что поддержала меня в затее с очередной книгой. Спасибо моим сыновьям, Николасу и Александру, за то, что они уже выросли и могут изучать программирование.

Эта книга стала лучше благодаря редакторам O’Reilly — Мелиссе Даффилд, Саре Грей, Бет Келли и Вирджинии Вильсон. Они помогали мне систематизировать общее содержание книги и выстраивать пояснения к нему. Технические рецензенты — Лаура Хелливелл, Чарли Лаверинг, Хелен Скотт, Стенли Силков и Аура Веларде — нашли множество неточностей, улучшили реализацию алгоритмов и дали пояснения к ним. Если остались какие-то недочеты — все они целиком на моей совести.

---

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

Глава 1. Решение задач

В этой главе

Несколько алгоритмов решения одной и той же вводной задачи.

Как исследовать производительность алгоритма на входных наборах данных размером N.

Как посчитать количество основных действий, выполненных при обработке конкретного набора данных.

Как определить уровень падения производительности при удвоении входных данных.

Как предсказать сложность алгоритма по времени на основании подсчета действий, которые он выполнит на входных данных размером N.

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

Что ж, начнем!

Что такое алгоритм

Объяснять алгоритм — это как рассказывать сказку. Каждый алгоритм — новый волшебный предмет или неожиданный поступок, которые помогают быстро и легко справиться с казавшейся трудной задачей. В этой главе мы рассмотрим несколько решений нетрудной задачи, а потом разберемся, какой алгоритм эффективнее и почему. Кроме того, поймем, как изучать быстродействие алгоритма независимо от его реализации — хотя непосредственные данные о работе конкретных реализаций у нас тоже будут.

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

Давайте посмотрим, как процесс решения и анализа задачи проходит в жизни. Скажем, нам нужно найти наибольшее значение в несортированном списке. На рис. 1.1, слева, приведено три набора данных для нашей задачи4 — каждый набор в виде списка Python. Данные обрабатываются алгоритмом (изображен в виде цилиндра), который должен выдавать правильный ответ; ответы перечислены в правой части. Как реализован алгоритм решения? Как он себя ведет на различных входных наборах? Можно ли предсказать время работы? Как быстро можно найти наибольшее из миллиона чисел?

Рис. 1.1. Обработка алгоритмом различных наборов входных данных

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

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

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

• Если длина последовательности увеличивается вдесятеро, время вычисления max() на ней тоже увеличивается плюс-минус вдесятеро, как если бы мы каждую проверку делали вручную.

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

Таблица 1.1. Запуск функции max() на двух типах наборов входных данных размером N5

N	Восходящая последовательность	Нисходящая последовательность
100	0.001	0.001
1000	0.013	0.013
10 000	0.135	0.125
100 000	1.367	1.276
1 000 000	14.278	13.419

Замечания о времени работы

• Невозможно с уверенностью предсказать время работы алгоритма на наборе, допустим, из 100 000 элементов (обозначим это время T(100 000)). Для разных языков программирования и на разных компьютерах оно будет разным.

• Однако, зная T(10 000), предсказать T(100 000) — время работы на десятикратно больших данных можно, хотя погрешность такого предсказания неизбежна.

Когда придумываешь алгоритм, важнее всего убедиться, что он работает правильно на всех допустимых наборах входных данных. Как сравнивать свойства двух алгоритмов, если они решают одну и ту же задачу? Этим мы по большей части займемся в главе 2. Изучение алгоритма тесно связано с интересными задачами из настоящей жизни, в которых он требуется. Математическая сторона алгоритма может быть непростой, но мы постараемся каждое отвлеченное понятие связать с таким вопросом жизненной практики.

Принято думать, что оценить эффективность алгоритма — значит подсчитать, сколько ему потребовалось вычислительных операций. Но как раз это совсем не просто! Центральный процессор компьютера (CPU) исполняет машинные инструкции — арифметические операции (наподобие сложения и умножения), пересылку данных из памяти в регистры процессора, сравнения и т.п. Современные языки программирования бывают как компилируемые (С или C++), в которых текст программы перед запуском транслируется в машинные инструкции, так и интерпретируемые (Python или Java). Программа на интерпретируемом языке транслируется в промежуточное представление, называемое байт-кодом. Затем программа-интерпретатор, Python например (в свою очередь сам написанный на С и откомпилированный), разбирает и выполняет этот байт-код6. При этом некоторые функции, например min() и max(), встро­ены в Python — они написаны на С, скомпилированы в машинные инструкции и так выполняются.

Массив всемогущий Массив — фиксированный набор однотипных значений, занимающий один непрерывный фрагмент оперативной памяти. Это одна из самых старых и самых надежных структур данных. Если значений больше одного — программисты хранят их в массиве. На схеме изображен целочисленный массив из восьми элементов: В массиве A восемь ячеек. Каждая ячейка доступна по номеру, например, A[0] — это 31, а A[7] — 5. В массивах можно хранить и строки, и вообще любые объекты сколь угодно сложного типа. Что следует знать о массивах. Начальный элемент массива A длиной N имеет индекс 0 и обозначается A[0], конечный обозначается A[N-1] и имеет индекс N – 1. Зная номер i элемента в массиве, можно прочитать оттуда элемент Ae[i] или записать на место A[i] новое значение. При этом i — это индекс в диапазоне от 0 до N – 1. Длина массива всегда известна. В Python и Java ее можно задать в процессе работы программы, а в С — только заранее. Чтобы изменить длину массива, необходимо выделить память под новый массив нужной длины и скопировать туда все данные из старого. Просто так размер массива уменьшить или увеличить нельзя. Несмотря на простоту, массивы — очень гибкий и удобный инструмент организации данных. В Python имеется тип данных list, с которым можно смело работать как с массивом, хотя его возможности куда шире: в list можно хранить объекты разных типов одновременно, а размер его может меняться в процессе работы программы.

Посчитать, сколько машинных инструкций выполнилось при работе алгоритма, практически невозможно — современные компьютеры выполняют их миллиардами за секунду! Давайте вместо этого считать, сколько основных действий выполнил алгоритм. Вопрос «Сколько действий?» может означать «Сколько раз сравнивались два элемента массива?» или, к примеру, «Сколько раз вызывалась некоторая функция?». В случае max() нас будет интересовать, сколько раз вызывалась операция сравнения «меньше» (>). Подробнее о правилах подсчета действий мы поговорим в главе 2.

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

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

Рассмотрим проблемную реализацию поиска наибольшего значения произвольной последовательности в примере 1.1. Каждый элемент A сравнивается с my_max, и, если найдено значение больше, my_max обновляется.

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

def flawed(A):

  my_max = 0        ❶

  for v in A:       ❷

    if my_max < v:

      my_max = v    ❸

  return my_max

❶ Переменная my_max хранит текущее наибольшее значение. Здесь она инициа­лизируется нулем.

❷ В цикле for определена переменная v, которая на каждом проходе цикла равна очередному элементу A. Оператор if внутри цикла выполняется для каждого такого v.

❸ Переменная my_max обновляется, если v оказалось больше.

Главное в нашем решении — операция сравнения двух выражений (<), которая определяет, меньше ли первое выражение второго. На рис. 1.2 показано, что по мере прохождения переменной v всех значений из A переменная my_max меняется трижды. Функция flawed() определяет наибольшее значение A из шести элементов, вызывая оператор < не более шести раз, по одному разу на каждый элемент. Если в наборе данных будет N элементов, flawed() вызовет < не более N раз.

Рис. 1.2. Как работает flawed()

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

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.

Подсчет действий

Первоначальное значение my_max лучше выбрать из элементов A — тогда можно быть уверенными, что вычисленное наибольшее значение будет тоже из A. Работающая на всех входных наборах, кроме пустых, а значит, правильная функция largest() приведена в примере 1.2. Здесь мы выбираем в качестве начального значения my_max начальный элемент A, а затем сравниваем его со всеми остальными: вдруг там найдется побольше?

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

def largest(A):

  my_max = A[0]                 ❶

  for idx in range(1, len(A)):  ❷

    if my_max < A[idx]:

      my_max = A[idx]           ❸

  return my_max

❶ Сделаем my_max равным начальному элементу списка (он доступен по индексу 0).

❷ Переменная idx принимает целочисленные значения от 1 до len(A)-1 включительно, не достигая len(A).

❸ Если в A по индексу idx стоит большее значение, обновить my_max.

Если передать largest() пустой список — largest([]), в первой же строчке возникнет исключение IndexError, потому что никакого элемента A[0] в списке нет. Встроенная функция max([]) для пустого списка порождает исключение ValueError с пояснением о том, что пустые последовательности не входят в область определения max(). Так программисту проще понять, в чем его ошибка.

В исправленном алгоритме можно уже начинать считать количество действий. Сколько раз вызывалась в нем операция сравнения <? Правильно, N – 1 раз. Значит, мы не только избежали ошибки, но и улучшили производительность алгоритма (по правде говоря, совсем чуть-чуть).

Почему важно считать именно операции сравнения? Это действие, описанное в алгоритме, — сравнить два значения. Другие операторы в программе (например, for или while) выбираются в соответствии с возможностями используемого языка программирования и вполне могут отличаться. Подробнее об этом мы поговорим в следующей главе, а пока продолжим считать сравнения7.

Как оценить эффективность алгоритма по схеме

Допустим, нам предлагают совсем иной алгоритм решения нашей задачи. На каком из них остановиться? Рассмотрим функцию alternate() из примера 1.3. В ней каждое значение из A сравнивается со всеми остальными, и, если выяснится, что оно не меньше, это и есть ответ. Выдаст ли этот алгоритм правильный ответ? И сколько раз в нем выполняется сравнение на входных данных размером N?

Пример 1.3. Другой способ найти наибольшее значение в списке A

def alternate(A):

    for v in A:         ❶

        for x in A:

            if v < x:   ❷

                break

        else:

            return v    ❸

    return None         ❹

❶ Для каждого v из A рассмотрим все x из A и сравним их.

❷ Если v меньше какого-то x, можно больше не сравнивать: это не максимум.

❸ Если мы просмотрели все x, так ни разу и не выполнив break, значит, v — это максимум и его можно уже возвращать.

❹ До этого места выполнение дойдет только при пустом A. В таком случае вернем специальный объект Python — None.

Функция alternate() пытается найти такое значение v из A, чтобы никакое другое значение x из A не оказалось больше него. На этот раз сложно предсказать, сколько потребуется операций сравнения, потому что внутренний цикл по x сразу останавливается, как только выясняется, что x больше v, а внешний — как только v оказывается максимумом. Работа alternate() показана на рис. 1.3.

В данном случае было выполнено 14 сравнений. Впрочем, очевидно, что общее количество действий зависит от того, какие конкретно значения находятся в списке. Что, если бы они шли в другом порядке? Например, так, чтобы для ответа потребовалось как можно меньше действий? Такой набор данных называется лучшим случаем для alternative(). Например, если наибольший из N элементов последовательности стоит в ее начале, количество сравнений в точности равно N. Итак:

• лучший случай — набор данных размером N, на котором алгоритм совершает наименьшее количество действий;

• худший случай — набор данных размером N, требующий наибольшего количества действий.

Рис. 1.3. Как работает alternate()

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

На рис. 1.4 показан наилучший случай, в котором A = [9 5 2 1 3 4], и наихудший случай, в котором A = [1 2 3 4 5 9].

Рис. 1.4. Как работает alternate() в лучшем и худшем случаях

В проиллюстрированном лучшем случае функция делает шесть сравнений >. Если значений всего N, сравнений будет N. В худшем случае подсчет действий слегка сложнее (табл. 1.2). На рис. 1.4 видно, что шесть элементов, упорядоченные по возрастанию, потребовали 26 сравнений. Немного арифметики, и становится понятно, что для N элементов число сравнений будет равно

Таблица 1.2. Сравнение работы largest() и alternate() в худших случаях

N	largest() (количество сравнений)	alternate() (количество сравнений)	largest() (время в миллисекундах)	alternate() (время в миллисекундах)
8	7	43	0.001	0.001
16	15	151	0.001	0.003
32	31	559	0.002	0.011
64	63	2143	0.003	0.040
128	127	8383	0.006	0.153
256	255	33 151	0.012	0.599
512	511	131 839	0.026	2.381
1024	1023	525 823	0.053	9.512
2048	2047	2 100 223	0.108	38.161

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

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

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

Подсчет количества сравнений показывает, как работают функции largest() и alternate(). При удвоении N количество сравнений в largest() удваивается, а в alternate() — увеличивается вчетверо. Это поведение вполне стабильно, и несложно предсказать, как оба алгоритма поведут себя на данных большего размера. На рис. 1.5 показано, что количество сравнений в функции alternate() (отмечено по оси Y с левой стороны) довольно точно соответствует ее производительности (затраченное время отмечено по оси Y с правой стороны).

Рис. 1.5. Соотношение количества сравнений и времени работы

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

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

В табл. 1.3 показано, что время, которое тратится на работу с данными при увеличении их размера, вполне предсказуемо. Если знать, сколько времени потратили largest() и max() на наборе длиной N, можно вычислить время, которое они затратят, если увеличить этот набор вдвое.

Таблица 1.3. Быстродействие largest() и max() в лучшем и худшем случаях

N	largest(), худший случай	max(), худший случай	largest(), лучший случай	max(), лучший случай
4096	0.20	0.05	0.14	0.05
8192	0.40	0.11	0.29	0.10
16 384	0.80	0.21	0.57	0.19
32 768	1.60	0.41	1.14	0.39
65 536	3.21	0.85	2.28	0.78
131 072	6.46	1.73	4.59	1.59
262 144	13.06	3.50	9.32	3.24
524 288	26.17	7.00	18.74	6.50

Теперь слегка поменяем условия задачи — так она станет поинтереснее.

Поиск двух наибольших значений в произвольном списке

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

В примере 1.4 показано возможное решение этой задачи.

Пример 1.4. Поиск двух максимумов с помощью отредактированной функции largest_two()

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)

❶ Предположим, что my_max и second — первые два значения в списке. Если порядок обратный — поменяем их местами.

❷ Если A[idx] больше подходит на роль максимума, сделаем my_max равным [idx], а second — равным my_max.

❸ Если A[idx] больше second, но меньше my_max, обновим только его.

Функция largest_two() работает похоже на largest(). Сначала предполагается, что my_max и second — это первые два элемента A (порядок проверяется). Затем для всех оставшихся элементов A (сколько их? Ну да, N – 2) проверяется очередной A[idx], и, если он больше my_max, обновляются обе переменные, а если он больше только second, обновляется только second.

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

Реже всего largest_two() будет сравнивать значения, если условие оператора if внутри цикла окажется всегда истинным. Например, если в A каждый следующий элемент больше предыдущего, то сравнение их оператором < всегда истинно, так что всего таких сравнений будет N – 2 — плюс еще одно, которое мы сделали в самом начале функции. Выходит, что в лучшем случае нам потребуется только N – 1 сравнений для поиска двух максимумов. Сравнение в условии при elif в лучшем случае не используется вообще.

Можно попробовать построить наихудший для largest_two() набор данных — в нем сравнение в условии оператора if внутри цикла всегда должно быть ложным.

Наверняка уже понятно, что больше всего сравнений largest_two() делает, когда элементы в A упорядочены по убыванию. Строго говоря, в наихудшем случае должны выполняться оба сравнения на каждом обороте цикла, что дает нам оценку 1 + 2 (N – 2) = 2N – 3 действий.

Таким образом, функция largest_two():

• в лучшем случае тратит N – 1 сравнений на поиск обоих ответов;

• в худшем случае тратит на аналогичный поиск 2N – 3 сравнений.

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

• Дополнительная память. Не требуется ли в алгоритме дублировать исходные данные?

• Трудоемкость. Много ли строк в исходной программе?

• Изменение исходных данных. Требуется ли в алгоритме менять непосредственно введенные данные, или их можно не трогать?

• Скорость. Действительно ли алгоритм работает не хуже других на всех возможных входных наборах данных?

В примере 1.5 рассмотрим еще три алгоритма, которые решают ту же задачу. Функция sorting_two() создает из A новый — отсортированный по убыванию — список, так что первые два его элемента и есть ответ. Функция double_two() находит максимум в A с помощью max(), создает копию A, удаляет оттуда этот элемент и ищет второй ответ тем же самым max() по урезанной копии. Функция mutable_two() находит индекс наибольшего элемента в списке, удаляет его оттуда на время, ищет второй ответ в урезанном списке, после чего вставляет удаленный элемент обратно. Первые два алгоритма нуждаются в дублировании исходных данных, третий изменяет их непосредственно; для всех трех алгоритмов в наборе данных должно быть больше одного элемента.

Пример 1.5. Еще три способа решить задачу средствами самого Python

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.

Все три способа не используют сравнений явно, потому что используют встроенные функции Python. Функции sorting_two() и double_two() копируют исходный список A, а largest_two() — нет; видимо, это не обязательно. Вдобавок сортировать весь список ради всего двух первых элементов тоже кажется излишним. Для обеих функций, задействующих дополнительную память, эту память можно посчитать тем же способом, каким мы считали количество сравнений — и там и там получится прямо пропорционально N. Третий вариант, mutable_two(), ненадолго изменяет A: удаляет оттуда элемент, а затем добавляет обратно. В программе, откуда была вызвана mutable_two(), возможно, не рассчитывали на то, что A будут изменять.

Если позволить себе конструкции Python посложнее — ввести специальный класс RecordedItem9, можно отследить, сколько операций сравнения < потребует любой алгоритм. Из табл. 1.4 видно, что double_two() делает больше всего сравнений на возрастающей последовательности, а все largest_two() и все остальные — на убывающей. Последний столбец — «Вперемежку» — характеризует работу функций на последовательности, в которой на четных местах элементы возрастают, а на нечетных — убывают. Например, для N = 8 перемежающаяся последовательность выглядит как [0,7,2,5,4,3,6,1].

Таблица 1.4. Производительность других вариантов решения на нисходящих и восходящих последовательностях

Алгоритм	По возрастанию	По убыванию	Вперемежку
largest_two	524 287	1 048 573	1 048 573
sorting_two	524 287	524 287	2 948 953
double_two	1 572 860	1 048 573	1 048 573
mutable_two	1 048 573	1 048 573	1 048 573
tournament_two	524 305	524 305	524 305

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

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

Турнирное дерево

В состязаниях на вылет выявляется победитель среди нескольких команд. Лучше всего, если количество команд изначально равно какой-нибудь степени двойки, например 16 или 64. Розыгрыш состоит из нескольких туров, в каждом из которых все оставшиеся команды разбиваются на пары для игры. Каждый проигравший в паре выбывает из соревнований, а остальные переходят на следующий круг. Команда, выигравшая в финале, объявляется победителем.

Предположим, нам надо найти максимум в списке p = [3,1,4,1,5,9,2,6] длиной N = 8. На рис. 1.6 показан розыгрыш на вылет, в первом туре которого попарно сравниваются восемь значений, и те, что больше, переходят на второй10. В туре «Великолепной Восьмерки» выбывают четыре значения, и остается [3,4,9,6], из тура «Чемпионской Четверки» в финал выходят [4,9], и в результате победителем становится 911.

Рис. 1.6. Турнирное дерево с восемью участниками

Для применения турнирного дерева требуется семь сравнений (по одному на игру), и это обнадеживает: как мы уже говорили, это означает, что на поиск максимума в наборе данных размером N требуется N – 1 сравнений. Если запоминать все эти сравнения, нетрудно показать, что второе наибольшее значение находится быстро.

Где может «прятаться» второе наибольшее значение, если победителем объявлено 9? Начнем со значения 4, раз уж оно добралось до финала и проиграло только там. Однако победитель, 9, участвовал еще в двух играх, так что надо проверить еще двух проигравших — 6 из тура «Четверки Чемпионов» и 5 из тура «Великолепной Восьмерки». Получается, что второй ответ — 6.

Чтобы выяснить, что 6 — второе наибольшее значение, для длины списка 8 достаточно двух дополнительных сравнений — «4 меньше 6?» и «6 меньше 5?». То, что 8 = 23, а сравнений было 3 – 1 = 2 — не совпадение. Действительно, для N = 2K необходимо K – 1 дополнительных сравнений, при этом K оказывается количеством туров в розыгрыше.

Для 8 = 23 элементов алгоритму требуется розыгрыш из трех туров. На рис. 1.7 приведен розыгрыш из пяти туров, соответствующий 32 элементам. Если удвоить количество элементов, потребуется еще один тур. Иными словами, в туре под номером K может участвовать 2K элементов. Нужно найти максимум среди 64 элементов? Потребуется шесть туров, потому что 26 = 64.

Рис. 1.7. Турнирное дерево c 32 участниками

Чтобы определить, сколько туров потребуется для произвольного N, используем логарифмическую функцию log() — это обратная к показательной функции, exp(). Для N = 8 элементов на весь розыгрыш требуется три тура, потому что 22 = 8, и, стало быть, log28 = 3. В нашей книге, как и в большинстве задач оценки сложности, используется логарифм с основанием 2 — двоичный.

Большинство настольных калькуляторов (а заодно Microsoft Excel) по команде log() вычисляют десятичный логарифм (по основанию 10). В них также есть команда ln() для вычисления натурального логарифма, основание которого равно константе e (примерно 2.7182818). Чтобы вычислить двоичный логарифм с помощью любой из этих функций, надо поделить результат на логарифм двух: log(N) / log(2).

Если N — степень двойки, например 64 или 65 536, в розыгрыше будет log2(N) туров, а это значит, что потребуется еще log2(N) – 1 сравнений. В примере 1.6 приведен алгоритм, который сводит к минимуму количество сравнений за счет дополнительной памяти, где откладываются результаты этих сравнений.

Пример 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 дополнительное сравнение на «меньше».

Рисунок 1.8 показывает работу нашего алгоритма. Начальный шаг превращает N значений исходного списка A в N / 2 значений в winners и losers; на рис. 1.6 это четыре пары. На следующем шаге с каждым проходом цикла while победитель и проигравший в очередной игре под номером idx (они находятся на соседних позициях m и m+1) помещаются соответственно в winner[idx] и loser[idx]. В prior[idx] мы записываем предыдущую позицию выигравшего, с которой он попал в эту игру (обозначено стрелкой справа налево). После трех шагов мы имеем всю информацию о розыгрыше, и алгоритм проверяет всех проигравших в играх с чемпионом — последовательность, которую можно проследить по стрелкам от чемпиона назад. Второе наибольшее значение можно найти всего двумя сравнениями, что больше — начальный кандидат (найденный в loser[6]), loser[5] или loser[2].

Рис. 1.8. Пошаговое выполнение алгоритма с использованием турнирного дерева

Итак, мы описали алгоритм поиска двух наибольших элементов A, которому нужно всего N – 1 + log2(N) – 1 = N + log2(N) – 2 сравнений на «меньше» для любого N, равного степени двойки. А насколько практична функция tournament_two()? Работает ли она быстрее largest_two()? Если считать только сравнения элементов на «меньше», tournament_two() должна быть быстрее. На наборе данных длиной N = 65 536 функция largest_two() выполняет 131 069 сравнений, а tournament_two() — только 65 536 + 16 – 2 = 65 550, то есть примерно половину. Но история на этом не кончается.

Таблица 1.5 показывает, что функция tournament_two() значительно медленнее всех своих соперниц! Достаточно посмотреть, сколько времени у нее уходит на обработку ста случайных наборов данных, размер которых растет от 1024 до 2 097 152 элементов. Раз уж мы об этом заговорили, давайте еще добавим в таблицу производительность функций из примера 1.5. Если программу с примерами запускать на другом компьютере, конкретные результаты получатся другими, но общая закономерность сохранится.

Таблица 1.5. Сравнение времени работы в миллисекундах всех четырех алгоритмов

N	double_two	mutable_two	largest_two	sorting_two	tournament_two
1024	0.00	0.01	0.01	0.01	0.03
2048	0.01	0.01	0.01	0.02	0.05
4096	0.01	0.02	0.03	0.03	0.10
8192	0.03	0.05	0.05	0.08	0.21
16 384	0.06	0.09	0.11	0.18	0.43
32 768	0.12	0.20	0.22	0.40	0.90
65 536	0.30	0.39	0.44	0.89	1.79
131 072	0.55	0.81	0.91	1.94	3.59
262 144	1.42	1.76	1.93	4.36	7.51
524 288	6.79	6.29	5.82	11.44	18.49
1 048 576	16.82	16.69	14.43	29.45	42.55
2 097 152	35.96	38.10	31.71	66.14	…

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

В таблице можно заметить кое-что неожиданное: к примеру, double_two() поначалу ведет себя как самое быстрое решение, но с ростом N (после N > 262.144) уступает пальму первенства largest_two(). А хитрая наша tournament_two() оказалась ужасно медленной — она тратит много времени на создание и обработку вспомогательных списков, размер которых даже больше, чем объем входных данных. Она настолько медленно работает, что на самых больших наборах даже не проверяется — это было бы слишком долго.

Чтобы получить представление обо всех этих числах, посмотрим на рис. 1.9, где в виде графиков представлена зависимость производительности от роста объема данных.

Рис. 1.9. Сравнение тестов производительности

Графики показывают особенности работы всех пяти алгоритмов.

• Видно, что производительность mutable_two(), double_two() и largest_two() примерно одинакова, но явно отличается от производительности двух других функций. Можно сказать, что эти три функции образуют «семейство»: графики их производительности — прямые линии, предсказать продолжение которых, по-видимому, просто.

• Функция tournament_two() — самая медленная, и ее график заметно отличается от прочих. Измерений сделано немного, поэтому до конца не ясно, будет ли график продолжать расти вверх или тоже в конце концов превратится в прямую.

• Функция sorting_two() явно получше, чем tournament_two(), однако медленнее остальных трех. А ее график? Будет ли он и дальше изгибаться кверху или стремиться к прямой?

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

Сложность по времени и сложность по памяти

Сложно посчитать, сколько конкретных машинных инструкций (например, сложений, присваиваний или ветвлений) выполнила программа: это зависит от языка программирования, тем более что некоторые из них, например Python или Java, требуют для работы интерпретатор. Но если общее число выполненных инструкций посчитать можно, то можно исследовать, как оно зависит от объема входных данных. Задача оценки сложности по времени — получить некоторую формулу C(N), которая вычисляла бы количество инструкций, выполненных некоторым алгоритмом, как функцию от N — размера набора входных данных.

Предположим, выполнение одной машинной инструкции центральным процессором некоторого компьютера требует фиксированного времени t. Тогда время T, затраченное на работу алгоритма на этом компьютере, можно выразить как T(N) = t × C(N). Пример 1.7 подтверждает догадку о том, что самое важное — это структура программы. Можно в точности посчитать, сколько потребуется сложений вида ct = ct + 1 для работы функций f0(), f1(), f2() и f3() на входных данных размером N.

Пример 1.7. Четыре различные функции с разной вычислительной сложностью

def f0(N):     def f1(N):           def f2(N):            def f3(N):

  ct = 0         ct = 0               ct = 0                ct = 0

  ct = ct + 1    for i in range(N):   for i in range(N):    for i in range(N):

  ct = ct + 1      ct = ct + 1          ct = ct + 1           for j in range(N):

  return ct      return ct              ct = ct + 1             ct = ct + 1

                                        ct = ct + 1         return ct

                                        ct = ct + 1

                                        ct = ct + 1

                                        ct = ct + 1

                                        ct = ct + 1

                                      return ct

Функция f0() всегда выполняет одно и то же количество действий, независимо от N. Количество действий в f2() всегда в семь раз больше, чем в f1(); при удвоении N обе функции выполняют в два раза больше действий. Количество действий, выполняемых f3(), растет гораздо быстрее. Мы такое уже видели: N удваивается, сложность f3(N) вырастает в четыре раза (табл. 1.6). Получается, что f1() и f2() больше похожи друг на друга, чем на f3(). В следующей главе мы обсудим важную роль, которую играют циклы и вложенные циклы при оценке сложности алгоритма.

Таблица 1.6. Количество действий в различных функциях

N	f0	f1	f2	f3
512	2	512	3584	262 144
1024	2	1024	7168	1 048 576
2048	2	2048	14 336	4 194 304

Когда мы исследуем алгоритм, важно установить его сложность по памяти — посчитать, сколько дополнительной памяти требуется на обработку входных данных размером N. Под памятью может подразумеваться занимаемое место в файловой системе или объем оперативной памяти, который требуется для работы. Функция largest_two() потребляет меньше всего памяти: в ней определены лишь три переменные — my_max, second и переменная цикла idx. Каким бы ни был объем входных данных, размер дополнительной памяти не меняется. Следовательно, сложность по памяти не зависит от размера входных данных, то есть является константой. Так же ведет себя и функция mutable_two(). А вот tournament_two() заводит аж три дополнительных списка размером N – 1 — winner, loser и prior. Так что при увеличении N объем дополнительной памяти увеличивается прямо пропорционально объему входных данных12. Необходимость создавать турнирную таблицу делает работу tournament_two() заметно медленнее по сравнению с largest_two(). Еще две функции — double_two() и sorting_two() — дублируют входные данные (список A), так что их потребление памяти скорее похоже на таковое у tournament_two(), чем у largest_two(). В книге мы будем исследовать и сложность по времени, и сложность по памяти каждого алгоритма.

Если еще раз посмотреть на табл. 1.5, можно заметить, что числа в столбце largest_two с каждой строкой становятся примерно в два раза больше. Мы уже подчеркивали, что столбцы double_two и mutable_two устроены в целом так же. Значит, время работы этих алгоритмов прямо пропорционально объему входных данных, который тоже удваивается на каждой строке. Это важное свойство, ибо эти функции быстрее, чем sorting_two(), а у нее и график быстродействия выглядит по-другому — менее эффективным. Самая медленная — tournament_two(), скорость ее работы падает настолько быстрее, чем вдвое, что под конец, на самых больших наборах, мы ее даже не запускали.

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

Заключение

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

Мы рассмотрели несколько важных понятий, в частности:

• сложность по времени, которая оценивается подсчетом количества основных действий алгоритма на наборе входных данных размером N;

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

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

Тренировочные задания

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

Пример 1.8. Довольно медленные функции — определители палиндрома

def is_palindrome1(w):

  """Сделаем секцию, содержащую все символы в обратном порядке,

  и проверим ее на наличие w."""

  return w[::-1] == w

def is_palindrome2(w):

  """Если первый и последний символы равны, удалим их.

  Если они не равны — вернем False."""

  while len(w) > 1:

      if w[0] != w[-1]:     # если не равны, вернем False

        return False

      w = w[1:-1]           # удаляем в цикле первый и последний символы

    return True             # это точно палиндром

После того, как функция заработает, дополните ее: научите определять палиндромы-фразы, в которых пробелы и знаки пунктуации игнорируются, а строчные и прописные буквы не отличаются. Например, вот эта строка — палиндром: Я не стар, брат Сеня!.

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

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

import random

def partition(A, lo, hi, idx):

  """Разделение A на две части относительно значения A[idx]."""

  if lo == hi: return lo

  A[idx],A[lo] = A[lo],A[idx]    # ставим в нужную позицию

  i = lo

  j = hi + 1

  while True:

    while True:

      i += 1

      if i == hi: break

      if A[lo] < A[i]: break

    while True:

      j -= 1

      if j == lo: break

      if A[j] < A[lo]: break

    if i >= j: break

    A[i],A[j] = A[j],A[i]

  A[lo],A[j] = A[j],A[lo]

  return j

def linear_median(A):

  """

  Быстрая реализация поиска медианы в произвольном списке.

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

  Обратите внимание на то, что при работе алгоритма

  порядок элементов в A меняется.

  """

  lo = 0

  hi = len(A) - 1

  mid = hi // 2

  while lo < hi:

    idx = random.randint(lo, hi)  # случайный выбор допустимого индекса

    j = partition(A, lo, hi, idx)

    if j == mid:

      return A[j]

    if j < mid:

      lo = j+1

    else:

      hi = j-1

  return A[lo]

Реализуйте другой способ (для него потребуется дополнительная память): отсортируйте список и верните в качестве ответа его средний элемент (то есть медиану). Сравните быстродействие этого алгоритма с работой linear_median(), составив таблицу тестов производительности.

3. Сортировка подсчетом. Если известно, что некоторый (произвольный) список A состоит только из целых чисел в диапазоне от 0 до M, его можно отсортировать за линейное время, используя дополнительную память размером M.

Хотя в примере 1.10 есть вложенные циклы — for внутри while, — количество присваиваний вида A[pos+idx] = v все равно ровно N. Докажите это!

Пример 1.10. Сортировка подсчетом за линейное время

def counting_sort(A, M):

  counts = [0] * M

  for v in A:

    counts[v] += 1

  pos = 0

  v = 0

  while pos < len(A):

    for idx in range(counts[v]):

      A[pos+idx] = v

    pos += counts[v]

    v += 1

Проанализируйте быстродействие и покажите, что время при удвоении N сортировки N элементов в диапазоне от 0 до M также удваивается.

Внутреннего цикла в counting_sort() можно избежать, если воспользоваться присваиванием секций списка. Если написать что-то вроде список[нача­ло:конец] = [1, 2, 3], то элементы списка в позициях от начала до конца заменятся значениями 1, 2, 3. Измените counting_sort() и проверьте на практике, что время работы, как и прежде, удваивается при удвоении N, но новая функция работает на 30 % быстрее старой.

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

5. Насколько хорошо функция из примера 1.11 находит два наибольших значения в списке A?

Пример 1.11. Еще одна попытка найти два наибольших значения в неупорядоченном списке

def two_largest_attempt(A):

  m1 = max(A[:len(A)//2])

  m2 = max(A[len(A)//2:])

  if m1 < m2:

    return (m2, m1)

  return (m1, m2)

При каких условиях функция работает правильно, а при каких — неправильно? Опишите эти условия.

---

Глава 2. Анализ алгоритмов

В этой главе

Как пользоваться обозначением «О большое» для определения класса вычислительной сложности алгоритма по времени или по памяти.

Какие бывают основные классы сложности, например:

O(1) — константный;

O(log N) — логарифмический;

O(N) — линейный;

O(N log N) — N-логарифмический;

O(N2) — квадратичный.

Как применять асимптотический анализ по N для оценки времени работы (или потребляемой памяти) алгоритма на наборе данных размером N.

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

Как устроен алгоритм двоичного поиска элемента в сортированном списке.

В главе вводятся обозначения и терминология из теории сложности алгоритмов, которые на практике используются для оценки их быстродействия и объема потребляемой ими памяти. Если некоторая программа работает без нареканий — вполне быстро с любыми данными, что попадаются на практике, — скорее всего, ее не стоит улучшать. Книга посвящена тому, с чего начинать, когда требуется улучшить быстродействие, — алгоритмам и структурам данных. И тогда возникают такие вопросы.

• Точно ли нынешнее решение — самое эффективное? Вполне могут существовать алгоритмы, которые решают задачу значительно быстрее.

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

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

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

Как оценить сложность с помощью эмпирической модели

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

И вот вы уже написали работающий прототип, но тестируете его на небольших наборах данных — по 100, 1000 и 10 000 элементов. В табл. 2.1 зафиксировано время работы прототипа на этих данных.

Таблица 2.1. Время работы прототипа

N	Время в секундах
100	0.063
1000	0.565
10 000	5.946

Можно ли по этим предварительным результатам прогнозировать время работы прототипа на больших наборах данных, например на 100 000 или 1 000 000 значений? Попробуем построить математическую модель на основании только этих результатов и найдем некоторую функцию T(N), которая будет предсказывать время работы на данных заданного объема. Достоверная модель не только вычислит T(N) достаточно близко к трем значениям из табл. 2.1, но еще и предскажет время работы на больших наборах, представленное в табл. 2.2 (известные нам результаты указаны в ней в квадратных скобках).

Возможно, вы пользовались инструментами, которые умеют находить линейную регрессию заданного набора данных, например Maple (https://maplesoft.com) или Microsoft Excel (https://microsoft.com/excel). Регрессионные модели можно построить и с помощью SciPy — библиотеки Python для математических, общенаучных и инженерных расчетов. В примере 2.1 показано, как с помощью SciPy подобрать константы a и b в линейном приближении TL(N) = a × N + b. Функция curve_fit() возвращает пару коэффициентов (a, b) линейного приближения на основании экспериментальных данных, которые передаются ей в списках xs и ys.

Строго говоря, дело обстоит так. Мы передаем в curve_fit() три параметра — векторную функцию linear_model(), массив xs и массив ys с известными значениями этой функции. Функция linear_model() — непростая. Во-первых, первый ее операнд, v, — это не число, а массив numpy, умножение которого на число или сложение с числом приводят к поэлементному выполнению соответствующих операций. Остальные операнды этой функции — a и b — коэффициенты. Их-то и подбирает curve_fit() методом наименьших квадратов и возвращает в виде массива. Она также возвращает матрицу ковариации, но для данного исследования она не нужна. По договоренности «ненужные» значения принимает специальная переменная с именем _.

Пример 2.1. Построение приближения на неполных данных

import numpy as np

from scipy.optimize import curve_fit

def linear_model(v, a, b):

  return a*v + b

# Экспериментальные данные

xs = [100, 1000, 10000]

ys = [0.063, 0.565, 5.946]

# Первое возвращаемое значение — массив из двух коэффициентов

(a, b), _ = curve_fit(linear_model, xs, ys)

print(f'Linear = {a}*N + {b}')

Полученная математическая модель выражается формулой TL(N) = 0.000596 × N – – 0.012833. Из табл. 2.2 понятно, что это приближение не слишком достоверно: чем больше размер входного набора, тем сильнее прогноз времени работы прототипа отстает от результатов эксперимента. Можно попробовать повысить степень N до второй и построить квадратичное приближение:

    def quadratic_model(v, a, b):

      return a*v*v + b*v;

В приведенном примере можно заметить две хитрости: во-первых, в формуле квадратного трехчлена свободный член c равен нулю (потому что время работы на пустом наборе данных полагается нулевым), во-вторых, вместо универсальной операции возведения в степень используется умножение, потому что оно в данном случае быстрее. На всякий случай стоит еще раз заметить, что v — это целый массив numpy, арифметические операции над которым производятся поэлементно. Например, в результате v * v получается массив квадратов исходных элементов v.

Задача анализа — подобрать такие параметры a и b функции quadratic_model(), чтобы полученная формула TQ(N) = a × N2 + b × N соответствовала имеющимся данным. Если исследовать ее по аналогии с примером 2.1, получится формула TQ(N) = 0.000000003206 × N2 + 0.000563 × N. Таблица 2.2 показывает, что эта модель тоже недостоверна: ее прогноз времени работы на больших наборах тем сильнее опережает экспериментальные результаты, чем больше данных в наборе.

Большинство найденных нами коэффициентов, например 0.000000003206, то есть 3.206 × 10–9, — довольно малые числа. Это происходит оттого, что наши алгоритмы работают на больших наборах данных, где N = 1 000 000 и даже больше. Тот же миллион, возведенный в квадрат, — это 1 000 0002 = 1012, так что стоит ожидать, что нам встретятся и очень большие, и очень маленькие числа.

Последний столбец табл. 2.2 — время работы, оцененное третьей математической моделью, TN(N) = a × log2 N: в ней один коэффициент — a, а в формуле присутствует двоичный логарифм. Полученное приближение — TN(N) = 0.0000448 × log2 N. Для N = 10 000 000 погрешность приближенного значения находится в пределах 5 % от экспериментального.

Таблица 2.2. Сравнение результатов различных математических моделей с фактическим временем работы

N	Время в секундах	TL	TQ	TN
100	[0.063]	0.047	0.056	0.030
1000	[0.565]	0.583	0.565	0.447
10 000	[5.946]	5.944	5.946	5.955
100 000	65.391	59.559	88.321	74.438
1 000 000	860.851	595.708	3769.277	893.257
10 000 000	9879.44	5957.194	326 299.837	10 421.327

Линейное приближение, TL, сильно преуменьшает время работы, а квадратичное, TQ, — преувеличивает. Расчет времени для N = 10 000 000 у TL равен 5957 секундам (это минут сто), а у TQ — целых 326 300 (почти 91 час). У TN предсказывать быстродействие получается куда лучше: ожидаемое время по TN — 10 421 секунда (примерно 2.9 часа), а фактическое — 9879 секунд (2.75 часа).

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

Отчего формула a × N × log2 N так хорошо предсказывает поведение программы? Это наверняка зависит от того, какие алгоритмы лежат в основании самой программы. Оценка сложности алгоритмов часто выдает одно из наших трех приближений — линейное, квадратичное или N-логарифмическое. Следующий пример напомнит нам об одном удивительном открытии 60-летней давности13.

Умножать быстрее, чем в столбик

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

Пример 2.2. Школьный алгоритм умножения N-значных чисел

   456                    123456

x 712                  x 712835

   ---                    ------

   912                    617280

  456                    370368

3192                    987648

------                 246912

324672                123456

                     864192

                     -----------

                     88003757760

Чтобы умножить два трехзначных числа друг на друга, надо перемножить девять пар цифр. Два шестизначных числа потребуют уже 36 умножений отдельных цифр. Умножая таким способом два N-значных числа, мы выполняем N2 умножений цифр. Можно еще заметить, что от увеличения количества цифр в целочисленных множимом и множителе вдвое количество действий «умножение цифры на цифру» растет вчетверо. Другие операции (например, сложение) можно даже не считать — умножение важнее.

Центральный процессор ЭВМ умеет быстро умножать целые числа только фиксированного размера — 32- или 64-разрядные, но с числами большей длины самостоятельно не справляется. Если целое число в Python оказывается слишком большим, оно преобразуется в специальную структуру PyLong, которая увеличивается по мере роста числа. Вот на ней и можно исследовать быстродействие умножения произвольных N-значных целых. В табл. 2.3 приведены результаты вычислений четырех эмпирических моделей производительности, которые построены на осно­вании первых пяти экспериментальных данных (в квадратных скобках).

Здесь TL — линейное приближение, а TQ — квадратичное. Karatsuba — это приближение с нестандартной степенью, a × N1.585, а TKN — более соответствующая экспериментальным данным формула, TKN(N) = a × N1.585 + b × N, с аккуратно подобранными коэффициентами a и b14. TL значительно недооценивает время работы умножения. А вот TQ — значительно переоценивает, хотя можно было ожидать, что квадратичное приближение окажется достаточно достоверным: количество действий при умножении столбиком растет квадратично, о том же говорит увеличение времени работы вчетверо при росте длины чисел вдвое. Но две другие математические модели оказались намного достовернее для расчета времени, за которое в Python умножаются .-значные целые, потому что для этого используется более эффективный алгоритм Карацубы — умножения длинных целых.

Таблица 2.3. Умножение N-значных чисел

N	Время в секундах	TL	TQ	Karatsuba	TKN
256	[0.0009]	–0.0045	0.0017	0.0010	0.0009
512	[0.0027]	0.0012	0.0038	0.0031	0.0029
1024	[0.0089]	0.0126	0.0096	0.0094	0.0091
2048	[0.0280]	0.0353	0.0269	0.0282	0.0278
4096	[0.0848]	0.0807	0.0850	0.0846	0.0848
8192	0.2524	0.1716	0.2946	0.2539	0.2571
16 384	0.7504	0.3534	1.0879	0.7617	0.7765
32 768	2.2769	0.7170	4.1705	2.2851	2.3402
65 536	6.7919	1.4442	16.3196	6.8554	7.0418
131 072	20.5617	2.8985	64.5533	20.5663	21.1679
262 144	61.7674	5.8071	256.7635	61.6990	63.5884

Внимательный читатель, должно быть, заметил, что «точная» формула (TKN) лучше «упрощенной» (Karatsuba) только на не слишком больших числах — аккурат на тех, для которых известны экспериментальные данные. Для умножения действительно больших чисел в Python используется уже не алгоритм Карацубы, а дискретное разложение Фурье. Класс сложности Nlog23 у этого алгоритма тот же (кажется, для достижимых чисел он минимально возможный), а накладных расходов на хранение промежуточных результатов, если их предполагается много, меньше. Возможно — эту гипотезу следует проверить! — TKN приближает как раз алгоритм Карацубы, а Karatsuba, вопреки названию, — алгоритм дискретного разложения.

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

Классы вычислительной сложности

Иногда довольно просто понять, какой из двух алгоритмов эффективнее справляется с одной и той же задачей: достаточно оценить их вычислительную сложность с помощью математических моделей. Обычно говорят «сложность O(N2)» или в худшем случае «сложность О(N log N)». Чтобы начать в этом разбираться, посмотрим на рис. 2.1. Тем, кто прочел книгу по теории сложности или изучал материалы по анализу алгоритмов, картинка покажется знакомой.

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

Поясню понятия верхней и нижней границы на примере автомобильного спидометра. Задача спидометра — вычислять и показывать приблизительное значение текущей скорости автомобиля. Скорость, которую показывает спидометр, должна быть не ниже текущей, чтобы водитель мог соблюдать правила движения. Это и есть нижняя граница. В бо´льшую сторону показания скорости не должны превышать 110 % плюс 4 км/ч от текущей15. В математике это соответствует понятию верхней границы.

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

На рис. 2.1 изображены три графика, которые представляют три наших приближения «длинного умножения» в Python — TL, TQ и TKN; экспериментальные данные обозначены там же черными квадратиками. TQ(N) — очевидная верхняя граница эксперимента (ибо TQ(N) всегда меньше экспериментального значения на всех N), но по самой иллюстрации видно, что эта граница очень неточная.

Рис. 2.1. Сравнение математических моделей с результатами измерений производительности

Если повнимательнее посмотреть на табл. 2.3, можно заметить, что, начиная с порогового значения объема входных данных N = 8192, приближение TKN(N) тоже всегда больше эмпирических данных для остальных N, но при этом гораздо ближе к ним. Обычно это признак того, что функция стабилизировалась и будет вести себя так впредь для «достаточно больших» N, но для каких именно — зависит от самого алгоритма и его конкретной реализации.

Очевидно также, что линейное приближение TL(N) — нижняя граница времени работы, потому что TL(N) меньше эмпирических данных для любого N. Впрочем, при увеличении N эта формула все сильнее отстает от экспериментальных значений, так что в качестве математической модели становится вполне бесполезной. Более точной нижней границей оказывается формула, названная в табл. 2.3 Karatsuba: a × N1.585.

Оценку производительности можно запускать на разных компьютерах, при этом конкретные числовые характеристики в табл. 2.3 поменяются. Скорость умножения может быть меньше или больше, коэффициенты a и b в TKN(N) могут оказаться другими, сама функция TKN(N) может стабилизироваться на другом большем или меньшем N. Но степень 1.585 в формулах не поменяется, потому что такова организация алгоритма быстрого умножения Карацубы, которым и определяется быстродействие. Никакой суперкомпьютер (за исключением, быть может, квантового) не сможет заставить умножение работать со скоростью линейного приближения TL(N).

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

Асимптотический анализ

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

В асимптотическом анализе эта идея развивается и вводится понятие мультипликативной постоянной алгоритма. Кто слышал о законе Мура, уже представляет себе, в чем оно состоит. Еще в 1965 году Гордон Мур, один из основателей и генеральных директоров корпорации Intel, высказал предположение, что количество элементов в интегральных микросхемах будет удваиваться ежегодно в течение ближайших десяти лет. В 1975-м он его скорректировал: «количество элементов в интегральных микросхемах удваивается каждые два года». Это наблюдение остается верным более 40 лет, и пока оно верно, скорость работы компьютеров тоже удваивается примерно за два года. Такая «мультипликативная постоянная в истории вычислительной техники» означает, что одна и та же программа на старом компьютере будет работать в тысячу раз медленнее (а то и хуже), чем на новом.

Возьмем два алгоритма, решающих одну и ту же задачу. Изучив их уже известным нам способом, предположим, что алгоритм X требует 5N действий на наборе данных размером N, а алгоритм Y — 2020 × log2 N действий на том же входном наборе. Какой из них эффективнее — X или Y?

Мы реализовали оба алгоритма и запускаем программы на двух компьютерах — один назовем Cfast, и он в два раза быстрее второго, Cslow. На рис. 2.2 приведено количество действий, затраченных каждым алгоритмом на входных данных объема N, а также время работы обоих алгоритмов на компьютере Cfast (столбцы обозначены как Xfast и Yfast) и на компьютере Cslow (столбцы Xslow и Yslow соответственно).

Рис. 2.2. Производительность алгоритмов X и Y на разных компьютерах

На небольших наборах данных одинакового размера алгоритму X требуется меньше действий, чем Y, однако, начиная с N = 8192, Y становится экономнее X, и чем N больше, тем разница сильнее. На рис. 2.3 видна точка пересечения графиков между 4096 и 8192, после которой Y оказывается эффективнее X по количеству выполняемых действий. На двух разных компьютерах идентичные реализации алгоритма X закономерно покажут, что Xfast, запущенный на Cfast, всегда быстрее Xslow, запущенного на Cslow.

Допустим, мы нашли суперкомпьютер Cfastest, который в 500 раз быстрее, чем Cslow. Можно отыскать такой объем входных данных, начиная с которого эффективный алгоритм Y будет работать на Cslow быстрее, чем неэффективный — на Cfastest. Мы здесь, конечно, немножко «сравниваем теплое с мягким» — компьютеры-то разные! — но все равно даже в нашем случае точка пересечения возникает между наборами размером 4 194 304 и 8 388 608. Если алгоритм в конечном счете более эффективен, то, работая даже на медленном компьютере, он обгонит неэффективный алгоритм, запущенный на суперкомпьютере, — когда объем входных данных достаточно велик.

Рис. 2.3. Графики для числовых данных рис. 2.2

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

В математике для классификации вычислительной сложности алгоритмов (и в худшем, и в лучшем случаях) используется обозначение «O большое». «O» в данном случае означает order, то есть «порядок». Порядок функции — это скорость, с которой она растет при росте ее переменной, N. Например, формула 4N2 + 3N – 5 — «порядка N2» (или квадратичная), потому что быстрее всего в этом многочлене растет первое слагаемое, в котором степень N равна 2.

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

T(N) — время, которое потребуется алгоритму для обработки набора данных размером N. Для входных данных из лучшего и худшего случаев могут быть свои, непохожие друг на друга T(N). При этом не имеет значения, в чем измеряется время — в секундах или миллисекундах.

S(N) — объем памяти, требуемый для работы алгоритма на наборе данных размером N. Для входных данных из лучшего и худшего случаев могут быть свои, непохожие друг на друга S(N). При этом не имеет значения, в чем измеряется объем памяти — в битах или гигабайтах.

Подсчет всех действий

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

Для начала определим функцию K(N) — количество основных действий, выполняемых в наихудшем случае на наборе данных размером N. Затем оценим число выполняемых машинных инструкций той же функцией с коэффициентом: c × K(N). Поскольку в современных языках программирования одно действие может быть транслировано в десятки, а то и тысячи инструкций, предосторожность в виде константы c будет нелишней. Вычислять ее не обязательно, хотя подобрать опытным путем с учетом производительности конкретного компьютера, как мы это делали раньше, вполне возможно.

Классификация вычислительной сложности (или потребления памяти) алгоритмов напрямую сопоставляет сложность с некоторой функцией от N. Этой функцией, f(N), описывается класс сложности O(f(N)) (поначалу в терминах легко запутаться). Относя алгоритм к определенному классу, мы составляем формулу в виде функции f от N. Нам уже встречались четыре класса сложности.

1. O(N) — линейная сложность, где f(n) = N.

2. O(N1.585) — сложность Карацубы, где f(N) = N1.585.

3. O(N2) — квадратичная сложность, где f(N) = N2.

4. O(N log N) — N-логарифмическая сложность, где f(N) = N log N16.

Для точного анализа надо изучать исходный текст программы и выявлять организацию алгоритма. Сколько раз выполняется действие ct += 1 в примере ниже?

       for i in range(100):

         for j in range(N):

             ct += 1

Внешний цикл, по i, делает 100 проходов, и на каждом из них внутренний цикл, по j, делает N проходов. Итого действие ct += 1 выполняется 100 × N раз. При должном выборе константы c время выполнения приведенного фрагмента программы T(N) на наборе данных размером N не будет превышать c × N. Запуская программу на конкретном компьютере, можно определить значение соответствующего c. Говоря точнее, в терминах «О большого», сложность этого фрагмента оценивается как O(N).

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

Подсчет всех байтов

Такой же анализ можно сделать для оценки «сложности по памяти» — объема памяти, потребляемого алгоритмом на входных наборах размером N. Динамическое выделение дополнительной памяти неизбежно ведет и к понижению производительности, потому что управление памятью — это тоже алгоритм со своей сложностью.

Вот такие конструкции Python требуют совершенно разных объемов памяти.

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

• list(range(N)) сделает из такой последовательности список с элементами от 0 до N – 1. Такому объекту требуется оперативная память в объеме, прямо пропорциональном N.

Четко определить объем той или иной конструкции языка программирования непросто уже потому, что не до конца понятно, в чем его измерять. В байтах или битах? Но тогда имеет ли значение, что на одних архитектурах целое число занимает 32 бита, а на других — 64? Допустим, в будущем появится компьютер, оперирующий 128-битными целыми17, — значит ли это, что сложность по памяти при работе с целыми числами для них удвоится? Размер объекта в байтах в Python показывает функция sys.getsizeof(объект). Давайте на примере убедимся, что использование вычислимой последовательности range() в Python 3 позволяет ощутимо сэкономить потребление памяти! Для этого достаточно запустить интерпретатор Python и подать ему такие команды:

>>> import sys

>>> sys.getsizeof(range(100))

48

>>> sys.getsizeof(range(10000))

48

>>> sys.getsizeof(list(range(100)))

1008

>>> sys.getsizeof(list(range(1000)))

9112

>>> sys.getsizeof(list(range(10000)))

90112

>>> sys.getsizeof(list(range(100000)))

900112

Здесь хорошо видно, что объем list(range(10000)) в байтах примерно в сто раз больше объема list(range(100)). Глядя на остальные значения, можно с уверенностью сказать, что список в Python потребляет порядка O(N) памяти.

Для сравнения: и range(100), и range(10000) занимают один и тот же объем памяти — 48 байт. Это новый для нас класс сложности, в котором значение постоянно и не зависит от N, он так и называется — константным.

O(1) — константная сложность, где f(N) = c с некоторой постоянной c.

Ну что ж, в этой главе мы рассмотрели довольно много теории; настало время применить наши знания на практике. Пора изучить алгоритм оптимального поиска элемента в упорядоченном списке — по-научному он называется алгоритмом двоичного поиска в массивах. Мы выясним, отчего он так эффективен, и попутно познакомимся с новым, логарифмическим классом сложности O(log N).

Одна дверь захлопнулась — другая откроется

За каждой из дверей на рис. 2.4 скрыто по одному произвольному числу. Извест­но, что числа за дверьми возрастают слева направо. Вопрос: сколько дверей необходимо в худшем случае открыть по одной, чтобы найти число 643 — или убедиться, что его за дверьми нет? Можно начать с самой левой и открывать каждую по очереди, пока не появится число 643 или большее (если числа 643 вообще не было за дверьми). Если не повезет, придется открыть все двери. В этом способе никак не учитывается, какие именно числа нашлись за уже открытыми дверьми. В действительности для ответа на вопрос достаточно открыть не более трех дверей. Для начала откроем дверь 4 — среднюю.

Рис. 2.4. Двери судьбы!

Там окажется число 173. Раз мы ищем 643, все двери слева от четвертой нас больше не интересуют, потому что номера за ними меньше 173. Теперь откроем дверь 6 — за ней число 900. Прекрасно, теперь двери правее шестой нас тоже не интересуют. Остается только дверь 5 — и либо за ней скрывается 643, либо этого числа вообще не было в исходной последовательности. Пока она закрыта, мы вольны воображать и то и другое.

На любой возрастающей последовательности из семи чисел и для любого искомого числа потребуется открыть не более трех дверей. Кстати, можно заметить, что 23 – 1 = 7. А если возрастающая последовательность будет состоять из миллиона элементов за миллионом дверей и с нами поспорят на 10 000 долларов, что мы не найдем нужное число, открыв только 20 дверей? Надо соглашаться! Ведь 220 – 1 = 1 048 575, так что 20 открытых дверей хватит на то, чтобы проверить возрастающую последовательность из 1 048 575 чисел. Более того, если количество дверей внезапно удвоится (даже дойдет до 2 097 151), понадобится дополнительно открыть всего одну дверь, 21 дверь на все два с лишним миллиона. Удивительно быстрый способ! Вот мы и изобрели алгоритм двоичного поиска в упорядоченном массиве.

Двоичный поиск в упорядоченном массиве

Двоичный поиск — один из базовых алгоритмов: порядок его сложности отличается от порядка сложности уже рассмотренных нами алгоритмов. В примере 2.3 реализован двоичный поиск значения target в упорядоченном списке A.

Пример 2.3. Двоичный поиск

def binary_array_search(A, target):

  lo = 0

  hi = len(A) - 1               ❶

  while lo <= hi:               ❷

    mid = (lo + hi) // 2        ❸

    if target < A[mid]:         ❹

      hi = mid-1

    elif target > A[mid]:       ❺

      lo = mid+1

    else:

      return True               ❻

  return False                  ❼

❶ Будем вести поиск в списке от индекса lo до индекса hi включительно. Поначалу они равны 0 и len(A)–1 соответственно.

❷ Цикл закончится, когда диапазон опустеет.

❸ В диапазоне A[lo … hi] найдем середину и значение A[mid] в ней.

❹ Если target меньше A[mid], продолжим поиск слева от середины.

❺ Если target больше A[mid], продолжим поиск справа от середины.

❻ Если это и есть target, вернем True.

❼ Если lo превысило hi, значит, искать больше негде. Вернем False в знак того, что target не найден в A.

Поначалу lo и hi равны наименьшему и наибольшему индексу в A. Пока диапазон поиска не исчерпан, с помощью целочисленного деления находим его середину, mid. Если A[mid] и есть target, поиск окончен; иначе становится понятно, сужать ли диапазон до левой части — A[lo … mid-1] или до правой — A[mid+1 … hi].

Запись A[lo … mid] в книге означает диапазон значений из списка A, начиная с индекса lo до индекса mid включительно. Если lo < mid, диапазон пуст.

Наша функция определяет, принадлежит ли некоторое значение упорядоченному списку из N элементов. На каждом обороте цикла можно либо отыскать нужный элемент, либо сузить диапазон. Цикл заканчивается, когда элемент найден или когда hi оказывается меньше lo.

Немногим сложнее, чем π

Рассмотрим двоичный поиск числа 53 в списке на рис. 2.5. Переменные hi и lo поначалу совпадают с границами списка A. В цикле while вычисляется mid. Поскольку A[mid] равно 19 и меньше 53, выполнение идет по ветке elif и значение lo меняется на mid + 1. Дальнейший поиск производится уже по диапазону A[mid+1 … hi]. Серым закрашены нерассматриваемые значения. Размер диапазона уменьшается вполовину (с 7 до 3).

Рис. 2.5. Поиск числа 53

На втором проходе цикла while вычисляется новое mid и оказывается, что A[mid] равно искомому числу, 53, так что функция возвращает True.

Имеет ли смысл перед запуском двоичного поиска проверить, точно ли A[0] <= target <= A[–1]? Так мы могли бы избежать бессмысленного поиска числа, которое в принципе не может оказаться в списке. Говоря коротко: нет, не имеет. Это добавит целых две проверки (которых даже на 1 000 000 всего 20) к каждому поиску, а сами проверки окажутся лишними в поиске чисел, которые заведомо принадлежат диапазону значений A.

Теперь поищем число 17, которого нет в списке. Как показано на рис. 2.6, lo и hi снова установлены по границам A. A[mid] равно 19; это больше, чем 17, так что вычисление идет по ветке if, и диапазон сужается до A[lo … mid-1]. Серым закрашены значения, которые нам больше не нужны. A[mid] теперь равно 14, это меньше 17, и вычисление идет по ветке elif, а диапазон сужается до A[mid+1 … hi].

Рис. 2.6. Поиск числа 17

На третьем проходе цикла while получаем A[mid] равным 15; это меньше, чем искомое 17. Снова идем по ветке elif, где lo делается больше, чем hi: диапазон «схлопывается», как показано в конце рис. 2.6. Условие цикла while становится ложным, и возвращается False: это означает, что target в A не найден.

Двух зайцев одним выстрелом

Зачастую требуется найти, где именно в A находится target, а не только проверить, есть ли он там. Пока наша функция возвращала только True или False. Слегка подправим исходный текст, и двоичный поиск будет возвращать позицию mid, где находится target (пример 2.4).

Пример 2.4. Вычисление позиции target в A

def binary_array_search(A, target):

  lo = 0

  hi = len(A) - 1

     while lo <= hi:

       mid = (lo + hi) // 2

      if target < A[mid]:

        hi = mid-1

      elif target > A[mid]:

        lo = mid+1

      else:

        return mid              ❶

     return -(lo+1)             ❷

❶ Возвращаем mid, потому что именно там мы нашли target.

❷ Уведомляем пользователя о том, что target не найден, возвращая отрицательный индекс -lo - 1.

Что бы такого полезного вернуть, если target нет в A? Можно просто None, как это принято в Python, но в нашем случае есть шанс дать пользователю дополнительные сведения. Например, можно не только сообщить о том, что target отсутствует в A, но и заранее вычислить место, куда его следует при необходимости вставить, не нарушая порядка A.

Давайте еще раз посмотрим на рис. 2.6. Пока мы искали число 17 в списке, где его не было, значение lo стало указывать на место, куда 17 можно было бы вставить, соблюдая порядок в A. Можно было бы в этом случае вернуть просто -lo, но если искомый элемент найден в начальной позиции или не найден и это только место вставки, в обоих случаях вернется 0. Так что возвращаем заведомо отрицательное число -(lo + 1). Если пользователь получит отрицательное x, он будет знать, что target отсутствует в A, но его можно туда добавить в позицию -(x + 1). Если x неотрицателен — это позиция target в A.

Напоследок еще немного оптимизации. В примере 2.4 над элементами A производится два сравнения, хотя можно было бы обойтись одним, а потом проверять его результаты. Если значения числовые, таким сравнением может быть их разность — как в примере 2.5, где над элементами A производится всего одно действие (а не два). Кстати, операция индексирования A[mid] в примере тоже одна.

Пример 2.5. Оптимизация, которая требует только одного сравнения элементов списка

diff = target - A[mid]

if diff < 0:

  hi = mid-1

elif diff > 0:

  lo = mid+1

else:

  return mid

Если target был меньше A[mid], diff окажется отрицательным, и это аналогично сравнению target < A[mid]. Если diff положителен, значит, target оказался больше A[mid]. Допустим, значения A — не числовые, но для них существует операция сравнения, которая возвращает отрицательное число, ноль или положительное число, в соответствии с тем, как эти значения можно упорядочить. Сравнение обычных целых вместо дорогостоящего сравнения элементов увеличивает быстродействие.

Если список упорядочен по убыванию, двоичный поиск тоже работает — только hi и lo в цикле while должны меняться по-другому.

Как быстро работает двоичный поиск на данных объемом N? Чтобы ответить на вопрос, надо привести наихудший случай входных данных и посчитать, сколько раз должен выполниться цикл while. Понятие логарифма нам в помощь!

Что такое логарифм? Попробуем ответить на вопрос: сколько раз нужно удвоить единицу, чтобы получить число 33 554 432? Можно, конечно, попробовать добраться до него вручную — 1, 2, 4, 8, 16 и т.д., — но это довольно утомительно. Что мы ищем с математической точки зрения? Такое x, что 2x = 33 554 432.

Запись 2x — это возведение основания 2 в степень x. Логарифм — функция, обратная возведению в степень, примерно как деление — функция, обратная умножению. Чтобы найти такое x, что 2x = 33 554 432, надо посчитать логарифм по основанию 2 от этого числа, log2 33554432. Получится 25.0. Если вычислить 225 на калькуляторе, получится 33 554 432.

То же значение — ответ на вопрос «Как долго можно делить 33 554 432 пополам?»: после 25 делений получится 1. Логарифм — вещественное число; например, log2 137 — примерно 7.098032. Что в целом понятно: раз уж 27 = 128, то для получения 137 степень нужна чуть-чуть побольше.

В алгоритме двоичного поиска цикл while повторяется до тех пор, пока lo ≤ hi, то есть пока есть где искать. На первом проходе в диапазоне поиска N значений, на втором их уже N / 2 (а если N нечетно, то (N – 1) / 2). Следовательно, чтобы предсказать количество проходов цикла, надо посчитать, сколько раз придется делить N пополам, пока не получится 1. А это и есть в точности k = log2 N, что дает нам 1 + k проходов цикла (первый — для полного N, остальные k — для меньших диапазонов). Логарифм — вещественное число, а нам для оценки количества проходов, конечно, нужно целое. Подойдет нижнее округление floor(x), математическая функция, возвращающая наибольшее целое число, не превосходящее x18.

Далеко не каждый калькулятор или приложение-калькулятор умеют вычислять двоичный логарифм. Но у нас же есть Python! Лучший в мире программируемый калькулятор всегда у вас под рукой. Достаточно запустить любую версию командного интерпретатора — стандартный Python, консоль любого средства разработки (например, IDLE — она есть в базовой поставке Python) или специализированный терминал наподобие iPython — и импортировать требуемую библиотеку. В ответ на подсказку >>> вводим нужную формулу — и вуаля, ответ перед нами.

>>> from math import *

>>> log2(16)

>>> log(16)

>>> log10(16)

>>> log(16)/log(2)

>>> log10(16)/log10(2)

В примере иллюстрируется важное свойство: логарифм одного и того же числа по разным основаниям отличается только множителем. Скажем, чтобы получить логарифм числа 16 по основанию 2, можно воспользоваться натуральным логарифмом (по основанию e ≈ 2.718281828459045…) числа 16 и натуральным логарифмом самого основания 2. Функция log(x) в Python вычисляет натуральный логарифм, log2(x) — двоичный, а log10(x) — логарифм по основанию 10.

Итак, в двоичном поиске цикл while делает не более floor(log2 N) + 1 проходов. Это невероятно быстро! Найти нужное число из миллиона отсортированных значений можно всего за 20 попыток.

Мы можем сами убедиться в корректности формулы: для любого объема входных данных от 8 до 15 элементов требуется не более четырех проходов. Если на первом проходе в диапазоне 15 элементов, то на втором их будет 7, на третьем — 3 и на четвертом останется только один. Если начать с десяти элементов, диапазон будет меняться так: 10 → 5 → 2 → 1 — и это тоже четыре прохода.

Получается, что изучение двоичного поиска дало нам новый класс сложности, O(log N), он называется логарифмическим, потому что определяющая его функция f(N) = log N.

Стало быть, если при изучении алгоритма мы утверждаем, что его сложность по времени — O(log N), это означает, что существует такая константа c, для которой, начиная с некоторого достаточно большого N, скорость работы алгоритма T(N) будет всегда меньше, чем c × log N. Наше утверждение верно, если неверны аналогичные утверждения относительно более низких классов вычислительной сложности (рис. 2.7).

Рис. 2.7. Иерархия классов вычислительной сложности в порядке доминирования

Классов вычислительной сложности в теории бесконечно много, но на практике эти восемь встречаются чаще всего. Константное время выполнения O(1) — это низший класс сложности, при этом время работы алгоритма постоянно и не зависит от размера входных данных. Следующий класс в иерархии — O(log N), логарифмический, мы уже видели, что двоичный поиск относится к этой категории. Оба класса — долинейные, они содержат чрезвычайно эффективные алгоритмы.

Линейная сложность, O(N), предусматривает увеличение времени работы прямо пропорционально объему данных. Далее идет набор полиномиальных классов в порядке возрастания сложности — O(N2), O(N3) и т.д. вплоть до любой наперед взятой константы c, O(Nc)19. Между O(N) и O(N2) затесался класс O(N log N); для многих задач именно алгоритм такого класса специалисты считают наилучшим.

Доминирование классов друг над другом выражается еще в том, как определяется алгоритм, в оценке сложности которого встречаются несколько различных компонентов-формул. Например, если сложность одной части алгоритма оценивается как O(N log N), а другой — как O(N2), то какова сложность всего алгоритма? Ответ: O(N2), потому что сложность второй части доминирует над сложностью первой. Если, например, оценка сложности вашего алгоритма T(N) оказалась равной 5N2 + 10 000 000 × N × log2 N, то класс его сложности — O(N2).

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

Как все это работает

В табл. 2.4 представлены результаты вычислений f(N) для каждого упомянутого класса сложности. Предположим, что числа в таблице — это время работы некоторого алгоритма в секундах. Сложность алгоритма указана в заголовке столбца, а размер входного набора данных N — в заголовке строки. Значение 4096 минут — это 1 час 8 минут, так что чуть больше чем за час можно решить:

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

• задачу сложности O(log N) на входном наборе размером не более чем 24096;

• задачу сложности O(N) на входном наборе размером не более чем 4096;

• задачу сложности O(N log N) на входном наборе размером не более чем 462;

• задачу сложности O(N2) на входном наборе размером не более чем 64;

• задачу сложности O(N3) на входном наборе размером не более чем 16;

• задачу сложности O(2N) на входном наборе размером не более чем 12;

• задачу сложности O(N!) на входном наборе размером не более чем 7.

Таблица 2.4. Рост различных оценок сложности

N	log N	N	N log N	N2	N3	2N	N!
2	1	2	2	4	8	4	2
4	2	4	8	16	64	16	24
8	3	8	24	64	512	256	40 320
16	4	16	64	256	4096	65 536	2.1 × 1013
32	5	32	160	1024	32 768	4.3 × 109	2.6 × 1035
64	6	64	384	4096	262 114	1.8 × 1019	1.3 × 1089
128	7	128	896	16 384	2 097 152	3.4 × 1038	∞
256	8	256	2048	65 536	16 777 216	1.2 × 1077	∞
512	9	512	4608	262 144	1.3 × 108	∞	∞
1024	10	1024	10 240	1 048 576	1.1 × 109	∞	∞
2048	11	2048	22 528	4 194 304	8.6 × 109	∞	∞

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

Быстродействие различных классов на больших объемах данных выглядит обычно так, как на рис. 2.8. Ось X отвечает за размер входного набора, ось Y — за полное время работы алгоритма, классы алгоритмов надписаны на графиках. Чем выше класс сложности алгоритма, тем меньше объем данных, которые он сможет обработать за «приемлемое время»20.

Рис. 2.8. График быстродействия разных классов сложности на возрастающем объеме входных данных

Рассмотрим еще несколько примеров посложнее.

• Если сложность алгоритма оценивается как O(N2 + N) — к какому классу его отнести? Согласно иерархии на рис. 2.7 N2 доминирует над N, и, следовательно, оценку можно упростить до O(N2). По тем же соображениям O(2N + N8) упрощается до O(2N).

• Если сложность оценивается как O(50 × N3), оценка упрощается до O(N3), потому что мультипликативная постоянная значения не имеет.

• Иногда быстродействие алгоритма зависит не только от размера входных данных N, но и от их свойств. Скажем, имеется алгоритм, на первом шаге которого N числовых значений отрабатывается за линейное время (то есть за время, прямо пропорциональное N). На втором шаге этого алгоритма из входных данных обрабатываются только четные числа и время этой обработки пропорционально E2 (где E — количество четных чисел во входном наборе). Если подходить к вопросу аккуратно, оценка получится O(N + E2). Допустим, четные числа не очень-то и нужны и для решения задачи достаточно входного набора без них. Тогда оценка упадет до O(N), что может быть весьма полезно. Понятное дело, худший случай для такого алгоритма — это набор исключительно четных чисел, так что общая оценка будет O(N2), поскольку E ≤ N.

Приближенная кривая или четкие границы?

В пакете SciPy есть функция curve_fit(), которая с помощью нелинейного метода наименьших квадратов может подобрать коэффициенты для некоторой модельной функции f, чтобы та как можно лучше описывала имеющиеся данные. Мы использовали ее, когда для измеренного на разных объемах данных N времени работы алгоритма прикидывали, какой функцией оно может выражаться. Как мы уже знаем, curve_fit() возвращает коэффициенты, подставив которые в f мы получим приближение с минимальной суммой квадратов отклонений значений этой функции от имеющихся данных.

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

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

В разговоре про двоичный поиск мы выяснили, что цикл while в функции делает не более floor(log2 N) + 1 проходов. Это значит, что оценка в худшем случае f(N) = log N и порядок сложности двоичного поиска — логарифмический, O(log N). Как двоичный поиск работает в лучшем случае? Если искать элемент, равный A[mid], функция завершится всего за один проход цикла. Этот результат постоянен и не зависит от размера входных данных, значит, порядок двоичного поиска в лучшем случае — константный, O(1). Обозначение «О большое» можно применять и для лучших, и для худших случаев, хотя, с точки зрения большинства программистов, это имеет смысл только для худших.

Для классификации сложности алгоритма нередко применяют обозначение вида Θ(N log N) (с большой греческой буквой тета). Хотя чаще всего оно применяется для оценки сложности алгоритма в среднем, его смысл более узкий. Такая запись означает, что и верхняя, и нижняя границы оценки определяются одной и той же формулой, в данном случае верхняя граница — O(N log N), а нижняя — Ω(N log N). По-английски этот термин звучит как tight bound — «строгая оценка». Строгая оценка производительности алгоритма, если она есть, лучше всего позволяет убедиться, что время его работы хорошо предсказуемо.

Заключение

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

Тренировочные задания

1. Оцените сложность по времени каждого из фрагментов программы в примере 2.6.

Пример 2.6. Оцените фрагменты программ

Фрагмент 1

for i in range(100):

  for j in range(N):

    for k in range(10000):

      ...

Фрагмент 2

for i in range(N):

  for j in range(N):

    for k in range(100):

      ...

Фрагмент 3

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

  for j in range(0,N,2):

    ...

Фрагмент 4

while N > 1:

  ...

  N = N // 2

Фрагмент 5

for i in range(2,N,3):

  for j in range(3,N,2):

    ...

2. Используя методику анализа, описанную в этой главе, оцените значение ct, возвращаемое функцией f4 в примере 2.7.

Пример 2.7. Исследуйте функцию

def f4(N):

  ct = 1

  while N >= 2:

    ct = ct + 1

    N = N ** 0.5

  return ct

Ни одну из рассмотренных в главе оценок применить не получится. Попробуйте взять за основу формулу a × log2(log2 N). Составьте таблицу значений функции вплоть до N = 250 и сравните с вашей оценкой. Полученный класс сложности можно определить как O(log(log N)).

3. Есть один неэффективный способ сортировки: перебрать все перестановки исходного массива и вернуть ту, которая окажется отсортированной. Этот способ показан в примере 2.8.

Пример 2.8. Сортировка путем перебора всех перестановок списка

from itertools import permutations, pairwise

from scipy.special import factorial

def factorial_model(v, a):

  return a * factorial(v)

def check_sorted(a):

  for x, y in pairwise(a):

    if x > y:

      return False

  return True

def permutation_sort(A):

  for attempt in permutations(A):

    if check_sorted(attempt):

      A[:] = attempt           # заполним A отсортированными значениями

      return

Составьте таблицу быстродействия функции permutation_sort() в наихудшем случае (здесь это список, упорядоченный по убыванию); размер списка от 1 до 12 элементов включительно. Подберите приближенную кривую с помощью функции factorial_model() и исследуйте, насколько хорошо она прогнозирует время работы permutation_sort(). Сколько лет, если верить полученным данным, эта функция будет сортировать упорядоченный по убыванию список из 20 элементов?21

4. Соберите данные по быстродействию 50 000 экспериментальных запусков двоичного поиска на случайных наборах размером N от 25 до 221. Каждый эксперимент должен использовать случайный входной набор размером N, получаемый с помощью random.sample() из диапазона чисел от 0 до 4 × N, который затем надо отсортировать. Искать в каждом эксперименте нужно случайное число из того же диапазона.

Используя методику, описанную в данной главе, подберите с помощью curve_fit() логарифмическое (log N) приближение к полученным данным для N в диапазоне от 25 до 212. Определите пороговое значение N, начиная с которого результаты экспериментов предсказуемо описываются найденным приближением. Нарисуйте график функции-приближения и точки экспериментальных данных. Насколько достоверно найденная функция описывает эксперимент?

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

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

def max_sort(A):

  result = []

  while len(A) > 1:

    index_max = max(range(len(A)), key=A.__getitem__)

    result.insert(0, A[index_max])

    A = list(A[:index_max]) + list(A[index_max+1:])

  return A + result

Используя методику из этой главы, оцените сложность по памяти функции max_sort().

6. Галактический алгоритм — это алгоритм решения некой задачи, который становится эффективнее других известных алгоритмов только на «недостижимо большом» наборе данных. Например, алгоритм умножения N-значных чисел, опубликованный в ноябре 2020 года Дэвидом Харви и Йорисом ван дер Хувеном, имеет сложность O(N log N), но только для N, превышающих 2Z, где Z = 172912. Это Z — само по себе астрономическое число, примерно 7 × 1038, а уж если в такую степень возвести 2, получится уже что-то запредельно огромное! Почитайте, что пишут о галактических алгоритмах. На практике их использовать нельзя, но зачастую осознание того, что для данной задачи может существовать алгоритм более низкого класса сложности, подталкивает к дальнейшим открытиям!

7. В табл. 2.1 приведены три ряда измерения для трех размеров набора входных данных. Если бы рядов было только два, удалось бы составить приближение для квадратичного алгоритма? Более общий вопрос: если имеется K замеров производительности, какова наибольшая степень многочлена, которым можно приблизить эти результаты?

---

Глава 3. Хороший хеш — залог успеха

В этой главе

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

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

Как использовать массив списков для хранения и поиска пар (ключ, зна­чение) с возможностью удаления по ключу.

Как менять размер хеш-таблицы, чтобы не потерять ее производительность.

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

Как довести оценку операции добавления в хеш-таблицу put() до амортизационной сложности O(1) в среднем путем геометрического масштабирования.

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

Соответствие значений ключам

Часто набор объектов, которые нужно уметь хранить в памяти, представлен не в виде последовательности, а в виде множества пар (ключ, значение), в котором каждому ключу однозначно соответствует некоторое значение. Такая структура называется ассоциативным массивом. Если наложить дополнительные требования на свойство ключа, вместо поиска пары (ключ, значение) по всему набору можно использовать гораздо более эффективный прием — хеширование. Поиск по хешу работает быстрее любого изученного нами алгоритма поиска! Ассоциативный массив сохраняет эффективность, даже если разрешить удаление ключей и значений. Порядок следования ключей в такой структуре определяется ее реализацией (в словарях Python ключи идут в порядке добавления, в устаревшем Python2 определенный порядок не гарантировался вовсе; в любом случае ключи почти наверняка не будут упорядочены по возрастанию, как индексы массива). Взамен мы получаем великолепную скорость поиска и добавления пары.

Скажем, мы хотим написать функцию print_month(month, year), которая будет выводить календарь на определенный месяц определенного года. С параметрами print_month('February', 2024) функция должна выводить примерно это:

    Февраль 2024

Пн Вт Ср Чт Пт Сб Вс

          1  2  3  4

5  6  7  8  9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28 29

Что нам нужно для этого знать? День недели, с которого в этом году начинается месяц (в примере это четверг), а еще — сколько дней в феврале этого года (28, а если год високосный, как 2024-й, то 29). Для количества дней в месяце заведем числовой массив, каждый элемент которого будет соответствовать месяцу, начиная с января:

month_length = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

Итак, в январе 31 день, поэтому month_length[0] == 31, в феврале — 28, так что следующее значение — 28 и т.д. до последнего 31, которое соответствует 31 дню в декабре.

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

key_array = ('Январь', 'Февраль', 'Март', 'Апрель', 'Май', 'Июнь', 'Июль',

             'Август', 'Сентябрь', 'Октябрь', 'Ноябрь', 'Декабрь')

idx = key_array.index('Февраль')

print('В феврале', month_length[idx], 'дней')

Если название месяца в массиве ключей есть, этот фрагмент будет работать. Однако в худшем случае, когда нам нужен 'Декабрь', придется просмотреть все значения. Если ключа в массиве нет, key_array.index() выдаст исключение, так что предварительно нам придется проверить наличие ключа, например, с помощью key in key_array. Это тоже худший случай, потому что будут просмотрены все строки в key_array. Следовательно, время поиска значения по ключу в изобретенной нами структуре прямо пропорционально количеству ключей. Такая скорость поиска довольно быстро станет медленной до полной неприемлемости. Несмотря на это, давайте все-таки напишем print_month(). В частности, в примере 3.1 приведена возможная реализация, в которой задействованы два стандартных модуля Python — datetime (для определения дня недели) и calendar (для определения високосного года).

Пример 3.1. Вывод на экран календаря за произвольный год и месяц в удобном формате

from datetime import date

import calendar

month_length = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

key_array = ('Январь', 'Февраль', 'Март', 'Апрель', 'Май', 'Июнь', 'Июль',

             'Август', 'Сентябрь', 'Октябрь', 'Ноябрь', 'Декабрь')

def print_month(month, year):

  idx = key_array.index(month)              ❶

  wd = date(year, idx + 1, 1).weekday()     ❷

  days = month_length[idx]                  ❸

  if calendar.isleap(year) and idx == 1:    ❹

   days += 1

  print(f"{month} {year}".center(20))

  print("Пн Вт Ср Чт Пт Сб Вс")

  print('   ' * wd, end='')                 ❺

  for day in range(days):

    wd = (wd + 1) % 7                       ❻

    eow = " " if wd % 7 else "\n"           ❼

    print(f"{day+1:2}", end=eow)

  print()

❶ Найдем номер месяца (целое число от 0 до 11) — индекс в month_length.

❷ Вычислим первый день недели данного месяца в данном году, 0 — это понедельник. В функцию date() передается idx + 1, потому что месяцы в ней нумеруются с единицы, а не с нуля.

❸ Определим количество дней в месяце.

❹ В високосном году в феврале 29 дней (мы нумеруем месяцы с нуля, так что февраль — это 1).

❺ Вместо дней прошедшего месяца в первой неделе выведем пробелы, тогда первый день окажется на своем месте.

❻ Вычислим следующий день недели.

❼ Вычислим, что выводить после текущей даты. Если следующий день не понедельник, то есть wd не делится на 7, нужно выводить пробел, а если понедельник — конец строки, потому что неделя закончилась.

Чтобы оценить производительность поиска ключа в наборе из N пар (ключ, значение), имеет смысл посчитать количество операций индексирования. Функция key_array.index() для поиска нужной строки может просматривать вплоть до N элементов, так что ее сложность — O(N).

Тип данных list реализован в Python как динамический массив, размер которого может меняться. Для краткости его часто называют просто списком. В этой главе мы также будем использовать термин «массив» в знак того, что наши методы применимы и к классическим массивам неизменяемой длины. Кроме того, если мы не собираемся менять и сами элементы массива, в программах на Python лучше использовать кортежи (тип данных tuple), как в примерах выше.

Ассоциативные массивы, хранящие произвольные значения по ключу, реализованы в Python специальным типом данных dict (от dictionary — «словарь»). Мы можем составить словарь days_in_month, хранящий целые числа — продолжительность месяцев в днях в соответствии с ключами — названиями месяцев (с заглавной буквы):

days_in_month = {'Январь':  31, 'Февраль': 28, 'Март':     31,

                 'Апрель':  30, 'Май':     31, 'Июнь':     30,

                 'Июль':    31, 'Август':  31, 'Сентябрь': 30,

                 'Октябрь': 31, 'Ноябрь':  30, 'Декабрь':  31 }

А вот пример вывода утверждения «в апреле 30 дней»:

print('В апреле', days_in_month['Апрель'], 'дней')

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

Будем считать, что буква «а» — это 0, буква «б» — 1 и т.д. до «я» — 31. С помощью этих 32 «цифр» любое русское слово (увы, без буквы «е»), записанное строчными буквами, соответствует некоторому числу в системе счисления с основанием 32. Например, в «числе» «июнь» четыре цифры — «и», «ю», «н» и «ь». Если начать переводить из тридцатидвоичной системы счисления в привычную нам десятичную, получится «и» × 323 + «ю» × 322 + «н» × 321 + «ь» × 320, или, после вынесения основания за скобки, 32 × (32 × (32 × «и» + «ю») + «н») + «ь». Именно так и работает функция base32() в примере 3.222.

Пример 3.2. Интерпретация слова как числа с основанием 32

def base32(w):

  val = 0

  for ch in w.lower():                  ❶

    next_digit = ord(ch) - ord('а')     ❷

    val = 32 * val + next_digit         ❸

  return val

❶ Преобразуем буквы строки в строчные.

❷ Вычислим значение очередной цифры.

❸ Припишем цифру в конец результата.

В base32() используется функция ord(), которая возвращает порядковый номер буквы в таблице всех известных Python символов Unicode23. Буквы от «а» до «я» идут в алфавитном порядке24, ord('а') == 1072, ord('б') == 1073 и т.д. до ord('я') == 1103. Так что для того, чтобы вычислить значение «и», достаточно вычесть порядковые номера: ord('и') - ord('а') — и получить 8.

Значение base32() очень быстро растет с ростом длины строки. Уже base32('Июнь') возвращает 293308, а base32('Сентябрь') — так и вовсе 589940360732.

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

Немного поэкспериментировав, мы можем обнаружить, что для всех названий месяцев значения base32(month) % 35 различны. Например, base32('Август') равно 2215474, а 2215474 % 35 == 9, и для каждого месяца результат будет иным. Теперь, как показано на рис. 3.1, мы можем завести массив на 35 элементов, с помощью которого можно узнать количество дней в данном месяце, за одно обращение, и перебирать все пары (ключ, значение) не нужно. Вычисляем формулу для февраля, получаем 0, на нулевой позиции в day_array стоит 28 — в феврале 28 дней. Проделываем то же самое с ноябрем — получаем позицию 32 и 30 дней.

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

base32('Февраль') % 35 == 0 // Нулевой элемент равен 28

day_array = (

  28, -1, 30, -1, -1, -1, -1,

  -1, 30, 31, -1, -1, 31, -1,

  31, 31, -1, -1, 30, -1, -1,

  31, -1, -1, -1, -1, 31, -1,

  -1, -1, -1, 31, 30, -1, -1

)

base32('Ноябрь') % 35 == 32 // 32-й элемент равен 30

Рис. 3.1. Массив с длинами месяцев; если формула не дает соответствующего индекса, в массиве записано –1

Поработать, правда, пришлось изрядно. Во-первых, подыскать формулу однозначного преобразования имени месяца в индекс, а во-вторых, создать массив на 35 элементов, из которых имеет смысл только дюжина, а значит, больше половины этого массива потрачено впустую. В нашем примере объем хранимых данных N равен 12, а объем хранилища M — 35.

Если для некоторой строки s элемент day_array в позиции base32(s) % 35 равен -1, очевидно, эта строка не название месяца. Этим удобно пользоваться. Может показаться, что если day_array[base32(s)%35] > 0, то любая строка s — допустимое название месяца, но это, конечно, не так. К примеру, base32("Промахнулось") выдает то же самое, что и base32("Февраль"); получится, что «Промахнулось» — это такой месяц и в нем 28 дней! Это довольно неприятное свойство, и нам придется разобраться, как с ним справиться.

Хеш-функции и хеш-суммы

Формула base32(s) % 35 — пример хеш-функции, которая отображает ключ произвольного размера в хеш-сумму (или просто хеш) в заданном диапазоне значений25. В нашем примере хеш не меньше нуля и не больше 34. Множество хеш-функций возвращают произвольное 32-разрядное целое (в диапазоне от –2 147 483 648 до 2 147 483 647) или произвольное 64-разрядное целое (в диапазоне от –9 223 372 036 854 775 808 до 9 223 372 036 854 775 807). Нетрудно заметить, что хеши бывают и отрицательными.

Задача отображения структурированных данных в фиксированные целые числа, то есть задача отыскания подходящей хеш-функции, занимает математиков последние несколько десятилетий. Программисты пользуются плодами их трудов: большинство языков программирования включают в себя вычисление хеша произвольного набора данных. В Python функция hash() для неизменяемых объектов встроена в сам язык.

Единственное обязательное свойство хеш-функции — однозначность. Хеш, посчитанный от двух одинаковых объектов, должен совпадать; нельзя каждый раз брать первое попавшееся число. Хеш неизменяемого объекта (например, string в Python) можно вычислять лишь единожды и потом хранить — это снизит общее количество вычислений.

Хеш-функция не обязана для каждого ключа давать уникальное число, не равное другим значениям функции (впрочем, в конце главы мы рассмотрим идеальные хеши, которые это умеют). Более того, ценой еще большей неуникальности мы можем резко уменьшить диапазон ее значений до 0… M – 1: возьмем остаток от деления на M.

В табл. 3.1 представлено 32-разрядное значение функции hash() для некоторых строк и соответствующий им остаток от деления на 15. Формула hash(key) % 15 обладает свойством однозначности, но если с точки зрения теории вероятности шанс на совпадение значений hash() у двух ключей исчезающе мал, то на малом диапазоне совпадение хешей вполне вероятно. В нашем примере таких совпадений два: «рифмы» — «возьми» со значением 10 и «ее» — «скорей» со значением 3. Несмотря на различие вероятностей, всегда стоит ожидать, что две разные строки могут иметь одинаковый хеш26.

Таблица 3.1. Пример значений функции hash() и хеш-суммы с диапазоном на 15 значений

Ключ	Значение hash(ключ)	Значение hash(ключ) % 15
Читатель	30 711 662 493 708 375	0
ждет	–8 425 886 308 320 884 491	14
уж	4 546 933 634 410 127 049	9
рифмы	5 680 402 382 273 197 615	10
розы	–2 463 836 295 302 140 937	13
На	8 516 920 402 432 418 136	6
вот	5 909 557 570 350 754 617	12
возьми	8 292 399 267 285 665 935	10
ее	2 740 441 431 699 165 093	3
скорей	4 193 948 643 156 477 063	3

Если использовать остаток от деления на M для того, чтобы вычислить хеш, hash(key) % M, стоит озаботиться тем, чтобы диапазон оказался не меньше, чем общее количество ключей.

Лет десять назад в Python (а в Java — до сих пор) встроенная функция hash() стабильно возвращала один и тот же конкретный хеш для каждого конкретного параметра. В современном Python в значения хешей при запуске интерпретатора подмешивается соль — независимое случайное значение. В течение работы одного процесса Python соль не меняется, но предсказать ее значение для очередного запуска интерпретатора невозможно — это повышает безопасность приложений. Если хеш предсказуем, хакер может наполнить словарь заранее просчитанными ключами с одинаковым хешем. Это нарушит равномерность их распределения в хеш-таблице, и производительность словаря упадет до O(N). Таким способом можно организовать так называемую DoS-атаку (от Denial of Service — «отказ в обслуживании»).

Больше информации относительно «подсоленного хеша» можно найти по ссылке https://oreil.ly/C4V0W и в Python-документации PEP 456. Кроме того, в конце главы есть упражнение на эту тему.

Хеш-таблица: хранение данных по ключу

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

class Entry:

  def __init__(self, k, v):

    self.key = k

    self.value = v

В примере 3.3 определен класс Hashtable, внутри которого в массиве table может храниться не более M объектов. Каждая из M позиций массива table — ячейка хеш-таблицы (по-английски bucket — «ведро» или «корзина»). Для начала определим, что каждая ячейка либо пуста, либо хранит ровно одну пару (объект типа Entry).

Пример 3.3. Неэффективная реализация хеш-таблицы

class Hashtable:

  def __init__(self, M=10):

    self.table = [None] * M     ❶

    self.M = M

  def get(self, k):             ❷

    hc = hash(k) % self.M

    return self.table[hc].value if self.table[hc] else None

  def put(self, k, v):          ❸

    hc = hash(k) % self.M

    entry = self.table[hc]

    if entry:

      if entry.key == k:

        entry.value = v

      else:                     ❹

        raise RuntimeError(f'Key Collision: {k} and {entry.key}')

    else:

      self.table[hc] = Entry(k, v)

❶ Заводим массив на M объектов.

❷ Метод .get() определяет номер ячейки по ключу k, для которого вычисляется хеш, и возвращает значение, если оно есть.

❸ Метод .put() определяет номер ячейки по ключу k, для которого вычисляется хеш, и перезаписывает хранящееся там значение — или записывает новое, если ячейка была пуста.

❹ Если хеш двух различных ключей приводит к одной и той же ячейке — это коллизия, происходит исключение.

Вот так нашей хеш-таблицей можно пользоваться:

table = Hashtable(1000)

table.put('Апрель', 30)

table.put('Май', 31)

table.put('Сентябрь', 30)

print(table.get('Август'))    # Промах: должно быть выведено None

print(table.get('Сентябрь'))  # Попадание: должно быть выведено 30

Если все работает как задумано, значит, в массиве на 1000 элементов нам удалось разместить три пары — объекты типа Entry. Скорость работы .put() и .get() не зависит от количества пар в таблице, так что их быстродействие можно оценить как O(1).

Если .get(key) не находит key в соответствующей хешу ячейке — это промах. Если .get(key) выбрал ячейку по хешу и ключ находящейся там пары равен key — это попадание. В таких случаях хеш-таблица работает так, как предполагается. Чего нам пока не хватает — это поведения на случай коллизии хеша, когда два или больше ключа имеют одинаковый хеш. Если не обрабатывать коллизии, метод .put(ключ) начнет удалять содержимое непустых ячеек, хеш ключа которых совпадает с хешем нового ключа. Смысла в хеше Hashtable, который теряет ключи, нет.

Определение коллизий и их разрешение последовательным просмотром

Вполне может случиться, что у ключей двух пар e1 = (key1, val1) и e2 = (key2, val2) окажется одинаковый хеш, несмотря на то что сами ключи будут разными. В табл. 3.1 и «возьми», и «рифмы» имеют хеш 10. Допустим, e1 попал в Hashtable первым. Тогда при попытке добавить туда еще и e2 возникнет коллизия хешей: для e2 будет вычислена та же ячейка, что и для e1, при этом ячейка будет уже занята, а ее ключ, key1, не будет равен key2 из e2. Если как-то это противоречие не разрешать, в одном объекте типа Hashtable нельзя будет хранить одновременно e1 и e2.

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

Допустим, мы добавили пару в ячейку, индекс которой не равен хешу ключа, потому что соответствующая ячейка была занята. Чтобы убедиться в том, что так делать вообще можно, надо придумать алгоритм поиска по такому ключу. Для начала договоримся, что удалять пары из Hashtable мы не будем, будем только добавлять. Понятно, что теперь чем больше пар мы добавляем в хеш-таблицу, тем длиннее становятся участки занятых ячеек в table. Тогда поиск довольно прост: по хешу ключа определяем первоначальную ячейку, а если ключи не совпадают, начинаем рассматривать все последующие непустые ячейки. Если в каком-то из этих просмотров ключи совпадут, нужная ячейка найдена, а если попадется пустая — соответствующей пары в таблице нет. То есть пара e1 найдется либо в ячейке с номером hash(e1.key) % M, либо в последующих непустых ячейках (с учетом перехода между концом и началом таблицы), либо не найдется.

На рис. 3.2 показано, как в Hashtable размером M = 7 с помощью последовательного просмотра добавляются пять пар с коллизией ключей (показаны только ключи). Заполненные серым ячейки — пустые. Ключ 20 попадает в table[6], потому что 20 % 7 = 6, ключ 15 — в table[1], а ключ 5 — в table[5].

Рис. 3.2. Как выглядит Hashtable после добавления пяти пар (ключ, значение)

Попытка добавить пару с ключом 26 приведет к коллизии, потому что ячейка table[5] уже занята (парой с ключом 5; на рис. 3.2 просмотр занятой ячейки выделен темным фоном), и запускается последовательный просмотр: сначала table[6], которая тоже занята, затем придется перевалить через конец таблицы и начать с начала, где для ключа 26 и отыщется первая свободная ячейка — table[0]. Добавление пары с ключом 19 тоже приводит к коллизии и просмотру всех непустых ячеек вплоть до table[2], которая наконец оказывается свободна.

В экземпляр Hashtable с рис. 3.2 можно добавить еще только одну пару: хотя бы одна ячейка должна оставаться незанятой. Куда попадет пара с ключом 44? Хеш ключа 44 % 7 = 2, ячейка 2 занята, а 3 — свободна, так что пара попадет в table[3]. Поскольку .get() и .put() пользуются одним и тем же алгоритмом просмотра, впоследствии эту пару можно будет найти с помощью .get(44).

Цепочкой для определенного хеша hc в таблицах с открытой адресацией наподобие нашего Hashtable называется последовательность ячеек в table. Эта последовательность начинается с table[hc] и продолжается вправо (с переходом из конца в начало table) вплоть до первой неиспользуемой ячейки, не включая ее. На рис. 3.2 цепочка для хеша 5 состоит из пяти элементов, хотя только в трех из них хеш ключа равен пяти. А для хеша 2 ключей вообще нет, но цепочка уже равна 1 из-за предыдущих коллизий. Длина цепочки не может превышать M – 1, потому что по правилам одна ячейка должна быть незанятой.

В примере 3.4 показано, как добавить открытую адресацию в Hashtable: класс Entry не меняется, а количество сохраненных пар запоминается в счетчике N для проверки того, что всегда есть хотя бы одна свободная ячейка (при этом запоминать, где она расположена, не надо!). Правило «одной свободной ячейки» очень важно, иначе цикл поиска while в .get() и .put() может оказаться вечным.

Пример 3.4. Реализация открытой адресации в Hashtable

class Hashtable:

  def __init__(self, M=10):

    self.table = [None] * M

    self.M, self.N = M, 0

  def get(self, k):

    hc = hash(k) % self.M           ❶

    while self.table[hc]:

      if self.table[hc].key == k:   ❷

        return self.table[hc].value

      hc = (hc + 1) % self.M        ❸

    return None                     ❹

  def put(self, k, v):

    hc = hash(k) % self.M           ❶

    while self.table[hc]:

      if self.table[hc].key == k:   ❺

        self.table[hc].value = v

        return

      hc = (hc + 1) % self.M        ❸

    if self.N >= self.M - 1:        ❻

       raise RuntimeError ('Table is Full.')

    self.table[hc] = Entry(k, v)    ❼

    self.N +=  1

❶ Начнем с первой же ячейки, в которой может быть ключ k.

❷ Если ключ найден, вернем соответствующее k значение.

❸ В противном случае просмотрим следующую ячейку, при необходимости продолжая просмотр с начала таблицы.

❹ Если table[hc] не занята, очевидно, k в table нет.

❺ Если ключ найден, обновим value соответствующей k ячейки.

❻ Если k нет в table, а свободная ячейка осталась одна, инициируем исключение RuntimeError.

❼ Запишем пару в свободную ячейку table[hc] и увеличим счетчик ключей N.

Так что, мы изобрели эффективный способ хранения? Теперь быстродействие .put() и .get() не зависит от M, размера таблицы ключей? Не тут-то было!

Связный список или динамический массив?

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

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

Размер связного списка определяется количеством узлов при его просмотре от начала до конца, начиная с указателя first, по всем next до тех пор, пока они не пусты. Сами узлы могут появляться в любом месте памяти и в любое время. В объектно-ориентированных языках удобно моделировать тип узла классом. В языках программирования с непосредственным выделением памяти необходимо освобождать память, выделенную под узел, если он больше нигде не используется. В других, например в Python и Java, выделением и освобождением памяти занимается сама исполняющая система языка.

Вставка в начало. Чтобы вставить узел в начало списка, надо этот узел, Node0, создать, положить в него нужное значение и сделать так, чтобы next, указатель на следующий элемент, ссылался на Node1. Кроме того, в переменной first следует переделать указатель на Node1 в указатель на Node0 (а также во всех других местах, ссылающихся на наш список).

Добавление в конец. Можно также хранить last — указатель на последний элемент связного списка. В этом случае для добавления значения в конец списка необходимо создать узел Node4 с пустым полем next, сохранить в узел требуемое значение, сходить по ссылке из last (в нашем случае это будет узел Node3), заменить там поле next указателем на Node4 и сам last тоже переделать в указатель на Node4.

Вставка в произвольное место. Если заранее известно, что новый узел q необходимо вставить после конкретного узла p, надо создать этот новый узел q с нужным значением и полем next, которое совпадает с полем next узла p. После чего поле next узла p сделать указателем на новый узел q.

Удаление произвольного элемента. Чтобы удалить некое значение из списка, необходимо найти узел, поле next которого указывает на узел, содержащий искомое значение. Тогда значение next искомого узла записывается в next узла-предшественника (где раньше была ссылка на искомый узел). Отдельно обрабатываются случаи, когда искомым оказывается первый или последний узел. Кроме того, следует соблюдать принятые в языке программирования договоренности по освобождению памяти.

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

Связные списки в Python не используются никогда — или почти никогда: вместо них следует применять динамические массивы. Гвидо ван Россум, автор языка Python, даже назвал такой тип данных list, прозрачно намекая на область его применения.

Рассмотрим таблицу сравнения быстродействия различных операций над связными списками и динамическими массивами.

Операция	Связные списки	Динамические массивы
Поиск элемента	O(N)	O(N)
Двоичный поиск элемента	Невозможен	Возможен
Поиск элемента по индексу	O(N)	O(1)
Добавление и удаление элемента в конце	O(1)	O(1)
Добавление и удаление элемента в произвольном заранее известном месте	O(1)	В среднем O(N)
Добавление и удаление элемента в начале	O(1)	O(N)
Количество операций «выделение памяти» при добавлении N элементов	O(N)	O(log N)

Как видно из таблицы, list в Python работает не хуже или даже лучше, чем связный список, за исключением случая, когда приходится модифицировать размер списка не в его конце. В самом деле, для вставки нового элемента в связный список, допустим между вторым и третьим элементами, достаточно указатель на третий записать в поле next нового элемента, а в поле next второго записать указатель на этот новый. А вот для вставки третьего элемента в динамический массив нужно добавить пустой элемент в его конец (это операция быстрая), а затем переставить все элементы, начиная с последнего, на одну позицию вперед — N – первый записать в позицию N, N – второй — в позицию N – 1 и т.д. до третьего, который записывается в позицию 4, освобождая тем самым место для нового элемента в позиции 3. Эта операция, очевидно, достаточно неэффективна — порядка N.

Поначалу кажется, что такое различие быстродействия при работе с почти любым элементом списка сводит на нет все преимущества list. Однако в действительности важными являются только операции работы с началом списка. Например, эффективно реализовать абстракцию «очередь» (FIFO — «первым вошел, первым вышел») с помощью list нельзя. Для этого в Python есть отдельный тип данных — collections.deque, в котором операции с обоих концов списка одинаково быстры (за счет некоторых накладных расходов).

А вот эффективная работа (удаление или добавление) с элементом в произвольной позиции не дает связному списку практически никаких преимуществ перед list. Для того чтобы понять, что вставка или удаление должны происходить в позиции k, эту k надо сначала определить. А все операции поиска в связном списке — как по значению, так и по индексу — линейны. Таким образом, например, в операции «поиск + вставка» линейный поиск доминирует над константной вставкой, и порядок ее сложности оказывается одинаков и для связных списков, и для динамических массивов (в которых, как мы видим, с поиском еще и получше).

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

Посмотрим, что происходит в худшем случае. Поначалу Hashtable на N элементов пуст27 и пара добавляется в пустую ячейку — для определенности пусть в table[0]. Если теперь каждый из оставшихся N – 1 запросов на добавление будет приводить к коллизии ключа, сколько всего ячеек придется за это время просмотреть? Для первого запроса — одну, для второго — две (из-за коллизий в первой), для третьего — три и т.д. Очевидно, во время k-го запроса придется просмотреть k ячеек. Значит, всего просмотров будет 1 + 2 + … + (N – 1), то есть N × (N – 1) / 2. Если поделить на количество запросов N, получится в среднем (N – 1) / 2 действий на один .put().

Согласно классификации из главы 2, сложность (N – 1) / 2 — это O(N). В самом деле, если раскрыть скобки, получится (N / 2) – 1/2. Порядок сложности определяется доминирующей составляющей — N / 2. Выходит, что в худшем случае количество просмотренных ячеек прямо пропорционально N (в нашем алгоритме равно половине N).

Итак, мы рассмотрели наихудший случай, в котором среднее количество просмотров ячеек оценивается как O(N). В алгоритме мы оценивали количество просмотров ячеек, а не время работы или количество инструкций, потому что производительность get() и put() напрямую зависит от количества просмотров.

Похоже, мы зашли в тупик. Можно увеличить M, размер table, так, чтобы он значительно превосходил возможное количество хранимых ключей, N, — тогда для случайных ключей количество коллизий (а следовательно, и время поиска) в таблице уменьшится28. Однако стоит ошибиться с прогнозами относительно N — и по мере приближения его к M производительность будет становиться все ужаснее; хуже того, на N = M – 1 переполнится table и значения вообще нельзя будет добавлять. В табл. 3.2 представлено время вставки N пар в структуру типа «Hashtable с открытой адресацией» размером M. Обратим внимание вот на что.

• Для небольшого N, скажем 32, среднее время работы (соответствующая строка таблицы) везде примерно одинаково, независимо от M, размера Hashtable, потому что M либо само по себе мало, либо значительно превосходит N.

• В любой Hashtable размером M среднее время вставки N ключей постоянно растет с увеличением N — это видно в соответствующем столбце таблицы.

• Любая диагональ «с северо-запада на юго-восток» в таблице содержит примерно одинаковое время работы. С учетом того, как меняются M и N в столбцах и строках таблицы, можно сказать, что для того, чтобы в Hashtable можно было вместо N ключей добавлять с той же средней скоростью 2N ключей, нужно увеличить ее размер вдвое.

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

Таблица 3.2. Среднее время добавления N ключей в таблицу Hashtable размером M (в миллисекундах)

	8192	16 384	32 768	65 536	131 072	262 144	524 288	1 048 576
32	0.048	0.036	0.051	0.027	0.033	0.034	0.032	0.032
64	0.070	0.066	0.054	0.047	0.036	0.035	0.033	0.032
128	0.120	0.092	0.065	0.055	0.040	0.036	0.034	0.032
256	0.221	0.119	0.086	0.053	0.043	0.038	0.035	0.033
512	0.414	0.230	0.130	0.079	0.059	0.044	0.039	0.035
1024	0.841	0.432	0.233	0.132	0.083	0.058	0.045	0.039
2048	1.775	0.871	0.444	0.236	0.155	0.089	0.060	0.047
4096	3.966	1.824	0.887	0.457	0.255	0.144	0.090	0.060
8192	—	4.266	2.182	0.944	0.517	0.276	0.152	0.095
16 384	—	—	3.864	1.812	0.908	0.484	0.270	0.148

Раздельное хранение цепочек в списках

Перепишем Hashtable так, чтобы в таблице хранились не сами пары, а цепочки пар с совпадающими ключами. Такой способ называется хешированием с раздельными цепочками. В случае последовательного просмотра для размещения пары нам приходилось искать очередную свободную ячейку, теперь же в ячейке table[idx] будет храниться не пара, а весь список пар, хеши ключей которых совпадают с idx. Если таких ключей нет, ячейка пуста: содержит пустой список (пример 3.5). Количество ячеек для удобства оставим M.

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

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

На рис. 3.3 пары (ключ, значение) добавляются в том же порядке, что и на рис. 3.2. Поначалу все ячейки пустые, это обозначено серым фоном. Первые три пары с ключами 20, 15 и 5 попадают в начало цепочек в соответствующих ячейках хеш-таблицы. Когда добавляется пара с ключом 26, возникает коллизия и эта пара добавляется в конец цепочки ячейки table[5]. То же самое происходит для ключа 19, так что в результате цепочка, соответствующая хешу 5, содержит три пары.

Рис. 3.3. Как выглядят цепочки Hashtable после вставки пяти пар (ключ, значение)

Пример 3.5. Вариант хеш-таблицы с раздельным хранением цепочек

class Hashtable:

    def __init__(self, M=10):

        self.table = [[] for i in range(M)]  ❶

        self.M = M

        self.N = 0

    def get(self, k):

        hc = hash(k) % self.M                ❷

        for entry in self.table[hc]:         ❸

            if entry.key == k:

                return entry.value

        return None

    def put(self, k, v):

        hc = hash(k) % self.M                ❷

        for entry in self.table[hc]:         ❸

            if entry.key == k:               ❹

                entry.value = v

                return

        self.table[hc].append(Entry(k, v))   ❺

        self.N += 1

❶ Написать self.table = [] * M значило бы создать список, все элементы которого являются одним и тем же объектом; нам же надо, чтобы это было M разных объектов (пускай они поначалу все равны []).

❷ Вычисляем номер ячейки hc (остаток от деления хешированного ключа k на размер таблицы).

❸ Ищем совпадение k с ключом одной из пар (быстродействие этой части пропорционально длине цепочки).

❹ Если пара с данным ключом k найдена, изменим хранимое значение.

❺ Добавим пару с новым ключом k в конец цепочки.

Методы .get() и .put() очень похожи: мы проходим по всем парам в цепочке table[hc] и сравниваем нулевой элемент пары (ключ) с k; если ключ найден — get() вернет значение, а put() поменяет старое значение на новое, если не найден — get() вернет None, а put() добавит пару (k, v) в конец цепочки.

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

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

Пример 3.6. Функция удаления пары по ключу

def remove(self, k):

    hc = hash(k) % self.M

    for i, entry in enumerate(self.table[hc]):  ❶

        if entry.key == k:

            del self.table[hc][i]               ❷

            self.N -= 1

            return entry.value                  ❸

    return None                                 ❹

❶ Функция enumerate(список) возвращает последовательность пар индекс элемента, элемент; индекс нам может потребоваться для удаления.

❷ Динамический массив позволяет удалять любой элемент по его индексу.

❸ Если ключ найден, возвращаем значение из удаленной пары.

❹ Если удаления не было, возвращаем None.

Стоит заметить, что операции над динамическим массивом (тип list), которые работают не с концом этого массива, обычно имеют линейную сложность, в среднем пропорциональную длине самого массива. Это относится как к операциям поиска вида элемент in список, так и к операциям удаления вида del список[i]. Поскольку массив — это непрерывный блок элементов в памяти, для удаления из него i-го элемента на место i-го надо переписать (i + 1)-й, на место (i + 1)-го — (i + 2)-й и т.д. до последнего элемента, который должен встать на место предпоследнего. Эта часть алгоритма очевидно зависит от длины списка и в среднем переставляет половину его элементов.

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

Насколько эффективны хеш-таблицы с раздельным хранением цепочек? Чтобы ответить на этот вопрос, надо посчитать и количество обращений к ячейкам таблицы, и количество просмотров пар в цепочке. Забегая вперед, скажу, что быстродействие таблиц с раздельными цепочками практически такое же, что и быстродействие таблиц с открытой адресацией. Единственное важное достижение — количество пар в раздельных цепочках может быть актуально бесконечным. Тем не менее, как мы скоро увидим, когда количество хранимых пар N заметно превышает количество ячеек M, производительность значительно падает. Требования к памяти у обоих методов примерно одинаковые, однако в случае с раздельными цепочками структура данных посложнее и нужно дополнительно заводить M пустых списков.

Оценка

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

Сначала оценим сложность по памяти: сколько ее требуется для хранения N пар (ключ, значение)? Обе структуры изначально содержат массив из M элемен­тов (при открытой адресации это пустые ячейки, при раздельном хранении цепочек — пустые списки ячеек). Для хеш-таблицы с раздельными цепочками N может быть сколь угодно большим, для хеш-таблицы с открытой адресацией N должно быть строго меньше M — значит, это M нужно выбирать, исходя из знания о максимально возможном количестве пар. В обеих структурах размер базового массива table прямо пропорционален M.

Когда мы добавим в хеш-таблицу все N пар, общий объем памяти при хранении с открытой адресацией не изменится, потому что базовый массив уже хранит ячейки типа Entry. При раздельном хранении цепочек каждая цепочка — это список из ячеек типа Entry, поэтому с каждой добавленной парой объем увеличивается на размер одной ячейки, и под конец размер этого дополнительного пространства будет прямо пропорционален N.

• Для открытой адресации требуется объем памяти, пропорциональный сразу и M, и N, но, поскольку N < M, можно просто заметить, что сложность по памяти в данном случае — O(M).

• Раздельное хранение цепочек для базового массива требует наличия памяти объемом, пропорциональным M, а для всех цепочек — памяти объемом, пропорциональным N; так что сложность по памяти стоит оценить как O(M + N).

Теперь возьмемся за сложность по времени. Основное действие — обращение к ячейке таблицы, а мы будем подсчитывать количество таких обращений. Наихудший случай наступает, когда все вычисленные хеши ключей оказываются равны. В обеих структурах при этом M – 1 цепочки пусты, а оставшаяся единственная цепочка, которая соответствует этому одному на всех хешу, содержит все N пар. Для наихудшего случая предположим, что искомый элемент всегда оказывается в конце этой цепочки, так что и поиск по списку при раздельном хранении, и поиск по самой таблице при открытой адресации прямо пропорционален N. Можно смело сказать, что независимо от реализации сложность худшего случая для операции get() — O(N).

Казалось бы, к чему тогда все наши усилия? Если хеш-функция исследована математически, она дает очень хороший разброс хешей на ожидаемом множестве ключей. В действительности с увеличением M вероятность коллизии уменьшается, а значит, уменьшаются и длины цепочек в наших структурах. В табл. 3.3 приведено сравнение обоих подходов: будем помещать 321 129 английских слов в хеш-таблицы размером M от N / 2 до 2N. Вдобавок в первой строке будут приведены данные по хеш-таблицам размером M = 20N, а в пяти последних — малых (непригодных для открытой адресации) размеров.

Таблица 3.3 показывает результаты двух измерений для каждого M, N.

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

• Максимальный размер цепочки в хеш-таблице. Этот параметр тоже годится для обеих структур и подсказывает ухудшение их быстродействия. Когда таблица с открытой адресацией близится к переполнению или хранимая цепочка становится чересчур длинной, быстродействие падает.

Таблица 3.3. Усредненные показатели при добавлении 321 129 ключей в хеш-таблицу размером M по мере уменьшения M

M	Раздельное хранение		Открытая адресация
	Средняя цепочка	Наибольшая цепочка	Средняя цепочка	Наибольшая цепочка
6 422 580	1.0	4	1.1	5
642 258	1.3	7	3.0	43
610 145	1.3	6	3.3	46
579 637	1.3	7	3.7	56
550 655	1.3	7	4.1	58
523 122	1.3	7	4.6	69
496 965	1.4	7	5.5	98
472 116	1.4	7	6.4	112
448 510	1.4	8	7.9	107
426 084	1.4	7	10.3	204
404 779	1.4	9	13.6	206
384 540	1.5	9	21.4	319
365 313	1.5	8	39.0	700
347 047	1.5	8	94.4	1516
329 694	1.6	8	784.5	9759
313 209	1.6	9	*	*
187 925	2.1	10	*	*
112 755	3.0	13	*	*
67 653	4.8	15	*	*
40 591	7.9	21	*	*
24 354	13.2	30	*	*

Все приведенные значения растут с уменьшением M29. Причина в том, что чем меньше хеш-таблица, тем больше случается коллизий при добавлении и цепочки ключей становятся длиннее. Хорошо видно, что в варианте с открытой адресацией этот рост существенно выше, особенно под конец, когда в одну многотысячную цепочку начинают сливаться последовательности ключей с разными хешами. Что еще хуже, стоит M оказаться меньше, чем N, и открытая адресация вообще становится неприменима (в таблице отмечено звездочками). А вот хранение цепочек в списках себя оправдало: в разумных пределах оно нечувствительно к этой проблеме. Когда размер таблицы M достаточно велик — скажем, в два раза больше количества хранимых элементов N, — средний размер цепочки вообще близок к 1, да и длина наибольшей цепочки сравнительно невелика. Тем не менее M нужно выбирать заранее, и в случае открытой адресации у нас закончится место, как только N станет равным M – 1.

С раздельным хранением не все так страшно. Таблица 3.3 показывает, что, даже когда N превышает размер таблицы M более чем десятикратно, списки растут себе и растут, и даже производительность не падает так ужасающе, как при открытой адресации c N, всего лишь примерно равным M. Это можно понять по размеру максимальной цепочки в списке, который приведен в той же таблице.

Изучив эти показатели, мы можем изобрести для хеш-таблицы размером M простую методику оценки эффективности. Производительность хеш-таблицы зависит от того, насколько она «заполнена», то есть от отношения N к M. В экономической науке есть похожее понятие — альфа-индекс30, но мы будем пользоваться более очевидным термином — «загруженность хеш-таблицы».

• При раздельном хранении цепочек показатель загруженности — это средняя длина цепочки (в отличие от данных в табл. 3.3, где приведена средняя длина только среди непустых цепочек). Этот показатель может превышать 1 и зависит только от объема доступной памяти.

• При открытой адресации показатель загруженности — это доля занятых ячеек таблицы. Наибольшее его значение — (M – 1) / M, так что он не может превышать 1.

Многолетние исследования показали, что хеш-таблицы начинают стремительно терять производительность при показателе загруженности больше 0,75 — например, когда таблица с открытой адресацией заполнена на 3/431. При раздельном хранении цепочек хеш-таблица не бывает совсем заполнена, но принцип остается тот же32.

На рис. 3.4 приведены средние и наибольшие длины цепочек после добавления N = 321 129 слов в хеш-таблицу размером M. Значение М меняется по оси ординат, длины отложены по оси абсцисс. Средние длины помечены ромбами, их шкала расположена слева от диаграммы, наибольшие — квадратами, их шкала — справа. Задавшись целью обеспечить определенный средний или наибольший размер цепочки для заранее известного количества ключей N, можно по аналогии с диаграммой на рис. 3.4 подобрать подходящее M.

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

Если бы мы могли расширять хеш-таблицу, то есть увеличивать M по необходимости, можно было бы удерживать оптимальный показатель загруженности! Как мы сейчас увидим, при должном старании такую таблицу сделать вполне реально.

Расширяемые хеш-таблицы

В классе DynamicHashtable из примера 3.7 заведено поле load_factor со значением 0.75. Это показатель загруженности, на основании которого вычисляется пороговая загруженность threshold.

Пример 3.7. Определение показателя и порога загруженности при создании динамической хеш-таблицы

class DynamicHashtable:

    def __init__(self, M=10):

        self.table = [[] for i in range(M)]

        if M < 1:

            raise ValueError('Hashtable storage must be at least 1.')

        self.M = M

        self.N = 0

        self.load_factor = 0.75

        self.threshold = min(M * self.load_factor, M-1)         ❶

❶ Для M ≤ 3 порог не должен превышать M – 1.

Что делать, если хеш-таблица будет заполнена свыше порогового значения? Распространенный подход геометрического масштабирования рекомендует сразу увеличивать таблицу вдвое. Точнее, увеличивать вдвое и еще прибавлять к размеру единицу. Как только количество занятых ячеек таблицы table превысит порог (threshold), для эффективной работы понадобится таблицу увеличить. В примере 3.8 приведен доработанный метод put() для раздельно хранимых цепочек.

Пример 3.8. Доработанный метод put(), который вызывает resize()

    def put(self, k, v):

        hc = hash(k) % self.M

        for entry in self.table[hc]:

            if entry.key == k:

                entry.value = v

                return

        self.table[hc].append(Entry(k, v))      ❶

        self.N += 1

        if self.N >= self.threshold:            ❷

            self.resize(2*self.M + 1)           ❸

❶ Добавим новую ячейку в конец цепочки table[hc].

❷ Проверим, не превысило ли N порог.

❸ Увеличим размер массива ячеек вдвое (плюс еще одна ячейка).

Процедура удвоения создает новый массив (при открытой адресации — ячеек, при раздельном хранении — цепочек) и заново добавляет в эту новую таблицу все пары (ключ, значение). Поскольку загруженность таблицы стала равна пороговой, но не превысила ее, мы ожидаем в среднем константное время добавления одной ячейки и, следовательно, в среднем линейную сложность функции resize() по отношению к количеству ячеек, то есть предположительно O(M). Прежде чем продвинуться дальше, попытаемся (некорректно!) упростить процедуру удвоения. Во многих языках программирования есть операция копирования части или целого массива в другой массив. Эта операция уж точно имеет сложность O(M), ибо копировать надо ровно M ячеек старого массива. Почему бы нам просто не скопировать старый массив в новый? А в случае Python так и вовсе просто добавить M + 1 ячеек прямо в конец старого (тип данных list позволяет сделать это очень эффективно)? Не окажется ли такое решение в несколько раз быстрее повторного добавления всех пар в таблицу?

Так-то оно так, только работать как надо эта операция не будет! После механического расширения хеш-таблицы с открытой адресацией некоторые ее элементы нельзя будет найти, а раздельно еще и хранимые цепочки окажутся некорректными! На рис. 3.5 показано, к чему приводит механическое удвоение размера таблицы для обоих подходов. Попробуйте, к примеру, проследить, что произойдет с ключами 19 и 26.

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

Начнем искать ключ 19. Хеш этого ключа — 19 % 15 = 4, но соответствующая ячейка будет пуста в обеих структурах, то есть его там как бы нет. При старом размере таблицы с открытой адресацией M = 7 последовательный просмотр цепочки (с перезапуском от начала таблицы) приводил пару с ключом 19 в ячейку 2. А теперь и хеш другой, и размер, так что возврат к началу таблицы происходит после ячейки 15, то есть алгоритм поиска не соответствует действительности.

По чистой случайности в таблице с открытой адресацией некоторые ключи все же можно найти, но алгоритм их поиска не будет адекватен исходному. Например, ключ 20 будет найден, но не сразу (в table[5]), а последовательным просмотром, в table[6]. Точно так же и ключ 15 найдется не в table[0], а в table[1]. И только ключ 5 остается на своем месте — потому что его хеш не изменился.

Дело, конечно же, в том, что при увеличении таблицы меняется хеш-функция, так что элементы, скорее всего, окажутся не на своих местах. Придется вернуться к идее повторного хеширования: создадим пустую хеш-таблицу размером 2M + 1 и заново добавим в нее все пары из исходной таблицы. В терминах примера 3.9: каждую пару (ключ, значение) исходного массива self.table добавим в новую таблицу temp с помощью temp.put(ключ, значение) — тогда все пары точно можно будет найти. Воспользуемся динамической природой объектов Python и подменим старый массив новым (никакого копирования ячеек при этом не происходит). В результате у нового массива окажется два имени — self.table и temp.table, а у старого — ни одного, и вскорости он будет удален исполняющей системой Python. При выходе из функции resize() прекращает существование переменная temp, и все объекты, у которых не осталось имен, также будут удалены — но новый массив никуда не денется: у него останется еще одно имя. Этот способ подходит обеим схемам хранения цепочек.

Пример 3.9. Динамическое масштабирование таблицы с открытой адресацией путем повторного хеширования

def resize(self, new_size):

    temp = DynamicHashtable(new_size)                   ❶

    for key, value in self.table:

        temp.put(key, value)                            ❷

    self.table, self.M = temp.table, temp.M             ❸

    self.threshold = self.load_factor * self.M

❶ Создаем временную хеш-таблицу нужного размера.

❷ Добавляем в нее все пары из старой таблицы.

❸ Обновляем массив ячеек, значение M и порог threshold.

При раздельном хранении цепочек процедура практически не меняется, надо только вспомнить, что элементы массива table не сами ячейки, а их списки (пример 3.10).

Пример 3.10. Динамическое масштабирование таблицы с раздельным хранением цепочек путем повторного хеширования

def resize(self, new_size):

    temp = DynamicHashtable(new_size)                  

    for bucket in self.table:                           ❶

      for key, value in bucket:                         ❷

          temp.put(key, value)                          

    self.table, self.M = temp.table, temp.M             

    self.threshold = self.load_factor * self.M

❶ Внешний цикл — по спискам ячеек.

❷ Внутренний цикл — по ячейкам в списке.

Итак, мы определили механизм масштабирования хеш-таблицы. На рис. 3.6 показано, как в действительности должны выглядеть таблица с открытой адресацией (см. рис. 3.2) и таблица с раздельными цепочками (см. рис. 3.3) после увеличения размера с 7 до 15.

Рис. 3.6. Структура хеш-таблиц после масштабирования с повторным хешированием

Насколько лучше стало с применением масштабирования? Проведем эксперимент: для каждого начального размера таблицы M предпримем 25 тестов, в которых будем измерять:

• время заполнения — время, которое потребуется для того, чтобы добавить N = 321 129 ключей в хеш-таблицу с начальным размером M и удвоением размера при превышении порога загруженности;

• время доступа — время, за которое мы найдем в получившейся таблице все N ключей.

В табл. 3.4 приведены результаты измерения времени заполнения и времени доступа для хеш-таблиц с открытой адресацией и с раздельными цепочками, причем начальный размер таблицы, M, меняется от 625 до 6 400 000. В последней строке приведены аналогичные данные для хеш-таблицы фиксированного размера на 428 172 ячейки — этот размер соответствует пороговому заполнению таблицы 321 129 элементами, потому что 428 172 × 0.75 = 321 129, и сравнение вполне оправданно.

Таблица 3.4. Сравнение масштабируемых хеш-таблиц с таблицами фиксированного размера (время в миллисекундах)

M	Раздельные цепочки		Открытая адресация
	Время заполнения	Время доступа	Время заполнения	Время доступа
625	0.783	0.173	1.050	0.197
1250	0.783	0.176	1.057	0.198
2500	0.787	0.177	1.053	0.198
5000	0.780	0.175	1.059	0.200
10 000	0.798	0.180	1.069	0.200
20 000	0.782	0.176	1.062	0.201
40 000	0.775	0.177	1.037	0.204
80 000	0.763	0.176	1.015	0.203
160 000	0.722	0.177	0.932	0.209
320 000	0.627	0.182	0.747	0.208
640 000	0.409	0.164	0.327	0.178
…	…	…	…	…
Фиксированное значение	0.378	0.172	0.434	0.285

В последнем ряду приведен «наихудший идеальный» случай: идеальный — потому что размер таблицы заранее подобран так, чтобы показатель загруженности не превысил 0.75 (стало быть, resize() не вызывается), а наихудший — потому что под конец заполнения таблицы он вплотную подходит к пороговому значению. Разумно ожидать, что в этом случае и время заполнения, и время доступа в таблице с открытой адресацией будут несколько больше аналогичных параметров в таблице с раздельными цепочками: в первом случае коллизии одного хеша в конце концов начинают неизбежно удлинять несколько разных цепочек, а во втором — только одну, которая этому хешу соответствует. А вот для «слишком идеального» случая в предпоследней строке (с таблицей, заполненной примерно наполовину) может выиграть открытая адресация — за счет более простой структуры, которая требует линейно меньше операций. Что более важно: время доступа к N = 321 129 элементам динамической хеш-таблицы не зависит от ее начального размера M, так что отпадает необходимость магически предсказывать этот размер заранее.

Оценка производительности динамических хеш-таблиц

Уже говорилось, что чисто теоретически хеши всех ключей могут совпасть и угодить в одну цепочку (как при открытой адресации, так и для цепочек в спис­ках). Как следствие, время выполнения операций put() и get() будет прямо пропорционально количеству элементов в хеш-таблице N, а значит, в наихудшем случае сложность этих операций следует оценить как O(N).

Довольно частое требование к хеш-функции — равномерное распределение хешей на всем множестве значений. Если это свойство обеспечить, любой случайный ключ будет иметь равную вероятность попасть в любую цепочку. В идеале средняя длина отдельной цепочки должна быть равна N / M, это доказывается математически. Остается только надеяться на то, что специалист, который разработал для Python функцию hash(), предусмотрел и равномерное распределение в ней33.

Раз уж у нас таблица динамически растет, причем N гарантированно меньше, чем M, можно уверенно утверждать, что среднее значение N / M — это константа, то есть O(1), а стало быть, оно не зависит от N.

Если ключ есть в таблице, поиск завершается попаданием, а если нет — промахом. Предположим, хеш-функция равномерно распределяет значения, и оценим среднее количество обращений к ячейкам таблицы с открытой адресацией и пороговым значением alpha для обоих результатов. В случае попадания придется просмотреть в среднем (1 + 1 / (1 – alpha)) / 2 ячеек, для alpha = 0.75 получается 2.5. В случае промаха результат равен 1 + 1 / / (1 – alpha)2 / 2, то есть 8.5, при тех же условиях.

Стоит понять, во что нам обходится динамическое изменение размера таблицы — допустим, с порогом загруженности 0,75 и геометрическим масштабированием (удвоением). Возьмем для начала M = 1023, а N — гораздо большим, чем M. К примеру, используем все тот же словарь из 321 129 английских слов. Попробуем посчитать, сколько раз мы добавляем пару в таблицу, в том числе в новую, внутри функции resize().

Первый раз resize() вызовется при добавлении 768-го ключа (потому что 768 ≥ 767.25 = 0.75 × 1023), и размер таблицы M станет равен 1023 × 2 + 1, то есть 2047. В процессе масштабирования нам придется заново добавить все 768 ключей (повторно вычисляя их хеши). Заметим, что в результате показатель загруженности упадет до 768 / 2047, то есть примерно до 0.375.

После добавления еще 768 ключей их количество опять подойдет к пороговому — 1536, и все пары будут перенесены (с повторным хешированием) в новую таблицу размером M = 2047 × 2 + 1, то есть 4095. В третий раз масштабирование произойдет после добавления еще 1536 ключей, и придется добавлять уже 3072 пары в таблицу размером 8191.

Что эти числа нам говорят? Посмотрим на табл. 3.5: там показано количество слов N, которые надо добавить в таблицу, чтобы произошло масштабирование, а еще — каково будет после этого общее число операций добавления ключа в таблицу. После каждого перехеширования будет увеличиваться, а затем снова падать среднее количество операций добавления на один хранимый элемент. Эта характеристика — отношение общего числа добавлений к N — представлена в последнем столбце. В нашем случае она никогда не превышает 3 в силу геометрической природы масштабирования — и это несмотря на то, что при каждой смене размера нужно заново добавлять все ключи из старой таблицы в новую.

Главное, что понятно из этих данных: с увеличением размера таблицы геометрическое масштабирование происходит значительно реже. В последней строке показано, как с добавлением заключительного слова среднее количество операций становится равным 2.22, и при этом масштабирование не понадобится еще для 72 087 добавлений. Если первый интервал между операциями масштабирования составлял 768 добавлений, то девятый (196 608) уже в 28 = 256 больше.

Если исследовать алгоритм геометрического масштабирования аналитически, картина не меняется. Для начала заметим, что ни размер таблицы, ни пороговый коэффициент загруженности на подсчет среднего количества добавлений не влияют. В самом деле, перед очередной операцией масштабирования в таблицу размером M уже добавлено N = M × 3/4 ячеек в соответствии с пороговым значением. При масштабировании размер таблицы становится 2M (забудем на время про одну дополнительную ячейку), а новое пороговое значение — 2M × 3/4 = 2N. При этом на операцию масштабирования тратится еще N добавлений, N ячеек в новой таблице оказываются заняты, и еще 2N – N = N ячеек туда можно добавить до следующего масштабирования. В следующий раз нам потребуется уже 2N добавлений, чтобы скопировать старую таблицу, и 2N добавлений останется в запасе.

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

Слово	M	N	Всего	В среднем
absinths	1023	768	1536	2.00
accumulatively	2047	1536	3840	2.50
addressful	4095	3072	8448	2.75
aladinist	8191	6144	17 664	2.88
anthoid	16 383	12 288	36 096	2.94
basirhinal	32 767	24 576	72 960	2.97
cincinnatian	65 535	49 152	146 688	2.98
flabella	131 071	98 304	294 144	2.99
peps	262 143	196 608	589 056	3.00
…	…	…	…	…
zyzzyvas	524 287	321 129	713 577	2.22

Итак, сколько добавлений выполнено между этими двумя операциями масштабирования? N — для новых элементов и 2N — при повторном хешировании. Вот и весь секрет «магического» числа 3, к которому приближается среднее количество операций на элемент в хеш-таблице! После первого же масштабирования на каждое добавление нового элемента приходятся дополнительно еще две операции при копировании. Если бы начинали сразу с полупустой таблицы, это отношение было бы равно строго 3. Но, поскольку мы начинаем с пустой таблицы размером M и, следовательно, имеем M / 2 «неучтенных» свободных ячеек, да еще после удвоения прибавляем дополнительную ячейку, отношение общего количества добавлений к количеству хранимых ключей в хеш-таблице с геометрическим удвоением всегда меньше 3.

В частности, добавление всех N = 321 129 слов в нашу динамически расширяемую хеш-таблицу медленнее добавления в неизменяемую таблицу подходящего для N размера не более чем втрое. Как мы уже договорились в главе 2, это всего лишь мультипликативная постоянная и она не влияет на оценку сложности операции put() в среднем: даже несмотря на дополнительные затраты на масштабирование сложность остается O(1).

Динамические массивы

Мы уже несколько раз указывали на то, что тип list в Python реализован как массив; строго говоря — как таблица, то есть массив ссылок на объекты. Объекты Python могут быть разного размера, а вот ссылки — всегда одинакового. Наиболее распространен интерпретатор Python, написанный на С, так называемом CPython; в нем, как в С, ссылки — это просто адреса соответствующих структур в оперативной памяти. Доступа к этим ссылкам программист почти не имеет: в том же CPython функция id(объект) вернет число, соответствующее адресу объекта в памяти, но смысла в этом немного, ибо сделать с ним ничего нельзя, да и сам этот id не обязан быть уникальным. Например, если создать произвольный объект (скажем, строку), затем удалить его, потом создать объект другого типа (скажем, кортеж), есть шанс, что оба эти объекта получат одинаковый id, потому что будут каждый в свое время расположены по одному и тому же адресу оперативной памяти.

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

Последовательная организация оперативной памяти предполагает, что «классические» массивы могут иметь только заранее заданный размер. Скажем, в восьми идущих подряд ячейках памяти находится массив из восьми целых чисел A, а в следующих восьми — массив из четырех вещественных чисел двойной точности B. Добавить больше восьми элементов в массив A невозможно: дальше начинается стартовый элемент массива B, и если записать в A[8] целочисленное значение, то в B[0] окажется что-то совсем невообразимое. Тем не менее в списки Python можно добавлять сколько угодно элементов, и я указывал на то, что операция эта сравнительно дешевая — в среднем O(1).

Ничего не напоминает? Конечно же, ситуацию с переполнением хеш-таблицы, только в упрощенной форме! Допустим, объект A типа list занимает восемь ячеек памяти и все они уже заняты: len(A) равно 8. Тогда операция A.append(объект) начнется с масштабирования массива, причем тоже геометрического и тоже с коэффициентом 2. Опуская подробности: будет выделен фрагмент памяти на 16 ячеек, туда скопировано содержимое восьми ячеек из старого фрагмента, добавлено значение девятой ячейки (ссылка на объект), имя A начнет указывать на этот новый фрагмент, а старый будет освобожден. При этом len(A) будет возвращать 9, и в A останется еще семь свободных мест для добавления новых объектов за константное время. Как и в случае динамической хеш-таблицы, операция добавления в динамический массив, достигший предела загруженности (здесь он просто равен 1), имеет линейную сложность. Мы уже знаем, что геометрическое масштабирование гарантирует нам O(1) в среднем, с мультипликативной постоянной 3.

Вот и весь секрет! Прежде чем двинуться дальше, остается сделать два важных замечания. Во-первых, мы не рассматривали операцию удаления ключа из хеш-таблицы, потому что она сравнительно редко требуется. Однако удаление элемен­та из динамического массива требуется сплошь и рядом, оно имеет в среднем линейную сложность (из-за «сдвига» элементов) и в среднем константную сложность при удалении последнего элемента, например, для A.pop(). Логично предположить, что при достижении некоторого нижнего порога загруженности (скажем, в четверть прежнего размера) нам захочется уменьшить размер массива. Это делается ровно тем же способом, геометрическим масштабированием, только в меньшую сторону, и ровно по этой причине также не влияет на константность операции .pop().

Во-вторых, здесь кажется уместным ответить (или, скорее, не ответить) на вопрос «Как Python справляется с фрагментацией памяти?». Суть вопроса в следующем. Допустим, мы создали сто динамических массивов и они расположились в оперативной памяти, как и полагается, подряд. Затем в каждый второй из этих массивов мы добавили столько элементов, что произошло их масштабирование. При этом, как мы договорились, для этих 50 элементов была выделена новая память, а старая освобождена. В результате фрагмент памяти, в котором изначально лежали все 100 массивов, приобрел вид «массив, свободное место, массив, свободное место, массив…». Итак, вопрос: не захламляют ли такие структуры оперативную память и кто в случае Python заведует всем этим хозяйством? Ответ: разумеется, захламляют, и заведует этим исполняющая система Python, пользуясь программным интерфейсом операционной системы.

Эффективное управление памятью — серьезная, активно развивающаяся дисциплина IT, не имеющая ни идеального, ни даже просто устраивающего всех решения. Ей посвящены многие научные и практические труды. В книге мы не станем посягать на эту тему. Чтобы оценить масштаб проблемы, задумаемся еще вот над чем. Допустим, мы создали 100 обычных объектов Python, а потом просто удалили каждый второй. Не произойдет ли и здесь фрагментации памяти, и если да, то кто и что с ней будет делать? Ведь такое происходит, считай, постоянно? Изучение этого вопроса столь же занимательно, сколь и обширно, оно может окончательно увести в сторону от главной темы. Лучше вернемся к ней.

Идеальный хеш

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

В примере 3.11 приведен вариант такой функции perfect_hash(), сгенерированный сторонним модулем perfect-hash из файла, в котором в каждой строке расположен один ключ — слово из бессмертного пушкинского «Читатель ждет уж рифмы розы; / На, вот возьми ее скорей!» (без знаков препинания и прописных букв, зато с буквами «е»)34. Несущественную отладочную информацию и комментарии мы удалили.

Пример 3.11. Идеальный хеш для десяти пушкинских слов

G = [0, 10, 3, 10, 10, 8, 1, 0, 3, 5, 6]

S1 = [4, 10, 4, 6, 9, 7, 1, 6]

S2 = [7, 1, 6, 1, 6, 8, 8, 9]

def hash_f(key, T):

    return sum(T[i % 8] * ord(c) for i, c in enumerate(key)) % 11

def perfect_hash(key):

    return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 11

Мы уже пользовались встроенной в Python функцией enumerate(), которая возвращает последовательность пар (индекс, элемент) для любой итерируемой последовательности. Строго говоря, исходная последовательность даже не обязана сама быть индексируемой, то есть конструкция последовательность[i] может быть синтаксически недопустимой. Но если существует возможность пройтись по ней циклом вида for элемент in последовательность, то всегда возможна конструкция вида for индекс, элемент in enumerate(последовательность). Переменная индекс при этом будет расти от 0 с шагом 1. Если при проходе циклом нужны и элементы, и их индексы, рекомендуется в любом случае использовать enumerate(), как в примере:

>>> for index, character in enumerate("QWE"):

...     print(index, character)

Вспомним, как на рис. 3.1 мы задали массив day_array и в дополнение к нему — функцию base32(), которая вычисляла хеш каждого из 12 месяцев. Тогда размер этого массива зависел от найденного нами числа — 35, остатки деления хешей каждого месяца на которое все оказываются различными. Тем самым мы задали идеальную для месяцев года хеш-функцию, формула которой — day_array[base32(месяц)%35]. Алгоритм из perfect-hash достигает того же эффекта, но существенно более остроумным способом. Не пытаясь описать методику создания полученных структур данных и функций35, попробуем убедиться хотя бы в том, что это именно хеш и он идеален для наших ключей.

Итак, у нас есть массив G, размер которого (11) превосходит общее количество ключей N = 10, два вспомогательных массива S1 и S2 меньшей длины (ниже мы убедимся, что эта длина растет очень незначительно по сравнению с ростом N), вспомогательная хеш-функция hash_f() и собственно perfect_hash(), которая, поверим авторам на слово, будет выдавать идеальный хеш для заданного множества ключей. Чтобы вычислить хеш ключа «уж», необходимо сначала получить два промежуточных значения:

• hash_f('уж', S1) = (S1[0] * ord('у') + S1[1] * ord('ж')) % 11, то есть (4 × 1091 + + 10 × 1078) % 11 = 15 144 % 11 = 8 (1091 и 1078 — порядковый номер букв «у» и «ж» в таблице Unicode);

• hash_f('уж', S2) = (S2[0] * ord('у') + S2[1] * ord('ж')) % 11, то есть (7 × 1091 + + 1 × 1078) % 11 = 8715 % 11 = 3.

Функция perfect_hash('уж') вычисляет (G[8] + G[3]) % 11, то есть (3 + 10) % 11 = 2. Таким образом, хеш ключа «уж» равен 2. Повторим упражнение на ключе «вот»:

• hash_f('вот', S1) = (4 × 1074 + 10 × 1086 + 4 × 1090) % 11 = 19 516 % 11 = 2;

• hash_f('вот', S2) = (7 × 1074 + 1 × 1086 + 6 × 1090) % 11 = 15 144 % 11 = 8;

• perfect_hash('вот') = (G[2] + G[8]) % 11 = (3 + 3) % 11 = 6.

Продолжая в том же духе, получим, что хеш «уж» — это 2, хеш «вот» — 6, и вообще хеш каждого слова из «читатель ждет уж рифмы розы на вот возьми ее скорей» уникален. Математика36 временами творит настоящие чудеса!

В примере 3.12 приведена функция perfect_hash(), которую сгенерировал этот модуль для нашего тренировочного словаря из 321 129 слов. На самом первом английском слове — a — функция возвращает 0, а на последнем, zyzzyvas — 321128. Сам массив G, содержащий 667 596 промежуточных ключей, я здесь, понятное дело, не привожу, а вот два массива S1 и S2 для вычисления идеального хеша все еще невелики.

Пример 3.12. Часть текста программы с идеальным хешем для словаря английских слов

S1 = [394429, 442829, 389061, 136566, 537577, 558931, 481136, 337378,

      395026, 636436, 558331, 393947, 181052, 350962, 657918, 442256,

      656403, 479021, 184627, 409466, 359189, 548390, 241079, 140332]

S2 = [14818, 548808, 42870, 468503, 590735, 445137, 97305, 627438,

      8414, 453622, 218266, 510448, 76449, 521137, 259248, 371823,

      577752, 34220, 325274, 162792, 528708, 545719, 333385, 14216]

def hash_f(key, T):

        return sum(T[i % 24] * ord(c) for i, c in enumerate(key)) % 667596

def perfect_hash(key):

        return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 667596

Читатель может самостоятельно изготовить полный пример: установить Python-модуль perfect-hash и выполнить команду python3 -m perfect_hash --hft=2 words.english.txt, используя файл words.english.txt из репозитория с программами к книге. Поскольку при наполнении служебных массивов модуль использует случайный выбор, числа в получившемся примере будут другие и длина G наверняка будет слегка отличаться.

Промежуточная функция hash_f() генерирует довольно большое число — сумму значений из S1 или S2, — далее это число обрезается с помощью остатка от деления на 667 596, что дает индекс каждой из половин хеша в большом массиве G. После того как половины складываются и снова обрезаются до 667 596, получается уникальный ключ для любого допустимого английского слова из нашего словаря в диапазоне от 0 до 667 595. В действительности все еще интереснее: алгоритм рассчитан так, что perfect_hash(слово) возвращает индекс этого слова во входном списке, то есть число от 0 до 321 128, и это значение (в отличие от содержимого S1, S2 и G) не меняется при повторной генерации текста функции.

Если попробовать внезапно посчитать хеш чего-то, что не является словом из исходного словаря, может возникнуть коллизия. В примере 3.9 слово watered и не слово not-a-word получали одинаковый хеш; в только что сгенерированном примере на not-a-word может не быть коллизии, но она (в силу того что всевозможных не слов гораздо больше, чем 667 595) обязательно появится на каких-то других парах «слово — не слово». Интересная задача — отыскание таких пар для конкретного варианта perfect_hash(). В этом нет никакой ошибки: за то, что нашей функции будут предъявляться только слова из исходного словаря, отвечает программист.

Проход таблицы циклом

Основная задача хеш-таблицы — эффективные операции get(k) и put(k, v). Но еще было бы неплохо иметь доступ ко всем ячейкам таблицы, независимо от того, какой цепочке они принадлежат и какой подход — открытая адресация или раздельное хранение — используется для их хранения.

Генератор, или вычислимая последовательность, — один из самых удобных инструментов Python. В современном языке программирования для последовательного просмотра некоторого набора данных не нужно задействовать отдельную память со списком этих данных. В главе 2 вы уже видели, что вычислимые последовательности range(0, 1000) и range(0, 100000) занимают одинаковый объем памяти, порождая соответствующие последовательности целых чисел. Генератор-функция — общая форма задания вычислимой последовательности в Python.

Вот такая генератор-функция изготовит и вернет вычислимую последовательность целых неотрицательных чисел от 0 до n, в десятичном представлении которой нет заданной цифры (пример 3.13).

Пример 3.13. Задание генератор-функции

{{{#highlight py3

def avoid_digit(n, digit):

  sd = str(digit)for i in range(n):

    if not sd in str(i):

      yield i

}}}

Анализируя синтаксис описания функции, Python обнаружит в ней оператор yield, и это будет значить, что это генератор-функция, которая при вызове возвращает собственно генератор. Генератор-функцию надо вызвать один раз, получить генератор, а по генератору — пройтись циклом. Когда мы первый раз в цикле обращаемся к генератору, выполняются строки от начала функции до первого встреченного yield. В примере — от строки 2 до строки 5, при этом в цикл возвращается выражение, указанное параметром yield (в примере — i). В следующий раз выполнение продолжается непосредственно после выполненного yield и до следующего yield. Здесь yield — последняя строка блока цикла, так что выполнение продолжается со строки 3 до строки 5, затем снова возвращается i, и так до тех пор, пока вычисляется цикл. Выход за пределы функции (в примере — когда i сравняется с n) означает останов цикла, использующего генератор.

Посмотрим, как работает наша avoid_digit() в командной строке Python (пример 3.14).

Пример 3.14. Работа генератор-функции

>>> gen = avoid_digit(15, "3")                 ❶

>>> gen                                        ❷

>>> for element in gen:                        ❸

...     print(element, end=" ")

... print()

>>> for element in gen:                        ❹

...     print(element, end=" ")

... print()

❶ Создадим генератор и назовем его gen.

❷ Еще раз убедимся в том, что avoid_digit() возвращает генератор, а не, скажем, целое число.

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

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

Если в классе Python задать специальный метод .__iter__(), сконструированный из этого класса объект станет итерируемым — его можно будет использовать в конструкции вида for элемент in объект. В примере 3.15 приведена реализация прохода циклом хеш-таблицы с открытой адресацией, а в примере 3.16 — реализация прохода циклом хеш-таблицы с раздельным хранением цепочек в списках.

Пример 3.15. Метод-итератор по всем элементам хеш-таблицы с открытой адресацией, реализованный как генератор-функция

class Hashtable:

    def __iter__(self):

        for entry in self.table:

            if entry:                           ❶

                yield entry.key, entry.value    ❷

❶ Пропустим все пустые (содержащие None) ячейки.

❷ Вернем в yield кортеж (ключ, значение).

Пример 3.16. Метод-итератор по всем элементам хеш-таблицы с раздельным хранением цепочек

class Hashtable:

    def __iter__(self):

        for chain in self.table:                ❶

            for entry in chain:                 ❷

                yield entry.key, entry.value    ❸

❶ Цикл по цепочкам.

❷ Цикл по ячейкам в цепочке.

❸ Пара (ключ, значение) в качестве возвращаемого значения.

Рассмотрим последовательности пар, порождаемые итераторами в трех случаях: проходом по хеш-таблице размером M = 13 с открытой адресацией, по таблице размером 13 с раздельным хранением цепочек и по идеальной хеш-таблице на основе слов английского языка. После добавления в них слов из строки a rose by any other name would smell as sweet порядок выдачи пар при проходе циклом будет различен. В табл. 3.6 показан результат для всех трех случаев.

Таблица 3.6. Порядок слов, возвращаемых итераторами хеш-таблиц

Открытая адресация	Раздельное хранение цепочек	Идеальный хеш
a	sweet	a
by	any	any
any	a	as
name	would	by
other	smell	name
would	other	other
smell	as	rose
as	name	smell
sweet	by	sweet
rose	rose	would

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

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

В последней, восьмой, главе вы поближе познакомитесь с типом данных dict —ассоциативными массивами Python (или словарями). Всякий раз, когда в программе нужна хеш-таблица, надо использовать dict, а не наши самодельные классы, потому что dict и намного быстрее, и больше умеет.

Заключение

В этой главе мы рассмотрели несколько важных понятий.

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

• Открытая адресация ключа позволяет рассредоточить хранимые пары по всему массиву, но тогда для действительно эффективной работы нужно, чтобы размер M этого массива был как минимум вдвое больше максимального количества элементов N. Удаление элемента из такой хеш-таблицы — это целое упражнение (в тренировочных заданиях есть два таких упражнения).

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

• Самому придумать хеш-функцию непросто, но в Python есть встроенная функция hash(), ее и стоит использовать.

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

• Тип данных Python list, который мы используем для списков, — по сути массив с геометрическим масштабированием при добавлении, то есть динамический массив. Это задает константную, O(1), сложность операциям добавления в конец списка.

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

Тренировочные задания

1. Улучшается ли работа открытой адресации, если вместо последовательного просмотра с шагом 1 и возвратом к началу избрать другую тактику разрешения коллизий? Сделайте размер массива равным степени двойки, а шаг просмотра — переменным, равным n-му элементу из последовательности так называемых треугольных чисел. После просмотра соседней ячейки (расстоя­ние +1) исследуются ячейки на расстоянии 3, 6, 10, 15, 21 и т.д. (с учетом возврата к началу при выходе за границы). Треугольное число под номером n вычисляется по формуле n × (n + 1) / 2.

Будет ли производительность такой таблицы лучше, чем при последовательном просмотре?

Проведите эксперимент. Добавьте в хеш-таблицу размером 524 288 половину словаря английских слов (160 564 слова — это наполнение примерно на треть) и измерьте время поиска всех 321 129 слов. Сравните результаты эксперимента для хеш-таблицы с раздельным хранением, для таблицы с открытой адресацией и последовательным просмотром и для новой таблицы с переменным шагом.

2. Имеет ли смысл сортировать ключи в раздельно хранимых цепочках хеш-таблицы? Напишите вариант хеш-таблицы с раздельным хранением, в которой ячейка в цепочку добавляется так, чтобы (ключ, значение) оставались упорядоченными по возрастанию ключа.

Проведите эксперимент. Создайте хеш-таблицу на 524 287 элементов (524 287 — простое число) и добавьте в нее первую половину словаря — 160 564 английских слова (загруженность будет примерно на треть). Если добавлять слова в порядке возрастания, это сделает линейной сложность поиска нужного места для вставки пары, но константной — сложность вставки (потому что она будет фактически соответствовать добавлению в конец). Если добавлять слова в порядке убывания — наоборот. Какой из этих вариантов окажется наихудшим случаем? Сравните его производительность с производительностью хеш-таблиц того же размера с открытой адресацией и несортированными раздельными цепочками.

Теперь измерьте время поиска первых 160 564 английских слов в этой таблице. Можно ожидать, что это будет наилучший случай, потому что все эти слова уже есть в таблице. Сравните производительность с производительностью аналогичных операций на хеш-таблицах с открытой адресацией и несортированными раздельными цепочками. Затем поищите оставшиеся 160 565 слов из второй половины словаря. Это должен оказаться наихудший случай, потому что поиск несуществующих слов в списке требует его полного просмотра. Снова сравните производительность с производительностью двух других типов таблиц. Насколько результаты сравнения связаны с индексом загруженности хеш-таблицы? Например, что изменится, если задать размер таблицы 214 129 (загруженность 75 %) или 999 983 (загруженность 16 %)?

3. Чтобы убедиться в опасности предсказуемой хеш-функции, посмотрите на пример 3.17. Класс BadString в примере порождает объекты, схожие во всем с типом Python str. Но работа встроенной функции hash() для них перегружена, потому что определен специальный метод .__hash__(). В результате hash() для таких объектов может быть равен только 0, 1, 2 или 3.

Пример 3.17. Ужасная реализация хеш-функции

class BadString(str):

    def __hash__(self):

        return hash(str(self)) % 4

Создайте хеш-таблицу с раздельно хранимыми цепочками на 50 000 элементов и вызовите .put(BadString(w), 1) для первых 20 000 английских слов из нашего словаря. Сделайте еще одну такую же хеш-таблицу и добавьте туда те же слова непосредственно, без преобразования в BadString. Посчитайте:

• среднюю длину цепочки;

• наибольшую длину цепочки.

Имейте в виду, что работать это будет довольно долго! Объясните полученные результаты.

4. Число ячеек в хеш-таблице, M, на практике выгодно делать простым. Если взять для примера числовой ключ и остаток от деления на M в качестве индекса в таблице, окажется, что ключ, имеющий общий делитель с M, попадает только в ячейку, индекс которой имеет тот же общий делитель с M. Скажем, пускай M = 632 = 8 × 79, а добавляем мы пару с ключом 2133 = 27 × 79 ; хеш этого ключа будет равен 2133 % 632 = 237 = 3 × 79. Видите 79? Неприятность в том, что вместо равномерного распределения по всем ячейкам, от которого зависит быстродействие хеш-таблицы, получается, что некоторые ключи будут попадать строго в ограниченный набор ячеек.

Исследуйте влияние M на результат. По аналогии с base32() напишите функцию base26(), которая каждому слову английского словаря поставит в соответствие числовой ключ. Создайте 101 хеш-таблицу размером M, где M будет меняться от 428 880 до 428 890 включительно, добавьте в каждую такую таблицу все 321 129 английских слов по их числовому ключу base26() и сравните средние и наибольшие длины цепочек. Повторите это на хеш-таблицах с открытой адресацией и на хеш-таблицах с раздельными цепочками. Нет ли среди результатов некоторой общей закономерности? Сформулируйте гипотезу и попробуйте воспользоваться ею для поиска наихудшего M среди последующих 10 000 размеров (до 438 890). Для этого длина M наибольшей цепочки должна быть почти вдесятеро больше.

5. Из хеш-таблицы с открытой адресацией нельзя просто так удалить произвольную пару — если пометить ячейку как пустую, проходившая через нее цепочка прервется и последовательный просмотр не позволит добраться до продолжения этой цепочки. Допустим, у нас есть хеш-таблица на пять элементов, в которую мы добавили ключи 0, 5 и 10. В результате ключи в таблице разместятся так: [0, 5, 10, None, None], потому что с каждой коллизией просмотр будет добираться до следующей ячейки. Если сейчас удалить 5, получится таблица с ключами [0, None, 10, None, None], в которой внезапно образовались две цепочки, причем ключ 10 найти в ней нельзя, потому что цепочка для хеша 0 теперь состоит из всего одного элемента.

Один из путей решения проблемы — ввести специальное логическое поле в классе Entry, в котором будет отмечено, что эта ячейка удалена, но является частью цепочки. Напишите метод .remove(ключ), удаляющий элемент по ключу. Что изменится в работе методов .get() и .put()? Не забудьте также поправить процедуру масштабирования и метод .__iter__() — они должны пропускать удаленные ячейки.

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

6. Масштабирование хеш-таблицы весьма серьезно понижает производительность: требуется повторно хешировать все N ключей и заполнить N ячеек новой таблицы. В поэтапном масштабировании хранятся обе таблицы — старая, размером M, и новая, размером 2M + 1. Вызов get(ключ) сначала ищет ключ в новой таблице, а если его там нет — в старой. Вызов put(ключ, значение) всегда добавляет пару в новую таблицу, после чего D раз берет пару из старой таблицы, повторно хеширует ключ, добавляет ее в новую, а из старой удаляет. Когда старая таблица опустеет, ее можно удалить38.

Реализуйте поэтапное масштабирование для хеш-таблиц с раздельным хранением цепочек и исследуйте различные значения D. В частности, каково минимальное D, при котором к следующему масштабированию старая таблица гарантированно опустеет? Постоянна ли величина D или она зависит от M либо даже от N?

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

7. Обратное масштабирование можно реализовать и в обычной хеш-таблице с удалением. При вызове метода .remove() надо проверить, что таблица загружена не более чем на 1/4 M, и если да — запустить масштабирование к половинному размеру. Это позволит освободить неиспользуемую память. Доработайте любой из вариантов хеш-таблицы с удалением элемента, добавив в него обратное масштабирование, и проведите несколько испытаний на предмет того, стоит ли результат затраченных усилий.

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

Например, most_duplicated([1, 2, 3, 4]) может вернуть 1, 2, 3 или 4, а вот most_duplicated([1, 2, 1, 3]) обязан вернуть 1.

9. Еще один способ удалить пару из хеш-таблицы с открытой адресацией — повторно хешировать все пары (ключ, значение), которые следуют в цепочке за удаляемой парой. Добавьте в хеш-таблицу с открытой адресацией такой способ удаления и проведите несколько экспериментов, сравнивая производительность хеш-таблицы с раздельным хранением цепочек c производительностью хеш-таблицы с открытой адресацией и удалением цепочки описанным способом39.

---

Глава 4. Могучая куча

В этой главе

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

Изобретенная в 1964 году структура данных — двоичная куча, которую можно хранить в обычном массиве.

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

Как добавить пару (значение, приоритет) в двоичную кучу за O(log N) операций, где N — количество элементов в куче.

Как и где в двоичной куче найти элемент с наивысшим приоритетом за O(1) операций.

Как снять с вершины двоичной кучи элемент с наивысшим приоритетом за O(log N) операций.

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

Мы сейчас описали работу так называемой приоритизированной очереди — структуры данных, в которой эффективно реализованы две операции: добавления пары enqueue(значение, прироритет) и снятия (удаления + возврата) значения с наивысшим приоритетом значение = dequeue(). Приоритизированная очередь не похожа на уже изученные нами в предыдущей главе хеш-таблицы: нам не нужно заранее знать приоритет, чтобы снять наиболее приоритетное значение.

Допустим, ночной клуб переполнен и у входа уже выстроилась очередь, как на рис. 4.1. Для того чтобы попасть внутрь, каждый вновь пришедший должен встать в конец очереди. Первым попадет в клуб человек из начала очереди — он ждал дольше всех. Так работает собственно очередь — структура данных, в которой предусмотрена операция добавления последнего появившегося значения в конец очереди, enqueue(значение), и операция снятия первого значения по времени добавления, dequeue(). Иными словами, принцип работы очереди — «первым вошел, первым вышел» (First in, first out, или FIFO), что в развернутом виде можно прочесть как «(элемент, который) первым вошел (в очередь), первым вышел (из нее, как только к ней обратились)».

Рис. 4.1. Ночной клуб. Ожидание в очереди

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

     class Node:

       def __init__(self, val):

         self.value = val

         self.next = None

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

Рис. 4.2. Три варианта представления очереди в ночной клуб

Уровень абстракции и модель памяти языка Python позволяют нам относиться к связным спискам и как к «матрешкам», в которых весь «хвост» списка вложен в его первый элемент, и как к «бахроме», в которой каждый объект представлен изолированно, а в узлах хранятся только ссылки на эти объекты. Действительности, однако, соответствует именно вторая модель, «бахрома»: поэтому, например, фактический размер узла в списке (элемента типа Node) не зависит от размера поля .value. Поскольку обе модели тяжелы для восприятия, впредь мы будем пользоваться их упрощенным гибридом, «цепочкой», в которой явными ссылками представлены только элементы списка, а все остальные данные проще показывать как хранящиеся внутри соответствующих структур. Сами такие структуры мы время от времени будем называть узлами.

В примере 4.1 класс Queue имеет два метода — .enqueue() для добавления элемента в конец связного списка и .dequeue() для снятия элемента из его начала. Обоим методам нужно константное время для работы, независимо от количества элементов в очереди.

Пример 4.1. Реализация очереди при помощи связного списка

class Queue:

  def __init__(self):                       ❶

    self.first = None

    self.last = None

  def is_empty(self):

    return self.first is None               ❷

  def enqueue(self, val):

    if self.first is None:                  ❸

      self.first = self.last = Node(val)

    else:

      self.last.next = Node(val)            ❹

      self.last = self.last.next

  def dequeue(self):

    if self.is_empty():

      raise RuntimeError('Queue is empty')

    val = self.first.value                  ❺

    self.first = self.first.next            ❻

    return val

❶ Поначалу и first, и last — это None.

❷ Если first — пусто, очередь считается пустой.

❸ Если очередь пуста, первый добавляемый элемент и есть последний.

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

❺ Значение, которое нужно вернуть, хранится в first.

❻ Первый элемент исключается из списка, и first теперь указывает на следующий (или равен None, если такого не было).

Поменяем условия. Допустим, ночной клуб стал продавать своим завсегдатаям входные билеты произвольной стоимости, кто сколько заплатит, и проставлять эту стоимость на выданном билете. К примеру, один может купить билет за 50 долларов, а другой — за 100. Люди все так же встают в очередь, когда клуб переполнен, но первым в него войдет тот, чей билет дороже всех остальных билетов в очереди. Если самые дорогие билеты оказываются у нескольких человек, очередь на вход предоставляется одному из них. Безбилетники считаются обладателями бесплатного билета.

На рис. 4.3 в середине очереди есть завсегдатай с самым дорогим — стодолларовым — билетом. Если сейчас двери откроются, он первым попадет в клуб. За ним последуют двое с билетами за 50 долларов (в не установленном пока порядке), следом — безбилетники; они тоже считаются равноправными (владельцами бесплатных билетов), так что их порядок также не определен.

Рис. 4.3. Войдет первым тот, кто больше заплатит

В приоритизированной очереди не задается, что делать с двумя и больше значениями, приоритеты которых совпадают. В действительности прио­ритизированная очередь может возвращать такие значения не в порядке добавления — это зависит от реализации. Вариант на основе кучи, описанный в этой главе, возвращает элементы с одинаковым приоритетом не в том порядке, в котором их добавляли. Встроенный модуль heapq, о котором мы поговорим в главе 8, тоже использует кучу.

Исправленные таким образом требования определяют абстрактный тип данных — приоритизированную очередь. Правда, в ней уже нельзя реализовать обе операции — enqueue() и dequeue() — за константное время. С одной стороны, если воспользоваться связным списком, то enqueue() останется O(1), а вот dequeue() придется просматривать все элементы в поисках значения с наивысшим приоритетом, так что в худшем случае сложность ожидается O(N). С другой стороны, если всегда держать элементы в очереди упорядоченными по приоритету, dequeue() окажется O(1), а enqueue() в худшем случае потребует O(N) просмотров в поисках правильного места для вставки в список.

По опыту, есть пять сравнительно простых способов организовать из набора объектов типа Entry приоритизированную очередь пар (значение, приоритет).

• Array. Неупорядоченный массив элементов без всякой внутренней структуры — может, и так сойдет. Операция enqueue() занимает константное время, а dequeue() мало того, что занимается поиском по всему массиву, так еще и вынуждена переставлять его элементы после удаления одного. Вдобавок массив имеет фиксированный размер, так что очередь может еще и переполниться. В Python такого типа данных нет.

• Built-in. Вместо массива в Python можно использовать тип list и воспользоваться встроенными методами поиска, добавления и удаления элементов. Если элементы в нем не упорядочивать, сложность операций останется той же, что и при использовании массива, разве что мультипликативная константа будет меньше и снимется ограничение по размеру.

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

• Linked. Связный список, элементы которого всегда расположены по убыванию приоритета: начальный элемент имеет наивысший приоритет, все остальные — меньший либо равный приоритету предыдущего элемента. В этом варианте в операции enqueue() линейную сложность имеет поиск места для вставки элемента, а сама вставка и операция dequeue() константны.

• OrderL. Элементы хранятся в порядке приоритетов в динамическом массиве типа list от Python. Для поиска в enqueue() можно снова использовать двоичный поиск, но сама вставка (встроенными в list методами) требует перемещения в среднем половины элементов массива и оттого линейна. Операция dequeue() ожидаемо константна, потому что элемент с наибольшим приоритетом находится в конце массива.

Мы сравнили производительность всех описанных способов, для чего провели испытания, в которых благополучно вызвали 3N / 2 операций enqueue() и 3N / 2 операций dequeue(). Для каждого способа измерялось отношение общего времени работы к количеству операций, 3N, в итоге получалось среднее время выполнения одной операции. Результаты, показанные в табл. 4.1, говорят следующее. Имитация «массива», в которой все действия реализованы явно, оказалась самым медленным вариантом, а использование встроенных методов list ускорило тест почти вдвое. Упорядоченное хранение элементов в «массиве» снова почти удвоило скорость, использование связных списков ускорило тест еще примерно на 20 %; однако реализация OrderL посредством упорядоченных списков типа list и их встроенных методов оказалась вне конкуренции.

Таблица 4.1. Среднее время операции в наносекундах для объема данных размером N

N	Heap	OrderL	Linked	OrderA	Built-in	Array
256	6.4	2.5	3.9	6.0	8.1	13.8
512	7.3	2.8	6.4	9.5	14.9	26.4
1024	7.9	3.4	12.0	17.8	28.5	52.9
2048	8.7	4.1	23.2	33.7	57.4	107.7
4096	9.6	5.3	46.6	65.1	117.5	220.3
8192	10.1	7.4	95.7	128.4	235.8	446.6
16 384	10.9	11.7	196.4	255.4	470.4	899.9
32 768	11.5	20.3	—	—	—	—
65 536	12.4	36.8	—	—	—	—

Так или иначе, для всех упомянутых способов среднее время либо enqueue(), либо dequeue() прямо пропорционально N. А вот в столбце, помеченном как Heap, числа ведут себя по-другому: среднее время выполнения пропорционально log(N). Этот столбец содержит результаты эксперимента над структурой данных Heap (кучей); на рис. 4.4 хорошо видно, насколько она эффективнее нашего победителя — упорядоченных списков Python. Хороший эмпирический признак логарифмической сложности — константное приращение времени выполнения при удвоении объема входных данных. В табл. 4.1 объем входных данных как раз удваивается в каждой следующей строке — и среднее время работы одной операции с кучей увеличивается примерно на 0,8 наносекунды.

Рис. 4.4. Логарифмическая сложность операций над кучей куда эффективнее линейной сложности других подходов

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

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

Двоичная куча

Не вполне понятно зачем, но предположим, что наши данные отсортированы только частично. Например, на рис. 4.5 изображена двоичная куча с частичным порядком — убыванием приоритетов40; у каждого элемента показан только прио­ритет. На уровне 0 находится единственный элемент, и приоритет его будет наивысшим среди всех элементов кучи. Если два элемента x → y связывает стрелка, то приоритет x больше приоритета y либо равен ему.

Частично упорядоченная по убыванию куча — это несортированный список, в ней, например, нельзя сразу найти элемент с наименьшим приоритетом (если что, он на уровне 3). Зато у нее есть иные полезные свойства. На первом уровне кучи находится два элемента, приоритет одного из которых — непременно наивысший для всех уровней, кроме приоритета элемента на уровне 0 (а не то равен и ему). Любой уровень k — кроме последнего — содержит 2k элементов; иными словами, он полон. Неполным может быть только самый низкий уровень (в нашем примере там два из возможных 16 элементов); заполняются уровни слева направо. Приоритет неуникален: в куче из примера приоритеты 8 и 14 встречаются более одного раза.

Рис. 4.5. Пример двоичной кучи с частичным убыванием

В двоичной куче из каждого узла может исходить не более двух стрелок. Возьмем узел на уровне 0, приоритет которого равен 15. Он связан стрелками с двумя узлами на уровне 1: узел с приоритетом 13 — это его левый потомок, а узел с прио­ритетом 14 — правый потомок. Для узлов на первом уровне узел на нулевом уровне (с приоритетом 15) является соответственно родительским.

Рассмотрим структурные свойства двоичной кучи.

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

• Пирамидальность. Каждый уровень k кучи, кроме последнего, содержит ровно 2k узлов, последний может содержать меньше, заполняется он слева направо, и до тех пор, пока он неполон, уровень k + 1 не появляется.

Если в двоичной куче только один элемент, в ней только один уровень — нулевой, то 20 = 1, пирамидальность соблюдена. Сколько уровней понадобится, чтобы хранить N > 0 элементов? Нужна математическая формула, которая по заданному N позволит вычислить необходимое количество уровней в куче. С помощью рис. 4.6 можно попробовать догадаться, что это за формула. Расположим в виде пирамиды 16 узлов и пронумеруем их согласно принципу пирамидальности: на вершине — e1, затем последовательно по каждому уровню с увеличением индекса на 1. Получится четыре полных уровня и единственный узел на пятом.

Рис. 4.6. Сколько уровней в куче из N узлов?

Пока в куче только семь узлов, e1–e7, они помещаются на трех уровнях. Начиная с восьми узлов уже нужно четыре уровня. Если идти по стрелкам сверху налево, нам встретятся узлы e1, e2, e4, e8 и e16 — очевидно, степень двойки влияет не только на размер уровня, но и на размер всей кучи. В формуле оценки количества слоев логично ожидать двоичный логарифм от N — если быть более точным, количество слоев L для хранения N элементов в двоичной куче равно L(N) = 1 +

log2N (неполные квадратные скобки здесь означают округление до целого числа вниз, аналогичная функция Python — math.floor()).

В каждом следующем уровне двоичной кучи помещается больше узлов, чем во всех предыдущих, вместе взятых! В двоичной куче из L полных уровней содержится 2L – 1 элемент. В самом деле, в куче из одного уровня 21 – 1 = 1 узел, в куче из двух уровней — 22 – 1 = 3 узла; предположим, что в куче из L – 1 уровней 2L – 1 – 1 узел — тогда в куче из L уровней с добавлением еще 2L – 1 элемента из очередного слоя окажется 2L – 1 – 1 + + 2L – 1 = 2(2L – 1) – 1 = 2L – 1 узел, и формула индуктивно доказана. Как следствие, если к куче добавить всего один слой, она вместо N элементов будет способна хранить 2N + 1 элемент.

Что же касается двоичных логарифмов, то мы помним правило: при удвоении N логарифм увеличивается на 1, или в виде формулы: log2 2N = 1 + log2 N.

Какие из вариантов на рис. 4.7 соответствуют двоичной куче с порядком убывания?

Рис. 4.7. Что из этого можно назвать двоичной кучей с убыванием?

Сначала проверим свойство пирамидальности. Варианты 1 и 2 подходят, потому что в них заполнены все уровни. Вариант 3 тоже подходит, потому что в нем неполон только последний уровень, и заполнен он правильно: содержит три узла из допустимых четырех, и это три самых левых узла. А вот в варианте 4 пирамидальность не соблюдается: последний уровень содержит три узла, при этом самый левый узел пуст.

Теперь проверим частичный порядок. В случае убывания приоритет каждого родителя должен быть не меньше приоритетов его потомков. Это верно для варианта 1, в чем можно убедиться, сравнив все начала и концы стрелок. Вариант 3 не годится, потому что у узла с приоритетом 8 есть потомок с приоритетом 9. Вариант 2 не годится, потому что уже на уровне 0 приоритет узла равен 4, а у обоих его потомков он выше.

В действительности вариант 2 — это пример двоичной кучи с убыванием, в которой приоритет родительского узла не превосходит приоритеты потомков. Этот вариант двоичной кучи мы рассмотрим в главе 7.

Операции добавления элемента в кучу enqueue() и снятия с кучи элемента с наивысшим приоритетом dequeue() должны сохранять оба ее свойства. Если удастся их реализовать так, чтобы производительность обеих операций оценивалась как O(log N), мы получим значительное улучшение быстродействия по сравнению с медленными моделями из табл. 4.1, в которых либо enqueue(), либо dequeue() в наихудшем случае показывали быстродействие O(N).

Добавление пары в кучу

Если задаться целью добавить пару (значение, приоритет) в двоичную кучу, соблюдая только свойство пирамидальности, то в каком конкретно месте функции enqueue() придется заводить узел? Ответ всегда одинаков.

• Если последний уровень неполон, заполняется самый левый пустой узел этого уровня.

• Если последний уровень полон, заводится новый уровень и заполняется самый левый его узел.

На рис. 4.8 показан свежедобавленный в кучу узел с приоритетом 12: он занял третье место на уровне 4. Свойство пирамидальности соблюдено — все уровни, кроме последнего, полны, а последний заполнен слева. Однако во многих случаях частичный порядок от такого добавления нарушается.

К счастью, это дело поправимое, причем достаточно переставить местами лишь узлы «по дороге» от вершины кучи к только что добавленному элементу. На рис. 4.10 показана куча с восстановленным частичным порядком; можно заметить, что для этого пришлось переставить в порядке невозрастания узлы отмеченного серым пути от вершины до крайнего левого узла на последнем уровне.

Рис. 4.8. Добавление элемента. Начальный шаг — заполняется первый свободный узел

Путь до заданного узла двоичной кучи — это последовательность узлов и стрелок вправо или влево между ними от единственного узла на уровне 0 до заданного.

Теперь надо позаботиться о восстановлении частичного порядка. Добавленный элемент начинает всплывать вдоль пути — если порядок нарушен, он и его родитель меняются местами. В примере на рис. 4.8 свежедобавленный узел с прио­ритетом 12 нарушает порядок, потому что его приоритет выше 2 — прио­ритета родителя. Два узла меняются местами; результат показан на рис. 4.9. Между тем всплытие продолжается.

Рис. 4.9. Добавление элемента. Второй шаг — если нужно, узел всплывает на уровень выше

После первого всплытия структура с вершиной в узле 12 будет полноценной двоичной кучей из двух элементов. Но 12 все еще нарушает частичный порядок, потому что приоритет родителя этого узла — 9, а это меньше 12. Надо всплывать еще выше, как показано на рис. 4.10.

После очередного всплытия структура с вершиной в узле 12 будет полноценной двоичной кучей. Меняя местами 9 и 12 (по правой стрелке), мы можем не проверить, соблюдаются ли свойства кучи в структуре с вершиной 8 (по левой стрелке). Поскольку раньше все элементы этой структуры были не больше 9, они и подавно будут меньше 12. После третьего шага приоритет родительского узла, 13, оказывается больше 12 — частичный порядок восстановлен.

Попробуем вручную отработать вызов enqueue(значение, 16) на куче с рис. 4.10. Сначала узел добавляется в четвертую ячейку уровня 4 в качестве правого потомка узла с приоритетом 9. Затем узел всплывает все выше и выше вплоть до уровня 0. В результате получается двоичная куча как на рис. 4.11.

Рис. 4.10. Добавление элемента. Третий шаг — если нужно, узел всплывает на уровень выше

Рис. 4.11. Элемент с приоритетом 16 после добавления всплывает на вершину кучи

Наихудший случай для операции добавления — когда добавляется элемент с прио­ритетом, превышающим все имеющиеся приоритеты в куче. Длина пути при добавлении равна количеству уровней в куче, 1 +

log2N, а это значит, что наибольшее возможное количество операций обмена будет на одну меньше — log2N. Теперь уже можно уверенно оценивать и процедуру восстановления пирамидальности, и всю операцию enqueue() как O(log N). Большое дело — но это только половина решения всей задачи: теперь надо убедиться в том, что операцию снятия с кучи элемента с наивысшим приоритетом можно реализовать так же эффективно.

Снятие элемента с кучи

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

1. Запомним самый последний (самый правый в последнем уровне) элемент кучи и удалим его. Получившаяся структура сохранит все свойства двоичной кучи.

2. Запомним значение элемента с наивысшим приоритетом (с уровня 0) — это значение должна вернуть функция dequeue().

3. Заменим верхний элемент кучи с уровня 0 элементом, который мы удалили из нижнего уровня и запомнили на первом шаге. Это сохранит пирамидальность, но, скорее всего, нарушит частичный порядок.

На примере рис. 4.12: сначала мы запоминаем и удаляем из кучи элемент 9; куча при этом остается кучей. Затем запоминаем возвращаемое значение, приоритет которого наивысший, 16; на рисунке это действие не показано.

Рис. 4.12. Снятие элемента. Удаляем последний узел

На втором шаге мы подменяем узел на уровне 0 только что удаленным узлом. Как это понятно из рис. 4.13, частичный порядок в куче нарушится. Мы видим, что приоритет единственного узла на уровне 0 меньше и приоритета его левого потомка, 15, и приоритета его правого потомка, 14. Чтобы порядок восстановился, узел должен начать тонуть, погружаясь вглубь кучи вплоть до отведенного ему места.

Рис. 4.13. Снятие элемента. Подставляем последний элемент вместо верхнего, порядок при этом нарушается

Поскольку наш узел нарушает порядок (сейчас на уровне 0 оказалась пара с приоритетом 9), надо решить, какой из узлов кучи необходимо поставить на его место. Очевидно, это должен быть узел с наивысшим приоритетом среди тех, что доступны по стрелкам на уровнях ниже нашего. Выбор придется делать среди всего двух узлов — правого и левого потомков (приоритеты остальных заведомо не выше). Если правого потомка нет, то остается только левый. В нашем примере мы выбираем левого потомка, чей приоритет равен 15, и это больше, чем 14, приоритет правого потомка. Меняем местами наш узел и выбранного потомка с наивысшим приоритетом, получаем состояние, показанное на рис. 4.14.

Рис. 4.14. Снятие элемента. Меняем местами верхний узел и его левого потомка, приоритет которого выше

Можно заметить, что вся структура, начинающаяся с узла с приоритетом 14 на уровне 1, — это полноценная двоичная куча; мы ее не трогали, и менять там ничего не надо. А вот в структуре под узлом с приоритетом 9, который оказался на уровне 1 после обмена, порядок нарушен — оба его потомка имеют более высокий приоритет. Значит, наш узел будет продолжать тонуть, меняясь с левым потомком (как это показано на рис. 4.15), потому что приоритет левого потомка 13 выше, чем приоритет правого.

Рис. 4.15. Снятие элемента. Узел продолжает тонуть

Осталось немного! На рис. 4.15 видно, что в новом положении у нашего узла с приоритетом 9 есть правый потомок, а приоритет оставшихся — 12, так что мы меняем эти два узла, после чего частичный порядок в нашей куче восстанавливается, как это видно на рис. 4.16.

Рис. 4.16. Снятие элемента. Куча после того, как узел погрузился на нужный уровень

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

log2N.

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

log2N.

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

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

Хранение двоичной кучи в массиве

На рис. 4.17 показан один из способов записать двоичную кучу размером N = 18 в массив фиксированного размера M > N. В такой куче будет пять уровней, каждый из которых будет соответствовать определенному диапазону индексов массива, содержащего хранимые пары. Пунктирные квадраты в правой стороне рисунка отмечают индекс, по которому хранится соответствующий узел двоичной кучи. Как обычно, при изображении кучи мы показываем только приоритеты, а значения опускаем.

Итак, каждой хранимой паре сопоставляется индекс в массиве storage[]. Чтобы не упражняться лишний раз с вычитанием и добавлением единицы к этому индексу, оставим storage[0] пустым и ничего там хранить не будем. Элемент с наивысшим приоритетом, 15, хранится в storage[1]. Согласно рис. 4.17, его левый потомок, с приоритетом 13, хранится в storage[2]. В общем случае, если у элемента storage[k] есть левый потомок, он будет храниться в storage[2*k] (в этом легко убедиться, проследив стрелочки между пунктирными квадратами на рис. 4.17). Если у элемента storage[k] есть правый потомок, он будет храниться в storage[2*k+1] соответственно.

Рис. 4.17. Запись двоичной кучи в массив

Если k > 1, родительский узел для storage[k] всегда находится в storage[k//2] (в Python k // 2 — это целая часть от деления k на 2). Если располагать вершину кучи в storage[1], то, чтобы вычислить индекс родителя любого узла, надо просто целочисленно поделить на 2 индекс узла-потомка. В примере родительский узел для storage[5] (с приоритетом 11) окажется в storage[2], потому что 5 // 2 = 2.

Если в куче содержится N элементов, storage[k] для любого 0 < k ≤ N содержит узел из двоичной кучи. Как следствие, если 2k > N, то у k-го узла нет потомков; например, у узла storage[10] (с приоритетом 1) потомков нет, потому что 2 × 10 = 20 > 18 = N. А у узла storage[9] (с приоритетом, так случайно вышло, тоже 9) нет только правого потомка, потому что 2 × 9 = 18 = N, а вот 2 × 9 + 1 = 19 > N.

Как погружаться и всплывать

Начнем программировать нашу двоичную кучу с частичным убыванием с задания класса для пары (значение, приоритет):

      class Entry:

        def __init__(self, v, p):

          self.value = v

          self.priority = p

В примере 4.2 для хранения узлов кучи применяется массив storage. При создании экземпляра класса PQ размер storage на единицу превосходит максимальный размер кучи — параметр size конструктора — потому что, напомню, мы храним элементы кучи в массиве, начиная с storage[1].

Чтобы можно было лучше изучить работу нашего класса, мы написали два вспомогательных метода. Метод .less(i, j) проверяет, что приоритет i-го узла меньше приоритета j-го, и возвращает True или False. Когда нам понадобится оценить, сколько раз мы сравниваем приоритеты двух узлов, достаточно будет просто посчитать количество вызовов .less(). Метод swap(i, j) меняет местами i-й и j-й узлы в массиве, он нам понадобится для подсчета количества обменов при перестройке кучи, когда узел всплывает или тонет.

Пример 4.2. Реализация кучи методами .enqueue() и .swim()

class PQ:

  def less(self, i, j):                                 ❶

    return self.storage[i].priority < self.storage[j].priority

  def swap(self, i, j):                                 ❷

    self.storage[i], self.storage[j] = self.storage[j], self.storage[i]

  def __init__(self, size):                             ❸

    self.size = size

    self.storage = [None] * (size+1)

    self.N = 0

  def enqueue(self, v, p):                              ❹

    if self.N == self.size:

      raise RuntimeError('Priority Queue is Full!')

    self.N += 1

    self.storage[self.N] = Entry(v, p)

    self.swim(self.N)

  def swim(self, child):                                ❺

    while child > 1 and self.less(child//2, child):     ❻

      self.swap(child, child//2)                        ❼

      child = child // 2                                ❽

❶ Метод .less(i, j) проверяет, что storage[i] имеет меньший приоритет, чем storage[j].

❷ Метод swap(i, j) меняет местами i-й и j-й узел.

❸ Узлы хранятся в ячейках от storage[1] до storage[size], а storage[0] не используется.

❹ Чтобы добавить элемент в кучу, надо разместить его в первой свободной ячейке массива, а затем позволить ему всплыть.

❺ Метод .swim() перестраивает массив storage, возвращая куче пирамидальность.

❻ Родительский узел для storage[child] находится в storage[child//2] (child//2 — это целочисленное деление child на 2).

❼ Меняем местами storage[child] и его родителя storage[child//2].

❽ Если надо, узел продолжит всплывать, и теперь child равен индексу родителя.

Метод .swim() оказался весьма лаконичен! Индекс свежедобавленного узла — child, индекс его родителя, если таковой имеется, — child//2. Если приоритет родителя меньше приоритета child, они меняются местами и всплытие продолжается.

На рис. 4.18 представлено, как меняется массив storage после вызова en­queue(значение, 12) из состояния, которое было показано на рис. 4.8. В каждом следующем ряду ячейки storage меняются, как это ранее отображалось на очередном рисунке. В последнем ряду — состояние массива, соответствующее двоичной куче с пирамидальностью и частичным порядком.

Рис. 4.18. Как меняется storage после вызова enqueue() на рис. 4.8

Путь от вершины кучи до только что добавленного элемента с приоритетом 12 состоит из пяти узлов — они помечены серым на рис. 4.18. После двух итераций цикла whlle в методе .swim(), в которых узел всплывает, меняясь местами со своим родителем, он попадает в ячейку storage[4] и свойство пирамидальности кучи восстанавливается. Количество обменов не может превышать log2N, где N — общее число ячеек в двоичной куче.

В примере 4.3 мы реализовали метод .sink(), который используется для восстановления свойств двоичной кучи при снятии элемента с ее вершины при помощи .dequeue().

Пример 4.3. После добавления методов .dequeue() и .sink() мы получаем полноценно работающую кучу

    def dequeue(self):

      if self.N == 0:

        raise RuntimeError ('PriorityQueue is empty!')

      max_entry = self.storage[1]                               ❶

      self.storage[1] = self.storage[self.N]                    ❷

      self.storage[self.N] = None

      self.N -= 1                                               ❸

      self.sink(1)

      return max_entry.value                                    ❹

    def sink(self, parent):

      while 2*parent <= self.N:                                 ❺

        child = 2*parent

        if child < self.N and self.less(child, child+1):        ❻

          child += 1

        if not self.less(parent, child)                         ❼

          break

        self.swap(child, parent)                                ❽

        parent = child

❶ Запомним ячейку на вершине кучи.

❷ Переставим на вершину последний (самый правый в самом нижнем уровне) элемент, а его место освободим.

❸ Уменьшим количество узлов и запустим sink() для storage[1].

❹ Вернем значение элемента, снятого с вершины кучи.

❺ Проверка продолжается, пока у узла есть хотя бы левый потомок.

❻ Если правый потомок существует и приоритет левого потомка меньше, нам нужен правый потомок.

❼ Если приоритет родителя не меньше максимального приоритета потомков, пирамидальность восстановлена.

❽ Если нет, поменяем местами родителя и потомка и продолжим топить наш узел уже с нового места.

На рис. 4.19 изображено, как меняется storage в процессе работы dequeue() — начиная с двоичной кучи с рис. 4.11. Первая строка на рис. 4.19 — это массив из 19 элементов. Во второй строке самый последний элемент с приоритетом 9 перемещается в самое начало (что соответствует вершине двоичной кучи и нарушает пирамидальность); кроме того, теперь в куче 18 узлов, так как последний мы удалили.

Рис. 4.19. Изменения массива storage в процессе снятия элемента с вершины кучи, приведенной на рис. 4.11

После трех последовательных итераций цикла while в методе .sink() узел с прио­ритетом 9 погружается на позицию, в которой достигается пирамидальность кучи, серым всюду обозначены потомки этого узла. Всякий раз, когда выясняется, что приоритет родителя меньше приоритета потомка, родитель и потомок с более высоким приоритетом меняются местами. Количество таких обменов не может превысить log2N.

Метод .sink() наглядно показать сложнее, потому что нет однозначного маршрута, по которому тонет переставленный на вершину кучи узел, — в отличие от .swim(). В окончательном состоянии storage из примера 4.19 погрузившийся на свое место узел с приоритетом 9 имеет еще одного потомка (с приоритетом 2). После отрабатывания .sink() мы можем быть уверены, что приоритет узла не меньше (то есть больше либо равен) приоритетов всех имеющихся у него потомков. Как частный случай, индекс ячейки p может превышать N // 2, тогда у узла потомков нет, так как элементов с индексами 2p и 2p + 1 нет в storage.

В методе .dequeue() важно сначала уменьшить N на 1, а только потом вызвать .sink(1), иначе sink() примет элемент, лежащий за пределами кучи. На всякий случай, если кто-то все-таки решит туда заглянуть, мы предварительно записываем None в storage[N] — тогда уж точно ее не перепутать с узлом. В программировании такой прием — защита от ошибки, которой вроде бы и так не должно случиться. Она называется hardening — усиление надежности исходного текста.

Чтобы убедиться в правильности такой логики метода .dequeue(), посмотрим, что случится, если куча содержит единственный элемент, а мы его снимаем. Узел max_entry мы запомнили, N уменьшили до 0, затем вызывали sink(), а он, как и ожидается, ничего не делает, потому что 2 × 1 > 0.

Заключение

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

• Добавление в очередь пары (значение, приоритет) имеет логарифмическую вычислительную сложность O(log N).

• Снятие из начала очереди элемента с наивысшим приоритетом тоже имеет сложность O(log N).

• Подсчет количества элементов в очереди имеет константную сложность O(1).

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

def less(self, i, j):

  return self.storage[i].priority > self.storage[j].priority

Приоритизированная очередь может быть любого размера, но в нашей реализации использовалась куча фиксированного размера M, в которой можно было хранить только N < M элементов. Если куча полна, больше элементов в очередь не добавить. Мы выбрали эту реализацию, чтобы аккуратнее оценить быстродействие: посчитать количество операций сравнения и обмена, не опасаясь, что какие-то другие действия с данными не попадут в оценку. Из главы 4 мы знаем, что массив фиксированного размера всегда можно заменить динамическим массивом с геометрическим масштабированием (удвоением при заполнении). Это не изменит оценку сложности в среднем, так что сложность enqueue() останется O(log N).

Тренировочные задания

1. В действительности для реализации двоичной кучи произвольного размера почти ничего дополнительно делать не надо: все равно мы используем не массив, а list, динамические свойства которого как раз и обеспечиваются геометрическим масштабированием. Перепишите класс PQ, чтобы в прио­ритизированной очереди можно было хранить произвольное количество элементов. Сравните быстродействие полученной структуры данных с PQ, для чего создайте достаточной длины последовательность со случайными приоритетами, добавьте их по одному в каждую из структур, а потом по одному снимите. Какая структура работает быстрее? Почему? Значимо ли это различие: есть ли основание считать, что какие-то операции над этими структурами имеют различный класс сложности?

• Отдельно хранить .size и .N нет необходимости: они всегда равны len(storage).

• Для работы с последней ячейкой массива используйте .append() и .pop().

• Другие методы, такие как .insert() или .pop() с параметром, исполь­зовать нельзя: их сложность в среднем линейна, в то время как сложность .append() и .pop() константна.

Обычную очередь фиксированного размера можно весьма эффективно реа­лизовать с помощью массива storage фиксированного размера, причем быстродействие операций enqueue() и dequeue() будет константным, O(1). Один из способов — это так называемый кольцевой буфер, использующий простую, но остроумную идею: начальный элемент очереди не обязательно лежит в storage[0]. Достаточно просто хранить два индекса — forst, позицию того, кто стоит в очереди дольше всех, и last, позицию, куда мы поместим очередной добавляемый элемент, когда он появится. Посмотрим на рис. 4.20.

Рис. 4.20. Массив в качестве кольцевого буфера

При каждом добавлении элемента в конец очереди и снятии элемента из ее начала надо аккуратно обновлять first и last. Скорее всего, будет удобно хранить N — количество элементов в очереди и придется использовать остаток от деления — операцию %. Изучите пример 4.4, допишите соответствующие методы и проверьте, что они действительно работают за константное время.

Пример 4.4. Допишите реализацию очереди в виде кольцевого буфера

class Queue:

  def __init__(self, size):

    self.size = size

    self.storage = [None] * size

    self.first = 0

    self.last = 0

    self.N = 0

  def is_empty(self):

    return self.N == 0

  def is_full(self):

    return self.N == self.size

  def enqueue(self, item):

    """If not full, enqueue item in O(1) performance."""

  def dequeue(self):

    """If not empty, dequeue head in O(1) performance."""

2. Добавьте в порядке возрастания N = 2k – 1 элемент в пустую двоичную кучу размером N. Изучите получившийся массив, который хранит узлы кучи (напомню, позиция 0 в нем не используется). Можно ли предсказать, какие места в массиве будут занимать k наибольших элементов? А если в пустую двоичную кучу добавить N элементов в порядке убывания, нельзя ли предсказать место каждого элемента в массиве ячеек?

3. Допустим, у нас есть две кучи размером M и N. Придумайте алгоритм, который заполняет массив размером M + N всеми элементами обеих куч в порядке возрастания за O(M log M + N log N) операций. Для подтверждения правильности алгоритма подготовьте таблицу с результатами экспериментов.

4. Придумайте метод получения k наименьших элементов среди произвольного набора из N элементов за время O(N log k). Для подтверждения правильности алгоритма подготовьте таблицу с результатами экспериментов.

5. В двоичной куче у каждого узла бывает не больше двух потомков. Рассмотрим другой вариант, в котором узел на вершине кучи имеет двух потомков, каждый из них имеет трех потомков (назовем их внуками), каждый из внуков — четырех потомков и т.д., как показано на рис. 4.21. Назовем эту структуру факториальной кучей: в ней с каждым уровнем у узлов прибавляется по дополнительному потомку. Куча должна обладать свойствами пирамидальности и частичного порядка. Реализуйте факториальную кучу, используя хранение ячеек в массиве, поэкспериментируйте с ней и убедитесь, что она работает медленнее двоичной. Попробуйте оценить вычислительную сложность; это задача похитрее, но в конце концов у вас должно получиться O((log N) / (log(log N))).

Рис. 4.21. Инновационная факториальная куча

6. Используя геометрическое масштабирование, описанное в главе 3, доработайте кольцевой буфер из упражнения 2 так, чтобы он мог работать с произвольным количеством элементов. Переносить ячейки из старого массива в новый удобнее не по одной, а сегментами (таких сегментов будет один или два). Реализуйте уменьшение размера массива, если показатель заполнения опустился ниже 1/4.

7. Допустим, мы хотим сделать итератор по всей куче, который возвращает по одному значения в том порядке, в котором мы снимали бы их с кучи. С одной стороны, такой итератор не должен модифицировать саму структуру, с другой — при снятии элемента с кучи нужно переструктурировать массив ячеек. Как совместить оба требования? Одно из решений — написать генератор-функцию iterator(pq), которая получает на вход приоритизированную очередь pq и создает ее копию, pqit, откуда потом и снимает по одному все элементы. Начнем с более надежного варианта, в котором pqit хранит не сами элементы pq, а их индексы в массиве pq.storage; приоритеты при этом остаются такими же, как и у соответствующих значений. По этим индексам мы и будем обращаться к pq.storage, до самого последнего момента не трогая его содержимого и вообще не меняя его структуры.

Допишите следующий пример, в начале которого в pqit добавляется индекс 1, который соответствует элементу pq с наивысшим приоритетом. Продолжите заполнение pqit и допишите цикл while из примера:

def iterator(pq):

  pqit = PQ(len(pq))

  pqit.enqueue(1, pq.storage[1].priority)

  ...

  while pqit:

    idx = pqit.dequeue()

    yield (pq.storage[idx].value, pq.storage[idx].priority)

    ...

Такой итератор должен возвращать все элементы pq в порядке приоритетов, не изменяя сам pq.

Стоит заметить, что особой надежности использование в куче-копии индексов вместо самих элементов, по-видимому, не добавляет. Напишите вариант нашей функции, iteratorc(pq), в которой задается новая куча pqit минимального размера, а затем все поля pq просто копируются туда (включая storage, который можно получить с помощью pq.storage.copy()). Будет ли такая структура надежной: нет ли случаев, в которых что-то в pq модифицируется? Какая из функций работает быстрее и почему?

---