Подведём итоги

Wrapping It Up В этой главе автор местами отстал от жизни, а местами просто довольно неаккуратно изложил подробности реализации в Python, я взял на себя труд в силу собственных знаний исправить положение, не вступая с ним в дискуссию. -- FrBrGeorge 2023-02-24 14:10:15

Цель нашей книги — описать алгоритмы, которые лежат в основании современных информационных технологий, и структуры данных в поддержку этих алгоритмов, от эффективной реализации которых напрямую зависит быстродействие программ. В книге мы привели примеры таких структур данных: My goal in this book was to introduce you to the fundamental algorithms and the essential data types used in computer science. You need to know how to efficiently implement the following data types to maximize the performance of your code:

Набор

Несколько (как правило, однотипных) элементов объединённых единой структурой, в которую можно добавлять элементы, а так же искать их в ней. Удаление элементов из набора обычно не предусмотрено. Если набор реализован с помощью связного списка, добавление — это вставка в начало, и она имеет константную (O(1)) сложность. Если набор реализован с помощью динамического массива, можно добиться также константной сложности добавления в среднем, хотя в редких случаях масштабирования массива сложность будет возрастать до O(N)¹. Bag A linked list ensures O( 1) performance when adding a value. If you choose to use an array, then you need to employ geometric resizing to extend the size of the array so you can guarantee amortized O(1) performance over its average use (though you will still incur an O(N) runtime performance on the infrequent resize events). Note that a bag does not typically allow values to be removed, nor does it prevent duplicate values from being added.

Стек

В Python не необходимости моделировать стек (LIFO — Last In, First Out) связным списком, так как с этим легко справляется встроенный тип данных, динамический массив list. Тем не менее связный список — это классический пример реализации стека. Операции добавления значения на вершину стека и снятия значения оттуда, push() и pop() (для типа list — .append() и .pop()) должны иметь константную сложность O(1). Stack A linked list can store the values in a stack so push() and pop() have O(1) run‐ time performance. The stack records the top of the stack to push and pop values.

Очередь

Если набор данных организован по принципу FIFO — First In, First Out, его можно смоделировать связным списком, в котором хранятся ссылки как на первый, так и на последний элементы. При этом обе операции — добавление в конец очереди enqueue() и удаление из начала очереди dequeue() — будут иметь сложность O(1). Queue A linked list can efficiently store a queue so enqueue() and dequeue() have O(1) runtime performance. The queue records the first and the last node in the linked list to efficiently add and remove values from the queue.

Хеш-таблица

Структура, хранящая пары (ключ, значение), эффективность которой зависит от удачного выбора хеш-функции, которая распределяет значения по хранилищу, сообразуясь с хешем ключа. Хорошо себя показывает открытая адресация хешей в тандеме с геометрическим масштабированием хранилища при его заполнении выше порогового. Геометрическое масштабирование, например, удвоение, позволяет сделать вычислительно «тяжёлую» операцию перехеширования настолько редкой, что это не влияет на среднее быстродействие. Symbol table The open addressing approach for symbol tables is surprisingly efficient, with suitable hash functions to distribute the (key, value) pairs. You still need geomet‐ ric resizing to double the size of the storage, thus effectively making these resize events less frequent.

Приоритетная очередь

Если реализовать кучу — структуру данных, которая хранит пары (значение, приоритет) таки образом, чтобы на её вершине всегда находилась пара с наивысшим приоритетом, её можно рассматривать как очередь. При этом и операция добавления enqueue(), и операция снятия с вершины dequeue() будут иметь логарифмическую сложность O(log N). Как правило, вместимость приоритетной очереди N известна заранее, если же нет, избежать значимого падения быстродействия нам снова поможет геометрическое масштабирование. Priority queue The heap data structure can store (value, priority) pairs to support enqueue() and dequeue() in O(log N) runtime performance. In most cases, the maximum number of values to store, N, is known in advance; if not, however, the geometric resizing strategy can be used to minimize the number of resize events.

Индексированная приоритетная очередь

Если добавить в реализацию кучи отдельный словарь, в котором записана позиция элемента кучи массиве-хранилище, получится структура данных, в которой можно быстро (за константное время) найти любой, а не только верхний, элемент. Для классических графов, в которых узлы не имеют названий, а просто пронумерованы от 0 до N-1, вместо словаря можно использовать массив, что ещё повысит быстродействие. Индексированная приоритетная очередь поддерживает операции добавления, удаления и повышения приоритета элемента, и сложность всех этих операций — логарифмическая, O(log N). Indexed min priority queue Implementing this data type combines the heap data structure with a separate symbol table that stores the index location of each value in the heap. For graph algorithms, it is common to store only integer node labels in the range from 0 to N – 1, where N is the maximum number of values to be stored in the indexed min priority queue. In this case, the separate symbol table can be implemented as an array for extremely efficient look-up. It supports enqueue(), dequeue(), and decrease_priority() in O(log N) runtime performance.

Граф

Структура, состоящая из узлов и рёбер, в которой рёбра обычно моделируются матрицей смежности — особенно когда есть подозрение, что в графе могут встретиться вообще все возможные рёбра. Если узлы пронумерованы от 0 до N - 1, для реализации матрицы смежности можно воспользоваться двумерным массивом. Однако в большинстве случаев удобнее применять список смежности, который можно смоделировать словарём, хранящим списки смежных узлов (или словарём с ключом — ребром, то есть парой смежных узлов). Вручную делать собственную реализацию графа смысла не имеет — и писать долго, и работать будет небыстро, лучше воспользоваться какой-нибудь готовой удобной реализацией в стороннем Python-модуле. В нашей книге мы применяли модуль NetworkX, поддержка графов в котором эффективна и разнообразна. Graph The adjacency matrix structure is appropriate when all possible edges in the graph exist, which is a common use case for algorithms that compute shortest distances. You can use a two-dimensional array to store an adjacency matrix if the nodes are represented using integers in the range from 0 to N – 1. In most cases, however, an adjacency list structure is more suitable for storing the graphs, and a symbol table is used to associate a bag of adjacent nodes for each node (or, alternatively, a bag of adjacent edges). Any home-built implementation of a graph is going to be insufficient in the long run. Instead, use NetworkX (or any other existing third-party library) to represent graphs efficiently.

В предисловии к нашей книге мы привели иллюстрацию, в которой кратко упомянули эти абстрактные типы данных. Разбираясь с алгоритмами, мы смоделировали абстрактные типы теми или иными структурами данных в Python и исследовали быстродействие наших моделей. Результаты представлены в таблице 8-1². The book preface contains a picture that summarizes each of these data types. Throughout the book I have demonstrated how different data structures can effi‐ ciently implement the data types, leading to the performance classifications in Table 8-1.

В таблице много неадекватных Python-у упоминаний «массивов» и связных списков, я переписал её сообразно правленному мной в предыдущих главах -- FrBrGeorge 2023-02-17 13:09:31

• Таблица 8-1. Быстродействие абстрактных типов данных Table 8-1. Performance of data types

Встроенные типы данных Python

Python Built-in Data Types

Язы программирования Python активно развивается более тридцати лет, и за это время встроенные типы данных стали весьма удобны и эффективны. Разработчики постоянно — буквально в каждом выпуске Python — пробуют улучшить быстродействие, даже если и ненамного. Довольно показателен текст «The Design and History FAQ» («Часто задаваемые вопросы про историю разработки») с официального сайта Python³. The Python implementations are highly tuned and optimized after decades of use. It is impressive how the designers of the Python interpreter constantly seek new ways to gain even a small improvement in performance with each updated release. The Design and History FAQ for Python is worth a read.

The four built-in container types in Python are tuple, list, dict, and set: Непосредственно в синтаксис языка встроено четыре типа для хранения данных — кортеж (tuple), список (list), словарь (dict) и множество (set):

tuple (кортеж)

Неизменяемая последовательность произвольных объектов Python, с которой можно обращаться как с массивом, только элементам нельзя присваивать новые значения. Реализован как таблица — массив ссылок на объекты Python. Часто используется для объединения элементов в группы например, попарно, или для того, чтобы вернуть из функции несколько значений. tuple data type A tuple is an immutable sequence of values that can be processed like a list, except that none of its values can be altered. Use a tuple to return multiple values from a function.

list (список)

Динамический массив произвольных объектов Python, один из главных типов данных. Удивительно гибкий инструмент, в котором, как и в кортеже, есть очень прозрачно оформленное секционирование — изготовление новых объектов-подпоследовательностей. Если нужно пройти такую подпоследовательность элементов циклом, с помощью объекта типа range() создаётся вычислимая последовательность индексов и применяется индексирование. Список тоже реализован как массив ссылок на объекты, но эти ссылки можно изменять, а также добавлять и удалять. Константную сложность операциям удаления и добавления (в конце списка) придаёт геометрическое масштабирование. list data type The built-in list data type is the dominant data structure in Python. It is extremely versatile, especially because of Python’s slicing syntax that allows pro‐ grammers to effortlessly work with iterables and select subranges of a list for processing. The list is a general purpose structure, implemented as a variable- length array that uses a contiguous array of references to other values.

dict (словарь)

Второй главный тип данных в Python — хеш-таблица, которая хранит данные в соответствие с их ключами. Всё, что мы знаем по третьей главе о хеш-таблицах, применимо и к dict. В реализации Python для разрешения коллизий используется открытая адресация с повторным хешированием. Тройки полный хеш ключа, ключ, значение хранятся (динамическом массиве), а их индексы (равные остатку от деления хеша на M) — в списке заранее заданного размера M, равного степени двойки. Это несколько отличается от обычной структуры хеш-таблиц. Размер словаря (массива индексов) начинается с M = 8, а при превышении порога заполнения в ⅔ применяется геометрическое масштабирования: размер удваивается, и хеши вычисляются заново. Размер меньше 8 смысла не имеет — слишком часто происходило бы масштабирование, и так-то в массиве хранится не более пяти элементов. Если большинство элементов таблицы не занято, список объектов достаточно мал, что обеспечивает эффективность по памяти в среднем. Поскольку значения хранятся в списке, всегда известен порядок их добавления в словарь; чтобы сохранить константную сложность удаления произвольного элементов словаря, по соответствующему индексу делается пометка о том, что элемент удалён, а сам элемент остаётся в списке-хранилище (таким образом удаление не уменьшает размер хранилища до следующего масштабирования). dict data type The built-in dict data type represents a symbol table that maps keys to values. All of the concepts in Chapter 3 continue to apply. The Python implementation uses open addressing to resolve collisions between keys and also uses storage arrays where M is a power of 2, which is different from how most hashtables are constructed. Each dict internal storage has storage for at least M = 8. This is done so it can store five entries without causing a resize (whereas smaller values of M would require a resize too quickly). It is also optimized to deal with sparse hashtables where most of the storage array is empty. The dict automatically resi‐ zes based on a load factor of ⅔.

Python — свободное программное обеспечение с открытыми исходными текстами, так что реализацию любого типа данных (Python написан на языке Си) всегда можно посмотреть в исходниках⁴. Вместо последовательного просмотра цепочки, в случае коллизии хеш-суммы hc следующий индекс вычисляется как ((5 × hc) + perturb 1) % 2ⁿ, где 2ⁿ — это M, размер массива с индексами, а perturb — небольшая числовая константа, помогающая равномерно рассеивать хеши по области значений. Довольно интересно поизучать, как небольшое изменение в формуле приводит к более эффективной реализации хеширования. Остаток от деления на степень двойки, как известно, можно взять и без деления — с помощью побитовой конъюнкции (в Python обозначается знаком «&»). Because Python is open source, you can always inspect the internal implementa‐ tion.1 Instead of using linear probing, as described in Chapter 3, a collision at hash code hc will subsequently select the next index to be ((5 × hc) + 1) % 2k, where 2k is M, or the size of the storage array. The implementation adds another layer of key distribution using a perturb value that is added to hc. It offers a case study showing how minor mathematical improvements to hash code computa‐ tions can improve the efficiency of the implementation. Because Python uses a different probing technique, its hashtables can have sizes that are powers of 2, which can eliminate the use of modulo when computing hash codes. This can speed up processing dramatically because the Python interpreter uses a technique known as bit masking to perform computations modulo a power of 2.

Таким образом можно значительно увеличить быстродействие. Например, остаток от деления на M на 2ⁿ — это M & (2ⁿ - 1)⁵. В таблице 8-2 показано время выполнения десяти миллионов операций взятия остатка отделения на 2ⁿ и побитовой конъюнкции с 2ⁿ - 1 в Python и Си: на Си написана основная реализация словарей в Python, и там быстродействие отличается более, чем впятеро! Specifically, using the bitwise and (&) operator, N % 2k is equal to N & (2k – 1). Table 8-2 shows the difference when timing 10,000,000 computations. The improvement is more pronounced within the Python interpreter (typically writ‐ ten in C), where bitwise and is more than five times faster than using modulo. 1 For example, you can find the implementation of dict in https://oreil.ly/jpI8F.

Язык	Выражение	Время выполнения
Python	1989879384 % M	0.6789181 secs
Python	1989879384 & (M - 1)	0.3776672 secs
Си	1989879384 % M	0.1523320 secs
Си	1989879384 & (M - 1)	0.0279260 secs

Таблица 8-2. Остаток деления на степень двойки M = 2ⁿ быстрее вычислять с помощью побитовой конъюнкции Table 8-2. Modulo power of 2 is faster with bitwise and, where M is 2k and M_less is M – 1

set (множество)

Набор различающихся хешируемых (в случае Python это означает «неизменяемых») данных. Попросту говоря, множество — это хеш-таблица, в которой ничего не хранится⁶. В отличие от словаря, основное назначение которого — накопление элементов и поиск конкретного значения по (скорее всего) существующему в словаре ключу, множество обычно нужно для того, чтобы проверить, принадлежит ли ему некоторый ключ или нет. Соответственно, в реализации Python оптимизирован не только успешный поиск ключа в множестве (когда ключ в множестве есть), но и неуспешный (когда его там нет). Кроме того, множества в Python поддерживают теоретико-множественные операции, такие как объединение, пересечение, дополнение и т. п. set data type A set collection contains distinct hashable objects.2 It is quite common to use a symbol table to act as a set, by simply mapping each key to some arbitrary value, such as 1 or True. The internal Python implementation is heavily based on the dict approach, but it is worth mentioning that the use cases for a set are quite different from a dict. Specifically, a set is often used for membership testing, to check to see whether a value is contained by the set—and the code is optimized to handle both hits (i.e., the value is contained in the set) and misses (i.e., the value is not contained in the set). In contrast, when working with a dict, it is much more common that the key exists within the dict.

Реализация стека в Python

Implementing Stack in Python В седьмой главе мы довольно подробно обсудили, как именно Python-овский тип list реализует абстрактный тип данных «стек». Если коротко: будучи динамическим массивом с геометрическим масштабированием, list предоставляет методы .append(), который добавляет элемент в конец списка, и .pop(), который снимает оттуда элемент. Оба метода имеют константную в среднем сложность, как это видно, например, из таблицы 6-1. A Python list can represent a stack, offering an append() function to push new val‐ ues to the end of the list (recall from Table 6-1 that appending to the end of a list is efficient). The list type actually has a pop() method that removes and returns the last value in the list.

В состав дистрибутива Python входит модуль queue, в котором реализованы и стек («последним вошёл, первым вышел», LIFO), и очередь («первым вошёл, первым вышел», FIFO), причём основной упор сделан на структуры данных фиксированного размера и их использование в многопоточных окружениях. Такой стек или очередь поддерживает несколько потоков выполнения, часть из которых может добавлять туда элементы, а часть — снимать их оттуда. Например, queue.LifoQueue() создаст стек актуально бесконечного размера, который отличается от обычного списка те, что методу .get() (аналог .pop()) по умолчанию передаётся дополнительный параметр block=True, тогда попытка снять значение из пустого стека не вызовет исключения, а приостановится до тех пор, пока в каком-нибудь другом потоке выполнения в этот стек не положат хотя бы одно значение. Если создать стек или очередь фиксированного размера, то и операция .put() (аналог .append()) также будет приостанавливаться, если соответствующая структура данных полна, и ждать, пока кто-то другой не снимет оттуда хотя бы одно значение. Python provides a queue module that implements multi-producer, multi-consumer stacks that support both “Last-in, first-out” (LIFO) behavior (as regular stacks should) and “First-in, first-out” (FIFO) behavior (as you would expect with a queue). The queue.LifoQueue(maxSize = 0) constructor will return a stack that can store a maximum number of values. This stack is meant to be used concurrently, which means that attempting to push a value to a full stack will block the execution until a value has been popped. Values are pushed with put(value) and popped with get(). 2 Find its source at https://oreil.ly/FWttm.

В частности, такая программа зависнет на операции .put(), и нам придётся остановить её средствами операционной системы: Invoking the following sequence of commands will freeze the Python interpreter, and you will have to forcefully stop it:

   1       import queue
   2       q = queue.LifoQueue(3)
   3       q.put(9)
   4       q.put(7)
   5       q.put(4)
   6       q.put(3)  # ... эту операцию можно прервать только остановив программу

Если многопоточность не нужна, но вдобавок мы хотим использовать наше хранилище и как стек, и как очередь (то есть наш алгоритм часто удаляет или добавляет элементы и в начало, и в конец хранилища), самый быстрый вариант — это упоминавшаяся в третьей главе «двусторонняя очередь» (double-ended queue) deque из модуля collections⁷. Операции добавления и в начало, и в конец deque имеют сложность O(1) в среднем, и при этом его быстродействие раз в 30 выше LifoQueue (хотя порядок сложности остаётся константным). As it turns out, the fastest implementation is deque (pronounced DECK) from the collections module, which stands for “double-ended queue.” This data type allows values to be added to (or removed from) either end. The performance of LifoQueue is about 30 times slower than deque, though both provide O(1) runtime performance.

Реализация очередей в Python

Implementing Queues in Python

Очередь в принципе можно было бы смоделировать на базе Python-овского list: использовать метод .append() для добавления в конец очереди (последний элемент списка), и .pop(0) — для снятия элемента из её начала (нулевой элемент списка). Однако мы знаем, что работа с началом списка требует уже не константного, а линейного времени, и как это видно из таблицы 6-1, лучше так вообще никогда не делать. A Python list can also represent a queue, offering an append() function to enqueue new values to the end of the list. You will need to remove the first element from the list using pop(0) to request removing the element at index position 0 in the list. Using the list in this fashion will become seriously inefficient, as shown in Table 6-1: you must avoid this at all costs.

Очередь с поддержкой многопоточности (несколько потоков выполнения добавляют в очередь, несколько снимают) и блокировок при переполнении и опустошении реализована классом queue.Queue, но, как уже говорилось выше относительно класса queue.LifoQueue, если все эти свойства не нужны, он оказывается слишком мощным инструментом с большими накладными расходами. Как и в LifoQueue, методы .put() и .get() используются для добавления и удаления элементов, и если ограничить размер хранилища, возникает блокировка. Например, такой диалог в командной строке Python придётся прерывать вручную средствами операционной системы: The queue.Queue(maxSize = 0) function constructs a queue that allows maxSize values to be enqueued, but this should not be your default queue implementation. This queue provides multi-producer, multi-consumer behavior, which means that attempting to enqueue a value to a full queue will block the execution until a value has been dequeued. Values are enqueued with put(value) and dequeued with get(). Invoking the following sequence of commands will freeze the Python interpreter, and you will have to forcefully stop it:

   1 >>> import queue
   2 >>> q = queue.Queue(2)
   3 >>> q.put(2)
   4 >>> q.put(5)
   5 >>> q.put(8)
   6 ... blocks until terminated

Классы queue.Queue и queue.LifoQueue можно использовать для создания очередей с заданиями: каждый поток выполнения—задание должен вызвать метод .task_done() после того, как выполнит последнюю по его мнению операцию с очередью, а поток выполнения, запустивший эти задания, вызовет метод .join(), который приостановится до тех пор, пока все задания не завершатся. Если вы не пользуетесь абстракцией «задание», можно задействовать класс queue.SimpleQueue — в нём нет этих двух методов (и механизма их реализации), и работает он несколько эффективнее. Ещё раз напомним, что классы из модуля queue обладают впечатляющим набором свойств, которые, возможно, не будут нужны в простых программах. Они не только адаптированы к многопоточным средам (тредобезопасны), но и допускают использование в повторно-входимых процедурах (сопрограммах) и т. п. — всё это за счёт падения производительности. Используйте эти классы если вам в самом деле нужны их свойства. If you need a simple queue implementation, you could use the queue.SimpleQueue() function,3 which provides the behavior for a queue with a simplified interface. Use put(value) to enqueue value to the end of the queue, and get() to retrieve the value at the head of the queue. This queue is much more powerful than most programmers need, because it handles not only thread-safe concurrent code, but also more compli‐ cated situations, such as reentrant concurrent code, and this extra functionality comes with a performance penalty. You should only use queue.SimpleQueue() if you need concurrent access to the queue.

Сноску про Python 3.7 я удалил: сейчас уже Python 3.11, нет смысла размечать текст комментариями, когда в Python какие особенности появились -- FrBrGeorge 2023-02-24 15:16:48 3 This capability was added in Python 3.7.

Самая быстрая реализация очереди в Python — это класс collections.dequeue: в нём неплохо оптимизирована производительность, и если важно быстродействие очереди, стоит использовать именно его. В таблице 8-3 приведено сравнение быстродействия очередей на базе различных типов — dequeue оказывается лучшим, а list — худшим, причём операция снятия из очереди на нём имеет сложность O(N) — в отличие от остальных классов; так что ещё раз напомним: для очередей списки использовать не надо. The deque is also the fastest implementation here. It is specially coded for raw speed and is the queue implementation you should choose if speed is critical. Table 8-3 shows that the deque implementation offers the best implementation; it also shows how list provides O(N) runtime performance for dequeuing a value. Once again, you must avoid using a generic list as a queue, since all other queue implementa‐ tions offer O(1) runtime performance.

• Таблица 8-3. Быстродействие снятия элемента из очереди для различных реализаций Table 8-3. Queue runtime performance comparisons when dequeuing a value

Базовые типы данных Python можно использовать для решения самых разнообразных задач, но в каждом случае стоит тщательно выбирать, с помощью чего моделировать ту или иную структуру данных — чтобы программа заработала быстрее. The essential data types provided by Python are flexible enough to be used in a vari‐ ety of ways, but you need to make sure you choose the appropriate data structures to realize the most efficient code.

Реализация кучи и приоритетной очереди

Heap and Priority Queue Implementations

В базовом дистрибутиве Pythopn есть модуль heapq, который реализует кучу с порядком возрастания — примерно так, как мы это сделали в четвёртой главе, но в качестве хранилища используется обычный список с индексацией элементов от 0, а не от 1, как в нашем варианте. Python provides a heapq module providing a min binary heap, as described in Chap‐ ter 4. Instead of using the 1-based indexing strategy I used in Chapter 4, this module uses 0-based indexing.

Более того: никакой специальной структуры данных для кучи создавать не надо. Достаточно передать процедуре heapq.heapify(h) список исходных значений h, и она превратит h в кучу с порядком возрастания, после чего можно будет пользоваться им и как кучей, и как списком (только не стоит нарушать порядок). Другой способ — завести пустой список h=[], и добавлять значения в кучу с помощью heapq.heappush(h, значение). Наименьшее значение можно снять с кучи при помощи heapq.heappop(h). Вдобавок к этому в heapq имеются две полезный функции: The heapq.heapify(h) function constructs a heap from a list, h, containing the ini‐ tial values to place in the heap. Alternatively, simply set h to the empty list [], and invoke heapq.heappush(h, value) to add value to the heap. To remove the smallest value from the heap, use the heapq.heappop(h) function. This heap implementation has two specialized functions:

heapq.heappushpop(h, value)

Сначала добавляет в кучу новый элемент, а затем снимает с её вершины наименьшее значение (если новый элемент и был минимальным, ничего добавлять и снимать не надо, достаточно просто возвращает его). Adds value onto the heap and then removes and returns the smallest value from heap

heapq.heapreplace(h, value)

Сначала снимает с кучи минимальный элемент, а затем добавляет туда новый (если он оказался не больше предыдущего минимума, достаточно просто заменить один на другой). Removes and returns the smallest value from the heap and also adds value onto the heap

Если изучить содержимое h — списка, в котором поддерживается порядок кучи, мы увидим в нём прямое сходство с хранилищем элементов кучи из нашей реализации в главе 4. These functions are all applied directly to the parameter h, making it easy to integrate with your existing code. The contents of h reflect the array-based storage of a heap, as described in Chapter 4.

Приоритизированную очередь реализует класс PriorityQueue из модуля queue (https://oreil.ly/sUiZd — как и другие структуры данных этого модуля, он поддерживает многопоточность и блокировку операций при выходе за размер хранилища). Нетрудно заметить, что это просто «обёртка» queue.Queue вокруг кучи из heapq: метод .put(item), добавляющий в очередь item — кортеж (приоритет, значение), просто хранит этот кортеж в куче, а метод .get(), снимающий элемент из начала очереди, просто выполняет heappop(). The queue.PriorityQueue(maxSize=0) method (https://oreil.ly/sUiZd) constructs and returns a min priority queue whose entries are added using put(item) function calls, where item is the tuple (priority, value). Retrieve the value with lowest prior‐ ity using the get() function.

А вот реализации индексированной приоритетной очереди среди стандартных структур данных Python нет — что неудивительно, ибо чаще всего она нужна при обработке графов — например, в Алгоритме Дейкстры, который мы рассматривали в седьмой главе. Метод IndexedMinPQ.decrease_priority() из нашей реализация в этой главе оказался коротким и эффективным как раз за счёт задействованной в нём совокупности различных структур данных. There is no built-in indexed min priority queue, which is not surprising because this data type is typically only needed for specialized graph algorithms, such as Dijkstra’s algorithm (presented in Chapter 7). The IndexedMinPQ class I developed shows how to compose different data structures together to achieve an efficient decrease_prior ity() function.

Что изучать дальше?

Future Exploration

В нашей книге мы только пробежались по верхам необъятного пространства — науки об алгоритмах. Углубляться в это пространство можно по нескольким направлениям, в различных предметных областях и с различными подходами к пониманию алгоритмов: This book has only scratched the surface of the incredibly rich field of algorithms. There are numerous avenues you can explore, including different application domains and algorithmic approaches:

Вычислительная геометрия

Великое множество практических задач включают в себя обработку наборов точек в двумерных или даже многомерных координатах. Алгоритмы для такой обработки весьма разнообразны, например, нередко используется подход «разделяй и властвуй», описанный в нашей книге, и для эффективной их реализации создаются специализированные структуры данных. Самые распространённые — это K-мерные деревья и их подвиды: дерево квадратов (для разбиения двумерного пространства), октодерево (для разбиения трёхмерного пространства) и R-дерево (для индексации многомерной информации). Как видим, идея двоичных деревьев живёт и побеждает повсеместно, в различных предметных областях. Computational geometry Numerous real-world problems involve data sets with two-dimensional points, or even higher dimensions. Within this application domain, there are many algo‐ rithms that build from the standard techniques I’ve introduced—such as divide and conquer—and introduce their own data structures to efficiently solve prob‐ lems. The most popular data structures include k-d trees, Quadtrees (for parti‐ tioning two-dimensional spaces), Octrees (for partitioning three-dimensional spaces), and R-trees for indexing multidimensional data sets. As you can see, the essential concept of a binary tree has been explored repeatedly in different appli‐ cation domains.

Динамическое программирование

Наглядный представитель этого класса алгоритмов — Алгоритм Флойда-Уоршелла (поиск кратчайших путей в графе от заданной вершины). Теория, лежащая в основе динамического программирования, позволила выработать целый спектр эффективных алгоритмов. Подробнее об этом можно прочитать в книге «Введение в алгоритмы», которая также вышла в издательстве О'Райлли (https://oreil.ly/1lXRF). Dynamic programming Floyd–Warshall is an example of dynamic programming applied to solving the single-source shortest path problem. There are many other algorithms that take advantage of dynamic programming. You can learn more about this technique in my Algorithms in a Nutshell (https://oreil.ly/1lXRF) book also published by O’Reilly.

Параллельные и распределённые алгоритмы

В нашей книги мы изучали алгоритмы, использующие единственный поток выполнения на единственном компьютере. Если решение задачи можно разбить на несколько независимо вычисляемых подзадач, эти решения можно запустит одновременно, например, на одном компьютере с несколькими процессорами или не нескольких вычислительных узлах, объединённых сетью. Параллелизмом довольно непросто управлять, и сами алгоритмы становятся сложнее, но игра стоит свеч: выигрыш в быстродействии от умело спроектированного параллелизма может быть очень значительным. Parallel and distributed algorithms The algorithms presented in this book are essentially single-threaded and execute on a single computer to produce a result. Often a problem can be decomposed into multiple constituent parts that can be executed independently, in parallel. The control structures become more complicated, but impressive speed-up can be achieved through parallelism.

Численные методы

Вычисления в практических задачах совершенно не обязаны быть алгебраически точными. Более того, для некоторых важных задач вычислительная сложность точного решения может быть слишком большой для необходимого набора данных, или даже точного решения может не существовать вообще. Такие задачи можно решить приближённо, с заданной степенью точности — и на этот счёт существует множество алгоритмов. Approximation algorithms In many real-worlds scenarios, you might be satisfied with an algorithm that effi‐ ciently computes an approximate answer to a really challenging problem. These algorithms are noticeably less computationally expensive than those producing the exact answer.

Вероятностные методы

Иногда для решения задачи невозможно построить алгоритм в собственном смысле: невозможно (или вычислительно сложно) написать программу, которая на одном и том же наборе входных данных давала одинаковый удовлетворительный результат. Можно применить принципиально иной подход: ввести в вычисления случайный компонент и запустить программу довольно много раз, получив множество отличающихся результатов. В некоторых случаях подходящим ответом будет среднее из полученных значений, в некоторых — если есть функция, позволяющая оценить «правильность» результата — процесс повторяется, пока проверочная функция не даст добро (в действительности подходов, конечно, больше). Probabilistic algorithms Instead of producing the exact same result when given the exact same input, a probabilistic algorithm introduces randomness into its logic, and it produces dif‐ ferent results when given the same input. By running these less complex algo‐ rithms a large number of times, the average overall runs can converge on the actual result, which would otherwise be prohibitively expensive to compute.

Конечно же, ни одна книга не может объять необъятного — всего многообразия возможных алгоритмов. В 1962 году Дональд Кнут, один из столпов программирования, начал писать грандиозную книгу — «Искусство программирования» (выходит в издательстве Addison-Wesley⁸. К нынешнему времени — более, чем шестьдесят лет спустя — вышло три первых тома этой книги (в 1968, 1969 и 1973 годах), а также первая часть четвёртого тома (в 2011-м). Впереди ещё три тома, так что проект далёк от завершения! No single book can cover the breadth of the field of algorithms. In 1962, Donald Knuth, a towering figure in computer science, began writing a 12-chapter book, The Art of Computer Programming (Addison-Wesley). Today—59 years later—the project has produced three volumes (published in 1968, 1969, and 1973) and the first part of volume 4 (published in 2011). With three more volumes planned for publication, the project is still not complete!

Изучать и применять алгоритмы можно до бесконечности, и мы надеемся, что знания, которые мы вложили в эту книгу, помогут в разработке быстрых и эффективных программ. You can find countless ways to continue your study of algorithms, and I hope you are inspired to use this knowledge to improve the performance of your software applications.

Об авторе

Джордж Хайнеман (George Heineman) — профессор Computer Science с более чем двадцатилетним стажем разработки программного обеспечения и исследования эффективности алгоритмов. Хайнеман — автор книги «Введение в алгоритмы» и множества учебных курсов О'Райлли, таких как «Исследование алгоритмов на языке Python» и «Работа с алгоритмами на языке Python». С давних пор он интересуется логическими и математическими головоломками, и даже изобрёл несколько: например Sujiken® (вариант Судоку) и Trexagon.

Об обложке

Животное на обложке книги «Изучаем алгоритмы» — чесапикский голубой краб (Callinectes sapidus). Название рода Callinectes происходит от древнегреческого «хороший пловец», а название вида — sapidus — на латыни значит «вкусный», «пикантный». Голубой цвет крабу придают пигменты в панцире, в частности ярко-синий альфа-крустацианин, который взаимодействуя с красным астаксантином даёт зелёно-голубой окрас. Если краба сварить, альфа-крустацианин разрушается и панцирь приобретает яркий оранжево-красный оттенок.

Родина голубого краба — атлантическое побережье Северной и Южной Америки и Мексиканский залив. В Европу и Японию он попал, по-видимому, с водным балластом, и уже в 1901 году его можно было встретить в тамошних водах. Прежде считалось, что причина расширения ареала голубого краба — повышение температуры океана вследствие глобального потепления.

Эти крабы откладывают икру на мелководье, после чего приливные течения относят её на глубину. Планктонная личинка краба проходит восемь стадий развития, прежде чем станет похожей на взрослую особь. Как и все ракообразные, голубые крабы растут во время линьки: старый панцирь сбрасывают и отращивают новый — побольше. Считается, что за свою жизнь краб успевает перелинять около 25 раз, и дорасти примерно до 9 дюймов в ширину. Брюшко самцов — плоское, самок — обширное и округлое; окраской они почти не различаются.

Многие животные с обложек О'Райлли находятся под угрозой исчезновения, и все животные без исключения — важный элемент биосферы.

Иллюстрация на обложке выполнена Karen Montgomery: за основу взята чёрно-белая гравюра из книги 1887 года «Animal Life in the Sea and on the Land» («Жизнь животных в море и на суше. Зоология для юношества»). Шрифты английского издания: на обложке — Gilroy Semibold и Guardian Sans; основной текст — Adobe Minion Pro; заголовки — Adobe Myriad Condensed; текст программ — Ubuntu Mono (автор этого шрифта — Dalton Maag).