Guide To Queues In Python

Ponovno objavil Platon

Spremljevalci: 0

Predstavitev

Od shranjevanja preprostih celih števil do upravljanja kompleksnih delovnih tokov, podatkovne strukture postavljajo temelje za robustne aplikacije. Med njimi je čakalna vrsta se pogosto pojavi kot intriganten in vseprisoten. Pomislite – a vrsto na banki, čakanje na vrsto pri pultu s hitro hrano ali medpomnjenje nalog v računalniškem sistemu – vsi ti scenariji odmevajo z mehaniko čakalne vrste.

Prva oseba v vrsti je prva postrežena, novi prišleki pa se pridružijo na koncu. To je primer čakalne vrste v resničnem življenju!

Za razvijalce, zlasti v Pythonu, čakalne vrste niso le teoretični konstrukti iz učbenika računalništva. Tvorijo osnovno arhitekturo v številnih aplikacijah. Čakalne vrste igrajo nepogrešljivo vlogo, od upravljanja opravil v tiskalniku do zagotavljanja nemotenega pretoka podatkov v oddajah v živo.

V tem priročniku se bomo poglobili v koncept čakalnih vrst, raziskali njihove značilnosti, aplikacije v resničnem svetu in, kar je najpomembneje, kako jih učinkovito implementirati in uporabljati v Pythonu.

Kaj je struktura podatkov čakalne vrste?

Pri krmarjenju po pokrajini podatkovnih struktur pogosto naletimo na vsebnike, ki imajo različna pravila za vnos in iskanje podatkov. Med temi je čakalna vrsta izstopa po svoji eleganci in naravnosti.

Načelo FIFO

V svojem bistvu je čakalna vrsta linearna podatkovna struktura, ki se drži Prvi vhod, prvi ven (FIFO) načelo. To pomeni, da bo prvi element, dodan v čakalno vrsto, prvi odstranjen. Če ga primerjamo s primerljivim scenarijem: razmislite o vrsti strank pri okencu za vstopnice. Oseba, ki prva pride, prejme svojo vstopnico, vsi naslednji prihodi pa se postavijo na koncu in čakajo, da pridejo na vrsto.

Opomba: Čakalna vrsta ima dva konca – zadaj in spredaj. Sprednja stran označuje, od kod bodo elementi odstranjeni, zadnja pa označuje, od kod bodo dodani novi elementi.

Osnovne operacije čakalne vrste

V vrsti – Dejanje dodajanje element do konca (zadaj) čakalne vrste.
Na vrsti – Dejanje odstranjevanje element iz spredaj čakalne vrste.
Peek ali Front – V mnogih situacijah je koristno samo opazovati sprednji element, ne da bi ga odstranili. Ta operacija nam omogoča prav to.
Je prazno – Operacija, ki pomaga ugotoviti, ali ima čakalna vrsta kakšne elemente. To je lahko ključnega pomena v scenarijih, kjer so dejanja odvisna od čakalne vrste s podatki.

Opomba: Medtem ko imajo nekatere čakalne vrste omejeno velikost (omejene čakalne vrste), se lahko druge potencialno povečajo, dokler sistemski pomnilnik dovoljuje (neomejene čakalne vrste).

Zaradi preprostosti čakalnih vrst in njihovih jasnih pravil delovanja so idealne za različne aplikacije pri razvoju programske opreme, zlasti v scenarijih, ki zahtevajo urejeno in sistematično obdelavo.

Vendar pa je razumevanje teorije le prvi korak. Ko gremo naprej, se bomo poglobili v praktične vidike in ponazorili, kako implementirati čakalne vrste v Python.

Kako implementirati čakalne vrste v Python – Seznami v primerjavi z modulom Deque in Queue

Python s svojo bogato standardno knjižnico in uporabniku prijazno sintakso ponuja več mehanizmov za implementacijo in delo s čakalnimi vrstami. Čeprav vsi služijo temeljnemu namenu upravljanja čakalnih vrst, imajo svoje nianse, prednosti in morebitne pasti. Razčlenimo vsak pristop, ponazorimo njegovo mehaniko in najboljše primere uporabe.

Opomba: Pred izvajanjem operacij vedno preverite stanje svoje čakalne vrste. Na primer, pred odstranitvijo iz vrste preverite, ali je čakalna vrsta prazna, da se izognete napakam. Podobno za omejene čakalne vrste zagotovite, da je dovolj prostora, preden se postavite v čakalno vrsto.

Uporaba seznamov Python za implementacijo čakalnih vrst

Uporaba vgrajenih seznamov Python za implementacijo čakalnih vrst je intuitivna in enostavna. Ni potrebe po zunanjih knjižnicah ali kompleksnih podatkovnih strukturah. Vendar ta pristop morda ne bo učinkovit za velike nabore podatkov. Odstranjevanje elementa z začetka seznama (pop(0)) zahteva linearni čas, kar lahko povzroči težave z delovanjem.

Opomba: Za aplikacije, ki zahtevajo visoko zmogljivost ali tiste, ki se ukvarjajo z veliko količino podatkov, preklopite na collections.deque za konstantno časovno kompleksnost tako za postavljanje v vrsto kot za odstranitev iz vrste.

Začnimo z ustvarjanjem seznama, ki bo predstavljal našo čakalno vrsto:

queue = []

Postopek dodajanja elementov na konec čakalne vrste (postavljanje v čakalno vrsto) ni nič drugega kot njihovo dodajanje na seznam:


queue.append('A')
queue.append('B')
queue.append('C')
print(queue)

Poleg tega je odstranitev elementa s sprednje strani čakalne vrste (odstranitev iz čakalne vrste) enakovredna samo odstranitvi prvega elementa seznama:


queue.pop(0)
print(queue)

Uporaba zbirke.deque za izvajanje čakalnih vrst

Ta pristop je zelo učinkovit, saj deque se izvaja z uporabo a dvojno vezan seznam. Podpira hitre O(1) dodajanja in izpiranja z obeh koncev. Slaba stran tega pristopa je, da je nekoliko manj intuitivno za začetnike.

Najprej bomo uvozili deque predmet iz collections modul in inicializiramo našo čakalno vrsto:

from collections import deque queue = deque()

Zdaj lahko uporabimo append() metoda za postavljanje elementov v čakalno vrsto in popleft() metoda za odstranitev elementov iz čakalne vrste:

Oglejte si naš praktični, praktični vodnik za učenje Gita z najboljšimi praksami, standardi, sprejetimi v panogi, in priloženo goljufijo. Nehajte Googlati ukaze Git in pravzaprav naučiti it!


queue.append('A')
queue.append('B')
queue.append('C')
print(queue) queue.popleft()
print(queue)

Uporaba Pythona čakalna vrsta Modul za izvajanje čakalnih vrst

O queue modul v Pythonovi standardni knjižnici zagotavlja bolj specializiran pristop k upravljanju čakalnih vrst, ki skrbi za različne primere uporabe:

SimpleQueue – Osnovna čakalna vrsta FIFO
LifoQueue – Čakalna vrsta LIFO, v bistvu sklad
PriorityQueue – Elementi so izključeni iz čakalne vrste na podlagi dodeljene prioritete

Opomba: Odločite se za queue modul, ki je zasnovan za navojno. To zagotavlja, da sočasne operacije v čakalni vrsti ne vodijo do nepredvidljivih rezultatov.

Ta pristop je odličen, ker je izrecno zasnovan za operacije v čakalni vrsti. Ampak, če sem popolnoma iskren, je to morda preveč za preproste scenarije.

Zdaj pa začnimo uporabljati queue modul tako, da ga uvozimo v naš projekt:

import queue

Ker implementiramo preprosto čakalno vrsto FIFO, jo bomo inicializirali z uporabo SimpleQueue() konstruktor:

q = queue.SimpleQueue()

Operacije postavljanja v čakalno vrsto in odstranjevanja iz čakalne vrste se izvajajo z uporabo put() in get() metode iz queue modul:


q.put('A')
q.put('B')
q.put('C')
print(q.queue) q.get()
print(q.queue)

Opomba: Operacije v čakalni vrsti lahko sprožijo izjeme, ki lahko motijo tok vaše aplikacije, če jih ne obravnavate. Če želite to preprečiti, zavijte svoje operacije čakalne vrste try-except bloki.

Na primer, ravnajte z queue.Empty izjema pri delu z queue modul:

import queue q = queue.SimpleQueue() try: item = q.get_nowait()
except queue.Empty: print("Queue is empty!")

Katero izvedbo izbrati?

Vaša izbira izvedbe čakalne vrste v Pythonu mora biti usklajena z zahtevami vaše aplikacije. Če obdelujete veliko količino podatkov ali potrebujete optimizirano delovanje, collections.deque je prepričljiva izbira. Vendar pa za večnitne aplikacije ali ko pridejo v poštev prioritete, je queue modul ponuja robustne rešitve. Za hitre skripte ali ko šele začenjate, lahko zadoščajo seznami Python, vendar bodite vedno pozorni na morebitne pasti pri delovanju.

Opomba: Ponovno odkrivanje kolesa z izvajanjem operacij v čakalni vrsti po meri, ko Python že ponuja zmogljive vgrajene rešitve.
Preden oblikujete rešitve po meri, se seznanite z vgrajenimi ponudbami Pythona, kot je deque in queue modul. Pogosteje izpolnjujejo širok spekter zahtev, prihranijo čas in zmanjšajo morebitne napake.

Potopite se globlje: Napredni koncepti čakalnih vrst v Pythonu

Za tiste, ki so dojeli osnovno mehaniko čakalnih vrst in se želijo poglobiti, Python ponuja obilico naprednih konceptov in tehnik za izboljšanje in optimizacijo operacij, ki temeljijo na čakalnih vrstah. Odkrijmo nekaj teh prefinjenih vidikov in vam ponudimo arzenal orodij za reševanje bolj zapletenih scenarijev.

Dvostranske čakalne vrste z deque

Medtem ko smo predhodno raziskovali deque kot čakalna vrsta FIFO podpira tudi operacije LIFO (Last-In-First-Out). Omogoča dodajanje ali izstopanje elementov z obeh koncev s kompleksnostjo O(1):

from collections import deque dq = deque()
dq.appendleft('A') dq.append('B') dq.pop() dq.popleft()

PriorityQueu v akciji

Uporaba preproste čakalne vrste FIFO, ko je vrstni red obdelave odvisen od prioritete, lahko povzroči neučinkovitost ali neželene rezultate, zato, če vaša aplikacija zahteva, da se določeni elementi obdelajo pred drugimi na podlagi nekaterih meril, uporabite PriorityQueue. To zagotavlja, da se elementi obdelujejo glede na njihove nastavljene prioritete.

Oglejte si, kako določamo prioritete za elemente, ki jih dodajamo v čakalno vrsto. To zahteva, da posredujemo tuple kot argument za put() metoda. Torka mora vsebovati prioriteto kot prvi element in dejansko vrednost kot drugi element:

import queue pq = queue.PriorityQueue()
pq.put((2, "Task B"))
pq.put((1, "Task A")) pq.put((3, "Task C")) while not pq.empty(): _, task = pq.get() print(f"Processing: {task}")

To nam bo dalo naslednje:

Processing: Task A
Processing: Task B
Processing: Task C

Upoštevajte, kako smo elemente dodali v drugačnem vrstnem redu, kot je shranjeno v čakalni vrsti. To je zaradi prednostnih nalog, ki smo jih določili v put() pri dodajanju elementov v prednostno čakalno vrsto.

Implementacija krožne čakalne vrste

Krožna čakalna vrsta (ali obročni medpomnilnik) je napredna podatkovna struktura, kjer je zadnji element povezan s prvim, kar zagotavlja krožni tok. deque lahko posnema to vedenje s svojim maxlen lastnost:

from collections import deque circular_queue = deque(maxlen=3)
circular_queue.append(1)
circular_queue.append(2)
circular_queue.append(3) circular_queue.append(4)
print(circular_queue)

zaključek

Čakalne vrste, temeljne, a zmogljive, najdejo svoje bistvo v različnih aplikacijah v resničnem svetu in računalniških težavah. Posledice čakalnih vrst so daljnosežne, od načrtovanja opravil v operacijskih sistemih do upravljanja pretoka podatkov v tiskalnikih v ozadju ali zahtevah spletnega strežnika.

Python na mizo prinaša bogato paleto orodij in knjižnic za delo s čakalnimi vrstami. Od preprostih čakalnih vrst na podlagi seznamov za hitre skripte do zelo učinkovitih deque za aplikacije, ki so kritične za zmogljivost, jezik resnično poskrbi za širok spekter potreb.