Ønsker du å legge til datastrukturer i programmeringsverktøykassen din? Ta de første skrittene i dag ved å lære om datastrukturer i Python.
Når du skal lære et nytt programmeringsspråk, er det viktig å forstå de grunnleggende datatypene og de innebygde datastrukturene som språket støtter. I denne veiledningen om datastrukturer i Python dekker vi følgende:
- fordelene med datastrukturer
- innebygde datastrukturer i Python, for eksempel lister, tupler, ordbøker og sett
- implementeringer av abstrakte datatyper som stabler og køer.
La oss begynne!
Innholdsfortegnelse
Hvorfor er datastrukturer nyttige?
Før vi går gjennom de ulike datastrukturene, la oss se hvordan bruk av datastrukturer kan være nyttig:
- Effektiv databehandling: Å velge riktig datastruktur bidrar til å behandle data mer effektivt. Hvis du for eksempel trenger å lagre en samling elementer av samme datatype – med konstante oppslagstider og tett kobling – kan du velge en matrise.
- Bedre minnehåndtering: I større prosjekter, for å lagre de samme dataene, kan en datastruktur være mer minneeffektiv enn en annen. For eksempel, i Python, kan både lister og tuples brukes til å lagre samlinger av data av samme eller forskjellige datatyper. Men hvis du vet at du ikke trenger å endre samlingen, kan du velge en tuppel som tar opp relativt mindre minne enn en liste.
- Mer organisert kode: Bruk av riktig datastruktur for en bestemt funksjonalitet gjør koden din mer organisert. Andre utviklere som leser koden din vil forvente at du bruker spesifikke datastrukturer avhengig av ønsket oppførsel. For eksempel: hvis du trenger en nøkkelverdi-kartlegging med konstante oppslags- og innsettingstider, kan du lagre dataene i en ordbok.
Lister
Når vi trenger å lage dynamiske matriser i Python – fra kodeintervjuer til vanlige brukstilfeller – er lister de viktigste datastrukturene.
Python-lister er beholderdatatyper som er mutbare og dynamiske, slik at du kan legge til og fjerne elementer fra en liste på plass – uten å måtte lage en kopi.
Når du bruker Python-lister:
- Å indeksere inn i listen og få tilgang til et element ved en bestemt indeks er en konstant tidsoperasjon.
- Å legge til et element på slutten av listen er en konstant tidsoperasjon.
- Å sette inn et element ved en bestemt indeks er en lineær tidsoperasjon.
Det finnes et sett med listemetoder som hjelper oss å utføre vanlige oppgaver effektivt. Kodebiten nedenfor viser hvordan du utfører disse operasjonene på en eksempelliste:
>>> 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-lister støtter også slicing og medlemskapstesting ved å bruke i Operator:
>>> nums[1:4] [5, 4, 3] >>> 3 in nums True
Listedatastrukturen er ikke bare fleksibel og enkel, men lar oss også lagre elementer av forskjellige datatyper. Python har også en dedikert array-datastruktur for effektive lagringselementer av samme datatype. Vi lærer om dette senere i denne veiledningen.
Tuples
I Python er tuples en annen populær innebygd datastruktur. De er som Python-lister ved at du kan indeksere dem på konstant tid og dele dem opp. Men de er uforanderlige, så du kan ikke endre dem på plass. Følgende kodebit forklarer det ovenfor med et eksempel på tall:
>>> 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
Så når du vil lage en uforanderlig samling og kunne behandle den effektivt, bør du vurdere å bruke en tuppel. Hvis du vil at samlingen skal kunne endres, foretrekker du å bruke en liste i stedet.
📋 Lær mer om likhetene og forskjellene mellom Python-lister og tupler.
Matriser
Arrays er mindre kjente datastrukturer i Python. De ligner på Python-lister når det gjelder operasjonene de støtter, for eksempel indeksering i konstant tid og innsetting av et element ved en spesifikk indeks i lineær tid.
Den viktigste forskjellen mellom lister og matriser er imidlertid at matriser lagrer elementer av en enkelt datatype. Derfor er de tett koblet og mer minneeffektive.
For å lage en array kan vi bruke array()-konstruktøren fra den innebygde array-modulen. Array()-konstruktøren tar inn en streng som spesifiserer datatypen til elementene og elementene. Her lager vi nums_f, en rekke flytende kommatall:
>>> 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])
Du kan indeksere til en matrise (ligner på Python-lister):
>>> nums_f[0] 1.5
Matriser kan endres, så du kan endre dem:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Men du kan ikke endre et element til å være av en annen datatype:
>>> nums_f[0]='zero' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must be real number, not str
Strenger
I Python er strenger uforanderlige samlinger av Unicode-tegn. I motsetning til programmeringsspråk som C, har ikke Python en dedikert tegndatatype. Så en karakter er også en streng med lengde en.
Som nevnt er strengen uforanderlig:
>>> 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-strenger støtter strengslicing og et sett med metoder for å formatere dem. Her er noen eksempler:
>>> str_1[1:4] 'yth' >>> str_1.title() 'Python' >>> str_1.upper() 'PYTHON' >>> str_1.swapcase() 'PYTHON'
⚠ Husk at alle operasjonene ovenfor returnerer en kopi av strengen og endrer ikke den originale strengen. Hvis du er interessert, sjekk ut veiledningen om Python-programmer på strengoperasjoner.
Settene
I Python er sett samlinger av unike og hashbare gjenstander. Du kan utføre vanlige settoperasjoner som union, skjæringspunkt og forskjell:
>>> 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}
Sett kan endres som standard, så du kan legge til nye elementer og endre dem:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Les sett i Python: En komplett guide med kodeeksempler
Frosne sett
Hvis du ønsker et uforanderlig sett, kan du bruke et frossent sett. Du kan lage et frosset sett fra eksisterende sett eller andre gjentakbare.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})
Fordi frozenset_1 er et frossen sett, får vi feil hvis vi prøver å legge til elementer (eller på annen måte endre det):
>>> frozenset_1.add(15) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'frozenset' object has no attribute 'add'
Ordbøker
En Python-ordbok ligner funksjonelt på et hash-kart. Ordbøker brukes til å lagre nøkkel-verdi-par. Nøklene til ordboken skal være hashbare. Dette betyr at hash-verdien til objektet ikke endres.
Du kan få tilgang til verdiene ved å bruke nøkler, sette inn nye elementer og fjerne eksisterende elementer på konstant tid. Det finnes ordbokmetoder for å utføre disse operasjonene.
>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}
>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}
>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}
BestiltDict
Selv om en Python-ordbok gir nøkkelverdi-kartlegging, er det iboende en uordnet datastruktur. Siden Python 3.7 er rekkefølgen for innsetting av elementer bevart. Men du kan gjøre dette mer eksplisitt ved å bruke OrderedDict fra samlingsmodulen.
Som vist, bevarer en OrderedDict rekkefølgen på nøklene:
>>> 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
Nøkkelfeil er ganske vanlige når du arbeider med Python-ordbøker. Hver gang du prøver å få tilgang til en nøkkel som ikke er lagt til i ordboken, vil du støte på et KeyError-unntak.
Men ved å bruke defaultdict fra samlingsmodulen kan du håndtere denne saken naturlig. Når vi prøver å få tilgang til en nøkkel som ikke finnes i ordboken, legges nøkkelen til og initialiseres med standardverdiene spesifisert av standardfabrikken.
>>> from collections import defaultdict >>> prices = defaultdict(int) >>> prices['carrots'] 0
Stabler
Stack er en sist-inn-først-ut (LIFO) datastruktur. Vi kan utføre følgende operasjoner på en stabel:
- Legg til elementer på toppen av stabelen: push-operasjon
- Fjern elementer fra toppen av stabelen: pop-operasjon
Et eksempel for å illustrere hvordan stack push og pop-operasjoner fungerer:
Hvordan implementere en stabel ved hjelp av en liste
I Python kan vi implementere stabeldatastrukturen ved å bruke en Python-liste.
Operasjon på StackEquivalent List OperationPush for å stable toppen Legg til på slutten av listen ved hjelp av append()-metodenPopp av stabelen topFjern og returner det siste elementet ved hjelp av pop()-metoden
Kodebiten nedenfor viser hvordan vi kan emulere oppførselen til en stabel ved å bruke en Python-liste:
>>> 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
Hvordan implementere en stabel ved hjelp av en Deque
En annen metode for å implementere en stack er å bruke deque fra samlingsmodulen. Deque står for double-ended queue og støtter tillegg og fjerning av elementer fra begge ender.
For å etterligne stabelen kan vi:
- legge til på slutten av deque ved hjelp av append(), og
- sprett av det sist lagte elementet ved å bruke 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
Køer
Kø er en først-inn-først-ut (FIFO) datastruktur. Elementene legges til på slutten av køen og fjernes fra begynnelsen av køen (hodeenden av køen) som vist:
Vi kan implementere kødatastrukturen ved å bruke en deque:
- legg til elementer på slutten av køen ved å bruke append()
- bruk popleft()-metoden for å fjerne element fra begynnelsen av køen
>>> from collections import deque >>> q = deque() >>> q.append(4) >>> q.append(3) >>> q.append(7) >>> q.append(2) >>> q.append(9) >>> q.popleft() 4
Dynger
I denne delen vil vi diskutere binære hauger. Vi vil fokusere på min hauger.
En min haug er et komplett binært tre. La oss analysere hva et komplett binært tre betyr:
- Et binært tre er en tredatastruktur der hver node har maksimalt to underordnede noder slik at hver node er mindre enn dens underordnede node.
- Begrepet komplett betyr at treet er helt fylt, bortsett fra kanskje det siste nivået. Hvis det siste nivået er delvis fylt, fylles det fra venstre mot høyre.
Fordi hver node har maksimalt to underordnede noder. Og tilfredsstiller også egenskapen at den er mindre enn barnets, roten er minimumselementet i en min haug.
Her er et eksempel på min haug:
I Python hjelper heapq-modulen oss med å konstruere hauger og utføre operasjoner på haugen. La oss importere de nødvendige funksjonene fra heapq:
>>> from heapq import heapify, heappush, heappop
Hvis du har en liste eller en annen iterabel, kan du konstruere en haug fra den ved å kalle heapify():
>>> nums = [11,8,12,3,7,9,10] >>> heapify(nums)
Du kan indeksere det første elementet for å sjekke at det er minimumselementet:
>>> nums[0] 3
Hvis du nå setter inn et element i heapen, vil nodene omorganiseres slik at de tilfredsstiller min heap-egenskapen.
>>> heappush(nums,1)
Når vi satte inn 1 (1 < 3), ser vi at tall[0] returnerer 1 som nå er minimumselementet (og rotnoden).
>>> nums[0] 1
Du kan fjerne elementer fra min-haugen ved å kalle heappop()-funksjonen som vist:
>>> while nums: ... print(heappop(nums)) ...
# Output 1 3 7 8 9 10 11 12
Max Heaps i Python
Nå som du vet om min hauger, kan du gjette hvordan vi kan implementere en maks haug?
Vel, vi kan konvertere en min haug-implementering til en maks haug ved å multiplisere hvert tall med -1. Negerte tall arrangert i en min haug tilsvarer de opprinnelige tallene arrangert i en maks haug.
I Python-implementeringen kan vi multiplisere elementene med -1 når vi legger til et element til haugen ved hjelp av heappush():
>>> maxHeap = [] >>> heappush(maxHeap,-2) >>> heappush(maxHeap,-5) >>> heappush(maxHeap,-7)
Rotnoden – multiplisert med -1 – vil være det maksimale elementet.
>>> -1*maxHeap[0] 7
Når du fjerner elementene fra haugen, bruk heappop() og multipliser med -1 for å få tilbake den opprinnelige verdien:
>>> while maxHeap: ... print(-1*heappop(maxHeap)) ...
# Output 7 5 2
Prioriterte køer
La oss avslutte diskusjonen ved å lære om datastrukturen for prioritert kø i Python.
Vi vet: I en kø fjernes elementene i samme rekkefølge som de kommer inn i køen. Men en prioritert kø serverer elementer etter prioritet – veldig nyttig for programmer som planlegging. Så når som helst blir elementet med høyest prioritet returnert.
Vi kan bruke nøkler til å definere prioritet. Her skal vi bruke numeriske vekter for tastene.
Hvordan implementere prioriterte køer ved hjelp av Heapq
Her er implementeringen av prioritert kø ved bruk av heapq og Python-liste:
>>> from heapq import heappush,heappop >>> pq = [] >>> heappush(pq,(2,'write')) >>> heappush(pq,(1,'read')) >>> heappush(pq,(3,'code')) >>> while pq: ... print(heappop(pq)) ...
Når du fjerner elementer, serverer køen elementet med høyest prioritet (1,’les») først, etterfulgt av (2,’skriv») og deretter (3,’kode»).
# Output (1, 'read') (2, 'write') (3, 'code')
Hvordan implementere Priority Queue ved hjelp av PriorityQueue
For å implementere en prioritetskø kan vi også bruke klassen PriorityQueue fra kømodulen. Dette bruker også heap internt.
Her er den tilsvarende implementeringen av prioritetskøen ved bruk av 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')
Oppsummering
I denne opplæringen lærte du om de ulike innebygde datastrukturene i Python. Vi gikk også gjennom de forskjellige operasjonene som støttes av disse datastrukturene – og de innebygde metodene for å gjøre det samme.
Deretter gikk vi over andre datastrukturer som stabler, køer og prioriterte køer – og deres Python-implementering ved å bruke funksjonalitet fra samlingsmodulen.
Deretter kan du sjekke ut listen over nybegynnervennlige Python-prosjekter.