Stack v Pythone: definícia, implementácie a príklady

Domov » Pytón » Stack v Pythone: definícia, implementácie a príklady

Zásobníky v Pythone sú jedným z tých základných konceptov, ktoré sa objavujú všade, keď sa začnete pozerať pod kapotu skutočných programov. – od volania funkcií, cez funkcie vrátenia zmien v editoroch, až po to, ako prehliadače spracovávajú vašu históriu navigácie. Aj keď prevažne píšete kód aplikácií na vysokej úrovni, pochopenie fungovania zásobníkov (a ich správnej implementácie v Pythone) vám dáva značnú výhodu, keď potrebujete ladiť zložité problémy alebo navrhovať efektívne algoritmy.

V tejto príručke si rozoberieme, čo je to zásobník, čo v praxi znamená „Posledný dnu, prvý von“, ktoré operácie by mal každý zásobník podporovať a ako implementovať zásobníky v Pythone pomocou rôznych nástrojov, ako sú zoznamy, kolekcie.deque, queue.LifoQueue a jednoducho prepojené zoznamy.Budeme sa tiež venovať výkonu, správaniu pamäte, bezpečnosti vlákien a reálnym scenárom, kde je zásobník presne tou správnou dátovou štruktúrou, po ktorej siahnuť.

Čo je to zásobník v Pythone?

Zásobník je lineárna dátová štruktúra, ktorá sa riadi pravidlom LIFO (Last-In, First-Out): posledný prvok, ktorý vložíte do zásobníka, je prvý, ktorý sa vráti von.Koncepčne si viete predstaviť kopu tanierov, kopu kníh alebo kopu oblečenia: položky môžete pridávať alebo odoberať iba zhora, nie zo stredu alebo zdola.

Toto správanie LIFO znamená, že keď vkladáte (push) prvky, každý nový prvok sa umiestni na predchádzajúce a keď ich odoberáte (pop), vždy vezmete naposledy pridaný prvok.Nikdy „nepreskočíte“ dopredu, aby ste sa dostali k tretiemu alebo štvrtému prvku bez toho, aby ste odstránili tie, ktoré sú nad ním.

V Pythone nie je zásobník samostatne vstavaným pomenovaným typom; namiesto toho implementujeme zásobníky nad existujúcimi dátovými štruktúrami, ako sú zoznamy, dvojrady, LIFO fronty alebo vlastné prepojené zoznamy.Každá možnosť má svoje vlastné kompromisy, pokiaľ ide o výkon, využitie pamäte a bezpečnosť vlákien.

Dve základné operácie na akomkoľvek zásobníku sú push a pop, ale praktické implementácie často odhaľujú niekoľko ďalších pomocníkov, ako napríklad peek (alebo top), size a empty checks.Tieto dodatočné operácie značne uľahčujú používanie zásobníkov v reálnych aplikáciách.

Predtým, ako sa ponoríme do kódovania, majte na pamäti kľúčovú vlastnosť: dobre implementovaný zásobník bude vykonávať operácie push a pop v konštantnom čase, označovanom ako O(1), bez ohľadu na to, koľko prvkov je uložených.Tento predvídateľný výkon je jedným z hlavných dôvodov, prečo sa zásobníky tak široko používajú v algoritmoch a nízkoúrovňových systémoch.

Operácie a správanie jadra zásobníka

Každý použiteľný stack v Pythone, bez ohľadu na základnú implementáciu, sa točí okolo niekoľkých bežných operácií, ktoré definujú jeho správanie.Pochopenie týchto vecí je oveľa dôležitejšie ako zapamätanie si názvov špecifických metód v každej knižnici.

Klasická operácia na vloženie prvku sa nazýva push: vezmete hodnotu a umiestnite ju na vrchol existujúceho zásobníka.Po odoslaní sa nový prvok stane tým, ktorý bude vrátený ako prvý pri ďalšej operácii vyzdvihnutia.

Na odstránenie prvkov používame funkciu pop, ktorá odoberie najvyššiu položku zo zásobníka a vráti ju.Ak je zásobník prázdny, robustná implementácia by mala buď vyvolať chybu, alebo vrátiť špecifickú hodnotu, ktorá jasne signalizuje absenciu prvkov.

Väčšina implementácií zásobníka tiež sprístupňuje operáciu peek alebo top, ktorá vám umožňuje pozrieť sa na prvok aktuálne na vrchole bez toho, aby ste ho museli odstrániť zo zásobníka.Toto je obzvlášť užitočné v algoritmoch, ktoré potrebujú skontrolovať ďalšiu hodnotu, ale stále ju chcú uchovať na neskôr.

Dve ďalšie pomocné operácie, s ktorými sa často stretnete, sú isempty (alebo isEmpty) a size, ktoré kontrolujú, či zásobník obsahuje nejaké prvky a koľko prvkov obsahuje.V Pythone je možné interne opätovne použiť vstavanú aj boolovskú kontrolu funkcie len() na implementáciu týchto pomocných funkcií s minimálnym kódom.

Z hľadiska časovej zložitosti, správne navrhnutý zásobník zaručuje, že push, pop, peek a isEmpty všetky bežia v konštantnom čase O(1) a veľkosť môže byť buď O(1), alebo O(n) v závislosti od toho, či implementácia ukladá dĺžku ako samostatné pole.Rozhodujúce je, že zásobníky nepodporujú efektívny náhodný prístup k ľubovoľným pozíciám ako polia.

Kedy a prečo použiť zásobník

Zásobníky vyniknú vždy, keď sa zaoberáte procesmi, ktoré budete neskôr musieť „pretočiť“ alebo prejsť v presne opačnom poradí, v akom boli vykonané kroky.Akákoľvek situácia, v ktorej si prirodzene pomyslíte: „Budem to musieť vrátiť späť od konca do konca“, je silným kandidátom na hromadu.

Klasickou analógiou z reálneho sveta je rozoberanie stroja: skrutky a súčiastky odstránite v určitom poradí a ak ho chcete správne zložiť, musíte ich vrátiť späť v presne opačnom poradí.Uloženie týchto častí na zásobník dokonale zodpovedá tomuto pracovnému postupu.

V softvéri je jedným z najzákladnejších použití zásobníkov zásobník volaní funkcií: vždy, keď funkcia volá inú funkciu, parametre, lokálne premenné a návratové adresy sa uložia na zásobník v pamäti.Keď funkcia vráti hodnotu, jej rámec sa odoberie, čím sa obnoví stav volajúceho.

Mechanizmy vrátenia a opakovania v textových editoroch, nástrojoch na kreslenie, IDE a mnohých ďalších aplikáciách sa zvyčajne spoliehajú na zásobníky akcií alebo stavov.Každá akcia používateľa sa presunie do zásobníka na vrátenie späť; po stlačení klávesov Ctrl+Z aplikácia zobrazí najnovšiu akciu a vráti ju späť.

Zásobníky sa tiež hojne používajú v algoritmoch, ako je vyhľadávanie do hĺbky (DFS) v grafoch, vyhodnocovanie výrazov (parsovanie zátvoriek, operátorov a operandov), spätné sledovanie a implementácia histórie prehliadača, kde sa každá navštívená stránka posunie späť a tlačidlo „Späť“ zobrazí poslednú stránku.Tieto scenáre profitujú z prirodzených disciplín LIFO, ktoré presadzujú a súvisia s jadrom. programovacia logika.

Implementácia zásobníka pomocou zoznamov v Pythone

Najjednoduchší spôsob, ako vytvoriť zásobník v Pythone, je použiť vstavaný typ zoznamu, pričom sa využije metóda append() na vloženie a metóda pop() na odstránenie posledného prvku.Zoznamy sú dynamické polia skryté v hlavnom kontexte a poskytujú všetky základné funkcie, ktoré zásobník potrebuje.

Minimálny zásobník založený na zoznamoch môže poskytovať pomocné funkcie ako create_stack, push, pop, isempty a show (alebo top, size atď.), ktoré všetky interne manipulujú s inštanciou jednoduchého zoznamu v Pythone.Napríklad, create_stack môže vrátiť iba prázdny zoznam a isempty môže byť definované ako len(stack) == 0.

Jeden bežný vzorec je považovať koniec zoznamu za vrchol zásobníka, takže stack.append(item) vykoná vloženie a stack.pop() vykoná vysunutie.Vďaka tomu sú obe operácie v priemernom konštantnom čase a kód zostáva veľmi čitateľný a krátky.

Ak uprednostňujete štruktúrovanejší kód, môžete toto správanie zabaliť do vlastnej triedy Stack, ktorá zapuzdrí zoznam a sprístupní prehľadné metódy ako push(), pop(), peek(), is_empty() a size().Zapuzdrenie uľahčuje neskoršie rozšírenie zásobníka o ďalšie kontroly alebo logovanie.

Zoznamy sú relatívne pamäťovo efektívne, pretože každý prvok priamo ukladá svoju hodnotu bez réžie ukazovateľa na ďalší uzol, ako by ste videli v prepojenom zozname.Navyše, mnoho vývojárov v Pythone je už veľmi dobre oboznámených so sémantikou zoznamov, vďaka čomu sa tento prístup ľahko učí a udržiava.

Existuje však dôležité upozornenie: zoznamy sú podporované súvislou pamäťou, takže keď presiahnu rezervovaný priestor, Python musí alokovať nový, väčší blok a skopírovať prvky doň.Väčšinou je toto prerozdelenie amortizované a neviditeľné, ale občas môže byť jedna funkcia append() citeľne pomalšia ako ostatné.

Ďalšou nevýhodou je, že zoznamy v Pythone nie sú bezpečné pre vlákna pri súbežných úpravách z viacerých vlákien, čo sa môže stať problémom, ak chcete použiť zásobník vo viacvláknových programoch.V takýchto situáciách by ste mali zvážiť alternatívy ako queue.LifoQueue namiesto obyčajných zoznamov.

Použitie collections.deque ako zásobníka

Modul kolekcií v Pythone poskytuje dvojradový front (deque), ktorý je často vhodnejší ako zoznamy, keď potrebujete časté operácie push a pop.Deque je optimalizovaný pre rýchle pridávanie a odosielanie z oboch koncov.

Pri použití dvojvrstvy ako zásobníka sa položky zvyčajne vkladajú pomocou metódy append() a odstraňujú sa pomocou metódy pop(), pričom pravý koniec sa považuje za vrchol zásobníka.Interne je deque implementovaný ako dvojito prepojený zoznam blokov, čím sa zabráni veľkým realokáciám, ktoré zoznamy občas potrebujú.

Vytvorenie zásobníka pomocou deque je jednoduché: zavolajte deque() na získanie prázdneho kontajnera, potom definujte operácie ako push(stack, item), ktoré volajú stack.append(item) a pop(stack), ktoré skontrolujú, či je zásobník neprázdny, a potom zavolajú stack.pop()Ďalšie pomocné funkcie ako show(stack) môžu jednoducho vypísať aktuálny obsah.

Keďže deque je špeciálne vyladený pre efektívne vkladanie a mazanie na oboch koncoch, operácie push a pop si zachovávajú konzistentný výkon O(1) aj pri raste štruktúry.Vďaka tomu môžu byť dvojesky (deques) vhodnejšie ako zoznamy pre veľké alebo intenzívne používané zásobníky.

V jednovláknovom kóde je deque zvyčajne jednou z najlepších predvolených možností pre implementáciu stackov v Pythone, pretože kombinuje dobrý výkon, čisté API a žiadne prekvapenia týkajúce sa obmedzení kapacity.Taktiež sa správa predvídateľnejšie z hľadiska načasovania, keď zásobník veľmi narastie.

Implementácia zásobníkov pomocou queue.LifoQueue

Keď sa bezpečnosť vlákien stane dôležitou, trieda LifoQueue modulu frontu je tou správnou voľbou pre implementáciu zásobníka v Pythone.LifoQueue je v podstate vláknovo bezpečný zásobník so vstavanými uzamykacími mechanizmami.

Ak chcete vytvoriť nový zásobník založený na LifoQueue, vytvoríte inštanciu LifoQueue s voliteľným parametrom maxsize, ktorý predstavuje maximálny počet prvkov, ktoré zásobník môže obsahovať.Interne bude front spracovávať čakanie, blokovanie a signalizáciu medzi vláknami, ak je zásobník plný alebo prázdny.

Vloženie prvku na zásobník LifoQueue sa vykonáva pomocou funkcie put(item), ktorá môže blokovať, ak je zásobník už naplnený na maximum.Na odoberanie prvkov sa používa metóda get(), ktorá môže tiež blokovať, ak je zásobník prázdny, kým nie je k dispozícii nová položka.

Ďalšie pomocné metódy ako qsize(), full() a empty() vám umožňujú skontrolovať aktuálny stav zásobníka spôsobom bezpečným pre vlákna.Napríklad full() vám povie, či už nie je možné pridať žiadne ďalšie prvky, zatiaľ čo empty() indikuje, či je potrebné niečo vybrať.

Hlavným kompromisom pri používaní LifoQueue je výkon: všetka synchronizácia potrebná na zabezpečenie vláknovej bezpečnosti predstavuje réžiu, vďaka čomu sú operácie pomalšie ako operácie na zoznamoch alebo dvojvláknových sekvenciách.V scenároch viazaných na CPU a vysoký výkon môže byť táto réžia dôležitá, ale pre mnohé viacvláknové aplikácie je bezpečnosť a správnosť oveľa dôležitejšia.

Stojí za zmienku, že vláknovanie v Pythone neznamená, že vlákna budú automaticky bežať na rôznych jadrách CPU kvôli Global Interpreter Lock (GIL), ale LifoQueue stále chráni váš zdieľaný stack pred súbehom a nekonzistentným stavom.Pre skutočný paralelizmus naprieč jadrami by ste potrebovali multiprocesovanie alebo iné prístupy, no koncept vláknovo bezpečných zásobníkov zostáva relevantný pre úlohy viazané na I/O alebo kooperatívne pracovné zaťaženia.

Implementácia zásobníka pomocou jednoducho prepojeného zoznamu

„Klasickejším“ spôsobom zostavenia zásobníka v Pythone z hľadiska informatiky je použitie jednoducho prepojeného zoznamu, kde každý uzol ukladá hodnotu a ukazovateľ (odkaz) na nasledujúci uzol.Tento prístup vám poskytuje dynamicky dimenzovaný zásobník, ktorý sa nespolieha na súvislú pamäť.

Zvyčajne definujete triedu Node s atribútmi pre hodnotu a nasledujúci odkaz a potom implementujete triedu Stack, ktorá sleduje hlavný uzol a počítadlo veľkostí.Často sa na zjednodušenie okrajových prípadov, keď je zásobník prázdny, používa fiktívny hlavný uzol.

V tomto návrhu je vrchol zásobníka reprezentovaný uzlom bezprostredne za hlavouAk chcete vložiť hodnotu, vytvoríte nový uzol, nastavíte jeho ďalší odkaz na aktuálny uzol head.next a potom aktualizujete uzol head.next tak, aby ukazoval na nový uzol, pričom postupne zvyšujete jeho veľkosť.

Vybratie prvku zahŕňa kontrolu, či je zásobník prázdny, následné prevzatie uzla, na ktorý ukazuje head.next, presunutie head.next na nasledujúci uzol, zníženie veľkosti a vrátenie odstránenej hodnoty.Táto operácia má konštantnú časovú zložitosť, pretože je potrebných iba niekoľko aktualizácií ukazovateľov.

Ďalšie metódy ako getSize(), isEmpty() a peek() sa s touto štruktúrou ľahko implementujú: size sa sleduje ako celé číslo, isEmpty dokáže skontrolovať, či je size nula, a peek vráti head.next.value, ak zásobník nie je prázdny.Môžete tiež definovať metódu __str__ na generovanie čitateľného reťazca so všetkými prvkami zásobníka.

Medzi výhody zásobníka založeného na prepojených zoznamoch patrí dynamický rast bez realokácie a predvídateľný výkon O(1) pre push a pop, aj keď sa štruktúra zväčší.Pamäť je alokovaná po jednotlivých uzloch, čo môže byť výhodné v systémoch s fragmentovanou pamäťou.

Nevýhodou je dodatočná pamäťová réžia pre ukazovatele (každý uzol ukladá aspoň jeden odkaz) a podrobnejší a komplexnejší kód v porovnaní so zoznamami alebo dvojsegmentovými reťazcami.Pre mnoho bežných programov v Pythone tieto náklady nestoja za výhody, ale táto technika je stále cenná na pochopenie a môže byť ideálna pre špecifické scenáre nízkej úrovne alebo vzdelávacie scenáre.

Vlastnosti, účinnosť a obmedzenia zásobníkov

Koncepčne sa zásobník správa ako hromada objektov, kde je prístupný iba vrch: vždy najprv interagujete s naposledy pridaným prvkom.Toto obmedzenie dáva stackom ich silu aj limity.

Pri správnej implementácii sú čítanie vrchného prvku, vloženie nového a odstránenie vrchného prvku operácie s konštantným časom O(1).Tento konzistentný výkon je mimoriadne užitočný pri navrhovaní algoritmov, ktoré môžu vyžadovať tisíce alebo milióny opakovaní.

Jedným dôležitým obmedzením je, že sa nedá efektívne dostať k ľubovoľným prvkom v strede zásobníka bez toho, aby sa zobrazilo všetko nad nimi.Ak neustále potrebujete náhodný prístup, vhodnejšia môže byť iná dátová štruktúra (napríklad zoznam použitý v podobe poľa).

Využitie pamäte a vzorce alokácie silne závisia od zvolenej implementácie: polia (zoznamy) používajú súvislú pamäť a niekedy ich môže byť potrebné realokovať, dvojsegmentové zoznamy spravujú bloky pamäte, aby sa predišlo veľkým kópiám, a prepojené zoznamy rozdeľujú uzly medzi dostupné pamäťové umiestnenia.Každý prístup inak vyvažuje réžiu, lokalitu a správanie kapacity.

Z hľadiska dizajnu sú zásobníky zámerne jednoduché: viditeľná je iba vrchná časť a neexistuje žiadna predstava o indexovaní alebo vkladaní do stredu.Táto jednoduchosť znižuje riziko náhodného zneužitia a podporuje kód, ktorý explicitne modeluje pracovné postupy LIFO.

Úvahy o zásobníkoch a vláknach v Pythone

Keď je váš program v Pythone jednovláknový, môžete si bezpečne vybrať medzi zoznamami a dvojvláknovými sekvenciami pre implementáciu zásobníkov na základe výkonu a pohodlia.Oba poskytujú funkcie push a pop a dajú sa ľahko integrovať do bežného kódu.

Keď zavediete viacero vlákien, ktoré zdieľajú zásobník, veci sa stanú chúlostivejšími: operácie, ktoré sa na úrovni Pythonu zdajú byť atomické, sa môžu neočakávaným spôsobom prelínať a poškodiť tak vnútorný stav.Jednoduché zoznamy a dvojsegmentové zaradenia nie sú navrhnuté tak, aby boli úplne bezpečné pre vlákna, keď sa používajú ako zdieľané meniteľné zásobníky.

Dvojité zadania sú relatívne bezpečné, ak ste extrémne disciplinovaní a obmedzíte sa na používanie iba funkcií append() a pop() z jedného konca starostlivo kontrolovaným spôsobom.Avšak aj vtedy sa môžu objaviť jemné problémy a podmienky súbehu, ak viacero vlákien číta a zapisuje súčasne bez externej synchronizácie.

Pre robustné viacvláknové scenáre, kde môže niekoľko vlákien súčasne odosielať a odosielať údaje, je odporúčanou implementáciou zásobníka queue.LifoQueue.Jeho vstavané zámky a blokovacia sémantika zabezpečujú, že súbežný prístup nepoškodí zásobník.

Nevýhodou je samozrejme to, že operácie LifoQueue (put a get) sú pomalšie ako metódy raw list alebo deque kvôli dodatočnej koordinácii medzi vláknami.Či je táto réžia dôležitá, závisí od výkonnostných požiadaviek vašej aplikácie a od toho, ako často sa k zásobníku pristupuje.

Tiež je potrebné mať na pamäti, že model vláknovania v Pythone stále beží pod globálnym zámkom interpreta, takže ani s vláknovo bezpečným zásobníkom automaticky nedosiahnete dokonalý paralelizmus CPU pre úlohy viazané na CPU.Napriek tomu je pre programy alebo návrhy viazané na I/O, ktoré sa spoliehajú na súbežnosť a nie na surový paralelizmus, zásobník bezpečný pre vlákna základným stavebným kameňom.

Výber správnej implementácie Python stacku

Vzhľadom na všetky tieto možnosti závisí „najlepšia“ implementácia zásobníka v Pythone vo veľkej miere od vášho kontextu: jednovláknové verzus viacvláknové, citlivosť na výkon, správanie pamäte a prehľadnosť kódu zohrávajú úlohu.Neexistuje jediná voľba, ktorá by bola dokonalá pre každú situáciu.

V jednoduchých, nevláknových skriptoch alebo vzdelávacích prostrediach je použitie zoznamu ako zásobníka často viac než postačujúce: append() a pop() sú intuitívne, rýchle pre väčšinu pracovných úloh a nevyžadujú takmer žiadny štandardný kód.Zoznamy tiež uľahčujú tlač a kontrolu obsahu na vzdelávacie účely.

Keď bude váš zásobník intenzívne využívaný, potenciálne bude ukladať veľa prvkov a chcete konzistentne rýchle push/pop operácie s menším počtom prekvapení súvisiacich s realokáciou pamäte, collections.deque býva najpraktickejšou voľbou.Jeho API veľmi dobre kopíruje zoznamy, takže migrácia je zvyčajne bezbolestná.

Ak od začiatku viete, že k zásobníku sa bude pristupovať z viacerých vlákien, najmä ak sa súčasne dejú push aj pops operácie, queue.LifoQueue je najbezpečnejšou možnosťou.Možno je to pomalšie, ale ušetrí vám to implementáciu vlastného uzamykacieho protokolu a pomôže vám vyhnúť sa zložitým podmienkam pretekov.

Prístup s jednoducho prepojeným zoznamom je ideálny, keď chcete preskúmať alebo naučiť vnútorné funkcie dátových štruktúr, alebo keď špecifické obmedzenia robia súvislé polia alebo dvojlisty menej atraktívnymi.Taktiež vám to dáva plnú kontrolu nad rozložením a správaním uzlov, ale za cenu väčšieho množstva kódu a trochu väčšej mentálnej réžie.

Bez ohľadu na to, ktorú implementáciu si vyberiete, základná myšlienka zostáva rovnaká: modelujete štruktúru typu „posledný dnu, prvý von“, ktorá ukladá prvky nad sebou a poskytuje vám rýchly a predvídateľný prístup k naposledy pridanej položke.Keď si s týmto modelom zvyknete, bude oveľa jednoduchšie premýšľať o algoritmoch a správaní systémov, kde sú zásobníky prirodzeným riešením.

Pochopením fungovania zásobníkov, operácií, ktoré podporujú, ich bežných implementácií v Pythone a ich kompromisov v oblasti výkonu a vlákien si môžete s istotou vybrať a implementovať verziu, ktorá najlepšie vyhovuje potrebám vášho projektu, a zároveň písať kód, ktorý zostane efektívny a zároveň ľahko pochopiteľný v priebehu času..