Структуры данных

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

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

Список

Список[1] – это структура данных, которая содержит упорядоченный набор элементов, т.е. хранит последовательность элементов. Это легко представить, если вспомнить список покупок, в котором перечисляется, что нужно купить, с тем лишь исключением, что в списке покупок каждый элемент обычно размещается на отдельной строке, тогда как в Python они разделяются запятыми.

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

Краткое введение в объекты и классы

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

Список – это один из примеров использования объектов и классов. Когда мы назначаем некоторой переменной i значение, скажем, целое число 5, это можно представить себе как создание объекта (т.е. экземпляра) i класса (т.е. типа) int. Чтобы лучше понять это, прочитайте help(int).

Класс может также иметь методы, т.е. функции, определённые для использования только применительно к данному классу. Этот функционал будет доступен только когда имеется объект данного класса. Например, Python предоставляет метод append для класса list, который позволяет добавлять элемент к концу списка. Так mylist.append('and item') добавит эту строку к списку mylist. Обратите внимание на обозначение точкой для доступа к методам объектов.

Класс также может иметь поля, которые представляют собой не что иное, как переменные, определённые для использования только применительно к данному классу. Эти переменные/имена можно использовать только тогда, когда имеется объект этого класса. Доступ к полям также осуществляется при помощи точки. Например, mylist.field.

Пример: (сохраните как using_list.py)

# Это мой список покупок
shoplist = ['яблоки', 'манго', 'морковь', 'бананы']

print('Я должен сделать', len(shoplist), 'покупки.')

print('Покупки:', end=' ')
for item in shoplist:
    print(item, end=' ')

print('\nТакже нужно купить риса.')
shoplist.append('рис')
print('Теперь мой список покупок таков:', shoplist)

print('Отсортирую-ка я свой список')
shoplist.sort()
print('Отсортированный список покупок выглядит так:', shoplist)

print('Первое, что мне нужно купить, это', shoplist[0])
olditem = shoplist[0]
del shoplist[0]
print('Я купил', olditem)
print('Теперь мой список покупок:', shoplist)

Вывод:

$ python3 using_list.py
Я должен сделать 4 покупки.

Покупки: яблоки манго морковь бананы
Также нужно купить риса.
Теперь мой список покупок таков: ['яблоки', 'манго', 'морковь', 'бананы', 'рис']
Отсортирую-ка я свой список
Отсортированный список покупок выглядит так: ['бананы', 'манго', 'морковь', 'рис', 'яблоки']
Первое, что мне нужно купить, это бананы
Я купил бананы
Теперь мой список покупок: ['манго', 'морковь', 'рис', 'яблоки']

Как это работает:

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

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

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

Далее мы добавляем элемент к списку при помощи append – метода объекта списка, который уже обсуждался ранее. Затем мы проверяем, действительно ли элемент был добавлен к списку, выводя содержимое списка на экран при помощи простой передачи этого списка функции print, которая аккуратно его печатает.

Затем мы сортируем список, используя метод sort объекта списка. Имейте в виду, что этот метод действует на сам список, а не возвращает изменённую его версию. В этом отличие от того, как происходит работа со строками. Именно это имеется в виду, когда мы говорим, что списки изменяемы, а строки – неизменяемы.

Далее после совершения покупки мы хотим удалить её из списка. Это достигается применением оператора del. Мы указываем, какой элемент списка мы хотим удалить, и оператор del удаляет его. Мы указываем, что хотим удалить первый элемент списка, и поэтому пишем “del shoplist[0]” (помните, что Python начинает отсчёт с 0).

Чтобы узнать более детально обо всех методах объекта списка, просмотрите help(list).

Кортеж

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

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

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

Пример: (сохраните как using_tuple.py)

zoo = ('питон', 'слон', 'пингвин') # помните, что скобки не обязательны
print('Количество животных в зоопарке -', len(zoo))

new_zoo = 'обезьяна', 'верблюд', zoo
print('Количество клеток в зоопарке -', len(new_zoo))
print('Все животные в новом зоопарке:', new_zoo)
print('Животные, привезённые из старого зоопарка:', new_zoo[2])
print('Последнее животное, привезённое из старого зоопарка -', new_zoo[2][2])
print('Количество животных в новом зоопарке -', len(new_zoo)-1+len(new_zoo[2]))

Вывод:

$ python3 using_tuple.py
Количество животных в зоопарке - 3
Количество клеток в зоопарке - 3
Все животные в новом зоопарке: ('обезьяна', 'верблюд', ('питон', 'слон', 'пингвин'))
Животные, привезённые из старого зоопарка: ('питон', 'слон', 'пингвин')
Последнее животное, привезённое из старого зоопарка - пингвин
Количество животных в новом зоопарке - 5

Как это работает:

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

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

Доступ к элементам кортежа осуществляется указанием позиции элемента, заключённой в квадратные скобки – точно так же, как мы это делали для списков. Это называется оператором индексирования. Доступ к третьему элементу в new_zoo мы получаем, указывая new_zoo[2], а доступ к третьему элементу внутри третьего элемента в кортеже new_zoo – указывая new_zoo[2][2]. Это достаточно просто, как только вы поймёте принцип.

Скобки

Хотя скобки и не являются обязательными, я предпочитаю всегда указывать их, чтобы было очевидно, что это кортеж, особенно в двусмысленных случаях. Например, print(1,2,3) и print( (1,2,3) ) делают разные вещи: первое выражение выводит три числа, тогда как второе – кортеж, содержащий эти три числа.

Кортеж, содержащий 0 или 1 элемент

Пустой кортеж создаётся при помощи пустой пары скобок – “myempty = ()”. Однако, с кортежем из одного элемента не всё так просто. Его нужно указывать при помощи запятой после первого (и единственного) элемента, чтобы Python мог отличить кортеж от скобок, окружающих объект в выражении. Таким образом, чтобы получить кортеж, содержащий элемент 2, вам потребуется указать “singleton = (2,)”.

Замечание для программистов на Perl

Список внутри списка не теряет своей индивидуальности, т.е. списки не развёртываются, как в Perl. Это же относится к кортежу внутри кортежа, или кортежу внутри списка, или списку внутри кортежа и т.д. В Python все они рассматриваются как объекты, хранящиеся внутри другого объекта – только и всего.

Словарь

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

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

Пары ключ-значение указываются в словаре следующим образом: “d = {key1 : value1, key2 : value2 }”. Обратите внимание, что ключ и значение разделяются двоеточием, а пары друг от друга отделяются запятыми, а затем всё это заключается в фигурные скобки.

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

Словари являются экземплярами/объектами класса dict.

Пример: (сохраните как using_dict.py)

# 'ab' - сокращение от 'a'ddress'b'ook

ab = {  'Swaroop'   : 'swaroop@swaroopch.com',
        'Larry'     : 'larry@wall.org',
        'Matsumoto' : 'matz@ruby-lang.org',
        'Spammer'   : 'spammer@hotmail.com'
     }

print("Адрес Swaroop'а:", ab['Swaroop'])

# Удаление пары ключ-значение
del ab['Spammer']

print('\nВ адресной книге {0} контакта\n'.format(len(ab)))

for name, address in ab.items():
    print('Контакт {0} с адресом {1}'.format(name, address))

# Добавление пары ключ-значение
ab['Guido'] = 'guido@python.org'

if 'Guido' in ab:
    print("\nАдрес Guido:", ab['Guido'])

Вывод:

$ python3 using_dict.py
Адрес Swaroop'а: swaroop@swaroopch.com

В адресной книге 3 контакта

Контакт Swaroop с адресом swaroop@swaroopch.com
Контакт Matsumoto с адресом matz@ruby-lang.org
Контакт Larry с адресом larry@wall.org

Адрес Guido: guido@python.org

Как это работает:

Мы создаём словарь ab[2] при помощи обозначений, описанных ранее. Затем мы обращаемся к парам ключ-значение, указывая ключ в операторе индексирования, которым мы пользовались для списков и кортежей. Как видите, синтаксис прост.

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

Далее мы обращаемся ко всем парам ключ-значение нашего словаря, используя метод items, который возвращает список кортежей, каждый из которых содержит пару элементов: ключ и значение. Мы получаем эту пару и присваиваем её значение переменным name и address соответственно в цикле for..in, а затем выводим эти значения на экран в блоке for.

Новые пары ключ-значение добавляются простым обращением к нужному ключу при помощи оператора индексирования и присваиванием ему некоторого значения, как мы сделали для Guido в примере выше.

Проверить, существует ли пара ключ-значение, можно при помощи оператора in.

Чтобы просмотреть список всех методов класса dict смотрите help(dict).

Ключевые Аргументы и Словари

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

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

Списки, кортежи и строки являются примерами последовательностей. Но что такое последовательности и что в них такого особенного?

Основные возможности – это проверка принадлежности (т.е. выражения “in” и “not in”) и оператор индексирования, позволяющий получить напрямую некоторый элемент последовательности.

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

Пример: (сохраните как seq.py)

shoplist = ['яблоки', 'манго', 'морковь', 'бананы']
name = 'swaroop'

# Операция индексирования
print('Элемент 0 -', shoplist[0])
print('Элемент 1 -', shoplist[1])
print('Элемент 2 -', shoplist[2])
print('Элемент 3 -', shoplist[3])
print('Элемент -1 -', shoplist[-1])
print('Элемент -2 -', shoplist[-2])
print('Символ 0 -', name[0])

# Вырезка из списка
print('Элементы с 1 по 3:', shoplist[1:3])
print('Элементы с 2 до конца:', shoplist[2:])
print('Элементы с 1 по -1:', shoplist[1:-1])
print('Элементы от начала до конца:', shoplist[:])

# Вырезка из строки
print('Символы с 1 по 3:', name[1:3])
print('Символы с 2 до конца:', name[2:])
print('Символы с 1 до -1:', name[1:-1])
print('Символы от начала до конца:', name[:])

Вывод:

$ python3 seq.py
Элемент 0 - яблоки
Элемент 1 - манго
Элемент 2 - морковь
Элемент 3 - бананы
Элемент -1 - бананы
Элемент -2 - морковь
Символ 0 - s
Элементы с 1 по 3: ['манго', 'морковь']
Элементы с 2 до конца: ['морковь', 'бананы']
Элементы с 1 по -1: ['манго', 'морковь']
Элементы от начала до конца: ['яблоки', 'манго', 'морковь', 'бананы']
Символы с 1 по 3: wa
Символы с 2 до конца: aroop
Символы с 1 до -1: waroo
Символы от начала до конца: swaroop

Как это работает:

Прежде всего, мы видим, как использовать индексы для получения отдельных элементов последовательности. Это ещё называют приписыванием индекса. Когда мы указываем число в квадратных скобках после последовательности, как показано выше, Python извлекает элемент, соответствующий указанной позиции в последовательности. Помните, что Python начинает отсчёт с 0. Поэтому shoplist[0] извлекает первый элемент, а shoplist[3] – четвёртый элемент последовательности shoplist.

Индекс также может быть отрицательным числом. В этом случае позиция отсчитывается от конца последовательности. Поэтому shoplist[-1] указывает на последний элемент последовательности shoplist, а shoplist[-2] – на предпоследний.

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

Первое число (перед двоеточием) в операции вырезки указывает позицию, с которой вырезка должна начинаться, а второе число (после двоеточия) указывает, где вырезка должна закончиться. Если первое число не указано, Python начнёт вырезку с начала последовательности. Если пропущено второе число, Python закончит вырезку у конца последовательности. Обратите внимание, что полученная вырезка будет начинаться с указанной начальной позиции, а заканчиваться прямо перед указанной конечной позицией, т.е. начальная позиция будет включена в вырезку, а конечная – нет.

Таким образом, shoplist[1:3] возвращает вырезку из последовательности, начинающуюся с позиции 1, включает позицию 2, но останавливается на позиции 3, и поэтому возвращает вырезку из двух элементов. Аналогично, shoplist[:] возвращает копию всей последовательности.

Вырезка может осуществляться и с отрицательными значениями. Отрицательные числа обозначают позицию с конца последовательности. Например, shoplist[:-1] вернёт вырезку из последовательности, исключающую последний элемент, но содержащую все остальные.

Кроме того, можно также указать третий аргумент для вырезки, который будет обозначать шаг вырезки (по умолчанию шаг вырезки равен 1):

>>> shoplist = ['яблоки', 'манго', 'морковь', 'бананы']
>>> shoplist[::1]
['яблоки', 'манго', 'морковь', 'бананы']
>>> shoplist[::2]
['яблоки', 'морковь']
>>> shoplist[::3]
['яблоки', 'бананы']
>>> shoplist[::-1]
['бананы', 'морковь', 'манго', 'яблоки']

Обратите внимание на то, что когда шаг равен 2, мы получаем элементы, находящиеся на позициях 0, 2, ... Когда шаг равен 3, мы получаем элементы с позиций 0, 3, ... и т.д.

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

Множество

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

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

>>> bri = set(['Бразилия', 'Россия', 'Индия'])
>>> 'Индия' in bri
True
>>> 'США' in bri
False
>>> bric = bri.copy()
>>> bric.add('Китай')
>>> bric.issuperset(bri)
True
>>> bri.remove('Россия')
>>> bri & bric # OR bri.intersection(bric)
{'Бразилия', 'Индия'}

Как это работает:

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

Ссылки

Когда мы создаём объект и присваиваем его переменной, переменная только ссылается на объект, а не представляет собой этот объект! То есть имя переменной указывает на ту часть памяти компьютера, где хранится объект. Это называется привязкой имени к объекту.

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

Пример: (сохраните как reference.py)

print('Простое присваивание')
shoplist = ['яблоки', 'манго', 'морковь', 'бананы']
mylist = shoplist # mylist - лишь ещё одно имя, указывающее на тот же объект!

del shoplist[0] # Я сделал первую покупку, поэтому удаляю её из списка

print('shoplist:', shoplist)
print('mylist:', mylist)
# Обратите внимание, что и shoplist, и mylist выводят один и тот же список
# без пункта "яблоко", подтверждая тем самым, что они указывают на один объект.

print('Копирование при помощи полной вырезки')
mylist = shoplist[:] # создаём копию путём полной вырезки
del mylist[0] # удаляем первый элемент

print('shoplist:', shoplist)
print('mylist:', mylist)
# Обратите внимание, что теперь списки разные

Вывод:

$ python3 reference.py
Простое присваивание
shoplist: ['манго', 'морковь', 'бананы']
mylist: ['манго', 'морковь', 'бананы']
Копирование при помощи полной вырезки
shoplist: ['манго', 'морковь', 'бананы']
mylist: ['морковь', 'бананы']

Как это работает:

Большая часть объяснения содержится в комментариях.

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

Ещё о строках

Мы уже детально обсуждали строки ранее. Что же ещё можно о них узнать? Что ж, вы знали, например, что строки также являются объектами и имеют методы, при помощи которых можно делать практически всё: от проверки части строки до удаления краевых пробелов?

Все строки, используемые вами в программах, являются объектами класса str. Некоторые полезные методы этого класса продемонстрированы на примере ниже. Чтобы посмотреть весь список методов, выполните help(str).

Пример: (сохраните как str_methods.py)

name = 'Swaroop' # Это объект строки

if name.startswith('Swa'):
    print('Да, строка начинается на "Swa"')

if 'a' in name:
    print('Да, она содержит строку "a"')

if name.find('war') != -1:
    print('Да, она содержит строку "war"')

delimiter = '_*_'
mylist = ['Бразилия', 'Россия', 'Индия', 'Китай']
print(delimiter.join(mylist))

Вывод:

$ python3 str_methods.py
Да, строка начинается на "Swa"
Да, она содержит строку "a"
Да, она содержит строку "war"
Бразилия_*_Россия_*_Индия_*_Китай

Как это работает:

Здесь мы видим сразу несколько методов строк в действии. Метод startswith служит для того, чтобы определять, начинается ли строка с некоторой заданной подстроки. Оператор in используется для проверки, является ли некоторая строка частью данной строки.

Метод find используется для определения позиции данной подстроки в строке; find возвращает -1, если подстрока не обнаружена. В классе str также имеется отличный метод для объединения (join)[3] элементов последовательности с указанной строкой в качестве разделителя между элементами, возвращающий большую строку, сгенерированную таким образом.

Резюме

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

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

Примечания

[1]	list – англ. “список” (прим.перев.)

[2]	address book – англ. “адресная книга” (прим. перев.)

[3]	join – англ. “объединять” (прим.перев.)