Vrei să-ți extinzi arsenalul de programare cu structuri de date? Fă primii pași astăzi explorând structurile de date în Python.
Când înveți un nou limbaj de programare, este crucial să înțelegi tipurile de date fundamentale și structurile de date predefinite pe care limbajul le oferă. În acest ghid dedicat structurilor de date în Python, vom explora:
- beneficiile utilizării structurilor de date
- structurile de date native în Python, incluzând liste, tupluri, dicționare și seturi
- implementările tipurilor abstracte de date, cum ar fi stive și cozi.
Să începem!
De ce sunt importante structurile de date?
Înainte de a examina diversele structuri de date, să vedem cum utilizarea acestora poate aduce avantaje:
- Procesarea eficientă a datelor: Alegerea structurii de date potrivite optimizează procesarea datelor. De exemplu, dacă ai nevoie să stochezi o colecție de elemente de același tip, cu acces rapid și conexiuni strânse, un array poate fi ideal.
- Gestionarea optimă a memoriei: În proiecte ample, o structură de date poate fi mai eficientă în consumul de memorie decât alta pentru aceleași date. De exemplu, în Python, atât listele, cât și tuplurile pot reține colecții de date de același tip sau diferite. Dacă știi că nu vei modifica colecția, un tuplu, care folosește mai puțină memorie decât o listă, este preferabil.
- Cod mai bine structurat: Folosirea structurii de date corespunzătoare pentru o anumită funcție face codul mai clar și mai ușor de înțeles. Alți programatori care citesc codul tău se vor aștepta să folosești anumite structuri de date, în funcție de comportamentul dorit. De exemplu, pentru o mapare cheie-valoare cu acces și inserare rapidă, un dicționar este alegerea ideală.
Liste
Listele sunt structurile de date de bază în Python, perfecte pentru a crea array-uri dinamice, de la interviuri de codare la aplicații zilnice.
Listele Python sunt containere mutabile și dinamice, permițându-ți să adaugi și să ștergi elemente direct, fără a crea copii.
Când folosești liste Python:
- Accesarea unui element la un anumit index este o operație rapidă, cu timp constant.
- Adăugarea unui element la finalul listei este, de asemenea, o operație rapidă, cu timp constant.
- Inserarea unui element la o anumită poziție este o operație mai lentă, cu timp liniar.
Există un set de metode pentru liste care ne ajută să efectuăm eficient operații comune. Următorul cod demonstrează cum să realizezi aceste operații pe o listă exemplificativă:
>>> 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]
Listele Python acceptă, de asemenea, slicing și testarea apartenenței folosind operatorul `in`:
>>> nums[1:4] [5, 4, 3] >>> 3 in nums True
Structura de date listă este nu numai flexibilă și ușoară, ci permite și stocarea de elemente de diverse tipuri. Python oferă și o structură de date dedicată array-urilor, pentru stocarea eficientă a elementelor de același tip. Vom explora acest aspect mai târziu în acest ghid.
Tupluri
Tuplurile sunt o altă structură de date încorporată populară în Python. Asemenea listelor, le poți accesa rapid folosind indici și le poți slice. Dar, fiind imuabile, nu le poți modifica direct. Următorul cod ilustrează aceste caracteristici cu un tuplu numeric:
>>> 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
Așadar, dacă dorești o colecție imuabilă și eficientă, ar trebui să iei în considerare utilizarea unui tuplu. Pentru o colecție care trebuie modificată, este preferabilă o listă.
📋 Descoperă mai multe despre similaritățile și diferențele dintre listele și tuplurile din Python.
Array-uri
Array-urile sunt structuri de date mai puțin cunoscute în Python. Ele sunt similare listelor în ceea ce privește operațiile suportate, cum ar fi accesarea rapidă a elementelor și inserarea mai lentă la o anumită poziție.
Totuși, principalul element de diferențiere este că array-urile stochează doar elemente de același tip de date, fiind astfel mai compacte și mai eficiente din punct de vedere al memoriei.
Pentru a crea un array, putem folosi constructorul `array()` din modulul încorporat `array`. Constructorul `array()` primește un șir ce indică tipul elementelor și elementele în sine. Aici, creăm `nums_f`, un array de numere în virgulă mobilă:
>>> 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])
Poți accesa elementele unui array similar cu listele Python:
>>> nums_f[0] 1.5
Array-urile sunt modificabile, așa că le poți schimba elementele:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Dar nu poți schimba tipul de date al unui element:
>>> nums_f[0]='zero' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must be real number, not str
Șiruri de caractere
În Python, șirurile sunt colecții imuabile de caractere Unicode. Spre deosebire de limbaje ca C, Python nu are un tip de date separat pentru caractere. Astfel, un caracter este de fapt un șir de lungime unu.
Așa cum am menționat, șirul este imuabil:
>>> 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
Șirurile Python permit slicing și oferă metode pentru formatare. Iată câteva exemple:
>>> str_1[1:4] 'yth' >>> str_1.title() 'Python' >>> str_1.upper() 'PYTHON' >>> str_1.swapcase() 'PYTHON'
⚠ Trebuie reținut că operațiile de mai sus returnează o copie a șirului, fără a-l modifica pe cel original. Dacă te interesează mai mult, poți consulta un ghid despre operații cu șiruri în Python.
Seturi
În Python, seturile sunt colecții de elemente unice și hash-abile. Poți efectua operații comune cu seturi, cum ar fi reuniunea, intersecția și diferența:
>>> 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}
Seturile sunt modificabile implicit, astfel încât poți adăuga și elimina elemente:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Vezi Seturi în Python: un ghid complet cu exemple de cod
FrozenSets
Pentru seturi imuabile, se folosesc frozen sets. Poți crea un frozen set dintr-un set obișnuit sau alte iterabile.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})
Întrucât `frozenset_1` este un set înghețat, vom primi erori dacă încercăm să adăugăm elemente (sau să-l modificăm în alt mod):
>>> frozenset_1.add(15) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'frozenset' object has no attribute 'add'
Dicționare
Un dicționar Python funcționează similar cu o hartă hash. Este folosit pentru a stoca perechi cheie-valoare. Cheile unui dicționar trebuie să fie hash-abile, adică valoarea hash a obiectului nu trebuie să se schimbe.
Poți accesa rapid valorile folosind cheile, poți adăuga elemente noi și poți șterge elemente existente. Există metode dedicate dicționarelor pentru aceste operații.
>>> 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
Deși un dicționar Python oferă maparea cheie-valoare, el este în mod implicit o structură de date neordonată. Începând cu Python 3.7, ordinea de inserare a elementelor este păstrată. Totuși, poți face acest lucru mai explicit folosind `OrderedDict` din modulul `collections`.
După cum se vede, un `OrderedDict` păstrează ordinea cheilor:
>>> 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
Erorile de cheie (`KeyError`) sunt frecvente atunci când lucrezi cu dicționare în Python. Dacă încerci să accesezi o cheie care nu a fost adăugată în dicționar, vei întâlni această excepție.
Dar folosind `defaultdict` din modulul `collections`, poți gestiona aceste situații direct. Când încerci să accesezi o cheie inexistentă, aceasta este adăugată și inițializată cu valorile implicite specificate de funcția implicită.
>>> from collections import defaultdict >>> prices = defaultdict(int) >>> prices['carrots'] 0
Stive
Stiva este o structură de date de tipul ultimul-intrat-primul-ieșit (LIFO). Operațiile pe care le putem efectua pe o stivă sunt:
- Adăugarea elementelor în vârful stivei: operația `push`
- Îndepărtarea elementelor din vârful stivei: operația `pop`
Un exemplu care ilustrează cum funcționează operațiile `push` și `pop`:
Cum să implementezi o stivă folosind o listă
În Python, putem implementa o stivă folosind o listă Python.
Operația pe listă Operația echivalentă pentru stivă Împingerea în stivă Adăugarea la finalul listei folosind metoda `append()` Extragerea din stivă Îndepărtarea și returnarea ultimului element folosind metoda `pop()`
Următorul cod arată cum putem simula comportamentul unei stive folosind o listă 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
Cum să implementezi o stivă folosind un Deque
O altă metodă de a implementa o stivă este folosind `deque` din modulul `collections`. `Deque` înseamnă coadă cu două capete și permite adăugarea și eliminarea elementelor de la ambele capete.
Pentru a simula o stivă, putem:
- adăuga elemente la sfârșitul cozi folosind `append()` și
- îndepărta ultimul element adăugat folosind `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
Cozi
Coada este o structură de date de tipul primul-intrat-primul-ieșit (FIFO). Elementele sunt adăugate la sfârșitul cozii și sunt eliminate de la început, după cum urmează:
Putem implementa o coadă folosind `deque`:
- adăugând elemente la sfârșitul cozii folosind `append()`
- utilizând metoda `popleft()` pentru a elimina elementul de la începutul cozii
>>> from collections import deque >>> q = deque() >>> q.append(4) >>> q.append(3) >>> q.append(7) >>> q.append(2) >>> q.append(9) >>> q.popleft() 4
Heap-uri
În această secțiune, vom discuta despre heap-urile binare, concentrându-ne pe min-heap-uri.
Un min-heap este un arbore binar complet, unde fiecare nod este mai mic decât copiii săi.
- Un arbore binar este o structură de date arborescentă unde fiecare nod are cel mult doi copii.
- Termenul complet înseamnă că arborele este complet umplut, cu excepția, poate, a ultimului nivel. Dacă ultimul nivel este parțial umplut, acesta este umplut de la stânga la dreapta.
Întrucât fiecare nod are maxim doi copii și respectă proprietatea că este mai mic decât copiii săi, rădăcina unui min-heap va fi elementul minim.
Iată un exemplu de min-heap:
În Python, modulul `heapq` ne ajută să construim heap-uri și să efectuăm operații asupra lor. Să importăm funcțiile necesare din `heapq`:
>>> from heapq import heapify, heappush, heappop
Dacă ai o listă sau un alt iterabil, poți construi un heap din ea apelând `heapify()`:
>>> nums = [11,8,12,3,7,9,10] >>> heapify(nums)
Poți accesa primul element pentru a verifica dacă este elementul minim:
>>> nums[0] 3
Dacă inserezi un element în heap, nodurile vor fi rearanjate pentru a respecta proprietatea min-heap.
>>> heappush(nums,1)
Deoarece am inserat 1 (1 < 3), vedem că `nums[0]` returnează 1, care este acum elementul minim (și nodul rădăcină).
>>> nums[0] 1
Poți elimina elemente din min-heap apelând funcția `heappop()`, după cum se arată:
>>> while nums: ... print(heappop(nums)) ...
# Output 1 3 7 8 9 10 11 12
Max Heaps în Python
Acum că știi despre min-heap-uri, poți ghici cum implementăm max-heap-uri?
Putem transforma o implementare de min-heap într-una de max-heap înmulțind fiecare număr cu -1. Numerele negative aranjate într-un min-heap sunt echivalente cu numerele originale aranjate într-un max-heap.
În implementarea Python, putem înmulți elementele cu -1 când le adăugăm în heap folosind `heappush()`:
>>> maxHeap = [] >>> heappush(maxHeap,-2) >>> heappush(maxHeap,-5) >>> heappush(maxHeap,-7)
Nodul rădăcină — înmulțit cu -1 — va fi elementul maxim.
>>> -1*maxHeap[0] 7
Când elimini elemente din heap, folosește `heappop()` și înmulțește cu -1 pentru a obține valoarea inițială:
>>> while maxHeap: ... print(-1*heappop(maxHeap)) ...
# Output 7 5 2
Cozi de prioritate
Să încheiem discuția învățând despre cozile de prioritate în Python.
Într-o coadă obișnuită, elementele sunt eliminate în ordinea în care au fost introduse. O coadă de prioritate, în schimb, servește elementele în funcție de prioritate – un aspect util pentru aplicații precum programarea. Astfel, elementul cu cea mai mare prioritate este returnat în orice moment.
Putem folosi chei pentru a defini prioritatea. Aici vom folosi valori numerice pentru chei.
Cum să implementezi cozi de prioritate folosind Heapq
Iată implementarea unei cozi de prioritate folosind `heapq` și o listă Python:
>>> from heapq import heappush,heappop >>> pq = [] >>> heappush(pq,(2,'write')) >>> heappush(pq,(1,'read')) >>> heappush(pq,(3,'code')) >>> while pq: ... print(heappop(pq)) ...
La eliminarea elementelor, coada va servi mai întâi elementul cu prioritatea cea mai mare (1, „read”), urmat de (2, „write”) și apoi (3, „code”).
# Output (1, 'read') (2, 'write') (3, 'code')
Cum să implementezi cozi de prioritate folosind PriorityQueue
Pentru a implementa o coadă de prioritate, putem folosi și clasa `PriorityQueue` din modulul `queue`. Aceasta folosește intern un heap.
Iată implementarea echivalentă a cozii de prioritate folosind `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')
Rezumat
În acest tutorial, ai învățat despre diversele structuri de date încorporate în Python. Am analizat operațiile suportate de aceste structuri și metodele încorporate pentru a le realiza.
Apoi, am trecut în revistă și alte structuri de date, cum ar fi stivele, cozile și cozile de prioritate – și implementările lor în Python, folosind funcționalități din modulul `collections`.
Următorul pas este să explorezi lista de proiecte Python pentru începători.