Підручник мови Python/Структури даних

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

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

Докладніше про списки

Спиcкові типи даних мають і інші методи. Нижче подано всі методи спискових об'єктів:

append(x)

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

extend(L)

Розширює список шляхом додання всіх елементів до даного списку; еквівалентно виразу a[len(a):] = L.

insert(i, x)

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

remove(x)

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

pop([i])

Видаляє елемент із заданої позиції та повертає його. Якщо індекс не вказано, a.pop() видадяє і повертає останній елемент списку. (Квадратні дужки навколо i у прототипі методу вказують на те, що параметр не є обов'язковим, а не на те, що квадратні дужки потрібно ввести у вказаній позиції. Ця нотація доволі часто зустрічається у "Довіднику з мови Python".

index(x)

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

count(x)

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

sort()

Впорядковує елементи списку (на місці).

reverse()

Організовує елементи в зворотньому порядку (на місці).

Ось приклад, що використовує більшість спискових методів:

>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]

Використання списку як стека (магазина)

Спискові методи дозволяють у доволі простий спосіб використання списків як стека, де перший елемент, що додається, першим і знімається ("останнім ввійшов, першим вийшов"). Щоб додати новий елемент на вершину стека, слід використовувати метод append(). Щоб видалити елемент з вершини стека, слід використовувати метод pop() без задання індексу. Наприклад:

>>> 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]

Використання списку як черги

Списки також зручно використовувати як черги (queue), де перший елемент, що додано, знімається першим ("першим ввійшов, першим вийшов"). Щоб додати елемент в кінець черги, використовуйте append(). Щоб видалити елемент з початку черги — використовуйте pop() з індексом 0. Наприклад:

>>> queue = ["Eric", "John", "Michael"]
>>> queue.append("Terry") # Terry arrives
>>> queue.append("Graham") # Graham arrives
>>> queue.pop(0)
'Eric'
>>> queue.pop(0)
'John'
>>> queue
['Michael', 'Terry', 'Graham']

Засоби функціонального програмування

Існують кілька надзвичайно корисних вбудованих функцій для роботи зі списками: filter(), map(), та reduce().

"filter(функція, послідовність)" повертає послідовність (того самого типу, якщо можливо), що складається з тих елементів послідовності, для яких функція(елемент) є істинною.

Наприклад, щоб віднайти прості числа:

>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]

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

>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

map може отримвувати більше ніж одну послідовість; при цьому кількість аргументів функції повинна відповідати кількості послідовностей, а сама функція викликається з відповідним елементом кожної послідовності (або з None, якщо одна послідовність коротша за іншу). Наприклад:

>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]

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

>>> def add(x,y): return x+y
...
>>> reduce(add, range(1, 11))
55

Якщо послідовність має лише один елемент, повертається його значення, якщо ж послідовність пуста — викликається виняток.

Може також передаватися і третій елемент, що задає початкове значення. У цьому випадку початкове значення повертається якщо послідовність — пуста. Сама ж функція застосовується до початкового значення і першого елемента, потім — до результату і другого і т.д. Наприклад:

>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
... 
>>> sum(range(1, 11))
55
>>> sum([])
0

Приклад функції sum(), поданий у цьому прикладі використовувати не слід: обчислення суми є настільки поширеною операцією, що для цього існує вбудована функція sum(послідовність) і діє вона так само, як і подана вище функція. Цю функцію було додано у версії 2.3.

Включення списків

Включення списків (list comprehension) надає можливість створювати списки без застосування функцій map(), filter() та lambda. Визначення списку, що утворюється, часто є набагато "чистішим", ніж створення списків за допомогою зазначених функцій. Кожне включення списку складається з виразу, за яким іде конструкція for, а потім — нуль чи більше конструкцій for чи if. Список, що утворюється, є результатом обчислення виразу в контексті розташованих за ним конструкцій for та if. Якщо обчислення виразу видає кортеж, то вираз повинен бути оточеним дужками.

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec] # помилка — навколо кортежа потрібні дужки
 File "&lt;stdin&gt;", line 1, in ?
 [x, x**2 for x in vec]
            ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Включення списків є набагато гнучкішим за map() і може застосовуватися до функцій, що отримують більш ніж один аргумент, а також до вкладених функцій (nested functions):

>>> [str(round(355/113.0, i)) for i in range(1,6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Оператор del

Видалити елемент з даного списку через посиланя на його індекс можна за допомогою оператора del. Він також може використовуватися для видалення частин списку (що було зроблено раніше шляхом призначення пустого списку частинам, призначеним для видалення). Наприклад:

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

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

>>> del a

Посилання на назву a після цього є помилкою (якщо тільки вона не отримує нове значення (перевизначиться) ). Далі йтиметься і про інші застосування del.

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

Ми бачили, що списки і рядки мають чимало спільних властивостей, зокрема індексацію та операції зрізів (slicing operations). Вони є прикладами типів даних послідовностей. Оскільки Пайтон є мовою, що еволюціонує, інші типи даних, що належать до послідовностей, можуть додатися в майбутньому. Існує також інший тип даних, що належить до послідовностей, — кортеж.

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

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Кортежі можуть також вкладуватися:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

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

Кортежі мають багато застосувань. Наприклад: пара координат (x, y), запис із бази даних тощо. Кортежі, подібно до рядків, є незмінними: приcвоєння нового значення певному елементу кортежа - неможливе (втім, це можна симулювати за допомогою зрізів та конкатенації. Можливо також створити кортежі, що містять змінні об'єкти, такі як списки.

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

>>> empty = ()
>>> singleton = 'hello', # <-- зауважте кінцеву кому
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

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

>>> x, y, z = t

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

При цьому існує певна асиментія: пакування кількох значень завжди створює кортеж, а розпаковування — працює з довільними послідовностями.

Множини

Пайтон також має спеціальний тип даних для множин. Множина (set) — це невпорядкована сукупність неповторюваних елементів. Серед основних застосувань множин є такі як перевірка наявності елемента чи видалення повторюваних елементів. Об'єкти, що виражають множини включають такі математичні операції як об'єднання (union), перетин (intersection), різниця (difference), та симетрична різниця (symmetric difference).

Ось кілька коротких прикладів:

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> fruits = set(basket) # створити множину без повторів
>>> fruits
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruits # швидка перевірка наявності елемента
True
>>> 'crabgrass' in fruits
False

>>> # Ілюструє операції над неповторюваними літерами з двох слів
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a # кількісь неповторюваних літер в a
set(['a', 'r', 'b', 'c', 'd'])
>>> a — b # різниця (літери, що є в a, але не в b)
set(['r', 'd', 'b'])
>>> a | b # об'єднання (літери, що є або в a або в b)
set(['a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'])
>>> a & b # перетин (літери, водночас присутні в a та b)
set(['a', 'c'])
>>> a ^ b # симетрична різниця (літери, присутні або в a або в b, але не в обох одночасно)
set(['r', 'd', 'b', 'm', 'z', 'l'])

Словники

Словник — це ще один корисний тип даних мови Пайтон. Інколи словники можна зустріти в інших мовах під назвою "асоціативна пам'ять" чи "асоціативні масиви". На відміну від послідовностей, що індексуються за допомогою чисел, словники індексуються за допомогою ключів, які можуть належати до будь-якого незмінного типу; рядки і числа завжди можуть бути ключами. Кортежі також можуть бути ключами, якщо вони складаються лише з рядків, чисел чи кортежів. Якщо ж кортеж містить, прямо чи опосередковано, певний змінний об'єкт, то він не може використовуватися як ключ. Використання списків у якості ключів неможливе, тому що списки можуть змінюватися на місці через їхні методи append() та extend(), а також шляхом присвоєння через зрізи та індексацію.

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

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

Метод об'єкта словника keys() повертає список всіх ключів, що використовуються у словнику, у випадковому порядку (якщо їх потрібно впорядкувати, то слід просто застосувати метод sort() для списку ключів). Щоб перевірити, чи присутній певний ключ у словнику, слід використовувати метод словника has_key().

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

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
True

Конструктор dict() створює словники зі списків пар ключ — значення, що задані кортежами. Якщо пари утворюються за певним повторюваним принципом, список ключів та значень може задаватися включеними списками:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>>> dict([(x, x**2) for x in vec])
{2: 4, 4: 16, 6: 36}

Далі у цьому підручнику ми познайомимося з конструкцією генератор, яка навіть краще підходить для задання пар ключ — значення для конструктора dict().

Способи перебору

При переборі значень словників, ключі та відповідні значення можуть отримуватися за допомогою методу iteritems():

>>> knights = {'Ґаллагад': 'Чистий', 'Робін': 'Хоробрий'}
>>> for k, v in knights.iteritems():
...     print k, v
...
Ґаллагад Чистий
Робін Хоробрий

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

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

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

>>> questions = ["ім'я", 'пошук', 'колір']
>>> answers = ['Ланселот', 'святий Ґрааль', 'блакитний']
>>> for q, a in zip(questions, answers):
...     print '%s? %s' % (q, a)
... 
ім'я? Ланселот
пошук? святий Ґрааль
колір? блакитний

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

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

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

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

Докладніше про умови

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

Оператори порівняння in та not in перевіряють, чи присутній (або чи відсутній) певний елемент у послідовності. Оператори is та is not порівнюють, чи два об'єкти є насправді тим самим об'єктом; це має значення лише для змінних об'єктів, скажімо, списків. Усі оператори порівняння мають однаковий пріоритет операцій, який є нижчим ніж у всіх числових операторів.

Порівняння можуть накопичуватися. Наприклад, 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 — це так звані оператори короткого замкнення (short-circuit operators): їхні аргументи обчислюються зліва направо і обчислення зупиняється як тільки стає відомим результат. Наприклад, якщо 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'

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

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

Об'єкти послідовностей можуть порівнюватися з іншими об'єктами, що належать до того самого типу послідовності. Порівняння робиться шляхом лексикографічного впорядкування: спочатку порівнюються перші два елементи, і якщо вони різняться, то це і визначає результат порівняння, якщо ж ні — то порівнюються наступні два елементи, і так далі аж до кінця послідовності. Якщо два елементи, що порівнюються, є в свою чергу послідовностями одного типу, то лексикографічне порівняння продовжується рекурсивно. Якщо всі елементи послідовностей однакові, то і самі послідовності вважаються однаковими. Якщо одна з послідовностей є початком іншої, то коротша послідовність і є меншою. Лексикографічне впорядкування відбувається на основі впорядкування кодування ASCII для окремих символів. Ось окремі приклади порівняння однакових за типом послідовностей:

(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)

Зауважте, що порівняння різнотипних об'єктів дозволяється. Результат детермінований, але довільний: типи впорядковуються за назвою. Таким чином, список (list) завжди менший за рядок (string), що завжди менший за кортеж (tuple) тощо. Змішані числові величини порівнюються відповідно до їхнього значення, отже 0 дорівнює 0.0 і т.д. (Зауваження: не варто покладатися на правила порівняння різнотипних об'єктів, тому що ці правила можуть змінитися в наступних версіях мови).