Хочете додати структури даних до свого інструментарію програмування? Зробіть перші кроки сьогодні, дізнавшись про структури даних у Python.
Коли ви вивчаєте нову мову програмування, важливо розуміти основні типи даних і вбудовані структури даних, які підтримує мова. У цьому посібнику зі структур даних у Python ми розглянемо наступне:
- переваги структур даних
- вбудовані структури даних у Python, такі як списки, кортежі, словники та набори
- реалізації абстрактних типів даних, таких як стеки та черги.
Давайте почнемо!
Чому структури даних корисні?
Перш ніж ми перейдемо до різних структур даних, давайте подивимося, як використання структур даних може бути корисним:
- Ефективна обробка даних: вибір правильної структури даних допомагає ефективніше обробляти дані. Наприклад, якщо вам потрібно зберігати колекцію елементів одного типу даних — із постійним часом пошуку та тісним зв’язком — ви можете вибрати масив.
- Краще керування пам’яттю: у великих проектах для зберігання одних і тих же даних одна структура даних може бути ефективнішою для пам’яті, ніж інша. Наприклад, у Python як списки, так і кортежі можна використовувати для зберігання колекцій даних одного або різних типів даних. Однак, якщо ви знаєте, що вам не потрібно змінювати колекцію, ви можете вибрати кортеж, який займає відносно менше пам’яті, ніж список.
- Більш упорядкований код: використання правильної структури даних для певної функції робить ваш код більш упорядкованим. Інші розробники, які читають ваш код, очікують від вас використання певних структур даних залежно від бажаної поведінки. Наприклад: якщо вам потрібне відображення ключ-значення з постійним часом пошуку та вставки, ви можете зберегти дані в словнику.
списки
Коли нам потрібно створити динамічні масиви в Python — від інтерв’ю з програмуванням до звичайних випадків використання — списки є основними структурами даних.
Списки Python — це контейнерні типи даних, які є змінними та динамічними, тому ви можете додавати та видаляти елементи зі списку на місці — без необхідності створювати копію.
При використанні списків Python:
- Індексування списку та доступ до елемента за певним індексом є операцією постійного часу.
- Додавання елемента в кінець списку є операцією постійного часу.
- Вставлення елемента за певним індексом є лінійною операцією часу.
Існує набір методів списку, які допомагають нам ефективно виконувати типові завдання. Наведений нижче фрагмент коду показує, як виконати ці операції на прикладі списку:
>>> nums = [5,4,3,2] >>> nums.append(7) >>> nums [5, 4, 3, 2, 7] >>> nums.pop() 7 >>> nums [5, 4, 3, 2] >>> nums.insert(0,9) >>> nums [9, 5, 4, 3, 2]
Списки Python також підтримують нарізку та перевірку членства за допомогою оператора in:
>>> nums[1:4] [5, 4, 3] >>> 3 in nums True
Структура даних списку є не тільки гнучкою та простою, але й дозволяє нам зберігати елементи різних типів даних. Python також має спеціальну структуру даних масиву для ефективного зберігання елементів того самого типу даних. Ми дізнаємося про це пізніше в цьому посібнику.
Кортежі
У Python кортежі є ще однією популярною вбудованою структурою даних. Вони схожі на списки Python у тому, що ви можете індексувати їх у постійному часі та розділяти. Але вони незмінні, тому ви не можете змінити їх на місці. Наступний фрагмент коду пояснює вищезазначене за допомогою прикладу кортежу nums:
>>> nums = (5,4,3,2) >>> nums[0] 5 >>> nums[0:2] (5, 4) >>> 5 in nums True >>> nums[0] = 7 # not a valid operation! Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'tuple' object does not support item assignment
Отже, якщо ви хочете створити незмінну колекцію та мати можливість ефективно її обробляти, вам слід розглянути можливість використання кортежу. Якщо ви бажаєте, щоб колекція була змінною, віддайте перевагу списку.
📋 Дізнайтеся більше про подібності та відмінності між списками та кортежами Python.
Масиви
Масиви є менш відомими структурами даних у Python. Вони подібні до списків Python з точки зору операцій, які вони підтримують, таких як індексування в постійному часі та вставка елемента за певним індексом у лінійному часі.
Однак ключова відмінність між списками та масивами полягає в тому, що масиви зберігають елементи одного типу даних. Таким чином, вони тісно пов’язані між собою та мають більшу ефективність пам’яті.
Щоб створити масив, ми можемо використати конструктор array() із вбудованого модуля масиву. Конструктор array() приймає рядок, що визначає тип даних елементів і елементів. Тут ми створюємо nums_f, масив чисел з плаваючою комою:
>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])
Ви можете індексувати в масив (подібно до списків Python):
>>> nums_f[0] 1.5
Масиви є змінними, тому їх можна змінювати:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Але ви не можете змінити тип даних елемента:
>>> nums_f[0]='zero' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must be real number, not str
рядки
У Python рядки є незмінними колекціями символів Unicode. На відміну від таких мов програмування, як C, Python не має спеціального символьного типу даних. Отже, символ також є рядком довжини один.
Як згадувалося, рядок незмінний:
>>> str_1 = 'python' >>> str_1[0] = 'c' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'str' object does not support item assignment
Рядки Python підтримують нарізку рядків і набір методів для їх форматування. Ось кілька прикладів:
>>> str_1[1:4] 'yth' >>> str_1.title() 'Python' >>> str_1.upper() 'PYTHON' >>> str_1.swapcase() 'PYTHON'
⚠ Пам’ятайте, що всі описані вище операції повертають копію рядка і не змінюють вихідний рядок. Якщо вам цікаво, перегляньте посібник із програм Python щодо операцій із рядками.
Набори
У Python набори — це колекції унікальних і хешованих елементів. Ви можете виконувати такі операції з загальними множинами, як об’єднання, перетин і різниця:
>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}
>>> set_1.union(set_2)
{3, 4, 5, 6, 7}
>>> set_1.intersection(set_2)
{4, 7}
>>> set_1.difference(set_2)
{3, 5}
Набори є змінними за замовчуванням, тому ви можете додавати нові елементи та змінювати їх:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Прочитайте набори в Python: повний посібник із прикладами коду
FrozenSets
Якщо вам потрібен незмінний набір, ви можете використовувати заморожений набір. Ви можете створити заморожений набір із існуючих наборів або інших ітерованих елементів.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})
Оскільки frozenset_1 є замороженим набором, ми стикаємося з помилками, якщо намагаємося додати елементи (або змінити його іншим чином):
>>> frozenset_1.add(15) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'frozenset' object has no attribute 'add'
словники
Словник Python функціонально схожий на хеш-карту. Словники використовуються для зберігання пар ключ-значення. Ключі словника повинні хешуватися. Це означає, що хеш-значення об’єкта не змінюється.
Ви можете отримувати доступ до значень за допомогою ключів, вставляти нові елементи та видаляти існуючі елементи в постійний час. Для виконання цих операцій існують словникові методи.
>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}
>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}
>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}
OrderedDict
Хоча словник Python забезпечує відображення ключ-значення, за своєю суттю це невпорядкована структура даних. Починаючи з Python 3.7 порядок вставки елементів зберігається. Але ви можете зробити це більш чітким, використовуючи OrderedDict із модуля колекцій.
Як показано, OrderedDict зберігає порядок ключів:
>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])
Defaultdict
Ключові помилки досить поширені при роботі зі словниками Python. Щоразу, коли ви намагаєтеся отримати доступ до ключа, який не було додано до словника, ви зіткнетеся з винятком KeyError.
Але використовуючи defaultdict з модуля колекцій, ви можете впоратися з цим випадком нативно. Коли ми намагаємося отримати доступ до ключа, якого немає в словнику, ключ додається та ініціалізується значеннями за замовчуванням, визначеними фабрикою за замовчуванням.
>>> from collections import defaultdict >>> prices = defaultdict(int) >>> prices['carrots'] 0
Стеки
Стек — це структура даних за принципом “останній прийшов – перший вийшов” (LIFO). Ми можемо виконувати такі операції зі стеком:
- Додайте елементи на вершину стека: операція push
- Видалення елементів із верхньої частини стека: операція вискакування
Приклад, щоб проілюструвати, як працюють операції надсилання та висунення стека:
Як реалізувати стек за допомогою списку
У Python ми можемо реалізувати структуру даних стека за допомогою списку Python.
Операція зі списком StackEquivalent OperationPush для стека topДодавання в кінець списку за допомогою методу append() Витягнення зі стеку topRemove та повернення останнього елемента за допомогою методу pop()
Наведений нижче фрагмент коду показує, як ми можемо емулювати поведінку стека за допомогою списку Python:
>>> l_stk = [] >>> l_stk.append(4) >>> l_stk.append(3) >>> l_stk.append(7) >>> l_stk.append(2) >>> l_stk.append(9) >>> l_stk [4, 3, 7, 2, 9] >>> l_stk.pop() 9
Як реалізувати стек за допомогою Deque
Інший спосіб реалізації стека — використання deque з модуля collections. Deque означає двосторонню чергу та підтримує додавання та видалення елементів з обох кінців.
Щоб емулювати стек, ми можемо:
- додавати в кінець deque за допомогою append(), і
- витягнути останній доданий елемент за допомогою pop().
>>> from collections import deque >>> stk = deque() >>> stk.append(4) >>> stk.append(3) >>> stk.append(7) >>> stk.append(2) >>> stk.append(9) >>> stk deque([4, 3, 7, 2,9]) >>> stk.pop() 9
Черги
Черга — це структура даних типу FIFO. Елементи додаються в кінець черги та видаляються з початку черги (головного кінця черги), як показано:
Ми можемо реалізувати структуру даних черги за допомогою deque:
- додати елементи в кінець черги за допомогою append()
- використовуйте метод popleft(), щоб видалити елемент із початку черги
>>> from collections import deque >>> q = deque() >>> q.append(4) >>> q.append(3) >>> q.append(7) >>> q.append(2) >>> q.append(9) >>> q.popleft() 4
Купи
У цьому розділі ми обговоримо двійкові купи. Ми зосередимося на міні-купах.
Мінімальна купа — це повне бінарне дерево. Давайте розберемо, що означає повне бінарне дерево:
- Бінарне дерево — це деревоподібна структура даних, де кожен вузол має щонайбільше два дочірніх вузла, так що кожен вузол менший за свого дочірнього.
- Термін завершено означає, що дерево повністю заповнене, за винятком, можливо, останнього рівня. Якщо останній рівень заповнений частково, він заповнюється зліва направо.
Оскільки кожен вузол має не більше двох дочірніх вузлів. А також задовольняє властивість, що він менший за свого дочірнього елемента, корінь є мінімальним елементом у min heap.
Ось приклад мінімальної купи:
У Python модуль heapq допомагає нам створювати купи та виконувати операції над купою. Давайте імпортуємо необхідні функції з heapq:
>>> from heapq import heapify, heappush, heappop
Якщо у вас є список або інший ітерований елемент, ви можете побудувати з нього купу, викликавши heapify():
>>> nums = [11,8,12,3,7,9,10] >>> heapify(nums)
Ви можете проіндексувати перший елемент, щоб переконатися, що це мінімальний елемент:
>>> nums[0] 3
Тепер, якщо ви вставите елемент до купи, вузли будуть переставлені таким чином, щоб вони задовольняли властивість min heap.
>>> heappush(nums,1)
Оскільки ми вставили 1 (1 < 3), ми бачимо, що nums[0] повертає 1, який тепер є мінімальним елементом (і кореневим вузлом).
>>> nums[0] 1
Ви можете видалити елементи з мінімальної купи, викликавши функцію heappop(), як показано:
>>> while nums: ... print(heappop(nums)) ...
# Output 1 3 7 8 9 10 11 12
Макс Хіпс у Python
Тепер, коли ви знаєте про мінімальні купи, чи можете ви здогадатися, як ми можемо реалізувати максимальну купу?
Ну, ми можемо перетворити реалізацію мінімальної купи в максимальну купу, помноживши кожне число на -1. Заперечені числа, розташовані в мінімальній купі, еквівалентні оригінальним числам, розташованим у максимальній купі.
У реалізації Python ми можемо помножити елементи на -1 під час додавання елемента до купи за допомогою heappush():
>>> maxHeap = [] >>> heappush(maxHeap,-2) >>> heappush(maxHeap,-5) >>> heappush(maxHeap,-7)
Кореневий вузол, помножений на -1, буде максимальним елементом.
>>> -1*maxHeap[0] 7
Видаляючи елементи з купи, використовуйте heappop() і помножте на -1, щоб повернути вихідне значення:
>>> while maxHeap: ... print(-1*heappop(maxHeap)) ...
# Output 7 5 2
Пріоритетні черги
Давайте завершимо обговорення, дізнавшись про структуру даних пріоритетної черги в Python.
Ми знаємо: у черзі елементи видаляються в тому ж порядку, в якому вони потрапляють до черги. Але пріоритетна черга обслуговує елементи за пріоритетом, що дуже корисно для таких програм, як планування. Тому в будь-який момент часу повертається елемент із найвищим пріоритетом.
Ми можемо використовувати ключі для визначення пріоритету. Тут ми будемо використовувати числові ваги для ключів.
Як реалізувати пріоритетні черги за допомогою Heapq
Ось реалізація пріоритетної черги за допомогою heapq і списку Python:
>>> from heapq import heappush,heappop >>> pq = [] >>> heappush(pq,(2,'write')) >>> heappush(pq,(1,'read')) >>> heappush(pq,(3,'code')) >>> while pq: ... print(heappop(pq)) ...
Під час видалення елементів черга спочатку обслуговує елемент з найвищим пріоритетом (1, «читання»), потім (2, «запис»), а потім (3, «код»).
# Output (1, 'read') (2, 'write') (3, 'code')
Як реалізувати пріоритетні черги за допомогою PriorityQueue
Щоб реалізувати пріоритетну чергу, ми також можемо використовувати клас PriorityQueue з модуля черги. Це також використовує купу всередині.
Ось еквівалентна реалізація пріоритетної черги з використанням PriorityQueue:
>>> from queue import PriorityQueue >>> pq = PriorityQueue() >>> pq.put((2,'write')) >>> pq.put((1,'read')) >>> pq.put((3,'code')) >>> pq <queue.PriorityQueue object at 0x00BDE730> >>> while not pq.empty(): ... print(pq.get()) ...
# Output (1, 'read') (2, 'write') (3, 'code')
Підводячи підсумки
У цьому посібнику ви дізналися про різноманітні вбудовані структури даних у Python. Ми також ознайомилися з різними операціями, які підтримують ці структури даних, і вбудованими методами для їх виконання.
Потім ми розглянули інші структури даних, такі як стеки, черги та пріоритетні черги, і їх реалізацію на Python, використовуючи функціональні можливості модуля колекцій.
Далі перегляньте список проектів Python, зручних для початківців.