Sklad v Pythonu: definicija, implementacije in primeri

Domov » Python » Sklad v Pythonu: definicija, implementacije in primeri

Skladi v Pythonu so eden tistih ključnih konceptov, ki se pojavljajo povsod, ko začnete gledati pod pokrov pravih programov. – od klicev funkcij do funkcij razveljavitve v urejevalnikih in načina, kako brskalniki obravnavajo vašo zgodovino navigacije. Tudi če večinoma pišete kodo za aplikacije na visoki ravni, vam razumevanje delovanja skladov (in kako jih pravilno implementirati v Pythonu) daje veliko prednost pri odpravljanju napak pri zapletenih težavah ali oblikovanju učinkovitih algoritmov.

V tem priročniku bomo razložili, kaj je sklad, kaj v praksi pomeni načelo »Zadnji noter, prvi ven«, katere operacije naj bi vsak sklad podpiral in kako implementirati sklade v Pythonu z uporabo različnih orodij, kot so seznami, zbirke.deque, queue.LifoQueue in enojno povezani seznami.Govorili bomo tudi o zmogljivosti, obnašanju pomnilnika, varnosti niti in resničnih scenarijih, kjer je sklad ravno prava podatkovna struktura, po kateri se je treba osredotočiti.

Kaj je sklad v Pythonu?

Sklad je linearna podatkovna struktura, ki sledi pravilu LIFO (Last In, First Out): zadnji element, ki ga potisnete na sklad, je prvi, ki se vrne ven.Konceptualno si lahko predstavljate kup krožnikov, kup knjig ali kup oblačil: predmete lahko dodajate ali odstranjujete le od zgoraj, ne pa od sredine ali od spodaj.

To vedenje LIFO pomeni, da se pri vstavljanju (push) elementov vsak nov element nahaja na prejšnjih, pri odstranjevanju (pop) pa se vedno vzame nazadnje dodan element.Nikoli ne "preskočiš naprej", da bi dosegel/a tretji ali četrti element, ne da bi odstranil/a tiste, ki so nad njim.

V Pythonu sklad ni vgrajen poimenovani tip sam po sebi; namesto tega sklade implementiramo na vrhu obstoječih podatkovnih struktur, kot so seznami, dvojne vrste, čakalne vrste LIFO ali prilagojeni povezani seznami.Vsaka možnost ima svoje kompromise glede zmogljivosti, porabe pomnilnika in varnosti niti.

Dve temeljni operaciji na katerem koli skladu sta push in pop, vendar praktične izvedbe pogosto razkrijejo še nekaj pomočnikov, kot so peek (ali top), size in empty check-i.Zaradi teh dodatnih operacij je uporaba skladov v resničnih aplikacijah veliko bolj priročna.

Preden se poglobimo v kodo, ne pozabite na ključno lastnost: dobro implementiran sklad bo izvajal operacije push in pop v konstantnem času, označenem kot O(1), ne glede na to, koliko elementov je shranjenih.Ta predvidljiva zmogljivost je eden glavnih razlogov, zakaj se skladi tako pogosto uporabljajo v algoritmih in nizkonivojskih sistemih.

Operacije in vedenje jedrnega sklada

Vsak uporaben sklad v Pythonu, ne glede na osnovno implementacijo, se vrti okoli peščice pogostih operacij, ki določajo njegovo vedenje.Razumevanje teh je veliko pomembnejše od pomnjenja specifičnih imen metod v vsaki knjižnici.

Klasična operacija za vstavljanje elementa se imenuje push: vzamete vrednost in jo postavite na vrh obstoječega sklada.Po potisku novi element postane tisti, ki ga bo naslednja operacija pop vrnila najprej.

Za odstranjevanje elementov uporabimo ukaz pop, ki vzame najvišji element iz sklada in ga vrne.Če je sklad prazen, bi morala robustna implementacija bodisi sprožiti napako bodisi vrniti določeno vrednost, ki jasno signalizira odsotnost elementov.

Večina implementacij sklada razkrije tudi operacijo peek ali top, ki vam omogoča ogled elementa, ki je trenutno na vrhu, ne da bi ga odstranili iz sklada.To je še posebej priročno pri algoritmih, ki morajo pregledati naslednjo vrednost, vendar jo želijo tam ohraniti za pozneje.

Dve dodatni pomožni operaciji, ki ju boste pogosto našli, sta isempty (ali isEmpty) in size, ki preverita, ali ima sklad kakšne elemente in koliko elementov vsebuje.V Pythonu je mogoče tako vgrajeno preverjanje len() kot tudi logična preverjanja ponovno uporabiti interno za implementacijo teh pomočnikov z minimalno kodo.

Kar zadeva časovno kompleksnost, pravilno zasnovan sklad zagotavlja, da se ukazi push, pop, peek in isEmpty izvajajo v konstantnem času O(1), velikost pa je lahko O(1) ali O(n), odvisno od tega, ali implementacija shrani dolžino kot ločeno polje.Ključno je, da skladi ne podpirajo učinkovitega naključnega dostopa do poljubnih položajev, kot to počnejo polja.

Kdaj in zakaj uporabiti sklad

Skladi so izstopajoči, kadar imate opravka s procesi, ki jih boste kasneje morali "premotati" ali prečkati v popolnoma obratnem vrstnem redu, kot so bili koraki izvedeni.Vsaka situacija, v kateri seveda pomislite: "To bom moral razveljaviti od začetka do konca", je močan kandidat za kup.

Klasična analogija iz resničnega sveta je razstavljanje stroja: vijake in dele odstranite v določenem vrstnem redu, in če ga želite pravilno sestaviti, jih morate namestiti nazaj v ravno obratnem vrstnem redu.Shranjevanje teh delov na sklad se popolnoma ujema s tem delovnim potekom.

V programski opremi je ena najosnovnejših uporab skladov sklad klicev funkcij: vsakič, ko funkcija pokliče drugo funkcijo, se parametri, lokalne spremenljivke in povratni naslovi potisnejo na sklad v pomnilniku.Ko se funkcija vrne, se njen okvir odstrani, s čimer se obnovi stanje klicatelja.

Mehanizmi za razveljavitev in ponovitev v urejevalnikih besedil, orodjih za risanje, integriranih razvojnih okoljih (IDE) in mnogih drugih aplikacijah se običajno zanašajo na niz dejanj ali stanj.Vsako uporabniško dejanje se premakne na sklad za razveljavitev; ko pritisnete Ctrl+Z, aplikacija prikaže najnovejše dejanje in ga razveljavi.

Skladi se pogosto uporabljajo tudi v algoritmih, kot so iskanje v globino (DFS) v grafih, vrednotenje izrazov (razčlenjevanje oklepajev, operatorjev in operandov), sledenje nazaj in za izvajanje zgodovine brskalnika, kjer se vsaka obiskana stran potisne, »Nazaj« pa prikaže zadnjo.Ti scenariji imajo koristi od naravnih skladov disciplin LIFO, ki jih uveljavljajo in so povezani z osrednjimi programska logika.

Implementacija sklada s seznami v Pythonu

Najenostavnejši način za izgradnjo sklada v Pythonu je uporaba vgrajenega tipa seznama, pri čemer se za dodajanje elementov uporabi metoda append() in metoda pop() za odstranjevanje zadnjega elementa.Seznami so dinamična polja v ozadju in zagotavljajo vse osnovne funkcionalnosti, ki jih sklad potrebuje.

Minimalni sklad, ki temelji na seznamih, lahko nudi pomožne funkcije, kot so create_stack, push, pop, isempty in show (ali top, size itd.), ki vse interno manipulirajo z navadnim primerkom seznama v Pythonu.Na primer, create_stack lahko vrne samo prazen seznam, isempty pa je lahko definiran kot len(stack) == 0.

Pogost vzorec je, da se konec seznama obravnava kot vrh sklada, zato stack.append(item) izvede push, stack.pop() pa izstrelitev.To ohranja obe operaciji v povprečnem konstantnem času, koda pa ostane zelo berljiva in kratka.

Če imate raje bolj strukturirano kodo, lahko to vedenje zavijete v razred Stack po meri, ki enkapsulira seznam in razkrije jasne metode, kot so push(), pop(), peek(), is_empty() in size().Z enkapsulacijo je lažje razširiti sklad z dodatnimi preverjanji ali kasnejšim beleženjem.

Seznami so relativno pomnilniško učinkoviti, ker vsak element neposredno shrani svojo vrednost brez dodatnega kazalca na naslednje vozlišče, kot bi videli v povezanem seznamu.Poleg tega mnogi razvijalci v Pythonu že zelo dobro poznajo semantiko seznamov, zaradi česar je ta pristop enostaven za poučevanje in vzdrževanje.

Vendar obstaja pomembno opozorilo: seznami so podprti s sosednjim pomnilnikom, zato mora Python, ko preseže rezervirani prostor, dodeliti nov, večji blok in prekopirati elemente.Večinoma je ta prerazporeditev amortizirana in nevidna, občasno pa je lahko posamezna funkcija append() opazno počasnejša od drugih.

Druga slabost je, da seznami v Pythonu niso varni za sočasne spremembe iz več niti, kar lahko postane težava, če želite uporabiti sklad v večnitnih programih.V takih primerih bi morali namesto navadnih seznamov razmisliti o alternativah, kot je queue.LifoQueue.

Uporaba zbirke collections.deque kot sklada

Pythonov modul za zbirke ponuja dvostransko čakalno vrsto (deque), ki je pogosto boljša izbira kot seznami, kadar potrebujete pogoste operacije "push" in "izstop".Deque je optimiziran za hitro dodajanje in odpiranje z obeh koncev.

Ko uporabljate deque kot sklad, običajno elemente potisnete z metodo append() in jih odstranite s pop(), pri čemer desni konec obravnavate kot vrh sklada.Interno je deque implementiran kot dvojno povezan seznam blokov, s čimer se izognemo velikim prerazporeditvam, ki jih seznami občasno potrebujejo.

Ustvarjanje sklada z uporabo deque je preprosto: pokličemo deque(), da dobimo prazen vsebnik, nato pa definiramo operacije, kot sta push(stack, item), ki kličejo stack.append(item) in pop(stack), ki preveri, ali je sklad neprazen, in nato pokliče stack.pop().Dodatni pomočniki, kot je show(stack), lahko preprosto izpišejo trenutno vsebino.

Ker je deque posebej uglašen za učinkovito vstavljanje in brisanje na obeh koncih, operaciji push in pop ohranjata dosledno zmogljivost O(1), tudi ko struktura raste.Zaradi tega so lahko dvojke bolj zaželene kot seznami za velike ali močno uporabljene sklade.

V enonitni kodi je deque običajno ena najboljših privzetih izbir za implementacijo skladov v Pythonu, saj združuje dobro zmogljivost, čist API in brez presenečenj glede omejitev zmogljivosti.Prav tako se obnaša bolj predvidljivo glede časa, ko sklad zelo naraste.

Implementacija skladov z queue.LifoQueue

Ko postane varnost niti pomembna, je razred LifoQueue modula čakalne vrste idealna možnost za implementacijo sklada v Pythonu.LifoQueue je v bistvu nitno varen sklad z vgrajenimi mehanizmi za zaklepanje.

Če želite ustvariti nov sklad, ki temelji na LifoQueue, ustvarite instanco LifoQueue z neobveznim parametrom maxsize, ki predstavlja največje število elementov, ki jih lahko sklad vsebuje.Interno bo čakalna vrsta obravnavala čakanje, blokiranje in signaliziranje med niti, če je sklad poln ali prazen.

Potiskanje elementa na sklad LifoQueue se izvede z ukazom put(item), ki lahko blokira, če je sklad že na svoji največji zmogljivosti.Za izvlečenje elementov se uporablja funkcija get(), ki lahko blokira tudi, če je sklad prazen, dokler ni na voljo nov element.

Dodatne pomožne metode, kot so qsize(), full() in empty(), vam omogočajo, da na nitno varen način pregledate trenutno stanje sklada.Na primer, full() vam pove, če ni mogoče dodati več elementov, medtem ko empty() označuje, ali je kaj za izvleči.

Glavna slabost pri uporabi LifoQueue je zmogljivost: vsa sinhronizacija, potrebna za varno delovanje v več nitih, povzroča dodatne stroške, zaradi česar so operacije počasnejše od tistih na seznamih ali dvojnih vrsticah.V scenarijih, ki so vezani na procesor in visoko zmogljivi, je ta režijski strošek lahko pomemben, vendar sta za številne večnitne aplikacije varnost in pravilnost veliko pomembnejši.

Omeniti velja, da Python-ovo navajanje niti ne pomeni, da se bodo niti samodejno izvajale na različnih jedrih procesorja zaradi globalnega zaklepanja interpreterja (GIL), vendar LifoQueue še vedno ščiti vaš skupni sklad pred tekmovalnimi pogoji in nedoslednim stanjem.Za resnično vzporednost med jedri bi potrebovali večprocesiranje ali druge pristope, vendar koncept nitno varnih skladov ostaja pomemben za delovne obremenitve, vezane na V/I ali kooperativne delovne obremenitve.

Implementacija sklada z uporabo enojno povezanega seznama

Bolj »klasičen« računalniški način gradnje sklada v Pythonu je uporaba enojno povezanega seznama, kjer vsako vozlišče shrani vrednost in kazalec (sklicevanje) na naslednje vozlišče.Ta pristop vam omogoča dinamično dimenzioniran sklad, ki se ne zanaša na sosednji pomnilnik.

Običajno definirate razred Node z atributi za vrednost in naslednjo referenco, nato pa implementirate razred Stack, ki sledi glavnemu vozlišču in števcu velikosti.Pogosto se za poenostavitev robnih primerov, ko je sklad prazen, uporablja navidezno glavno vozlišče.

V tej zasnovi je vrh sklada predstavljen z vozliščem takoj za glavoZa potisk vrednosti ustvarite novo vozlišče, nastavite njegovo naslednjo referenco na trenutni head.next in nato posodobite head.next, da kaže na novo vozlišče, pri čemer sproti povečujete velikost.

Odstranjevanje elementa vključuje preverjanje, ali je sklad prazen, nato pa prevzem vozlišča, na katerega kaže head.next, premikanje head.next na naslednje vozlišče, zmanjšanje velikosti in vrnitev odstranjene vrednosti.Ta operacija ima konstantno časovno kompleksnost, ker je potrebnih le nekaj posodobitev kazalcev.

Dodatne metode, kot so getSize(), isEmpty() in peek(), je s to strukturo enostavno implementirati: size se sledi kot celo število, isEmpty lahko preveri, ali je size nič, peek pa vrne head.next.value, če sklad ni prazen.Definirate lahko tudi metodo __str__ za generiranje berljivega niza z vsemi elementi sklada.

Prednosti sklada, ki temelji na povezanem seznamu, vključujejo dinamično rast brez prerazporeditve in predvidljivo zmogljivost O(1) za push in pop, tudi ko struktura postane velika.Pomnilnik se dodeljuje vozlišče za vozliščem, kar je lahko koristno v sistemih s fragmentiranim pomnilnikom.

Slabosti so dodatna poraba pomnilnika za kazalce (vsako vozlišče shrani vsaj eno referenco) in bolj podrobna, kompleksna koda v primerjavi s seznami ali dvojnimi sklopi.Za številne vsakdanje programe v Pythonu ti stroški niso vredni koristi, vendar je tehnika še vedno dragocena za razumevanje in je lahko idealna za specifične scenarije nizke ravni ali izobraževalne scenarije.

Lastnosti, učinkovitost in omejitve skladov

Konceptualno se sklad obnaša kot kup predmetov, kjer je dostopen samo vrh: vedno najprej interagirate z nazadnje dodanim elementom.Ta omejitev daje skladom tako moč kot omejitve.

Ko je pravilno implementirano, so branje zgornjega elementa, vstavljanje novega in odstranjevanje zgornjega elementa vse operacije s konstantnim časom O(1).Ta dosledna zmogljivost je izjemno uporabna pri načrtovanju algoritmov, ki se morajo morda večkrat ali celo milijonkrat ponoviti.

Pomembna omejitev je, da ne morete učinkovito doseči poljubnih elementov na sredini sklada, ne da bi iz njih izstopilo vse, kar je nad njimi.Če nenehno potrebujete naključni dostop, je morda primernejša drugačna podatkovna struktura (na primer seznam, uporabljen v obliki polja).

Poraba pomnilnika in vzorci dodeljevanja so močno odvisni od izbrane implementacije: polja (seznami) uporabljajo sosednji pomnilnik in jih je včasih treba prerazporediti, dvojne vrstice upravljajo bloke pomnilnika, da se izognejo velikim kopijam, povezani seznami pa razporejajo vozlišča po razpoložljivih lokacijah v pomnilniku.Vsak pristop drugače usklajuje režijske stroške, lokalnost in obnašanje zmogljivosti.

Z vidika oblikovanja so skladi namerno preprosti: viden je samo vrh, na sredini pa ni pojma indeksiranja ali vstavljanja.Ta preprostost zmanjšuje možnost nenamerne zlorabe in spodbuja kodo, ki eksplicitno modelira delovne tokove LIFO.

Premisleki o skladih in nitih v Pythonu

Ko je vaš program v Pythonu enonitni, lahko varno izbirate med seznami in dvojnimi nizi za implementacijo skladov glede na zmogljivost in udobje.Oba omogočata zmožnosti »push« in »pop« ter ju je enostavno integrirati v običajno kodo.

Ko uvedete več niti, ki si delijo sklad, postanejo stvari bolj občutljive: operacije, ki se na ravni Pythona zdijo atomske, se lahko prepletajo na nepričakovane načine in pokvarijo notranje stanje.Navadni seznami in dvojni seznami niso zasnovani tako, da bi bili popolnoma varni za delovanje v nitih, kadar se uporabljajo kot skupni spremenljivi skladi.

Deque-ji so relativno varni, če ste izjemno disciplinirani in se omejite na uporabo samo append() in pop() z enega konca na skrbno nadzorovan način.Vendar pa se lahko tudi takrat pojavijo subtilne težave in tekmovalni pogoji, če več niti hkrati bere in piše brez zunanje sinhronizacije.

Za robustne večnitne scenarije, kjer lahko več niti hkrati potiska in odpira podatke, je priporočena implementacija sklada queue.LifoQueue.Vgrajene ključavnice in semantika blokiranja zagotavljajo, da sočasni dostop ne poškoduje sklada.

Kompromis je seveda v tem, da so operacije LifoQueue (put in get) počasnejše od metod surovega seznama ali deque zaradi dodatne koordinacije med nitmi.Ali je ta režijska obremenitev pomembna, je odvisno od zahtev glede zmogljivosti vaše aplikacije in od tega, kako pogosto se dostopa do sklada.

Prav tako je vredno upoštevati, da Pythonov model niti še vedno deluje pod globalnim zaklepom interpreterja, zato tudi z nitno varnim skladom ne boste samodejno dosegli popolne vzporednosti CPU-ja za naloge, vezane na CPU.Kljub temu je za programe, vezane na V/I, ali zasnove, ki se zanašajo na sočasnost in ne na surovo vzporednost, sklad, varen za niti, bistveni gradnik.

Izbira prave implementacije Python stack-a

Glede na vse te možnosti je »najboljša« implementacija sklada v Pythonu močno odvisna od vašega konteksta: enonitni ali večnitni, občutljivost na zmogljivost, obnašanje pomnilnika in jasnost kode igrajo pomembno vlogo.Ni ene same izbire, ki bi bila popolna za vsako situacijo.

V preprostih, nenitnih skriptah ali učnih okoljih je uporaba seznama kot sklada pogosto več kot dovolj: append() in pop() sta intuitivna, hitra za večino delovnih obremenitev in ne zahtevata skoraj nobene standardne kode.Za izobraževalne namene seznami olajšajo tudi tiskanje in pregledovanje vsebine.

Ko bo vaš sklad močno uporabljen, potencialno bo shranjeval veliko elementov, in želite dosledno hitro dodajanje/izmenjavanje z manj presenečenji, povezanimi s prerazporeditvijo pomnilnika, je collections.deque ponavadi najbolj praktična izbira.Njegov API natančno odraža sezname, zato je migracija običajno neboleča.

Če že od začetka veste, da bo do sklada dostopano iz več niti, še posebej, če se hkrati izvajajo tako potiski kot izpisi, je queue.LifoQueue najvarnejša možnost.Morda je počasnejše, vendar vam prihrani implementacijo lastnega protokola zaklepanja in pomaga preprečiti zapletene dirkaške pogoje.

Pristop z enojno povezanim seznamom je idealen, kadar želite raziskati ali se naučiti notranjega delovanja podatkovnih struktur ali kadar določene omejitve naredijo sosednja polja ali dvojke manj privlačne.Prav tako vam daje popoln nadzor nad postavitvijo in vedenjem vozlišč, za ceno več kode in nekoliko več mentalnih stroškov.

Ne glede na to, katero implementacijo izberete, osnovna ideja ostaja enaka: modelirate strukturo »zadnji noter, prvi ven«, ki shranjuje elemente drug na drugega in vam omogoča hiter in predvidljiv dostop do nazadnje dodanega elementa.Ko se s tem modelom enkrat seznanite, postane veliko lažje razmišljati o algoritmih in vedenju sistemov, kjer so skladi naravno primerni.

Z razumevanjem delovanja skladov, operacij, ki jih podpirajo, njihovih pogostih implementacij v Pythonu ter kompromisov pri zmogljivosti in nitih, lahko samozavestno izberete in implementirate različico, ki najbolje ustreza potrebam vašega projekta, hkrati pa pišete kodo, ki ostane učinkovita in enostavna za razmišljanje skozi čas..