datastructures.md
1> **Источник:** https://python-all.ru/3.1/tutorial/datastructures.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# 5. Структуры данных89В этой главе более подробно рассматриваются некоторые уже изученные темы, а также добавляются новые.1011## 5.1. Подробнее о списках1213Тип данных list имеет ещё несколько методов. Ниже перечислены все методы объектов list:1415#### `list.append(x)`1617Добавляет элемент в конец списка; эквивалентно1819`a[len(a):] = [x]`2021.2223#### `list.extend(L)`2425Расширяет список, добавляя все элементы из переданного списка; эквивалентно2627`a[len(a):] = L`2829.3031#### `list.insert(i, x)`3233Вставляет элемент в заданную позицию. Первый аргумент – это индекс элемента, перед которым нужно вставить, поэтому3435`a.insert(0, x)`3637вставляет в начало списка, а3839`a.insert(len(a), x)`4041эквивалентно4243`a.append(x)`4445.4647#### `list.remove(x)`4849Удаляет первый элемент списка, значение которого равно5051*x*5253. Возникает ошибка, если такого элемента нет.5455#### `list.pop([i])`5657Удаляет элемент в заданной позиции в списке и возвращает его. Если индекс не указан,5859`a.pop()`6061удаляет и возвращает последний элемент списка. (Квадратные скобки вокруг6263*i*6465в сигнатуре метода указывают, что параметр является необязательным, а не на то, что нужно вводить квадратные скобки в этой позиции. Эта нотация часто встречается в Справочнике по библиотеке Python.)6667#### `list.index(x)`6869Возвращает индекс первого элемента в списке, значение которого равно7071*x*7273. Если такого элемента нет, возникает ошибка.7475#### `list.count(x)`7677Возвращает количество вхождений7879*x*8081в список.8283#### `list.sort()`8485Сортирует элементы списка на месте.8687#### `list.reverse()`8889Разворачивает элементы списка на месте.9091Пример, использующий большинство методов списка:9293```python94>>> a = [66.25, 333, 333, 1, 1234.5]95>>> print(a.count(333), a.count(66.25), a.count('x'))962 1 097>>> a.insert(2, -1)98>>> a.append(333)99>>> a100[66.25, 333, -1, 333, 1, 1234.5, 333]101>>> a.index(333)1021103>>> a.remove(333)104>>> a105[66.25, -1, 333, 1, 1234.5, 333]106>>> a.reverse()107>>> a108[333, 1234.5, 1, 333, -1, 66.25]109>>> a.sort()110>>> a111[-1, 1, 66.25, 333, 333, 1234.5]112```113114### 5.1.1. Использование списков в качестве стеков115116Методы списков позволяют легко использовать список как стек, где последний добавленный элемент извлекается первым (принцип «последним пришёл – первым вышел»). Чтобы добавить элемент на вершину стека, используйте `append()`. Чтобы извлечь элемент с вершины стека, используйте `pop()` без явного указания индекса. Например:117118```python119>>> stack = [3, 4, 5]120>>> stack.append(6)121>>> stack.append(7)122>>> stack123[3, 4, 5, 6, 7]124>>> stack.pop()1257126>>> stack127[3, 4, 5, 6]128>>> stack.pop()1296130>>> stack.pop()1315132>>> stack133[3, 4]134```135136### 5.1.2. Использование списков в качестве очередей137138Список также можно использовать как очередь, где первый добавленный элемент извлекается первым (первым пришёл – первым ушёл); однако списки неэффективны для этой цели. Хотя добавление и извлечение элементов с конца списка выполняется быстро, вставка или извлечение с начала списка – медленно (поскольку все остальные элементы приходится сдвигать на одну позицию).139140Для реализации очереди используйте [`collections.deque`](https://python-all.ru/3.1/library/collections.html#collections.deque), который разработан для быстрого добавления и извлечения элементов с обоих концов. Например:141142```python143>>> from collections import deque144>>> queue = deque(["Eric", "John", "Michael"])145>>> queue.append("Terry") # Терри прибывает146>>> queue.append("Graham") # Грэм прибывает147>>> queue.popleft() # Первый прибывший теперь уходит148'Eric'149>>> queue.popleft() # Второй прибывший теперь уходит150'John'151>>> queue # Оставшаяся очередь в порядке прибытия152deque(['Michael', 'Terry', 'Graham'])153```154155### 5.1.3. Списковые включения156157Генераторы списков предоставляют краткий способ создания списков из последовательностей. Обычно они применяются для создания списков, каждый элемент которых является результатом некоторых операций, применённых к каждому элементу последовательности, или для создания подпоследовательности тех элементов, которые удовлетворяют определённому условию.158159Генератор списка состоит из квадратных скобок, содержащих выражение, за которым следует предложение [`for`](https://python-all.ru/3.1/reference/compound_stmts.html#for), а затем ноль или более предложений [`for`](https://python-all.ru/3.1/reference/compound_stmts.html#for) или [`if`](https://python-all.ru/3.1/reference/compound_stmts.html#if). Результатом будет список, полученный в результате вычисления выражения в контексте предложений [`for`](https://python-all.ru/3.1/reference/compound_stmts.html#for) и [`if`](https://python-all.ru/3.1/reference/compound_stmts.html#if), которые следуют за ним. Если выражение вычисляется в кортеж, его необходимо заключить в скобки.160161Здесь мы берём список чисел и возвращаем список, содержащий каждое число, умноженное на три:162163```python164>>> vec = [2, 4, 6]165>>> [3*x for x in vec]166[6, 12, 18]167```168169Теперь сделаем немного сложнее:170171```python172>>> [[x, x**2] for x in vec]173[[2, 4], [4, 16], [6, 36]]174```175176Здесь мы применяем вызов метода к каждому элементу последовательности:177178```python179>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']180>>> [weapon.strip() for weapon in freshfruit]181['banana', 'loganberry', 'passion fruit']182```183184Используя предложение [`if`](https://python-all.ru/3.1/reference/compound_stmts.html#if), мы можем отфильтровать поток:185186```python187>>> [3*x for x in vec if x > 3]188[12, 18]189>>> [3*x for x in vec if x < 2]190[]191```192193Кортежи часто можно создавать без круглых скобок, но не в этом случае:194195```python196>>> [x, x**2 for x in vec] # ошибка – для кортежей требуются скобки197 File "<stdin>", line 1, in ?198 [x, x**2 for x in vec]199 ^200SyntaxError: invalid syntax201>>> [(x, x**2) for x in vec]202[(2, 4), (4, 16), (6, 36)]203```204205Вот несколько вложенных циклов for и другие хитрости:206207```python208>>> vec1 = [2, 4, 6]209>>> vec2 = [4, 3, -9]210>>> [x*y for x in vec1 for y in vec2]211[8, 6, -18, 16, 12, -36, 24, 18, -54]212>>> [x+y for x in vec1 for y in vec2]213[6, 5, -7, 8, 7, -5, 10, 9, -3]214>>> [vec1[i]*vec2[i] for i in range(len(vec1))]215[8, 12, -54]216```217218Генераторы списков можно применять к сложным выражениям и вложенным функциям:219220```python221>>> [str(round(355/113, i)) for i in range(1, 6)]222['3.1', '3.14', '3.142', '3.1416', '3.14159']223```224225### 5.1.4. Вложенные списковые включения226227Если у вас хватит смелости, генераторы списков можно вкладывать друг в друга. Это мощный инструмент, но – как и все мощные инструменты – им нужно пользоваться осторожно, если вообще использовать.228229Рассмотрим следующий пример матрицы 3x3, хранящейся в виде списка, содержащего три списка, по одному списку на строку:230231```python232>>> mat = [233... [1, 2, 3],234... [4, 5, 6],235... [7, 8, 9],236... ]237```238239Теперь, если нужно поменять строки и столбцы местами, можно использовать генератор списка:240241```python242>>> print([[row[i] for row in mat] for i in [0, 1, 2]])243[[1, 4, 7], [2, 5, 8], [3, 6, 9]]244```245246Особую осторожность следует проявлять при работе с *вложенным* генератором списка:247248> Чтобы избежать путаницы при вложении генераторов списков, читайте справа налево.249250Более подробная версия этого фрагмента показывает поток выполнения наглядно:251252```python253for i in [0, 1, 2]:254 for row in mat:255 print(row[i], end="")256 print()257```258259В реальных задачах следует предпочесть встроенные функции сложным конструкциям управления потоком. Функция [`zip()`](https://python-all.ru/3.1/library/functions.html#zip) отлично подойдёт для этого случая:260261```python262>>> list(zip(*mat))263[(1, 4, 7), (2, 5, 8), (3, 6, 9)]264```265266Смотрите [*Распаковка списков аргументов*](https://python-all.ru/3.1/tutorial/controlflow.html#tut-unpacking-arguments) для подробностей об звёздочке в этой строке.267268## 5.2. Оператор [`del`](https://python-all.ru/3.1/reference/simple_stmts.html#del)269270Существует способ удалить элемент из списка по его индексу, а не по значению: оператор [`del`](https://python-all.ru/3.1/reference/simple_stmts.html#del). Он отличается от метода `pop()`, который возвращает значение. Оператор [`del`](https://python-all.ru/3.1/reference/simple_stmts.html#del) также можно использовать для удаления срезов из списка или очистки всего списка (что мы делали ранее, присваивая пустой список срезу). Например:271272```python273>>> a = [-1, 1, 66.25, 333, 333, 1234.5]274>>> del a[0]275>>> a276[1, 66.25, 333, 333, 1234.5]277>>> del a[2:4]278>>> a279[1, 66.25, 1234.5]280>>> del a[:]281>>> a282[]283```284285[`del`](https://python-all.ru/3.1/reference/simple_stmts.html#del) также можно использовать для удаления целых переменных:286287```python288>>> del a289```290291Ссылка на имя `a` в дальнейшем приведёт к ошибке (по крайней мере, пока ему не присвоено другое значение). Позже мы найдём другое применение для [`del`](https://python-all.ru/3.1/reference/simple_stmts.html#del).292293## 5.3. Кортежи и последовательности294295Мы видели, что списки и строки имеют много общих свойств, таких как индексирование и операции среза. Это два примера типов данных *последовательность* (см. [*Типы последовательностей – str, bytes, bytearray, list, tuple, range*](https://python-all.ru/3.1/library/stdtypes.html#typesseq)). Поскольку Python развивается, могут быть добавлены другие типы данных последовательностей. Существует также ещё один стандартный тип данных последовательности: *кортеж*.296297Кортеж состоит из нескольких значений, разделенных запятыми, например:298299```python300>>> t = 12345, 54321, 'hello!'301>>> t[0]30212345303>>> t304(12345, 54321, 'hello!')305>>> # Кортежи могут быть вложенными:306... u = t, (1, 2, 3, 4, 5)307>>> u308((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))309```310311Как видите, при выводе кортежи всегда заключаются в круглые скобки, чтобы вложенные кортежи интерпретировались правильно; при вводе их можно указывать как со скобками, так и без, хотя часто скобки всё равно необходимы (если кортеж является частью более крупного выражения).312313Кортежи имеют множество применений. Например: пары координат (x, y), записи о сотрудниках из базы данных и т.д. Кортежи, как и строки, неизменяемы: невозможно присваивать значения отдельным элементам кортежа (хотя во многом того же эффекта можно добиться с помощью срезов и конкатенации). Также можно создавать кортежи, содержащие изменяемые объекты, такие как списки.314315Особая проблема – создание кортежей, содержащих 0 или 1 элемент: в синтаксисе есть некоторые дополнительные особенности для таких случаев. Пустые кортежи создаются с помощью пустой пары круглых скобок; кортеж с одним элементом создается путем добавления запятой после значения (недостаточно заключить одно значение в скобки). Некрасиво, но эффективно. Например:316317```python318>>> empty = ()319>>> singleton = 'hello', # <-- обратите внимание на завершающую запятую320>>> len(empty)3210322>>> len(singleton)3231324>>> singleton325('hello',)326```327328Оператор `t = 12345, 54321, 'hello!'` является примером *упаковки кортежа*: значения `12345`, `54321` и `'hello!'` упаковываются вместе в кортеж. Возможна и обратная операция:329330```python331>>> x, y, z = t332```333334Это называется, что вполне уместно, *распаковкой последовательности* и работает для любой последовательности в правой части. Распаковка последовательности требует, чтобы переменных в левой части знака равенства было столько же, сколько элементов в последовательности. Обратите внимание, что множественное присваивание – это на самом деле комбинация упаковки кортежа и распаковки последовательности.335336## 5.4. Множества337338Python также включает тип данных для *множеств*. Множество – это неупорядоченная коллекция без повторяющихся элементов. Основные применения: проверка принадлежности и удаление дубликатов. Объекты-множества также поддерживают математические операции, такие как объединение, пересечение, разность и симметрическая разность.339340Фигурные скобки или функция [`set()`](https://python-all.ru/3.1/library/stdtypes.html#set) могут использоваться для создания множеств. Примечание: чтобы создать пустое множество, нужно использовать `set()`, а не `{}`; последнее создаёт пустой словарь – структуру данных, которую мы обсудим в следующем разделе.341342Вот краткая демонстрация:343344```python345>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}346>>> print(basket) # показать, что дубликаты удалены347{'orange', 'banana', 'pear', 'apple'}348>>> 'orange' in basket # быстрая проверка принадлежности349True350>>> 'crabgrass' in basket351False352353>>> # Демонстрация операций над множествами с уникальными буквами из двух слов354...355>>> a = set('abracadabra')356>>> b = set('alacazam')357>>> a # уникальные буквы в a358{'a', 'r', 'b', 'c', 'd'}359>>> a - b # буквы, которые есть в a, но нет в b360{'r', 'd', 'b'}361>>> a | b # Буквы из a или b362{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}363>>> a & b # буквы, которые есть и в a, и в b364{'a', 'c'}365>>> a ^ b # буквы, которые есть в a или в b, но не в обоих366{'r', 'd', 'b', 'm', 'z', 'l'}367```368369Как [*для списков*](https://python-all.ru/3.1/tutorial/datastructures.html#tut-listcomps), существует синтаксис генератора множеств:370371```python372>>> a = {x for x in 'abracadabra' if x not in 'abc'}373>>> a374{'r', 'd'}375```376377## 5.5. Словари378379Ещё одним полезным типом данных, встроенным в Python, является *словарь* (см. [*Типы отображений – dict*](https://python-all.ru/3.1/library/stdtypes.html#typesmapping)). В других языках словари иногда называются «ассоциативными запоминающими устройствами» или «ассоциативными массивами». В отличие от последовательностей, которые индексируются диапазоном чисел, словари индексируются *ключами*, которые могут быть любого неизменяемого типа; строки и числа всегда могут быть ключами. Кортежи могут использоваться как ключи, если они содержат только строки, числа или кортежи; если кортеж содержит любой изменяемый объект прямо или косвенно, он не может быть использован как ключ. Списки нельзя использовать как ключи, поскольку списки можно изменять на месте с помощью присваиваний по индексу, срезу или методов, таких как `append()` и `extend()`.380381Словарь лучше всего представлять как неупорядоченное множество пар *ключ: значение*, при этом ключи должны быть уникальными (в пределах одного словаря). Пара фигурных скобок создает пустой словарь: `{}`. Размещение внутри скобок списка пар ключ:значение, разделенных запятыми, добавляет начальные пары ключ:значение в словарь; так же словари отображаются при выводе.382383Основные операции над словарём – это сохранение значения по некоторому ключу и извлечение значения по заданному ключу. Также можно удалить пару ключ:значение с помощью `del`. Если сохранить значение по уже используемому ключу, старое значение, связанное с этим ключом, будет забыто. Извлечение значения по несуществующему ключу является ошибкой.384385Выполнение `list(d.keys())` над словарём возвращает список всех ключей, используемых в словаре, в произвольном порядке (если требуется отсортированный список, используйте вместо этого `sorted(d.keys())`). [\[1\]](https://python-all.ru/3.1/tutorial/datastructures.html#id2) Чтобы проверить, находится ли отдельный ключ в словаре, используйте ключевое слово [`in`](https://python-all.ru/3.1/reference/expressions.html#in).386387Вот небольшой пример использования словаря:388389```python390>>> tel = {'jack': 4098, 'sape': 4139}391>>> tel['guido'] = 4127392>>> tel393{'sape': 4139, 'guido': 4127, 'jack': 4098}394>>> tel['jack']3954098396>>> del tel['sape']397>>> tel['irv'] = 4127398>>> tel399{'guido': 4127, 'irv': 4127, 'jack': 4098}400>>> list(tel.keys())401['irv', 'guido', 'jack']402>>> sorted(tel.keys())403['guido', 'irv', 'jack']404>>> 'guido' in tel405True406>>> 'jack' not in tel407False408```409410Конструктор [`dict()`](https://python-all.ru/3.1/library/stdtypes.html#dict) создаёт словари непосредственно из последовательностей пар ключ-значение:411412```python413>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])414{'sape': 4139, 'jack': 4098, 'guido': 4127}415```416417Кроме того, словарные включения можно использовать для создания словарей из произвольных выражений ключа и значения:418419```python420>>> {x: x**2 for x in (2, 4, 6)}421{2: 4, 4: 16, 6: 36}422```423424Когда ключи являются простыми строками, иногда проще указать пары с помощью именованных аргументов:425426```python427>>> dict(sape=4139, guido=4127, jack=4098)428{'sape': 4139, 'jack': 4098, 'guido': 4127}429```430431## 5.6. Техники циклов432433При переборе словарей ключ и соответствующее значение можно получить одновременно с помощью метода `items()`.434435```python436>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}437>>> for k, v in knights.items():438... print(k, v)439...440gallahad the pure441robin the brave442```443444При переборе последовательности индекс позиции и соответствующее значение можно получить одновременно с помощью функции [`enumerate()`](https://python-all.ru/3.1/library/functions.html#enumerate).445446```python447>>> for i, v in enumerate(['tic', 'tac', 'toe']):448... print(i, v)449...4500 tic4511 tac4522 toe453```454455Для одновременного перебора двух или более последовательностей элементы можно объединить в пары с помощью функции [`zip()`](https://python-all.ru/3.1/library/functions.html#zip).456457```python458>>> questions = ['name', 'quest', 'favorite color']459>>> answers = ['lancelot', 'the holy grail', 'blue']460>>> for q, a in zip(questions, answers):461... print('What is your {0}? It is {1}.'.format(q, a))462...463What is your name? It is lancelot.464What is your quest? It is the holy grail.465What is your favorite color? It is blue.466```467468Чтобы перебрать последовательность в обратном порядке, сначала укажите последовательность в прямом порядке, а затем вызовите функцию [`reversed()`](https://python-all.ru/3.1/library/functions.html#reversed).469470```python471>>> for i in reversed(range(1, 10, 2)):472... print(i)473...47494757476547734781479```480481Чтобы перебрать последовательность в отсортированном порядке, используйте функцию [`sorted()`](https://python-all.ru/3.1/library/functions.html#sorted), которая возвращает новый отсортированный список, не изменяя исходный.482483```python484>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']485>>> for f in sorted(set(basket)):486... print(f)487...488apple489banana490orange491pear492```493494## 5.7. Подробнее об условиях495496Условия, используемые в операторах `while` и `if`, могут содержать любые операторы, а не только сравнения.497498Операторы сравнения `in` и `not in` проверяют, встречается ли значение в последовательности (или не встречается). Операторы `is` и `is not` сравнивают, являются ли два объекта действительно одним и тем же объектом; это важно только для изменяемых объектов, таких как списки. Все операторы сравнения имеют одинаковый приоритет, который ниже приоритета всех числовых операторов.499500Сравнения могут быть объединены в цепочку. Например, `a < b == c` проверяет, `a` меньше ли `b` и, более того, `b` равно `c`.501502Сравнения могут объединяться с помощью логических операторов `and` и `or`, а результат сравнения (или любого другого логического выражения) может быть инвертирован с помощью `not`. Эти операторы имеют более низкий приоритет, чем операторы сравнения; среди них `not` имеет самый высокий приоритет, а `or` – самый низкий, так что `A and not B or C` эквивалентно `(A and (not B)) or C`. Как всегда, для выражения желаемой группировки можно использовать круглые скобки.503504Логические операторы `and` и `or` являются так называемыми *short-circuit* операторами: их аргументы вычисляются слева направо, и вычисление прекращается, как только результат становится определённым. Например, если `A` и `C` истинны, а `B` ложно, то `A and B and C` не вычисляет выражение `C`. При использовании в качестве общего значения, а не логического, возвращаемым значением оператора короткого замыкания является последний вычисленный аргумент.505506Результат сравнения или другого логического выражения можно присвоить переменной. Например,507508```python509>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'510>>> non_null = string1 or string2 or string3511>>> non_null512'Trondheim'513```514515В Python, в отличие от C, присваивание не может использоваться внутри выражений. Программисты на C могут ворчать по этому поводу, но это позволяет избежать распространённого класса проблем, встречающихся в программах на C: ввод `=` в выражении, когда подразумевался `==`.516517## 5.8. Сравнение последовательностей и других типов518519Объекты последовательностей можно сравнивать с другими объектами того же типа последовательности. Сравнение использует *лексикографический* порядок: сначала сравниваются первые два элемента, и если они различаются, это определяет результат сравнения; если они равны, сравниваются следующие два элемента, и так далее, пока одна из последовательностей не закончится. Если два сравниваемых элемента сами являются последовательностями того же типа, лексикографическое сравнение выполняется рекурсивно. Если все элементы двух последовательностей равны, последовательности считаются равными. Если одна последовательность является начальной подпоследовательностью другой, более короткая последовательность считается меньшей (меньшей). Лексикографический порядок для строк использует номер кодовой точки Unicode для упорядочивания отдельных символов. Некоторые примеры сравнений между последовательностями одного типа:520521```python522(1, 2, 3) < (1, 2, 4)523[1, 2, 3] < [1, 2, 4]524'ABC' < 'C' < 'Pascal' < 'Python'525(1, 2, 3, 4) < (1, 2, 4)526(1, 2) < (1, 2, -1)527(1, 2, 3) == (1.0, 2.0, 3.0)528(1, 2, ('aa', 'ab')) < (1, 2, ('abc', 'a'), 4)529```530531Обратите внимание, что сравнение объектов разных типов с помощью `<` или `>` допустимо при условии, что объекты имеют соответствующие методы сравнения. Например, смешанные числовые типы сравниваются по их числовому значению, поэтому 0 равно 0.0 и т.д. В противном случае, вместо того чтобы давать произвольный порядок, интерпретатор вызовет исключение [`TypeError`](https://python-all.ru/3.1/library/exceptions.html#TypeError).532533Сноски534535| [\[1\]](https://python-all.ru/3.1/tutorial/datastructures.html#id1) | Вызов `d.keys()` вернёт объект *представления словаря*. Он поддерживает такие операции, как проверка принадлежности и итерация, но его содержимое не является независимым от исходного словаря – это всего лишь *представление*. |536| --- | --- |537