datastructures.md
1> **Источник:** https://python-all.ru/3.0/tutorial/datastructures.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# Структуры данных89В этой главе более подробно рассматриваются некоторые уже изученные темы, а также добавляются новые.1011## Подробнее о списках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### Использование списков в качестве стеков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### Использование списков в качестве очередей137138Список также можно удобно использовать в качестве очереди, где первый добавленный элемент является первым извлечённым («первым пришёл – первым вышел»). Чтобы добавить элемент в конец очереди, используйте `append()`. Чтобы извлечь элемент из начала очереди, используйте `pop()` с индексом `0`. Например:139140```python141>>> queue = ["Eric", "John", "Michael"]142>>> queue.append("Terry") # Терри прибывает143>>> queue.append("Graham") # Грэм прибывает144>>> queue.pop(0)145'Eric'146>>> queue.pop(0)147'John'148>>> queue149['Michael', 'Terry', 'Graham']150```151152### Списочные включения153154Генераторы списков предоставляют краткий способ создания списков из последовательностей. Обычно они применяются для создания списков, каждый элемент которых является результатом некоторых операций, применённых к каждому элементу последовательности, или для создания подпоследовательности тех элементов, которые удовлетворяют определённому условию.155156Каждое списковое включение состоит из выражения, за которым следует предложение [`for`](https://python-all.ru/3.0/reference/compound_stmts.html#for), а затем ноль или более предложений [`for`](https://python-all.ru/3.0/reference/compound_stmts.html#for) или [`if`](https://python-all.ru/3.0/reference/compound_stmts.html#if). Результатом будет список, полученный в результате вычисления выражения в контексте предложений [`for`](https://python-all.ru/3.0/reference/compound_stmts.html#for) и [`if`](https://python-all.ru/3.0/reference/compound_stmts.html#if), которые следуют за ним. Если выражение вычисляется в кортеж, его нужно заключить в скобки.157158Здесь мы берём список чисел и возвращаем список, содержащий каждое число, умноженное на три:159160```python161>>> vec = [2, 4, 6]162>>> [3*x for x in vec]163[6, 12, 18]164```165166Теперь сделаем немного сложнее:167168```python169>>> [[x, x**2] for x in vec]170[[2, 4], [4, 16], [6, 36]]171```172173Здесь мы применяем вызов метода к каждому элементу последовательности:174175```python176>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']177>>> [weapon.strip() for weapon in freshfruit]178['banana', 'loganberry', 'passion fruit']179```180181Используя предложение [`if`](https://python-all.ru/3.0/reference/compound_stmts.html#if), мы можем отфильтровать поток:182183```python184>>> [3*x for x in vec if x > 3]185[12, 18]186>>> [3*x for x in vec if x < 2]187[]188```189190Кортежи часто можно создавать без круглых скобок, но не в этом случае:191192```python193>>> [x, x**2 for x in vec] # ошибка – для кортежей требуются скобки194 File "<stdin>", line 1, in ?195 [x, x**2 for x in vec]196 ^197SyntaxError: invalid syntax198>>> [(x, x**2) for x in vec]199[(2, 4), (4, 16), (6, 36)]200```201202Вот несколько вложенных циклов for и другие хитрости:203204```python205>>> vec1 = [2, 4, 6]206>>> vec2 = [4, 3, -9]207>>> [x*y for x in vec1 for y in vec2]208[8, 6, -18, 16, 12, -36, 24, 18, -54]209>>> [x+y for x in vec1 for y in vec2]210[6, 5, -7, 8, 7, -5, 10, 9, -3]211>>> [vec1[i]*vec2[i] for i in range(len(vec1))]212[8, 12, -54]213```214215Генераторы списков можно применять к сложным выражениям и вложенным функциям:216217```python218>>> [str(round(355/113, i)) for i in range(1, 6)]219['3.1', '3.14', '3.142', '3.1416', '3.14159']220```221222### Вложенные списковые включения223224Если у вас хватит смелости, генераторы списков можно вкладывать друг в друга. Это мощный инструмент, но – как и все мощные инструменты – им нужно пользоваться осторожно, если вообще использовать.225226Рассмотрим следующий пример матрицы 3x3, хранящейся в виде списка, содержащего три списка, по одному списку на строку:227228```python229>>> mat = [230... [1, 2, 3],231... [4, 5, 6],232... [7, 8, 9],233... ]234```235236Теперь, если нужно поменять строки и столбцы местами, можно использовать генератор списка:237238```python239>>> print([[row[i] for row in mat] for i in [0, 1, 2]])240[[1, 4, 7], [2, 5, 8], [3, 6, 9]]241```242243Особую осторожность следует проявлять при работе с *вложенным* генератором списка:244245> Чтобы избежать путаницы при вложении генераторов списков, читайте справа налево.246247Более подробная версия этого фрагмента показывает поток выполнения наглядно:248249```python250for i in [0, 1, 2]:251 for row in mat:252 print(row[i], end="")253 print()254```255256На практике следует предпочитать встроенные функции сложным конструкциям управления потоком. Функция [`zip()`](https://python-all.ru/3.0/library/functions.html#zip) отлично подходит для этой задачи:257258```python259>>> list(zip(*mat))260[(1, 4, 7), (2, 5, 8), (3, 6, 9)]261```262263Смотрите [*Распаковка списков аргументов*](https://python-all.ru/3.0/tutorial/controlflow.html#tut-unpacking-arguments) для подробностей об звёздочке в этой строке.264265## Инструкция [`del`](https://python-all.ru/3.0/reference/simple_stmts.html#del)266267Существует способ удалить элемент из списка по его индексу, а не по значению: оператор [`del`](https://python-all.ru/3.0/reference/simple_stmts.html#del). Он отличается от метода `pop()`, который возвращает значение. Оператор [`del`](https://python-all.ru/3.0/reference/simple_stmts.html#del) также можно использовать для удаления срезов из списка или очистки всего списка (что мы делали ранее, присваивая пустой список срезу). Например:268269```python270>>> a = [-1, 1, 66.25, 333, 333, 1234.5]271>>> del a[0]272>>> a273[1, 66.25, 333, 333, 1234.5]274>>> del a[2:4]275>>> a276[1, 66.25, 1234.5]277>>> del a[:]278>>> a279[]280```281282[`del`](https://python-all.ru/3.0/reference/simple_stmts.html#del) также можно использовать для удаления целых переменных:283284```python285>>> del a286```287288Ссылка на имя `a` в дальнейшем приведёт к ошибке (по крайней мере, пока ему не присвоено другое значение). Позже мы найдём другое применение для [`del`](https://python-all.ru/3.0/reference/simple_stmts.html#del).289290## Кортежи и последовательности291292Мы видели, что списки и строки имеют много общих свойств, таких как индексирование и операции среза. Это два примера типов данных *последовательность* (см. [*Типы последовательностей – str, bytes, bytearray, list, tuple, range*](https://python-all.ru/3.0/library/stdtypes.html#typesseq)). Поскольку Python развивается, могут быть добавлены другие типы данных последовательностей. Существует также ещё один стандартный тип данных последовательности: *кортеж*.293294Кортеж состоит из нескольких значений, разделенных запятыми, например:295296```python297>>> t = 12345, 54321, 'hello!'298>>> t[0]29912345300>>> t301(12345, 54321, 'hello!')302>>> # Кортежи могут быть вложенными:303... u = t, (1, 2, 3, 4, 5)304>>> u305((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))306```307308Как видите, при выводе кортежи всегда заключаются в круглые скобки, чтобы вложенные кортежи интерпретировались правильно; при вводе их можно указывать как со скобками, так и без, хотя часто скобки всё равно необходимы (если кортеж является частью более крупного выражения).309310Кортежи имеют множество применений. Например: пары координат (x, y), записи о сотрудниках из базы данных и т.д. Кортежи, как и строки, неизменяемы: невозможно присваивать значения отдельным элементам кортежа (хотя во многом того же эффекта можно добиться с помощью срезов и конкатенации). Также можно создавать кортежи, содержащие изменяемые объекты, такие как списки.311312Особая проблема – создание кортежей, содержащих 0 или 1 элемент: в синтаксисе есть некоторые дополнительные особенности для таких случаев. Пустые кортежи создаются с помощью пустой пары круглых скобок; кортеж с одним элементом создается путем добавления запятой после значения (недостаточно заключить одно значение в скобки). Некрасиво, но эффективно. Например:313314```python315>>> empty = ()316>>> singleton = 'hello', # <-- обратите внимание на завершающую запятую317>>> len(empty)3180319>>> len(singleton)3201321>>> singleton322('hello',)323```324325Оператор `t = 12345, 54321, 'hello!'` является примером *упаковки кортежа*: значения `12345`, `54321` и `'hello!'` упаковываются вместе в кортеж. Возможна и обратная операция:326327```python328>>> x, y, z = t329```330331Это называется, что вполне уместно, *распаковкой последовательности*. Распаковка последовательности требует, чтобы список переменных слева содержал то же количество элементов, что и длина последовательности. Обратите внимание, что множественное присваивание – это на самом деле комбинация упаковки кортежа и распаковки последовательности!332333Здесь есть небольшая асимметрия: упаковка нескольких значений всегда создаёт кортеж, а распаковка работает для любой последовательности.334335## Множества336337Python также включает тип данных для *множеств*. Множество – это неупорядоченная коллекция без повторяющихся элементов. Основные применения: проверка принадлежности и удаление дубликатов. Объекты-множества также поддерживают математические операции, такие как объединение, пересечение, разность и симметрическая разность.338339Фигурные скобки или функция [`set()`](https://python-all.ru/3.0/library/stdtypes.html#set) могут использоваться для создания множеств. Примечание: Для создания пустого множества нужно использовать set(), а не {}; последнее создаёт пустой словарь – структуру данных, которую мы обсудим в следующем разделе.340341Вот краткая демонстрация:342343```python344>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}345>>> print(basket)346{'orange', 'banana', 'pear', 'apple'}347>>> fruit = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']348>>> fruit = set(basket) # создать множество без дубликатов349>>> fruit350{'orange', 'pear', 'apple', 'banana'}351>>> fruit = {'orange', 'apple'} # синтаксис {} эквивалентен [] для списков352>>> fruit353{'orange', 'apple'}354>>> 'orange' in fruit # быстрая проверка принадлежности355True356>>> 'crabgrass' in fruit357False358359>>> # Демонстрация операций над множествами с уникальными буквами из двух слов360...361>>> a = set('abracadabra')362>>> b = set('alacazam')363>>> a # уникальные буквы в a364{'a', 'r', 'b', 'c', 'd'}365>>> a - b # буквы, которые есть в a, но нет в b366{'r', 'd', 'b'}367>>> a | b # Буквы из a или b368{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}369>>> a & b # буквы, которые есть и в a, и в b370{'a', 'c'}371>>> a ^ b # буквы, которые есть в a или в b, но не в обоих372{'r', 'd', 'b', 'm', 'z', 'l'}373```374375Как и для списков, существует синтаксис включения множества:376377```python378>>> a = {x for x in 'abracadabra' if x not in 'abc'}379>>> a380{'r', 'd'}381```382383## Словари384385Ещё одним полезным типом данных, встроенным в Python, является *словарь* (см. [*Типы отображений – dict*](https://python-all.ru/3.0/library/stdtypes.html#typesmapping)). В других языках словари иногда называются «ассоциативными запоминающими устройствами» или «ассоциативными массивами». В отличие от последовательностей, которые индексируются диапазоном чисел, словари индексируются *ключами*, которые могут быть любого неизменяемого типа; строки и числа всегда могут быть ключами. Кортежи могут использоваться как ключи, если они содержат только строки, числа или кортежи; если кортеж содержит любой изменяемый объект прямо или косвенно, он не может быть использован как ключ. Списки нельзя использовать как ключи, поскольку списки можно изменять на месте с помощью присваиваний по индексу, срезу или методов, таких как `append()` и `extend()`.386387Словарь лучше всего представлять как неупорядоченное множество пар *ключ: значение*, при этом ключи должны быть уникальными (в пределах одного словаря). Пара фигурных скобок создает пустой словарь: `{}`. Размещение внутри скобок списка пар ключ:значение, разделенных запятыми, добавляет начальные пары ключ:значение в словарь; так же словари отображаются при выводе.388389Основные операции над словарём – это сохранение значения по некоторому ключу и извлечение значения по заданному ключу. Также можно удалить пару ключ:значение с помощью `del`. Если сохранить значение по уже используемому ключу, старое значение, связанное с этим ключом, будет забыто. Извлечение значения по несуществующему ключу является ошибкой.390391Применение `list(d.keys())` к словарю возвращает список всех ключей, используемых в словаре, в произвольном порядке (если нужна сортировка, просто примените функцию [`sorted()`](https://python-all.ru/3.0/library/functions.html#sorted)). Чтобы проверить, есть ли конкретный ключ в словаре, используйте ключевое слово [`in`](https://python-all.ru/3.0/reference/expressions.html#in).392393Вот небольшой пример использования словаря:394395```python396>>> tel = {'jack': 4098, 'sape': 4139}397>>> tel['guido'] = 4127398>>> tel399{'sape': 4139, 'guido': 4127, 'jack': 4098}400>>> tel['jack']4014098402>>> del tel['sape']403>>> tel['irv'] = 4127404>>> tel405{'guido': 4127, 'irv': 4127, 'jack': 4098}406>>> list(tel.keys())407['irv', 'guido', 'jack']408>>> sorted(tel.keys())409['guido', 'irv', 'jack']410>>> 'guido' in tel411True412>>> 'jack' not in tel413False414```415416Конструктор [`dict()`](https://python-all.ru/3.0/library/stdtypes.html#dict) строит словари напрямую из списков пар «ключ-значение», хранящихся в виде кортежей. Если пары образуют шаблон, списковые включения могут компактно задать список пар «ключ-значение».417418```python419>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])420{'sape': 4139, 'jack': 4098, 'guido': 4127}421```422423Кроме того, словарные включения можно использовать для создания словарей из произвольных выражений ключа и значения:424425```python426>>> {x: x**2 for x in (2, 4, 6)}427{2: 4, 4: 16, 6: 36}428```429430Когда ключи являются простыми строками, иногда проще указать пары с помощью именованных аргументов:431432```python433>>> dict(sape=4139, guido=4127, jack=4098)434{'sape': 4139, 'jack': 4098, 'guido': 4127}435```436437## Приёмы организации циклов438439При переборе словарей ключ и соответствующее значение можно получить одновременно с помощью метода `items()`.440441```python442>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}443>>> for k, v in knights.items():444... print(k, v)445...446gallahad the pure447robin the brave448```449450При переборе последовательности индекс позиции и соответствующее значение можно получить одновременно с помощью функции [`enumerate()`](https://python-all.ru/3.0/library/functions.html#enumerate).451452```python453>>> for i, v in enumerate(['tic', 'tac', 'toe']):454... print(i, v)455...4560 tic4571 tac4582 toe459```460461Для одновременного перебора двух или более последовательностей элементы можно объединить в пары с помощью функции [`zip()`](https://python-all.ru/3.0/library/functions.html#zip).462463```python464>>> questions = ['name', 'quest', 'favorite color']465>>> answers = ['lancelot', 'the holy grail', 'blue']466>>> for q, a in zip(questions, answers):467... print('What is your {0}? It is {1}.'.format(q, a))468...469What is your name? It is lancelot.470What is your quest? It is the holy grail.471What is your favorite color? It is blue.472```473474Чтобы перебрать последовательность в обратном порядке, сначала укажите последовательность в прямом порядке, а затем вызовите функцию [`reversed()`](https://python-all.ru/3.0/library/functions.html#reversed).475476```python477>>> for i in reversed(range(1, 10, 2)):478... print(i)479...48094817482548334841485```486487Чтобы перебрать последовательность в отсортированном порядке, используйте функцию [`sorted()`](https://python-all.ru/3.0/library/functions.html#sorted), которая возвращает новый отсортированный список, не изменяя исходный.488489```python490>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']491>>> for f in sorted(set(basket)):492... print(f)493...494apple495banana496orange497pear498```499500## Подробнее об условиях501502Условия, используемые в операторах `while` и `if`, могут содержать любые операторы, а не только сравнения.503504Операторы сравнения `in` и `not in` проверяют, встречается ли значение в последовательности (или не встречается). Операторы `is` и `is not` сравнивают, являются ли два объекта действительно одним и тем же объектом; это важно только для изменяемых объектов, таких как списки. Все операторы сравнения имеют одинаковый приоритет, который ниже приоритета всех числовых операторов.505506Сравнения могут быть объединены в цепочку. Например, `a < b == c` проверяет, `a` меньше ли `b` и, более того, `b` равно `c`.507508Сравнения могут объединяться с помощью логических операторов `and` и `or`, а результат сравнения (или любого другого логического выражения) может быть инвертирован с помощью `not`. Эти операторы имеют более низкий приоритет, чем операторы сравнения; среди них `not` имеет самый высокий приоритет, а `or` – самый низкий, так что `A and not B or C` эквивалентно `(A and (not B)) or C`. Как всегда, для выражения желаемой группировки можно использовать круглые скобки.509510Логические операторы `and` и `or` являются так называемыми *short-circuit* операторами: их аргументы вычисляются слева направо, и вычисление прекращается, как только результат становится определённым. Например, если `A` и `C` истинны, а `B` ложно, то `A and B and C` не вычисляет выражение `C`. При использовании в качестве общего значения, а не логического, возвращаемым значением оператора короткого замыкания является последний вычисленный аргумент.511512Результат сравнения или другого логического выражения можно присвоить переменной. Например,513514```python515>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'516>>> non_null = string1 or string2 or string3517>>> non_null518'Trondheim'519```520521В Python, в отличие от C, присваивание не может использоваться внутри выражений. Программисты на C могут ворчать по этому поводу, но это позволяет избежать распространённого класса проблем, встречающихся в программах на C: ввод `=` в выражении, когда подразумевался `==`.522523## Сравнение последовательностей и других типов524525Объекты-последовательности можно сравнивать с другими объектами того же типа последовательности. Сравнение использует *лексикографический* порядок: сначала сравниваются первые два элемента, и если они различаются, это определяет результат сравнения; если они равны, сравниваются следующие два элемента, и так далее, пока одна из последовательностей не закончится. Если два сравниваемых элемента сами являются последовательностями того же типа, лексикографическое сравнение выполняется рекурсивно. Если все элементы двух последовательностей равны, последовательности считаются равными. Если одна последовательность является начальной подпоследовательностью другой, более короткая последовательность считается меньшей. Лексикографический порядок для строк использует порядок ASCII для отдельных символов. Несколько примеров сравнения последовательностей одного типа:526527```python528(1, 2, 3) < (1, 2, 4)529[1, 2, 3] < [1, 2, 4]530'ABC' < 'C' < 'Pascal' < 'Python'531(1, 2, 3, 4) < (1, 2, 4)532(1, 2) < (1, 2, -1)533(1, 2, 3) == (1.0, 2.0, 3.0)534(1, 2, ('aa', 'ab')) < (1, 2, ('abc', 'a'), 4)535```536537Обратите внимание, что сравнение объектов разных типов с помощью `<` или `>` допустимо при условии, что объекты имеют соответствующие методы сравнения. Например, смешанные числовые типы сравниваются по их числовому значению, поэтому 0 равно 0.0 и т.д. В противном случае, вместо того чтобы давать произвольный порядок, интерпретатор вызовет исключение [`TypeError`](https://python-all.ru/3.0/library/exceptions.html#exceptions.TypeError).538