image_pdf

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

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

В этой статье мы рассмотрим реализации массива в Python с использованием только основных конструкций языка или возможности стандартной библиотеки Python.

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

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

Итак, как работаю массивы в Python и для чего они нужны?

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

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

Реальной аналогией для массива является парковка:

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

Но не все парковки одинаковы:

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

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

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

Давайте обсудим возможные варианты:

Изменяемые одномерные динамические массивы — list

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

Списки Python могут содержать произвольные элементы любого типа — в Python «всё» есть объект, включая функции. Поэтому можно смешивать, сравнивать различные типы данных и хранить их все в одном списке.

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

>>> arr = ['one', 'two', 'three']
>>> arr[0]
'one'

# Lists have a nice repr:
>>> arr
['one', 'two', 'three']

# Lists are mutable:
>>> arr[1] = 'hello'
>>> arr
['one', 'hello', 'three']

>>> del arr[1]
>>> arr
['one', 'three']

# Lists can hold arbitrary data types:
>>> arr.append(23)
>>> arr
['one', 'three', 23]

Неизменяемый контейнер, кортеж — tuple

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

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

>>> arr = 'one', 'two', 'three'
>>> arr[0]
'one'

# Tuples have a nice repr:
>>> arr
('one', 'two', 'three')

# Tuples are immutable:
>>> arr[1] = 'hello'
TypeError: "'tuple' object does not support item assignment"

>>> del arr[1]
TypeError: "'tuple' object doesn't support item deletion"

# Tuples can hold arbitrary data types:
# (Adding elements creates a copy of the tuple)
>>> arr + (23,)
('one', 'two', 'three', 23)

Базовый типизированный массив  — array.array

Модуль array Python обеспечивает эффективное хранение базовых типов данных в C-стиле, таких как байты, 32‑разрядные целые числа, числа с плавающей точкой и т. д.

Массивы, созданные с помощью класса array.array, могут изменяться и ведут себя аналогично спискам за исключением того, что являются “типизированными массивами” и ограничены одним типом.

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

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

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

>>> import array
>>> arr = array.array('f', (1.0, 1.5, 2.0, 2.5))
>>> arr[1]
1.5

# Arrays have a nice repr:
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

# Arrays are mutable:
>>> arr[1] = 23.0
>>> arr
array('f', [1.0, 23.0, 2.0, 2.5])

>>> del arr[1]
>>> arr
array('f', [1.0, 2.0, 2.5])

>>> arr.append(42.0)
>>> arr
array('f', [1.0, 2.0, 2.5, 42.0])

# Arrays are "typed":
>>> arr[1] = 'hello'
TypeError: "must be real number, not str"

Неизменные массивы символов Юникода — str

Python 3.x использует объекты str для хранения текстовых данных в виде неизменных последовательностей символов Юникода. Собственно говоря, это означает, что str — это рекурсивная структура данных, где каждый символ сам является объектом str с длиной равной 1, кроме того, он не может быть изменён.

Строковые объекты эффективны с точки зрения использования памяти, поскольку плотно упакованы и все элементы относятся к одному типе данных. Если вы храните текст в Юникоде, то надо использовать все возможности обработки. Поскольку строки неизменны, то для модификации необходимо создать копию. Наиболее близким эквивалентом «изменяемой строки» является список, где хранятся отдельные символы.

>>> arr = 'abcd'
>>> arr[1]
'b'

>>> arr
'abcd'

# Strings are immutable:
>>> arr[1] = 'e'
TypeError: "'str' object does not support item assignment"

>>> del arr[1]
TypeError: "'str' object doesn't support item deletion"

# Strings can be unpacked into a list to
# get a mutable representation:
>>> list('abcd')
['a', 'b', 'c', 'd']
>>> ''.join(list('abcd'))
'abcd'

# Strings are recursive data structures:
>>> type('abc')
""
>>> type('abc'[0])
""

Неизменный массив байт — bytes

Байтовые объекты — это неизменные последовательности отдельных байтов (целые числа в диапазоне от 0 <= x <= 255). Концептуально они похожи на объекты str.

Как и строки, bytes имеют свой собственный синтаксис для создания компактных объектов. Байтовые объекты неизменны, но в отличие от строк есть специальный тип данных «изменяемый байтовый массив», называемый bytearray, куда они могут быть распакованы. Но об этом в следующем разделе.

>>> arr = bytes((0, 1, 2, 3))
>>> arr[1]
1

# Bytes literals have their own syntax:
>>> arr
b'\x00\x01\x02\x03'
>>> arr = b'\x00\x01\x02\x03'

# Only valid "bytes" are allowed:
>>> bytes((0, 300))
ValueError: "bytes must be in range(0, 256)"

# Bytes are immutable:
>>> arr[1] = 23
TypeError: "'bytes' object does not support item assignment"

>>> del arr[1]
TypeError: "'bytes' object doesn't support item deletion"

Изменяемый массив байт — bytearray

Тип bytearray представляет собой изменяемую последовательность целых чисел в диапазоне от 0 до 255. Он тесно похож на тип bytes, а главным отличием является то, что bytearrays можно свободно изменять — можно перезаписывать элементы, удалять существующие элементы или добавлять новые. Объект bytearray при этом будет расти или уменьшаться должным образом.

Объекты Bytearrays могут быть преобразованы обратно в неизменные объекты bytes, но при этом производится полное копированию сохраненных данных и операция занимает O(n) времени.

>>> arr = bytearray((0, 1, 2, 3))
>>> arr[1]
1

# The bytearray repr:
>>> arr
bytearray(b'\x00\x01\x02\x03')

# Bytearrays are mutable:
>>> arr[1] = 23
>>> arr
bytearray(b'\x00\x17\x02\x03')

>>> arr[1]
23

# Bytearrays can grow and shrink in size:
>>> del arr[1]
>>> arr
bytearray(b'\x00\x02\x03')

>>> arr.append(42)
>>> arr
bytearray(b'\x00\x02\x03*')

# Bytearrays can only hold "bytes"
# (integers in the range 0 <= x <= 255)
>>> arr[1] = 'hello'
TypeError: "an integer is required"

>>> arr[1] = 300
ValueError: "byte must be in range(0, 256)"

# Bytearrays can be converted back into bytes objects:
# (This will copy the data)
>>> bytes(arr)
b'\x00\x02\x03*'

Какой способ представления массивов надо использовать в Python?

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

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

Оставаясь в рамках естественных типов данных Python и стандартной библиотеки, вот к чему сводится наш выбор:

  • Нужно хранить произвольные объекты, потенциально, с различными типами данных? — Используйте list или tuple, в зависимости от необходимости проводить в них изменения.
  • Есть числовые данные (целочисленные/с плавающей данные), требуется плотная упаковка и важна производительность? — Попробуйте array.array и посмотрите, делает ли он все, что нужно. Рассмотрите возможность выхода за пределы стандартной библиотеки и попробуйте такой пакет, как NumPy.
  • Есть текстовые данные, представленные в виде символов Юникода? — Используйте встроенный в Python str. Если нужна «изменяемая строка», используйте список символов list.
  • Хотите сохранить непрерывный блок байтов? — Используйте bytes (неизменяемый) или bytearray (изменяемый) массивы байтов.

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

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

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

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

Ознакомьтесь с полной серией статей «Основные структуры данных в Python». В этой статье чего-то не хватает или вы нашли ошибку? Помогите коллеге и оставьте комментарий ниже.

Source

Опубликовано Вадим В. Костерин

Ст.преп. кафедры ИТЭ. Автор более 130 научных и учебно-методических работ. Лауреат ВДНХ (серебряная медаль).

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *