Глава 2. Массив последовательностей

Общие сведения о встроенных последовательностях

Контейнерные последовательности

Позволяют хранить элементы разных типов, в т. ч. вложенные контейнеры. Примерами могут служить list, tuple и collections.deque.

Плоские последовательности

Позволяют хранить элементы только одного типа. Примерами могут служить str, bytes и array.array.

В контейнерных последовательностях хранятся ссылки на объекты любого типа, тогда как в плоских последовательностях – сами значения прямо в памяти, занятой последовательностью, а не как отдельные объекты Python.

Упрощенные диаграммы размещения кортежа и массива в памяти

Каждый объект Python, находящийся в памяти, имеет заголовок с метаданными. У простейшего объекта, float, имеется поле значения и два поля метаданных:

• ob_refcnt: счетчик ссылок на объект;

• ob_type: указатель на тип объекта;

• ob_fval: число типа double (в смысле C), в котором хранится значение с плавающей точкой.

Изменяемые последовательности

Например, list, bytearray, array.array и collections.deque.

Неизменяемые последовательности

Например, tuple, str и bytes.

Упрощенная UML-диаграмма нескольких классов из модуля collections.abc суперклассы показаны слева, стрелки ведут от подклассов к суперклассам, курсивом набраны имена абстрактных классов и абстрактных методов)

Списковое включение и удобочитаемость

Также имеет название списочное выражение

Построить список кодовых позиций Unicode по строке

Построить список кодовых позиций Unicode по строке с применением listcomp

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

Локальная область видимости внутри включений и генераторных выражений

В документе PEP 572 «Assignment Expressions» область видимости оператора := определена как объемлющая функция, если только соответствующая переменная не является частью объявления global или nonlocal

Значение x не перезаписано: оно по прежнему привязано к ABC

c пропала, она существовала только внутри listcomp.

Сравнение спискового включения с map и filter

Один и тот же список, построенный с помощью listcomp

и композиции map и filter

Раньше я думал, что композиция map и filter быстрее эквивалентного спискового включения, но Алекс Мартелли показал, что это не так, по крайней мере в примере выше.

02-array-seq/listcomp_speed.py

Декартовы произведения

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

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

Ниже показано выражение, которое использовалось для инициализации колоды карт списком, состоящим из 52 карт четырех мастей по 13 карт в каждой:

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

Генераторные выражения

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

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

Инициализация кортежа и массива с помощью генераторного выражения

Если генераторное выражение – единственный аргумент функции, то дублировать круглые скобки необязательно.

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

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

Кортеж – не просто неизменяемый список

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

• использование в качестве неизменяемых списков

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

Второе применение иногда незаслуженно игнорируется.

Кортежи как неизменяемые списки

Преимущества:

Ясность

Видя в коде кортеж, мы точно знаем, что его длина никогда не изменится.

Производительность

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

Однако не забывайте, что неизменность кортежа относится только к хранящимся в нем ссылкам – их нельзя ни удалить, ни изменить.

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

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

def fixed(o): try: hash(o) except TypeError: return False return True tf = (10, 'alpha', (1, 2)) tm = (10, 'alpha', [1, 2]) print(fixed(tf)) print(fixed(tm))

True False

Раймонд Хэттингер: Правда ли, что в Python кортежи эффек- тивнее списков?

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

• Имея кортеж t, вызов tuple(t) просто возвращает ссылку на тот же t. Никакого копирования не производится. Напротив, если дан список l, то конструктор list(l) должен создать новую копию l.

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

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

Сравнение методов кортежа и списка

** Методы и атрибуты списка и кортежа (для краткости методы, унаследованные от object, опущены)**

Сопоставление с последовательностями-образцами

Самая заметная новая возможность в Python 3.10 – предложение match/case для сопоставления с образцом.

Ниже приведен первый пример предложения match/case. Допустим, что мы проектируем робота, который принимает команды в виде последовательностей слов и чисел, например BEEPER 440 3. Разбив команду на части и разобрав числа, мы должны получить сообщение вида ['BEEPER', 440, 3]. Для обработки таких сообщений можно воспользоваться показанным ниже методом.

1. Выражение после ключевого слова match называется субъектом. Это данные, которые Python попытается сопоставить с образцами в ветвях case.

2. С этим образцом сопоставляется любой субъект, являющийся последовательностью из трех элементов. Первый элемент должен быть равен 'BEEPER'. Второй и третий могут быть любыми, они связываются с переменными frequency и times именно в таком порядке.

3. С этим образцом сопоставляется любой субъект, содержащий два элемента, причем первый должен быть равен 'NECK'.

4. С этим образцом сопоставляется субъект, содержащий три элемента, первым из которых должен быть 'LED'. Если число элементов не совпадает, то Python переходит к следующей ветви case.

5. Еще одна последовательность-образец, начинающаяся с 'LED', но теперь содержащая пять элементов, включая константу 'LED'.

6. Это ветвь case по умолчанию. С ней сопоставляется любой субъект, для которого не нашлось подходящего образца. Переменная _ специальная.

На первый взгляд, конструкция match/case похожа на предложение switch/case в языке C – но это только на первый взгляд. Основное улучшение match по сравнению с switch – деструктуризация, т. е. более развитая форма распаковки.

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

Последовательность-образец может сопоставляться с большинством реальных или виртуальных подклассов класса collections.abc.Sequence, за исключением лишь классов str, bytes и bytearray.

С последовательностями-образцами совместимы следующие типы из стандартной библиотеки:

• list

• memoryview

• array.array

• tuple

• range

• collections.deque

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

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

Любую часть образца можно связать с переменной с помощью ключевого слова as:

Образцы можно сделать более специфичными, добавив информацию о типе.

Выражения str(name) и float(lat) выглядят как вызовы конструкторов, как было бы, если бы мы хотели преобразовать name и lat соответственно в типы str и float. Но в контексте образца эта синтаксическая конструкция производит проверку типа во время выполнения: образец сопоставится с 4-элементной последовательностью, в которой элемент 0 должен иметь тип str, а элемент 3 должен быть парой чисел типа float. Кроме того, str в позиции 0 будет связана с переменной name, а два числа типа float в позиции 3 – с переменными lat и lon соответственно. Таким образом, хотя str(name) заимствует синтаксис конструктора, в контексте образца семантика совершенно другая.

Гвидо ван Россум собрал коллекцию примеров case/match, один из которых назвал «Очень глубокий итерируемый объект и сравнение типа с выделением».

Головоломка: присваивание A +=

Что произойдет в результате? Какой ответ кажется вам правильным?

1. t принимает значение (1, 2, [30, 40, 50, 60]).

2. Возбуждается исключение TypeError с сообщением о том, что объект tuple не поддерживает присваивание.

3. Ни то, ни другое.

4. И то, и другое.

Я был почти уверен, что правильный ответ 2, но на самом деле правилен ответ 4: «И то, и другое»! В примере нижк показано, как этот код выполняется в оболочке для версии Python 3.9

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

Начальное и конечное состояния кортежа в задаче о присваивании

Изучение байт-кода, который Python генерирует для выражения s[a] += b, показывает, что происходит на самом деле.

Это патологический случай.

Из этого примера надо вынести три урока.

1. Не стоит помещать изменяемые элементы в кортежи.

2. Составное присваивание – не атомарная операция; мы только что видели, как она возбуждает исключение, проделав часть работы.

3. Изучить байт-код не так уж трудно, и часто это помогает понять, что происходит под капотом.

метОд list.sort и вСтрОенная функция sorted

Метод list.sort сортирует список на месте, т. е. не создавая копию. Он возвращает None, напоминая, что изменяет объект-приемник, а не создает новый список.

Аналогичное поведение демонстрирует, к примеру, функция random.shuffle, которая перетасовывает изменяемую последовательность s на месте и возвращает None.

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

===

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

Массивы

Если список содержит только числа,то тип array.array эффективнее,чем list: он поддерживает все операции над изменяемыми последовательностями (включая pop, insert и extend), а также дополнительные методы для быстрой загрузки и сохранения, например frombytes и tofile.

Массив Python занимает столько же памяти, сколько массив C. В массиве значений типа float хранятся не полноценные экземпляры этого типа, а только упакованные байты, представляющие их машинные значения, – как в массиве double в языке C. При создании экземпляра array задается код типа – буква, определяющая, какой тип C использовать для хранения элементов.

Например, код типа b соответствует типу C signed char, описывающему целые числа от –128 до 127. Если создать массив array('b'), то каждый элемент будет храниться в одном байте и интерпретироваться как целое число.

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

Как видим, пользоваться методами array.tofile и array.fromfile легко. Выполнив этот пример, вы убедитесь, что и работают они очень быстро. Несложный эксперимент показывает, что для загрузки методом array.fromfile 10 миллионов чисел с плавающей точкой двойной точности из двоичного файла, созданного методом array.tofile, требуется примерно 0,1 с. Это почти в 60 раз быстрее чтения из текстового файла, когда требуется разбирать каждую строку встроенной функцией float. Метод array.tofile работает примерно в 7 раз быстрее, чем запись чисел с плавающей точкой в текстовый файл по одному на строку. Кроме того, размер двоичного файла с 10 миллионами чисел двойной точности составляет 80 000 000 байт (по 8 байт на число, с нулевыми накладными расходами), а текстового файла с теми же данными – 181 515 739 байт.

Таблица 2.3. Методы и атрибуты типов list и array (нерекомендуемые методы массива, а также унаследованные от object, для краткости опущены)

Двусторонние и другие очереди

Методы append и pop позволяют использовать список list как стек или очередь (если вызывать только .append и .pop(0), то получится дисциплина обслуживания LIFO). Однако вставка и удаление элемента из левого конца списка (с индексом 0) обходятся дорого, потому что приходится сдвигать весь список.

Класс collections.deque – это потокобезопасная двусторонняя очередь, предназначенная для быстрой вставки и удаления из любого конца. Эта структура удобна и для хранения списка «последних виденных элементов» и прочего в том же духе, т. к. deque можно сделать ограниченной (при создании задать максимальную длину). Тогда по заполнении deque добавление новых элементов приводит к удалению элементов с другого конца.

Отметим, что deque реализует большинство методов list и добавляет несколько новых, связанных с ее назначением, например popleft и rotate. Но существует и скрытая неэффективность: удаление элементов из середины deque производится медленно. Эта структура данных оптимизирована для добавления и удаления элементов только с любого конца.

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

Таблица 2.4. Методы, реализованные в классах list и deque (унаследованные от object для краткости опущены)

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