Strukture podataka i algoritmi: cjeloviti vodič za programere

Informatec Digital » Sredstva » Strukture podataka i algoritmi: cjeloviti vodič za programere

Algoritmi i strukture podataka dva su dijela koja se uklapaju poput slagalice: jedan definira postupak rješavanja problema, a drugi određuje gdje i kako pohranjujemo informacije. Iako možda zvuči akademski, savladavanje ovog para ono je što razlikuje kod koji samo radi od koda koji leti i skalira se bez kvarova.

Ako želite nastaviti karijeru u profesionalnom programiranju, pripremiti se za tehničke intervjue ili jednostavno prestati mučiti se s vježbama poput LeetCodea i Codewarsa, potrebna vam je čvrsta osnova u strukturama podataka i algoritmima . U ovom članku saznat ćete što su, zašto su toliko važne, glavne vrste koje postoje, osnovne operacije koje izvode i vrste pitanja koja se obično pojavljuju na ispitima i u procesima odabira.

Što su strukture podataka i algoritmi?

Struktura podataka je, u biti, specifičan način organiziranja i pohranjivanja informacija u memoriji kako bi se omogućila učinkovita manipulacija. Ova organizacija nije slučajna: ona izravno određuje koje su operacije brze, a koje postaju skupe (umetanje, pretraživanje, brisanje, pregledavanje itd.).

Kada odaberete pravu strukturu podataka, vaš program može bez problema obraditi velike količine podataka ; kada odaberete loše, čak i mala aplikacija može postati spora, trošiti previše memorije ili je s vremenom postati nemoguće održavati.

Algoritam je konačan, uređen niz dobro definiranih koraka koji transformira ulaze u izlaze kako bi riješio određeni problem. To je poput recepta za kuhanje: govori vam što učiniti, kojim redoslijedom i pod kojim uvjetima, ali ga ne brine kako pohranjujete sastojke u hladnjaku, što bi bio dio strukture podataka.

U računalnoj znanosti, svaki algoritam je dizajniran s obzirom na vrstu podataka s kojima će raditi. Izbor strukture podataka nije mali detalj: struktura i algoritam idu ruku pod ruku , a male promjene u bilo kojem od njih mogu značajno poboljšati ili pogoršati performanse.

S teorijske perspektive, autori poput Niklausa Wirtha popularizirali su ideju da algoritmi + strukture podataka = programi još 70-ih . Desetljećima kasnije, to ostaje jednako istinito: bez obzira programirate li u Javi, Pythonu, C++ ili dolazite s bootcampa, ono što će se tražiti na intervjuima i ozbiljnim projektima jest sposobnost učinkovitog odabira i kombiniranja oba elementa.

Zašto su toliko važni u programiranju?

U bilo kojoj stvarnoj aplikaciji, bez obzira koliko se činila jednostavnom, uvijek radite s podacima: plaćama, proizvodima, korisnicima, transakcijama, rutama, dokumentima , zapisima dnevnika itd. Pitanje nije hoćete li rukovati podacima, već kako ćete ih organizirati tako da vaš kod bude brz, jasan i jednostavan za održavanje.

Strukture podataka koriste se za pohranu informacija na organiziran i koherentan način, ovisno o problemu. Nije isto uvijek pristupiti prvom elementu, pretraživati ​​po ključu, iterirati po redu, umetati u sredinu ili često brisati; svaki obrazac korištenja bolje odgovara drugoj strukturi.

Algoritmi nam, sa svoje strane, omogućuju učinkovitu obradu tih podataka : sortiranje, filtriranje, pretraživanje elemenata, pronalaženje optimalnih putova, otkrivanje uzoraka putem rudarenja podataka , optimiziranje resursa i tako dalje. Mnogi problemi koji se čine teškima postaju trivijalni kada pronađete pravu kombinaciju algoritma i strukture podataka.

U tehničkim intervjuima za razvoj softvera rijetko se postavlja pitanje koje se izravno ne odnosi na ove teme. Ponekad pitanje eksplicitno spominje strukturu, poput "uz dano binarno stablo...", a ponekad je implicitno: "želimo prebrojati koliko knjiga ima svaki autor", što sugerira korištenje hash tablice ili mape ključ-vrijednost.

Nadalje, formalna i profesionalna obuka često se vrti oko ovog područja. Mnoga sveučilišta i programi visokog obrazovanja uključuju predmet pod nazivom Strukture podataka i algoritmi , sa službenim nastavnim planom i programom, preduvjetima, predavanjima i praktičnim vježbama, ispitima i zadacima, jer se smatra ključnim predmetom za svakog softverskog inženjera.

Preduvjeti i potrebni temelji

Kako biste izvukli maksimum iz proučavanja struktura podataka i algoritama, korisno je imati neko poznavanje programskog jezika opće namjene, kao što su Java, Python ili C++ . Ne morate biti stručnjak, ali trebali biste biti upoznati s osnovnim konceptima poput varijabli, tipova podataka, uvjetnih naredbi, petlji, funkcija i prosljeđivanja parametara.

Također je nevjerojatno korisno razumjeti koncept algoritamske složenosti i Big O notacije: kako se vrijeme izvršavanja ili korištenje memorije povećava s povećanjem veličine podataka (n). Poznavanje razlikovanja između O(1), O(log n), O(n), O(n log n) i O(n²) omogućuje vam objektivnu usporedbu alternativa i opravdanje vaših odluka.

Drugi važan aspekt je imati određeno iskustvo s rješavanjem problema : vježbe strukturiranog programiranja, mali logički izazovi, jednostavne kata itd. Što više vježbate svoj "nos" da razložite problem na korake, lakše ćete vidjeti koja struktura podataka odgovara svakom slučaju.

Neki nastavni planovi i programi izričito navode preduvjete ili korekvizite za tečaj Strukture podataka i algoritmi, kao što su položene Osnove programiranja, Programiranje I ili Diskretna matematika. To ima smisla: bez čvrstih temelja u osnovnom programiranju i malo logike, lako se frustrirati ovim predmetom.

Konačno, poznavanje stvarnih praktičnih okruženja (kao što su mali web projekti, skripte ili konzolne aplikacije) pomaže vam da bolje vizualizirate za što ćete koristiti svaku strukturu, umjesto da je doživljavate kao nešto isključivo akademsko.

Najčešće korištene strukture podataka

U računalnoj znanosti postoji mnogo struktura podataka , ali postoji skupina "osnovnih" koje se ponavljaju iznova i iznova: nizovi (vektori), stogovi, redovi čekanja, povezane liste, stabla, grafovi, try-sumovi i hash tablice. Razumijevanje kako funkcioniraju, koje operacije nude i njihovih tipičnih troškova ključno je za postizanje vještog programiranja.

Zatim ćemo pregledati svaki od njih , s glavnom idejom, tipičnim operacijama i primjerima problema koji se obično pojavljuju u nastavi, vježbama i razgovorima za posao za razvojne programere.

Nizovi

Niz je najjednostavnija linearna struktura podataka i jedna od najčešće korištenih. Sastoji se od susjednog bloka memorije koji pohranjuje kolekciju elemenata istog tipa, dostupnih putem cjelobrojnog indeksa, obično počevši od nule.

Zamislite niz veličine 4 koji sadrži vrijednosti 1, 2, 3 i 4. Svaka pozicija ima indeks (0, 1, 2, 3) i možete izravno pristupiti bilo kojem elementu s njegovim indeksom u konstantnom vremenu O(1). To čini nizove vrlo učinkovitima za slučajno čitanje.

Postoje dvije glavne kategorije: jednodimenzionalni nizovi (jedan red elemenata) i višedimenzionalni nizovi (na primjer, matrice, koje su nizovi nizova). Mnogi programski jezici nude obje varijante izvorno ili s malim razlikama u sintaksi i performansama.

Osnovne operacije na nizu su obično:

• Umetnuti: postavljanje elementa na određenu poziciju, što u statičkim nizovima može uključivati ​​pomicanje drugih elemenata.
• Dobiti: pristup elementu na zadanom indeksu, obično O(1).
• Izbrisati: izbrisati ili označiti kao prazan element na određenoj poziciji, obično pomicanjem elemenata ulijevo.
• Veličina: provjerava koliko je elemenata pohranjeno ili maksimalni kapacitet niza.

U intervjuima i ispitima, vježbe poput pronalaženja druge minimalne vrijednosti u nizu , pronalaženja prvog jedinstvenog cijelog broja, spajanja dva sortirana niza ili promjene redoslijeda pozitivnih i negativnih brojeva uz zadržavanje određenih svojstava vrlo su česte. Sve se one oslanjaju na pristup indeksu i linearne ili dvostruke obilaske.

Slojevi

Stog je linearna struktura podataka koja slijedi LIFO princip: Zadnji unutra, prvi van. Zamislite hrpu knjiga postavljenih jedna na drugu: knjige možete uzimati ili ostavljati samo s vrha.

Zbog takvog ponašanja možemo pristupiti samo elementu na vrhu stoga . Ne možemo ukloniti srednji element bez prethodnog uklanjanja elemenata iznad njega. To ga čini idealnom strukturom za modeliranje povijesti akcija (poništavanje), ugniježđenih poziva funkcija, navigacije (natrag/naprijed) i tako dalje.

Tipične operacije sa stogom su:

• Gurati: umetnite novu stavku na vrh.
• Pop: izdvojiti i vratiti element na vrhu, smanjujući veličinu stoga.
• Vrh ili pogled: konzultirati gornji element bez brisanja.
• prazno je: provjerite je li baterija prazna.

U kontekstu intervjua, uočavaju se problemi poput procjene izraza u postfiksnoj notaciji (RPN), sređivanja elemenata korištenjem samo stogova ili provjere je li niz zagrada (i drugih simbola) ispravno uravnotežen korištenjem push i pop.

U praksi, mnoge interne implementacije jezika (na primjer, stog sistemskih poziva ) rade prema istim principima, čak i ako ih ne vidimo izravno.

Redovi čekanja

Red je još jedna linearna struktura podataka, ali umjesto LIFO principa, koristi FIFO model: Prvi unutra, Prvi van. Najjasnija analogija je red ljudi koji čekaju na blagajni u kinu.

U standardnom redu čekanja, stavke se dodaju na kraj, a uklanjaju s početka . Prva stavka u redu čekanja je prva stavka koja se poslužuje, što ga čini idealnim za upravljanje zadacima na čekanju, procesima operacijskog sustava, zahtjevima poslužitelja, redovima čekanja za ispis i tako dalje.

Osnovne operacije reda čekanja uključuju:

• U redu: umetnite novu stavku na kraj reda čekanja.
• U redu čekanja: ukloni i vrati element koji se nalazi na početku.
• Prednji ili gornji dio: pogledajte prvu stavku bez njenog uklanjanja.
• prazno je: provjeri je li red prazan.

U programerskim izazovima uobičajeno je da se od vas zatraži, na primjer, implementacija stoga pomoću dva reda čekanja , preokretanje prvih k elemenata reda čekanja bez promjene ostatka ili generiranje binarnih brojeva od 1 do n korištenjem FIFO ponašanja reda čekanja.

Uz osnovni red, postoje varijante kao što su kružni red , red s prioritetom ili dvostruki redovi (deque), koje nude dodatne operacije i poboljšavaju performanse u određenim scenarijima.

povezane liste

Povezana lista je također linearna struktura, ali se interno jako razlikuje od nizova. Umjesto korištenja susjednog bloka memorije, sastoji se od rijetkih čvorova koji su međusobno povezani referencama ili pokazivačima.

Svaki čvor obično sadrži dva dijela: podatke koji se pohranjuju i pokazivač (ili nekoliko) koji pokazuje na sljedeći čvor u nizu (a u slučaju dvostruko povezanih popisa i na prethodni). Popisom se upravlja putem reference na njegov početak, koji pokazuje na prvi čvor, a u složenijim popisima održava se i referenca na rep.

Postoje dvije glavne varijante:

• jednostruko povezana lista: svaki čvor pokazuje samo na sljedeći; put je obično u jednom smjeru.
• dvostruko povezana listaSvaki čvor pokazuje na sljedeći i prethodni čvor, što olakšava dvosmjerno kretanje i učinkovitije operacije brisanja.

Tipične operacije na povezanim listama uključuju:

• Umetni na početak: umetnite novi čvor na početak popisa.
• Umetni na kraju: dodavanje čvora na kraj, ažuriranje reda ako postoji.
• Izbrisati: ukloniti određeni čvor, prilagođavajući pokazivače susjednih čvorova.
• Izbriši na početku: izbrišite prvi čvor i premjestite glavu na sljedeći.
• Traži: pregledavanje popisa u potrazi za određenom vrijednošću.
• prazno jeprovjeri je li zaglavlje null i stoga lista nema elemenata.

U nastavi i na razgovorima za posao, problemi su brojni poput preokretanja povezane liste , otkrivanja postojanja ciklusa (obično korištenjem algoritma "kornjače i zeca"), dobivanja čvora N brojanjem od kraja ili uklanjanja dupliciranih čvorova, uvijek pažljivo manipulirajući pokazivačima.

Povezane liste se široko koriste za implementaciju hash tablica s ulančavanjem , lista susjednosti u grafovima i dinamičkih struktura podataka gdje se elementi često umeću i brišu.

drveće

Stablo je hijerarhijska struktura podataka sastavljena od čvorova povezanih bridovima. Za razliku od općih grafova, stablo nema cikluse: uvijek postoji korijen, djeca, roditelji, braća i sestre, listovi, razine i podstabla, s organizacijom tipa "obitelj" ili "organizacijski dijagram".

Stabla su vrlo korisna kada želimo prikazati hijerarhijske odnose ili podijeliti problem na manje podprobleme: datotečne sustave, izbornike, DOM strukture u preglednicima, stabla odlučivanja u umjetnoj inteligenciji itd.

Postoji mnogo vrsta drveća, uključujući:

• N-arno stablo: svaki čvor može imati varijabilan (i moguće velik) broj djece.
• Uravnoteženo stablo: održava svoje grane na sličnoj dubini kako bi se izbjeglo smanjenje performansi.
• Binarno stablo: svaki čvor ima maksimalno dva potomka (lijevo i desno).
• Binarno stablo pretraživanja (BST): binarno stablo sa svojstvom da je sve lijevo od čvora manje, a sve desno veće (prema nekom kriteriju uređenja).
• AVL stablo, crveno-crno, 2-3 i druge varijanteTo su uravnotežena stabla pretraživanja koja jamče dobra ograničenja složenosti pri operacijama umetanja, brisanja i pretraživanja.

U praksi, najčešći tipovi koji se koriste u vježbama su binarno stablo i binarno stablo pretraživanja . Tipični problemi uključuju izračunavanje visine stabla, pronalaženje k-te maksimalne vrijednosti u binarnom stablu pretraživanja, popisivanje čvorova na određenoj udaljenosti od korijena ili određivanje predaka određenog čvora.

Nadalje, algoritmi prolaska (preorder, inorder, postorder, level by level) temeljni su za mnoge sljedeće procese: sortirani ispis, procjenu izraza, serijalizaciju i deserijalizaciju stabla itd.

grafovima

Graf generalizira koncept stabla dopuštajući cikluse i višestruke proizvoljne veze između čvorova. Sastoji se od skupa vrhova (čvorova) i skupa bridova koji povezuju parove vrhova, ponekad s pridruženom težinom ili cijenom.

Postoji nekoliko vrsta grafova: neusmjereni (brigovi nemaju smjer, odnos je dvosmjeran) i usmjereni (brigovi imaju ishodište i odredište). Također se mogu klasificirati kao ponderirani ili neponderirani, povezani ili nepovezani, sa ili bez ciklusa itd.

U kodu se grafovi obično predstavljaju na dva osnovna načina:

• Matrica susjednosti: matrica gdje ćelija označava postoji li rub između vrha i i j (i moguće težinu veze).
• Popis susjedstva: za svaki vrh pohranjuje se popis njegovih susjeda, što štedi memoriju u rijetkim grafovima.

Najklasičniji algoritmi za prolazak kroz graf su pretraživanje u širinu (BFS) i pretraživanje u dubinu (DFS) . Oba se koriste kao građevni blokovi za mnoštvo problema: provjeru je li graf povezan, otkrivanje ciklusa, pronalaženje povezanih komponenti itd.

U tehničkim testovima uobičajeno je da se traži implementacija BFS-a i DFS-a, provjera formira li graf stablo, brojanje bridova ili traženje kraćih putova između dva čvora (na primjer, na karti gradova) korištenjem varijanti poput Dijkstre ili BFS-a u neponderiranim grafovima.

Pokušaji ili prefiksna stabla

Prefiksno stablo (ili prefiksno stablo) je struktura podataka u obliku stabla optimizirana za rukovanje nizovima znakova, posebno korisna pri radu s rječnicima riječi, sustavima za automatsko dovršavanje ili pretraživanjima prefiksa.

U trie-u, svaki čvor obično predstavlja znak, a putovi od korijena do određenih čvorova označavaju cijele riječi . Čvorovi koji završavaju riječi obično su označeni na neki način (na primjer, logičkim indikatorom) kako bi se razlikovali od jednostavnih prefiksa.

Ako pohranimo riječi „top“, „thus“ i „their“ u trie, dijelit ćemo dio početnog puta za sve one koji počinju istim slovima, što nam omogućuje izvođenje pretraga i prijedloga po prefiksu u vrlo učinkovitom vremenu , proporcionalno duljini riječi koju tražimo, a ne ukupnom broju pohranjenih riječi.

Uobičajene operacije i problemi s naredbom try uključuju: brojanje pohranjenih riječi , ispis svih riječi leksikografskim redoslijedom, sortiranje elemenata polja umetanjem u try, generiranje valjanih riječi iz skupa slova ili izgradnju struktura sličnih T9 rječniku.

U kontekstu intervjua, to nije najosnovnija struktura koju će tražiti, ali se redovito pojavljuje u tvrtkama koje rade sa sustavima za pretraživanje, obradu teksta ili prijedloge.

Hash tablice i hashiranje

Hashiranje je tehnika dodjeljivanja numeričkog ključa (hasha) svakom dijelu podatka na deterministički način, tako da možemo pohranjivati ​​i dohvaćati elemente u gotovo konstantnom vremenu, koristeći taj ključ kao indeks u unutarnjoj strukturi, obično nizu.

Hash tablica je struktura podataka koja koristi ovaj mehanizam. Svaki element pohranjuje se kao par ključ-vrijednost: ključ se pretvara u indeks tablice pomoću hash funkcije, a vrijednost (ili referenca na nju) pohranjuje se tamo. Kasnije, za pretraživanje, jednostavno ponovno hashirajte ključ i pristupite odgovarajućoj poziciji.

Performanse hash tablice ključno ovise o tri faktora: odabranoj hash funkciji (mora dobro rasporediti ključeve kako bi se izbjegle koncentracije), veličini tablice (nedovoljna veličina dovodi do mnogih kolizija) i metodi za rješavanje kolizija (ulančavanje s povezanim listama, otvoreno adresiranje itd.). To je slično indeksu baze podataka , gdje odabir odgovarajuće strukture poboljšava pretraživanje i pristup.

Tipične vježbe hash programiranja često zahtijevaju, na primjer, pronalaženje simetričnih parova u nizu , rekonstrukciju kompletnog itinerera putovanja iz pojedinačnih letova, brzu provjeru je li jedan niz podskup drugog ili provjeru jesu li dva niza disjunktna, a sve to koristeći približno O(1) pretraživanja hash tablice.

U većini modernih jezika, strukture mapa, rječnika, hash mapa ili hash skupova interno su podržane hash tablicama, iako se programeru nudi sučelje visoke razine.

Kako su algoritmi i strukture podataka povezani

Izbor strukture podataka izravno određuje koji algoritmi imaju smisla i koliko će biti složeni. Linearni algoritam pretraživanja na neuređenom popisu prolazi kroz elemente jedan po jedan; ako promijenimo strukturu u uravnoteženo stablo pretraživanja ili hash tablicu, postižemo puno brže rezultate.

Na primjer, ako želite više puta pretraživati ​​ključeve u velikoj kolekciji, pohranjivanje podataka u hash tablicu ili binarno stablo pretraživanja omogućuje vam dizajniranje puno bržih algoritama pretraživanja nego ako koristite jednostavan nesortirani niz. Isto vrijedi i za redove prioriteta i hrpe za raspoređivanje ili algoritme najkraćeg puta.

Suprotno tome, prilikom dizajniranja algoritma često shvatite da su vam potrebna određena svojstva: pristup indeksu, brzo umetanje na početku, hijerarhijski obilazak, pretraživanje prefiksa itd. Te potrebe vode vaš izbor strukture: nizovi, popisi, stabla, grafovi, hash tablice, petlje try-it i tako dalje.

Ova pravilna kombinacija algoritma i strukture podataka čini složene aplikacije učinkovitima i skalabilnima . Bez čvrste osnove, rješenja postaju spora, teška za razumijevanje i održavanje ili ih je nemoguće prilagoditi kako količina informacija raste.

Stoga, savladavanje algoritama i struktura podataka nije gotovo nužan zahtjev za svakoga tko teži postati kompetentan i konkurentan programer na današnjem tržištu rada.

Kako naučiti strukture podataka i algoritme

Mnogi se ljudi osjećaju zaglavljeno kada pokušavaju samostalno učiti s platformama poput LeetCodea ili Codewarsa . Uobičajeno je započeti s "jednostavnim" vježbama i dalje ne znati odakle početi, na kraju gledajući rješenje i ne znajući kako ga kasnije reproducirati.

Praktični pristup obično kombinira nekoliko sastojaka: dobro teorijsko objašnjenje svake strukture i algoritma, vizualne primjere, puno vođene vježbe i, ako je moguće, podršku nekoga s iskustvom tko vam može pomoći u usavršavanju vještina rješavanja problema.

U španjolskom govornom području postoje stručnjaci s bogatim iskustvom koji su pomogli u olakšavanju ovog učenja. Jedan primjer je rad nastavnika s iskustvom u poslovanju i obrazovanju koji su objavili knjige i tečajeve o osnovama programiranja, Javi, strukturama podataka i izazovima programiranja temeljenim na igrama, predstavljajući te koncepte na zanimljiv način koji je primjenjiv na projekte iz stvarnog svijeta.

Također je uobičajeno da akademije i centri za obuku u svoje programe za web developere ili programere aplikacija uključuju specifične module o strukturama podataka i algoritmima. U mnogim slučajevima naglašavaju vrlo praktičan, projektno utemeljen pristup , s vježbama sve veće težine i simulacijama tipičnih problema tehničkih intervjua.

Ako ste zapeli, može vam pomoći slijediti strukturirani put: počnite s nizovima i listama , prijeđite na stogove i redove čekanja, zatim na stabla i osnovne grafove, te na kraju na hash tablice i pokušaje, uvijek izmjenjujući teorijska objašnjenja, male primjere koda i puno individualne vježbe.

Za intervjue je preporučljivo pregledati ne samo strukture već i algoritme grube sile i pridružene klasične algoritme (prolaske, pretraživanja, sortiranje, jednostavno vraćanje unatrag, osnovno dinamičko programiranje) te se pobrinuti da možete naglas objasniti zašto ste odabrali određenu strukturu i koja je složenost vašeg rješenja.

S vremenom i malo upornosti , ono što se u početku čini kao zid, postaje skup poznatih alata koje gotovo instinktivno koristite kada se suočite s novim problemima.

Dobro razumijevanje algoritama, načina rada glavnih struktura podataka i njihovog međusobnog odnosa omogućit će vam pisanje bržih, jasnijih i robusnijih programa , otvoriti vrata u zahtjevnim procesima selekcije i osigurati da su vaši akademski i profesionalni projekti izgrađeni na čvrstim i budućnosti prikladnim temeljima.