Doriți să adăugați structuri de date la cutia dvs. de instrumente de programare? Faceți primii pași astăzi învățând despre structurile de date în Python.
Când învățați un nou limbaj de programare, este important să înțelegeți tipurile de date de bază și structurile de date încorporate pe care le acceptă limbajul. În acest ghid despre structurile de date în Python, vom acoperi următoarele:
- avantajele structurilor de date
- structuri de date încorporate în Python, cum ar fi liste, tupluri, dicționare și seturi
- implementări de tipuri de date abstracte, cum ar fi stive și cozi.
Sa incepem!
Cuprins
De ce sunt utile structurile de date?
Înainte de a trece peste diferitele structuri de date, să vedem cum poate fi utilă utilizarea structurilor de date:
- Prelucrare eficientă a datelor: alegerea structurii corecte de date ajută la procesarea datelor mai eficient. De exemplu, dacă trebuie să stocați o colecție de articole de același tip de date – cu timpi de căutare constante și cuplare strânsă – puteți alege o matrice.
- Gestionare mai bună a memoriei: în proiecte mai mari, pentru stocarea acelorași date, o structură de date poate fi mai eficientă în memorie decât alta. De exemplu, în Python, atât listele, cât și tuplurile pot fi utilizate pentru a stoca colecții de date de același tip de date sau diferite. Cu toate acestea, dacă știți că nu trebuie să modificați colecția, puteți alege un tuplu care ocupă relativ mai puțină memorie decât o listă.
- Cod mai organizat: utilizarea structurii de date potrivite pentru o anumită funcționalitate face codul dvs. mai organizat. Alți dezvoltatori care vă citesc codul se vor aștepta să utilizați structuri de date specifice, în funcție de comportamentul dorit. De exemplu: dacă aveți nevoie de o mapare cheie-valoare cu timpi constante de căutare și inserare, puteți stoca datele într-un dicționar.
Liste
Atunci când trebuie să creăm matrice dinamice în Python – de la interviuri de codificare la cazuri de utilizare obișnuite – listele sunt structurile de date de bază.
Listele Python sunt tipuri de date container care sunt mutabile și dinamice, astfel încât să puteți adăuga și elimina elemente dintr-o listă în loc, fără a fi nevoie să creați o copie.
Când utilizați liste Python:
- Indexarea în listă și accesarea unui element la un anumit index este o operație în timp constant.
- Adăugarea unui element la sfârșitul listei este o operație în timp constant.
- Inserarea unui element la un index specific este o operație de timp liniară.
Există un set de metode de listă care ne ajută să îndeplinim sarcini comune în mod eficient. Fragmentul de cod de mai jos arată cum să efectuați aceste operațiuni într-o listă exemplu:
>>> 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, tăierea și testarea apartenenței utilizând în Operator:
>>> nums[1:4] [5, 4, 3] >>> 3 in nums True
Structura datelor din listă nu este doar flexibilă și simplă, dar ne permite și să stocăm elemente de diferite tipuri de date. Python are, de asemenea, o structură de date matrice dedicată pentru elemente de stocare eficiente de același tip de date. Vom afla despre acest lucru mai târziu în acest ghid.
Tupluri
În Python, tuplurile sunt o altă structură de date încorporată populară. Sunt ca listele Python, deoarece le puteți indexa în timp constant și le puteți tăia. Dar sunt imuabile, așa că nu le puteți modifica în loc. Următorul fragment de cod explică cele de mai sus cu un exemplu de 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
Deci, atunci când doriți să creați o colecție imuabilă și să o puteți procesa eficient, ar trebui să luați în considerare utilizarea unui tuplu. Dacă doriți ca colecția să fie mutabilă, preferați să utilizați o listă.
📋 Aflați mai multe despre asemănările și diferențele dintre listele Python și tupluri.
Matrice
Matricele sunt structuri de date mai puțin cunoscute în Python. Ele sunt similare listelor Python în ceea ce privește operațiunile pe care le suportă, cum ar fi indexarea în timp constant și inserarea unui element la un anumit index în timp liniar.
Cu toate acestea, diferența cheie dintre liste și matrice este că matricele stochează elemente de un singur tip de date. Prin urmare, ele sunt strâns cuplate și mai eficiente în memorie.
Pentru a crea o matrice, putem folosi constructorul array() din modulul de matrice încorporat. Constructorul array() preia un șir care specifică tipul de date al elementelor și elementelor. Aici creăm nums_f, o matrice 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])
Puteți indexa într-o matrice (similar listelor Python):
>>> nums_f[0] 1.5
Matricele sunt modificabile, așa că le puteți modifica:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Dar nu puteți modifica un element pentru a fi de alt tip de date:
>>> nums_f[0]='zero' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must be real number, not str
Siruri de caractere
În Python, șirurile sunt colecții imuabile de caractere Unicode. Spre deosebire de limbajele de programare precum C, Python nu are un tip de date dedicat caracterelor. Deci un caracter este, de asemenea, un șir de lungime unu.
După 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 acceptă tăierea șirurilor și un set de metode pentru a le formata. Aici sunt cateva exemple:
>>> str_1[1:4] 'yth' >>> str_1.title() 'Python' >>> str_1.upper() 'PYTHON' >>> str_1.swapcase() 'PYTHON'
⚠ Rețineți, toate operațiunile de mai sus returnează o copie a șirului și nu modifică șirul original. Dacă sunteți interesat, consultați ghidul despre programele Python despre operațiunile cu șiruri.
Seturi
În Python, seturile sunt colecții de articole unice și hashable. Puteți efectua operațiunile comune de set, cum ar fi unirea, 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 în mod implicit, astfel încât să puteți adăuga elemente noi și să le modificați:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Citiți seturi în Python: un ghid complet cu exemple de cod
FrozenSets
Dacă doriți un set imuabil, puteți folosi un set înghețat. Puteți crea un set înghețat din seturi existente sau alte iterabile.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})
Deoarece frozenset_1 este un set înghețat, ne confruntăm cu 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 este similar din punct de vedere funcțional cu o hartă hash. Dicționarele sunt folosite pentru a stoca perechi cheie-valoare. Cheile dicționarului ar trebui să fie hashable. Înseamnă că valoarea hash a obiectului nu se modifică.
Puteți accesa valorile folosind chei, puteți introduce elemente noi și puteți elimina elementele existente în timp constant. Există metode de dicționar pentru a efectua 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ă mapare cheie-valoare, este în mod inerent o structură de date neordonată. Începând cu Python 3.7, ordinea de inserare a elementelor este păstrată. Dar puteți face acest lucru mai explicit folosind OrderedDict din modulul de colecții.
După cum se arată, 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 cheie sunt destul de frecvente atunci când lucrați cu dicționare Python. Ori de câte ori încercați să accesați o cheie care nu a fost adăugată în dicționar, veți întâlni o excepție KeyError.
Dar folosind defaultdict din modulul de colecții, puteți gestiona acest caz în mod nativ. Când încercăm să accesăm o cheie cu care nu este prezentă în dicționar, cheia este adăugată și inițializată cu valorile implicite specificate de fabrica implicită.
>>> from collections import defaultdict >>> prices = defaultdict(int) >>> prices['carrots'] 0
Stive
Stack este o structură de date last-in-first-out (LIFO). Putem efectua următoarele operații pe o stivă:
- Adăugați elemente în partea de sus a stivei: operație de împingere
- Scoateți elemente din partea de sus a stivei: operațiune pop
Un exemplu pentru a ilustra modul în care funcționează operațiunile de push și pop stive:
Cum să implementați o stivă folosind o listă
În Python, putem implementa structura de date a stivei folosind o listă Python.
Operație pe lista StackEquivalent OperationApăsați pentru a stivui topAdăugați la sfârșitul listei folosind metoda append() Scoateți din partea de sus a stivei Îndepărtați și returnați ultimul element folosind metoda pop()
Fragmentul de cod de mai jos arată cum putem emula 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ă implementați o stivă folosind un Deque
O altă metodă de implementare a unei stive este utilizarea deque din modulul de colecții. Deque înseamnă coadă cu două capete și acceptă adăugarea și eliminarea elementelor de la ambele capete.
Pentru a emula stiva, putem:
- adăugați la sfârșitul dequei folosind append() și
- scoateți 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
Cozile
Coada este o structură de date primul-intrat-primul-out (FIFO). Elementele sunt adăugate la sfârșitul cozii și sunt eliminate de la începutul cozii (capătul cozii), după cum se arată:
Putem implementa structura de date a cozii folosind un deque:
- adăugați elemente la sfârșitul cozii folosind append()
- utilizați 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
Grămezi
În această secțiune, vom discuta despre heapurile binare. Ne vom concentra pe grămezi minime.
Un min heap este un arbore binar complet. Să defalcăm ce înseamnă un arbore binar complet:
- Un arbore binar este o structură de date arborescentă în care fiecare nod are cel mult două noduri copil, astfel încât fiecare nod este mai mic decât copilul său.
- 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.
Pentru că fiecare nod are cel mult două noduri copil. Și, de asemenea, satisface proprietatea că este mai mică decât copilul său, rădăcina este elementul minim într-un heap min.
Iată un exemplu min heap:
În Python, modulul heapq ne ajută să construim heap-uri și să efectuăm operațiuni pe heap. Să importăm funcțiile necesare din heapq:
>>> from heapq import heapify, heappush, heappop
Dacă aveți o listă sau un alt iterabil, puteți construi un heap din ea apelând heapify():
>>> nums = [11,8,12,3,7,9,10] >>> heapify(nums)
Puteți indexa primul element pentru a verifica dacă este elementul minim:
>>> nums[0] 3
Acum, dacă inserați un element în heap, nodurile vor fi rearanjate astfel încât să satisfacă proprietatea min heap.
>>> heappush(nums,1)
Pe măsură ce am inserat 1 (1 < 3), vedem că nums[0] returnează 1 care este acum elementul minim (și nodul rădăcină).
>>> nums[0] 1
Puteți elimina elemente din heap-ul min apelând funcția heappop() așa cum se arată:
>>> while nums: ... print(heappop(nums)) ...
# Output 1 3 7 8 9 10 11 12
Max Heaps în Python
Acum că știți despre min. heaps, puteți ghici cum putem implementa max heap?
Ei bine, putem converti o implementare de heap min într-un heap maxim înmulțind fiecare număr cu -1. Numerele negate aranjate într-un heap min este echivalent cu numerele originale aranjate într-un heap maxim.
În implementarea Python, putem înmulți elementele cu -1 atunci când adăugăm un element la 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 eliminați elementele din heap, utilizați heappop() și înmulțiți cu -1 pentru a obține înapoi valoarea inițială:
>>> while maxHeap: ... print(-1*heappop(maxHeap)) ...
# Output 7 5 2
Cozi prioritare
Să încheiem discuția învățând despre structura datelor de cozi prioritare în Python.
Știm: într-o coadă elementele sunt eliminate în aceeași ordine în care intră în coadă. Dar o coadă de prioritate servește elemente după prioritate – foarte utilă pentru aplicații precum programarea. Deci, în orice moment, elementul cu cea mai mare prioritate este returnat.
Putem folosi tastele pentru a defini prioritatea. Aici vom folosi greutăți numerice pentru chei.
Cum să implementați cozile prioritare folosind Heapq
Iată implementarea cozii de prioritate folosind heapq și lista 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 servește mai întâi elementul cu cea mai mare prioritate (1, „citire”), urmat de (2, „scriere”) și apoi (3, „cod”).
# Output (1, 'read') (2, 'write') (3, 'code')
Cum să implementați cozile prioritare folosind PriorityQueue
Pentru a implementa o coadă de prioritate, putem folosi și clasa PriorityQueue din modulul de coadă. Acest lucru folosește și heap intern.
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')
Rezumând
În acest tutorial, ați învățat despre diferitele structuri de date încorporate în Python. Am analizat, de asemenea, diferitele operațiuni susținute de aceste structuri de date – și metodele încorporate pentru a face același lucru.
Apoi, am trecut peste alte structuri de date, cum ar fi stivele, cozile și cozile prioritare – și implementarea lor Python folosind funcționalitatea din modulul de colecții.
Apoi, consultați lista proiectelor Python pentru începători.