5. Структури даних

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

5.1. Більше про списки

Тип даних список має ще кілька методів. Ось усі методи об’єктів типу список:

list.append(x)

Додати елемент у кінець списку. Еквівалент a[len(a):] = [x].

list.extend(iterable)

Розширити список, додавши всі елементи з iterable. Еквівалент a[len(a):] = iterable.

list.insert(i, x)

Вставте елемент у задану позицію. Перший аргумент — це індекс елемента, перед яким потрібно вставити, тому a.insert(0, x) вставляє на початку списку, а a.insert(len(a), x) еквівалентно a.append(x).

list.remove(x)

Видаліть зі списку перший елемент, значення якого дорівнює x. Це викликає ValueError, якщо такого елемента немає.

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

list.clear()

Видалити всі елементи зі списку. Еквівалент del a[:].

list.index(x[, start[, end]])

Повертає індекс від нуля в списку першого елемента, значення якого дорівнює x. Викликає ValueError, якщо такого елемента немає.

Необов’язкові аргументи start і end інтерпретуються так само, як і в нотації фрагментів, і використовуються для обмеження пошуку певною підпослідовністю списку. Повернений індекс обчислюється відносно початку повної послідовності, а не аргументу start.

list.count(x)

Повертає кількість разів x у списку.

list.sort(*, key=None, reverse=False)

Відсортуйте елементи списку за місцем (аргументи можна використовувати для налаштування сортування, див. sorted() для їх пояснення).

list.reverse()

Переверніть елементи списку на місці.

list.copy()

Поверніть мілку копію списку. Еквівалент a[:].

Приклад, який використовує більшість методів списку:

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # Find next banana starting a position 4
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

You might have noticed that methods like insert, remove or sort that only modify the list have no return value printed – they return the default None. 1 This is a design principle for all mutable data structures in Python.

Another thing you might notice is that not all data can be sorted or compared. For instance, [None, 'hello', 10] doesn’t sort because integers can’t be compared to strings and None can’t be compared to other types. Also, there are some types that don’t have a defined ordering relation. For example, 3+4j < 5+7j isn’t a valid comparison.

5.1.1. Використання списків як стеків

The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved («last-in, first-out»). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index. For example:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

5.1.2. Використання списків як черг

Також можна використовувати список як чергу, де перший доданий елемент є першим отриманим елементом («першим увійшов, першим вийшов»); однак списки не ефективні для цієї мети. У той час як додавання та висування з кінця списку є швидкими, виконання вставок або висунення з початку списку відбувається повільно (оскільки всі інші елементи мають бути зміщені на одиницю).

Щоб реалізувати чергу, використовуйте collections.deque, який був розроблений для швидкого додавання та висування з обох кінців. Наприклад:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

5.1.3. Розуміння списку

Розуміння списків забезпечує стислий спосіб створення списків. Загальні застосування полягають у створенні нових списків, де кожен елемент є результатом деяких операцій, застосованих до кожного члена іншої послідовності або ітерації, або створення підпослідовності тих елементів, які задовольняють певну умову.

Наприклад, припустимо, що ми хочемо створити список квадратів, наприклад:

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Зауважте, що це створює (або перезаписує) змінну з назвою x, яка все ще існує після завершення циклу. Ми можемо обчислити список квадратів без побічних ефектів за допомогою:

squares = list(map(lambda x: x**2, range(10)))

або, що еквівалентно:

squares = [x**2 for x in range(10)]

який більш стислий і читабельний.

Розуміння списку складається з дужок, які містять вираз, після якого йде речення for, потім нуль або більше речень for або if. Результатом буде новий список, отриманий в результаті обчислення виразу в контексті речень for і if, які слідують за ним. Наприклад, цей listcomp поєднує елементи двох списків, якщо вони не рівні:

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

і це еквівалентно:

>>> combs = []
>>> for x in [1,2,3]:
...     for y in [3,1,4]:
...         if x != y:
...             combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

Зверніть увагу, що порядок операторів for і if однаковий в обох цих фрагментах.

Якщо вираз є кортежем (наприклад, (x, y) у попередньому прикладі), його потрібно взяти в дужки.

>>> vec = [-4, -2, 0, 2, 4]
>>> # create a new list with the values doubled
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # filter the list to exclude negative numbers
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # apply a function to all the elements
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # call a method on each element
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # create a list of 2-tuples like (number, square)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # the tuple must be parenthesized, otherwise an error is raised
>>> [x, x**2 for x in range(6)]
  File "<stdin>", line 1, in <module>
    [x, x**2 for x in range(6)]
               ^
SyntaxError: invalid syntax
>>> # flatten a list using a listcomp with two 'for'
>>> vec = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in vec for num in elem]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Розуміння списків може містити складні вирази та вкладені функції:

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

5.1.4. Розуміння вкладених списків

Початковим виразом у розуміння списку може бути будь-який довільний вираз, включаючи інший розуміння списку.

Розглянемо наступний приклад матриці 3x4, реалізованої як список із 3 списків довжини 4:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

Наступне включення списку транспонує рядки та стовпці:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

As we saw in the previous section, the nested listcomp is evaluated in the context of the for that follows it, so this example is equivalent to:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

що, у свою чергу, те саме, що:

>>> transposed = []
>>> for i in range(4):
...     # the following 3 lines implement the nested listcomp
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

У реальному світі вам слід віддавати перевагу вбудованим функціям перед складними операторами потоку. Функція zip() чудово впорається з цим випадком використання:

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

Перегляньте Розпакування списків аргументів, щоб дізнатися більше про зірочку в цьому рядку.

5.2. Оператор del

There is a way to remove an item from a list given its index instead of its value: the del statement. This differs from the pop() method which returns a value. The del statement can also be used to remove slices from a list or clear the entire list (which we did earlier by assignment of an empty list to the slice). For example:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

del також можна використовувати для видалення змінних повністю:

>>> del a

Посилання на назву a у подальшому є помилкою (принаймні доти, доки їй не буде присвоєно інше значення). Пізніше ми знайдемо інші способи використання del.

5.3. Кортежі та послідовності

Ми побачили, що списки та рядки мають багато спільних властивостей, таких як операції індексування та нарізки. Це два приклади типів даних sequence (див. Типи послідовностей — list, tuple, range). Оскільки Python є мовою, що розвивається, можна додавати інші типи даних послідовності. Існує ще один стандартний тип даних послідовності: кортеж.

Кортеж складається з кількох значень, розділених комами, наприклад:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
... t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
... v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

Як ви бачите, на виході кортежі завжди взяті в круглі дужки, так що вкладені кортежі інтерпретуються правильно; вони можуть бути введені з круглими дужками або без них, хоча часто дужки все одно необхідні (якщо кортеж є частиною більшого виразу). Неможливо призначити окремі елементи кортежу, однак можна створити кортежі, які містять змінні об’єкти, наприклад списки.

Хоча кортежі можуть здаватися схожими на списки, вони часто використовуються в різних ситуаціях і для різних цілей. Кортежі є immutable і зазвичай містять різнорідну послідовність елементів, доступ до яких здійснюється через розпакування (див. далі в цьому розділі) або індексування (або навіть за атрибутом у випадку namedtuples). Списки є mutable, і їхні елементи, як правило, є однорідними та доступні за допомогою ітерації по списку.

Особливою проблемою є побудова кортежів, що містять 0 або 1 елемент: синтаксис має деякі додаткові примхи для їх врахування. Порожні кортежі будуються за допомогою порожньої пари круглих дужок; кортеж з одним елементом створюється шляхом коми після значення (недостатньо взяти одне значення в дужки). Негарно, але ефективно. Наприклад:

>>> empty = ()
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

Оператор t = 12345, 54321, 'hello!' є прикладом упакування кортежів: значення 12345, 54321 і 'hello!'' упаковуються разом в кортежі. Можлива і зворотна операція:

>>> x, y, z = t

Це називається, доречно, розпакуванням послідовності і працює для будь-якої послідовності в правій частині. Розпакування послідовності вимагає, щоб ліворуч від знака рівності було стільки змінних, скільки елементів у послідовності. Зауважте, що множинне призначення насправді є лише комбінацією упаковки кортежів і розпакування послідовності.

5.4. Набори

Python також містить тип даних для наборів. Набір — це невпорядкована колекція без повторюваних елементів. Основні способи використання включають тестування членства та усунення повторюваних записів. Об’єкти множини також підтримують математичні операції, такі як об’єднання, перетин, різниця та симетрична різниця.

Для створення наборів можна використовувати фігурні дужки або функцію set(). Примітка: щоб створити порожній набір, потрібно використовувати set(), а не {}; останній створює порожній словник, структуру даних, яку ми обговоримо в наступному розділі.

Ось коротка демонстрація:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # letters in a but not in b
{'r', 'd', 'b'}
>>> a | b                              # letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # letters in both a and b
{'a', 'c'}
>>> a ^ b                              # letters in a or b but not both
{'r', 'd', 'b', 'm', 'z', 'l'}

Подібно до списків розуміння, також підтримуються набір розуміння:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

5.5. словники

Another useful data type built into Python is the dictionary (see Типи зіставлення — dict). Dictionaries are sometimes found in other languages as «associative memories» or «associative arrays». Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can’t use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend().

Найкраще думати про словник як про набір пар ключ:значення з вимогою, щоб ключі були унікальними (в межах одного словника). Пара фігурних дужок створює порожній словник: {}. Розміщення розділених комами списку пар ключ:значення в фігурних дужках додає початкові пари ключ:значення до словника; це також спосіб написання словників на виході.

Основними операціями зі словником є збереження значення з деяким ключем і вилучення значення з заданим ключем. Також можна видалити пару ключ:значення за допомогою del. Якщо ви зберігаєте за допомогою ключа, який уже використовується, старе значення, пов’язане з цим ключем, забувається. Видобування значення за допомогою неіснуючого ключа є помилкою.

Виконання list(d) для словника повертає список усіх ключів, використаних у словнику, у порядку вставки (якщо ви хочете, щоб він був відсортований, просто використовуйте sorted(d)). Щоб перевірити, чи є один ключ у словнику, використовуйте ключове слово in.

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

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Конструктор dict() створює словники безпосередньо з послідовностей пар ключ-значення:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'guido': 4127, 'jack': 4098}

Крім того, розуміння dict можна використовувати для створення словників із довільних ключів і виразів значень:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Коли ключі є простими рядками, інколи легше вказати пари за допомогою аргументів ключових слів:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'guido': 4127, 'jack': 4098}

5.6. Техніка циклу

When looping through dictionaries, the key and corresponding value can be retrieved at the same time using the items() method.

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

Під час циклічного перегляду послідовності індекс позиції та відповідне значення можна отримати одночасно за допомогою функції enumerate().

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Щоб перейти до двох або більше послідовностей одночасно, записи можна поєднати з функцією zip().

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

Щоб виконати цикл у зворотному напрямку, спочатку вкажіть послідовність у прямому напрямку, а потім викличте функцію reversed().

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Щоб перейти до послідовності у відсортованому порядку, використовуйте функцію sorted(), яка повертає новий відсортований список, залишаючи джерело без змін.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for i in sorted(basket):
...     print(i)
...
apple
apple
banana
orange
orange
pear

Використання set() у послідовності усуває повторювані елементи. Використання sorted() у поєднанні з set() над послідовністю є ідіоматичним способом проходження унікальних елементів послідовності в порядку сортування.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

Іноді виникає спокуса змінити список, поки ви переглядаєте його; однак часто простіше й безпечніше створити новий список.

>>> import math
>>> raw_data = [56.2, float('NaN'), 51.7, 55.3, 52.5, float('NaN'), 47.8]
>>> filtered_data = []
>>> for value in raw_data:
...     if not math.isnan(value):
...         filtered_data.append(value)
...
>>> filtered_data
[56.2, 51.7, 55.3, 52.5, 47.8]

5.7. Детальніше про умови

Умови, які використовуються в операторах while і if, можуть містити будь-які оператори, а не лише порівняння.

The comparison operators in and not in check whether a value occurs (does not occur) in a sequence. The operators is and is not compare whether two objects are really the same object. All comparison operators have the same priority, which is lower than that of all numerical operators.

Порівняння можуть бути ланцюжками. Наприклад, a < b == c перевіряє, чи a є меншим за b і, крім того, b дорівнює c.

Порівняння можна комбінувати за допомогою логічних операторів and і or, а результат порівняння (або будь-якого іншого логічного виразу) можна заперечувати за допомогою not. Вони мають нижчий пріоритет, ніж оператори порівняння; між ними not має найвищий пріоритет, а or найнижчий, так що A and not B or C еквівалентно (A and (not B)) or C . Як завжди, дужки можна використовувати для вираження бажаної композиції.

Логічні оператори and і or є так званими операторами короткого замикання: їхні аргументи обчислюються зліва направо, і обчислення припиняється, щойно визначається результат. Наприклад, якщо A і C є істинними, B є хибними, A and B and C не обчислює вираз C. Якщо використовується як загальне значення, а не як логічне, значення, що повертається оператором короткого замикання, є останнім обчисленим аргументом.

Змінній можна призначити результат порівняння або інший логічний вираз. Наприклад,

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Зауважте, що в Python, на відміну від C, призначення всередині виразів має виконуватися явно за допомогою оператора walrus :=. Це дозволяє уникнути типових проблем, які виникають у програмах на C: введення = у виразі, коли передбачалося ==.

5.8. Порівняння послідовностей та інших типів

Об’єкти послідовності зазвичай можна порівнювати з іншими об’єктами того самого типу послідовності. Порівняння використовує лексикографічне впорядкування: спочатку порівнюються перші два елементи, і якщо вони відрізняються, це визначає результат порівняння; якщо вони рівні, наступні два елементи порівнюються і так далі, поки будь-яка послідовність не буде вичерпана. Якщо два елементи для порівняння самі є послідовностями одного типу, лексикографічне порівняння виконується рекурсивно. Якщо всі елементи двох послідовностей порівняно однакові, послідовності вважаються рівними. Якщо одна послідовність є початковою підпослідовністю іншої, коротша послідовність є меншою (меншою). Лексикографічне впорядкування для рядків використовує номер кодової точки Unicode для впорядкування окремих символів. Деякі приклади порівнянь між послідовностями одного типу:

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Зауважте, що порівняння об’єктів різних типів за допомогою < or > є законним за умови, що об’єкти мають відповідні методи порівняння. Наприклад, змішані числові типи порівнюються відповідно до їхнього числового значення, тому 0 дорівнює 0,0 тощо. В іншому випадку, замість надання довільного порядку, інтерпретатор викличе виняток TypeError.

Виноски

1

Інші мови можуть повертати змінений об’єкт, що дозволяє об’єднувати методи, наприклад d->insert("a")->remove("b")->sort();.