Pogovor:Kopica

Iz MaFiRaWiki

Pri straneh o podatkovnih strukturah sem opazil več pripomb tipa "v praksi implementiramo dotično strukturo kar s tabelami" (npr. kopico ali dvojiško drevo). Zgodovinsko je to bilo res, ker so ljudje programirali v fortranu in so imeli na voljo samo tabele. Sodobni programski jeziki pa podpirajo rekurzivne podatkovne strukture, zato so take pripombe arhaične in morda celo škodljive iz vzgojnega stališča. Predlagam, da se v bodoče pokaže implementacijo podatkovne strukture v večih jezikih, da se da poudarek tistim implementacijam, ki podatkovno strukturo izražajo neposredno (in ne s pomočjo kake druge strukture, npr. tabele), ter da se omeni implementacijo s tabelo kot "zanimivost". AndrejBauer 08:19, 16 marec 2006 (CET)

S tem komentarjem se žal ne morem v celoti strinjati. Kopico se namreč skoraj vedno implementira s tabelo, saj se z rekurzivno implementacijo prav nič ne pridobi. Na implementaciji s tabelo temelji učinkovito urejanje s kopicami. Mogoče bi bilo dobro, če bi si obnovil znanje s tega področja in potem dopolnil svoj komentar. Strinjam se s tistim delom komentarja, ki vabi k različnim implementacijam podatkovnih struktur. Velika je namreč razlika med implementacijo kopice in dvojiškega drevesa. Pri dvojiškem drevesu je seveda v praksi implementacija odvisna od moči programskega jezika, ki ga uporabljamo. če imamo na voljo rekurzivne podatkovne strukture, je priporočljivo, da jih uporabimo.

Zanimvo vprašanje pa je, kako učiti npr. implementacijo sklada. Jaz npr. najprej pokažem, kako je mogoče sklad implementirati v Mathematici najbolj "prosto", vendar v praksi takšna rekurzivna implementacija in najbolj primerna. Še prej pokažem, da je mogoče tudi naravna števila implementirati "unarno". Tudi tu takšna neposredna implementacija in primerna. Potem povem, da imajo programski jeziki naravna (in cela ter druga) števila že vgrajena in je najbolje uporabljati kar takšno implementacijo. Povem tudi, da sklad v Mathematici lahko implementiramo kar s seznami (brez dela), povem pa tudi, da je mogoče sklad implementirati s tabelo. Mislim, da je takšna "arhaična" informacija koristna vsaj zaradi treh razlogov.

  1. Mislim, da današnji študent ne razume več osnovega delovanja računalnika in je brez sodobnega programskega jezika izgubljen, saj si ne predstavlja, kako v principu rešiti kakšen problem brez pripomočkov. Naj pojasnim z zgledom: mislim, da ni potrebno, da bi študent poznal aloritem za peš računanje kubičnega korena. Moral pa bi poznati vsaj eno numerično metodo, ki mu omogoča vsaj v načelu s svinčnikom in papirjem računati kubični koren iz 2. Podobno je s podatkovnimi strukturami. Mislim, da bi moral imet vsak študent ves čas trdna tla pod nogami. Tudi če nima na volj najbolj sodobnega računalnika, bi moral znati "peš" realizirati še tako komplicirano podatkovno strukturo.
  2. Pri skladu je implementacija s tabelo spet bolj učinkovtita, kot kakršnakoli rekurzivna rešitev. To je lahko pri računsko intezivnih postopkih, kjer gre za daljša računanja pomembno.
  3. Implementacije s tabelo olajšajo analizo časovne zahtevnosti osnovnih operacij nad podatkovno

strukturo.

Toliko v zagovor "arhaičnemu" pristopu. Seveda pa je mogoč tudi drugačen pristop. Recimo, da moramo uporabljati redke matrike. Namesto na naučimo študenta, kako je mogoče implementirati redke matrike s tabelo, ga raje napotimo na Matlab, kjer je to že vse zelo dobro implementiramo in mu povemo, da gre za "čudež", ki ga kakšen drugi programski jezik še nima. Samo to pomeni, da bi večino matematike in računalništva poučevali le kot veščino uporabljanja pripravljenih receptov. Namesto, da študent zna osnove odvajanja in integriranja, ga napotimo na Mathematico, namesto statistike, ga učimo uporabljati R, itd. TomazPisanski 08:23, 17 marec 2006 (CET)

Leva poravnanost

Kar se kopice in implementacije tiče še tole: Načeloma se včasih loči med tem, da ima dvojiško drevo "kopično lastnost" (vsak oče ni vmanjši od sinov) in da je kopica (tu se zahteva še leva poravnanost). Leva poravnanost je zahtevana ravno zaradi tega, ker so kopice predstavljene v tabeli in potrebujemo učinkovito predstavitev. Večkrat je bila kopica že definirana kot tabela v kateri velja, da je i-ti element ni manjši od 2*i in 2*i+1-vega (če seveda obstajata).

Res pa je, da se da vse skupaj narediti lepo tudi s poljubno implementacijo. Le vse tri relacije: oče, levi sin, desni sin potrebuješ. Seveda pa odpade (nima smisla govoriti o njih) del algoritmov (sestavi kopico, če elemente poznaš vnaprej, ...), določeni so precej neučinkoviti (poišči minimalni element, ...) Prav tako nima pomena zahtevati leve poravnanosti. In potem smo pri problemu izrojenosti, učinkovitosti algoritmov, ... --Matija Lokar 09:39, 29 oktober 2006 (CET)

Dve pripombi k levi poravnanosti:

  • Mogoče se splača ločiti pojma levo poravnano drevo in popolnoma levo poravnano drevo. Če definiramo levo poravnano drevo kot dvojiško drevo, v katerem je levo poddrevo največ za en nivo globlje od desnega (in to rekurzivno), med levo poravnana drevesa uvrstimo monoga AVL drevesa, ki pa niso "kopice", kakor pravi Matija. Pri popolnoma levo poravnanem drevesu imamo opravka drevo, ki ga dobimo iz dvojiškega drevesa z vsemi listi na istem nivoju, ki pa mu odvzamemo nekaj listov zaporedoma z desne strani.
  • Če bi kopico implementirali res z dvojiškim drevesom in ne s tabelo, bi seveda časovna zahtevnost osnovnih operacij ostala enaka: O(log n), zaradi dela s kazalci pa bi se dejanski čas najbrž povečal za konstantni faktor. Vprašanje pa je, kako težko je vzdrževati uravnoteženost drevesa ob zaporednem vstavljanju in brisanju elementov. Najbrž bi moral uporabljati tehnike, ki jih poznamo pri AVL drfevesih. Sam v resnici še nisem tega nikoli poskusil. Vedno pri kopici delam s tabelo.TomazPisanski 06:26, 31 oktober 2006 (CET)

Kako predstaviti podatkovne strukture

Predlagam naslednjo rešitev. Podatkovno strukturo se vedno najprej predstavi v njeni neposredni obliki, torej kopico kot zakoreninjeno drevo z dodatno strukturo. Potem se v razdelkih ali na podstraneh razloži, kako se to podatkovno strukturo učinkovito implementira, npr. kopico s tabelo. Še vedno se mi zdi pomembno, da študente učimo razliko med abstraktno podatkovno strukturo (kopica) in konkretno implementacijo (tabela). Kaj pravite? AndrejBauer 10:41, 29 oktober 2006 (CET)

Se strinjam. Le pri urejanju s kopico je potrebno vedeti, da je prednost kopice v tem, da je logično vse premisli v okviru kopic, fizično pa se urejanje naredi "na licu mesta" kar v tabeli, brez dodatnega prostora in kazalcev.TomazPisanski 15:30, 29 oktober 2006 (CET)

Osebna orodja