Массив (array) — это фундаментальная структура данных, имеющаяся в большинстве языков программирования, и он имеет широкий спектр применений в самых разных алгоритмах.
В этой статье мы рассмотрим реализации массива в Python, в которых используются только базовые функциональные средства языка или функциональность, которая включена в стандартную библиотеку Python.
Вы увидите достоинства и недостатки каждого подхода, благодаря чему сможете решить, какая реализация подходит для вашего варианта использования. Но прежде чем начать, рассмотрим некоторые основы.
Как работают массивы и для чего они применяются?
Массивы состоят из записей данных, при этом записи имеют фиксированный размер, что позволяет эффективно размещать каждый элемент на основе его индекса.
Поскольку массивы хранят информацию в смежных блоках памяти, их рассматривают как непрерывные (нефрагментированные) структуры данных (в противоположность связным структурам данных, таким списки, например).
Аналогией из реального мира, соответствующей этой структуре данных, является автостоянка:
Автостоянку можно рассматривать как единое целое и как отдельный объект, но внутри автостоянки есть места для парковки, индексируемые по уникальному числу. Места для парковки являются контейнерами для транспортных средств — каждое место для парковки может либо быть пустым, либо содержать автомобиль, мотоцикл или другое транспортное средство, припаркованное там.
Но не все автостоянки одинаковые:
Некоторые автостоянки могут быть ограничены только одним типом транспортного средства. Например, на кемпинговой автостоянке не разрешено парковать велосипеды. «Ограниченная» автостоянка соответствует структуре данных для «типизированного массива», которая допускает только те элементы, которые имеют одинаковый тип хранящихся в них данных.
С точки зрения производительности поиск элемента, содержащегося в массиве, выполняется очень быстро при условии, что указан индекс эле мента. Для данного случая надлежащая реализация массива гарантирует постоянное O(1) время доступа.
В своей стандартной библиотеке Python содержит несколько массивоподобных структур данных, каждая из которых обладает слегка отличающимися характеристиками. Давайте их рассмотрим.
list — изменяемые динамические массивы
Списки (lists) являются составной частью ядра языка Python. Несмотря на свое имя, списки Python реализованы как динамические массивы. Это означает, что список допускает добавление и удаление элементов и автоматически корректирует резервное хранилище, в котором эти элементы содержатся, путем выделения или высвобождения дополнительной памяти.
Списки Python могут содержать произвольные элементы — в Python абсолютно "всё" считается объектом, включая и функции. Поэтому вы можете сочетать комбинировать разные типы данных и хранить их все в одном списке.
Такая возможность может быть очень мощной, но у нее есть и обратная сторона: поддержка многочисленных типов данных одновременно означает, что данные‚ как правило, упакованы менее плотно. И в результате вся структура занимает больше места.
tuple — неизменяемые контейнеры
Аналогично спискам, кортежи тоже являются составной частью ядра языка Python. Однако в отличие от списков, в Python объекты-кортежи не изменяются. Это означает, что элементы не могут динамично изменяться или удаляться — все элементы в кортеже должны быть определены во время создания.
Точно так же, как и списки, кортежи могут содержать элементы произвольных типов данных. В этой гибкости много мощности, но, опять-таки, это также означает, что данные упакованы менее плотно, чем это было бы в типизированном массиве.
array.array — элементарные типизированные массивы
Модуль Python array обеспечивает пространственно-эффективное хранение элементарных типов данных в стиле языка С, таких как байт, 32-разрядные целые числа, числа с плавающей точкой и т. д.
Массивы, создаваемые на основе класса array.array, могут изменяться и ведут себя аналогично спискам, за исключением одного важного различия — они являются «типизированными массивами», ограниченными единственным типом данных.
Из-за этого ограничения объекты array.array со многими злементами более пространственно эффективны, чем списки и кортежи. Хранящиеся в них элементы плотно упакованы, и это может быть полезно, если вам нужно хранить много элементов одного и того же типа.
Кроме того, массивы поддерживают многие из тех же методов, что и у обычных списков, и вы можете их использовать в качестве «прямой замены» без необходимости вносить в свой код другие изменения.
str — неизменяемые массивы символов Юникода
В Python 3.х объекты строкового типа str используются для хранения текстовых данных в виде неизменяемых последовательностей символов Юникода. В сущности, это означает, что тип str представляет собой изменяемый массив символов. Как это ни странно, но тип str также является рекурсивной структурой данных: каждый элемент в строке также является объектом str длиной, равной 1.
Строковые объекты пространственно эффективны, потому что они плотно упакованы и специализируются на одном-единственном типе данных, Если вы храните текст в кодировке Юникод, то лучше использовать этот тип данных.
Поскольку строки в Python не могут изменяться, модификация строкового значения требует создания модифицированной копии. Самым близким эквивалентом «изменяющейся последовательности символов» будет список, в котором символы хранятся по отдельности.
bytes — неизменяемые массивы одиночных байтов.
Объекты bytes представляют собой неизменяемые последовательности одиночных байтов (целых чисел в диапазоне 0 <= х <= 255). В концептуальном плане они подобны объектам str и их также можно представить как неизменяемые массивы байтов.
Аналогично строковому типу, тип bytes имеет свой собственный литеральный синтаксис, предназначенный для создания объектов, и объекты этого типа пространственно эффективны. Объекты bytes не могут изменяться, но, в отличие от строковых объектов, для «изменяемых массивов байтов» есть специальный тип данных, который называется bytearray или байтовый массив, в который они могут быть распакованы. Вы узнаете о нем подробнее в следующем подразделе.
bytearray— изменяемые массивы одиночных байтов
Тип bytearray представляет собой изменяемую последовательность целых чисел в диапазоне 0 <= х <= 255. Они тесно связаны с объектами bytes, при этом главное их отличие в том, что объекты bytearray можно свободно изменять — вы можете переписывать элементы, удалять существующие элементы или добавлять новые. Объект bytearray будет соответствующим образом расти и сжиматься.
Объекты bytearray могут быть преобразованы обратно в неизменяемые объекты bytes, но это влечет за собой копирование абсолютно всех хранящихся в них данных — весьма медленная операция, занимающая О(n) времени.
Ключевые выводы
В том, что касается реализации массивов в Python, вы можете выбирать из широкого круга встроенных структур данных. В этом разделе мы сосредоточились на ключевых функциональных средствах языка и структурах данных, включенных только в стандартную библиотеку.
Если вы готовы выйти за пределы стандартной библиотеки Python, то сторонние пакеты, такие как NumPy, предлагают широкий спектр массивоподобных реализаций с большим быстродействием для научных вычислений и науки о данных.
Если ограничиваться массивоподобными структурами данных, включенными в Python, то наш выбор сводится к следующему.
- Вам нужно хранить произвольные объекты, которые потенциально могут иметь смешанные типы данных? Используйте список или кортеж в зависимости от того, хотите вы иметь неизменяемую структуру данных или нет.
- У вас есть числовые (целочисленные или с плавающей точкой) данные и для вас важны плотная упаковка и производительность? Попробуйте array.array и посмотрите, способен ли этот тип делать все, что вам нужно. Кроме того, рассмотрите выход за пределы стандартной библиотеки и попробуйте такие пакеты, как NumPy или Pandas.
- У вас есть текстовые данные, представленные символами Юникода? Используйте встроенный в Python тип str. Если вам нужна «изменяемая последовательность символов», то используйте list как список символов.
- Вы хотите хранить нефрагментированный блок байтов? Используйте неизменяемый тип bytes, либо bytearray, если вам нужна изменяемая структура данных.
В большинстве случаев мне нравится начинать с простого списка list. И только потом я конкретизирую используемый тип, если производительность или занимаемое пространство оперативной памяти становятся проблемой.
В большинстве случаев использование массивоподобной структуры данных общего назначения, такой как список list, обеспечивает наибольшую скорость разработки и удобство во время программирования. Для себя я понял, что в самом начале это обычно намного важнее, чем пытаться выжимать последнюю каплю производительности.
#структуры данных #технологии #python #программирование #интернет