Červeno-čierne stromy

23.3.2010 23:41 | Přečteno: 4115×

V poslednom čase programujem dosť vecí do školy a tak som si povedal, že je škoda to niekam nezavesiť, nech majú z toho úžitok aj ďalšie generácie. Ako prvé budú červeno-čierne stromy...

V zimnom semestri som mal predmet Algoritmy a dátové štruktúry a ako nepovinný projekt si náš tím vybral červeno-čierne stromy, ktoré sa akosi ani nevyučovali, takže to bol trošku výber mimo rámec, no nejako sme to zvládli. Ale o čo vlastne išlo? Mali sme naprogramovať danú dátovú štruktúru, ktorá mala spĺňať nasledovné:

• vkladanie prvku
• vymazávanie prvku
• vyhľadávanie prvku
• vykresľovanie štruktúry
• všetky operácie, ktoré pozostávajú z viacerých krokov (rotácie v strome, prefarbovanie vrcholov, ...) sú naprogramované tak, aby sa dali krokovať
• štruktúru možno zapamätať do súboru a načítať zo súboru
• program má funkciu undo
• program má pohodlné ovládanie a dobrú vizualizáciu
• pomocou rôznych volieb sa dajú nastaviť parametre softvéru

Okrem vymazávania a krokovania sú implementované všetky veci zo zoznamu. Dokonca v kóde sa nachádza aj vymazávanie, avšak nie v použiteľnom stave. Viem, že nepoužitý kód nemá v zdrojáku čo robiť, avšak nechám ho tam, nech tam hnije. ;) Ou, skoro som zabudol - najhlavnejšou podmienkou bolo, aby sme to naprogramovali v Lazaruse, takže to bolo celkom obmedzujúce, no dalo sa - veď posúďte sami:

Keďže som autorom všetkého kódu, tak mi nerobí problém vypustiť to pod GPLv3, čiže užívajte v zdraví - balík na stiahnutie je v diskusí.

       

Komentáře

[Milan Lajtoš]

Příloha:

• rbt-0.3b.zip (30043 bytů)

viď. príloha

[Saljack]

Hele na jakou školu chodíš? Proč bylo podmínkou Lazarus? To ještě nějací zabedněnci pořád vyučují packala?

[Ondřej Profant]

No on se vyučuje často a pro vysvětlení základů procedurálního programování člověku, který nikdy neprogramoval je dobrý (velmi dobře čitelný). Čili na ten první semestr. Navíc je tak "primitivní", že každý cvičí ho může znát opravdu hodně dobře (zkus najít dost cvičících, co umí hodně dobře .NET, či Javu).

Třeba na MFF se taky první semestr učí, doporučuji přečíst: Jak učit programování?

[Dent]

To o té dobré čitelnosti Pascalu jsem nikdy nepochopil. V čem je dobře čitelný? Mě osobně ta bezzávorková begin-end syntax přijde krajně nepřehledná. Pokud je něco uvozeno závorkou, vím hned, že tam něco začíná, takže i při zběžném prolétávání kódem tak nějak vím, jak je strukturován. Begin a end jsou klasická slova, takže mi v kódu dost splývala se zbytkem a bylo to pro mě dost nepřehledné (a na odsazení nezáleželo). Fuj, ještě že už je to za mnou. { a } rulezzz :))

[Robo]

ja mam naopak radsej BEGIN ... END (PL/SQL); (IF .. FI v shelly a pod.); to, kde nieco zacina a konci robim odsadzovanim textu vo vnutri daneho bloku, takze mi to pride potom prehladnejsie; zatvorky mi pridu naopak neprehladne, ak su tam viac ako jedny, zacinam sa v tom stracat a tazko sa rozlisuje {} od ()

[Dent]

Asi je to o zvyku. Řekl bych, že každý považuje za jazyk vhodný pro začátečníky ten, na kterém sám začínal.

[Milan Lajtoš]

Musím nesúhlasiť. Mojím prvým programovacím jazykom bol Pascal a myslím si, že Python by bol pre začiatočníkov vhodnejší.

[rajcze]

Musim nesouhlasit, Python je sice muj nejmilejsi jazyk, ale na vyuku programovani je IMHO stale nejlepsi Pascal. I kdyz pominu takove triviality jako nepritomnost "bezneho" for cyklu, nebo switch-case, tak Python porad dela pomerne neprijemnej maglajz treba s mutable/immutable objekty. Co se didaktickeho hlediska pro _nauceni se programovani_ tyka (tj. kdyz ty lidi potrebujes naucit _myslet_ ne neco nabastlit a ono to mozna pojede), neznam zatim nic lepsiho.

Ano, Pascal ma samozrejme svoje nevyhody (fuj objektovemu programovani v turbo pascalu), ale vylozene neprijemny je jen u veci, ktere stejne ucis na takove urovni (v idealnim pripade) kdy je tem lidem jedno, jaka je syntaxe toho konkretniho jazyka, ve kterem pisou, ale je dulezite, aby pochopili princip.

[Milan Lajtoš]

Aby sme mali jasno - pod pojmom "začiatočník" myslím človeka, ktorý naozaj nikdy nevidel žiaden programovací jazyk a absolútne nemá žiadne základy algoritmizácie.

Mne príde Python vhodný vďaka tomu, že je dynamicky typový. Človeku sa premenná vysvetlí ako krabička, do ktorej môže niečo dať. A keď mu poviem, že tam môže dať hocičo, tak je to super, pretože mu nemusím vysvetľovať aké dátové typy tam môže dávať a vôbec že nejaké dátové typy sú. (Neskôr sa k tomu aj tak dostanem, no...)

Na druhej strane by mal programovací jazyk "rásť" s človekom. Ako sa postupne učí nové veci, tak to všetko by mal programovací jazyk zvládať. V Pythone, či Jave sa nikdy nenaučím o smerníkoch, či v C++ nikdy o Lambda výrazoch (v C++0x že vraj budú).

V konečnom dôsledku, programovací jazyk má byť len nástroj na odskúšanie si svojho myslenia, teda algoritmu, nie bastliť - ako si trefne napísal.

[rajcze]

Na pojmu zacatecnik se, myslim, naprosto shodneme :)

Jasne, dynamicke typy a silna typova kontrola jsou svym zpusobem fajn, ale muze to byt dvojsecna zbran - ono kdyz ti uz prekladas rekne, ze scitat cislo s retezcem je kravovina, tak to IMHO taky trochu dopostrci to mysleni smerem "jak to vlastne funguje, ze to nejde" mozna spis, nez kdyz jednou nahodou zadas spatnej vstup a vybleje to na tebe vyjimku o nekompatibilite typu.

Je pravda, ze co se "rustu s clovekem" tyka, je python hodne silny (rozhodne si netroufam tvrdit, ze skvele zvladam alespon tretinu jeho skutecnych moznosti, a ze v nem delam peknych par let).

On problem "prvniho jazyka" je asi nerozhodnutelny, jedine, co vim jiste, je, ze C neni ten nejlepsi prvni jazyk :) Doucuju ted jednu slecnu (prvak gymplu) programovani - tedy snazim se ji naucit myslet - a ta si teda Pascal ve srovanani s Cckem (ve kterem zacinaji ve skole) pochvaluje. Premyslel sem o Pythonu, ale tam me odradily fakt predevsim mutable/imutable objekty, takze nemuzes smysluplne popsat predavani parametru hodnotou/odkazem, protoze v pythonu se sice _vzdy_ predava odkazem, ale holt immutable objekt nezmenis a libovolna operace nad nim vytvori novou instanci, takze se to tvari jako predane hodnotou. A pak na Pythonu vysvetli reference/dereference v Ccku...

[Saljack]

A co si třeba na tom Pascalu pochvaluje a na C nadává? Mě by celkem zajímali takové pohledy člověka co začíná já z mého pohledu bych se nejraději zezačátku vyhnul Pascalu velkým obloukem.

[Michal Vyskočil]

Naopak, Pascal (alespoň ten Turbo) je něco jako těžko na cvičišti, lehko na bojišti Na druhou stranu unit crt a hlavně turbo vision - to byla věc, to se s (n)curses nedá srovnat.

[rajcze]

Asi ti to bude znit divne, ale syntaxe Pascalu ji prijde primocarejsi a min krypticka nez Ccka. Mimo jine taky kompilator Pascalu negeneruje tak otresny chybove hlasky (kolikrat by ses az divil, co dokaze vyplodit v Ccku zapomenutej strednik...).

Me by zas zajimalo, proc by ses chtel pascalu na zacatku vyhybat? Ja se klidne priznam k tomu, ze kdyz nas na gymplu nutili programovat v Pascalu, tak to byla tezka otrava, predevsim pro tech par lidi, co umeli programovat a Pascal otravoval svou ukecanou sytaxi: "Proc mam ku*va psat a = a + 1, kdyz a++ je tak krasne...", a posleze i tou nejsilenejsi implementaci OOP ever (na druhou stranu, napsal jsem v tom objektovou GUI knihovnu pro DOS, takze proc ne...).

Ale jak porad opakuju, pokud je cilem naucit se myslet, je Pascal fajn, protoze zbytecne nekomplikuje bezne cinnosti, a v mnoha pripadech je syntakticka ukecanost vykoupena nazornosti kodu (aneb function/procedure vs. [typ]/void - ano je to to stejne, ale to prvni je nazornejsi). Ve chvili, kdy te zacne pascal svazovat, tak si pravdepodobne na urovni, kdy uz neco jako syntaxi neresis (ukaz mi jazyk jehoz sytaxi se nejde naucit za maximalne pul dne), protoze te zajimaji funkcni vlastnosti jazyka.

[Saljack]

Právě kvůli té v celku nelogické syntaxi a hlavně deklarování proměnných, polí atp. to je podle mě v Pascalu to co prostě nepřekousnu. Prostě se v té syntaxi vůbec nedokážu orientovat protože begin a end na první pohled splívají s ostatním kódem. Dále mi přijde jako naprostá blbost používat pro přiřazení := a pro porovnání = to je pro mě naprosto nelogická věc. Objektově bych v tom po zkušenostech ve škole nikdy nic nedělal, to bych raději neprogramoval už nic, protože člověk co to tam implementoval to neměl v hlavě asi v pořádku. Ale co když někomu přijde syntaxe pěkná tak je to jeho věc. Stejně asi holčina dál s programováním nepočítá.

[rajcze]

Ad nelogicka syntaxe - zalezi _proc_ je to pro tebe *nelogicke* - pokud je to pro to, ze "vsude jinde se prirazuje = a porovnava ==" tak je to otazka zvyku, ne logiky.

Co ti prijde nelogickeho na deklaracich v Pascalu, me osobne tam nic nerusi. Jasne, nemuzes si vytvorit promennou jen pro jeden blok kodu, aniz bys ten blok kodu vystrcil do procedury/funkce, ale uprimne, jak casto potrebujes neco takoveho delat?

Nesnadne orientovani se v kodu - jasne, muzu souhlasit s tim, ze pokud nemas zvyraznovani syntaxe, muze ti pripadat begin/end vice splyvajici, nez {}.

Na objektovym programovani v turbo pascalu je bohuzel videt, ze je tam dobastleny az post mortem. Na druhou stranu ObjectPascal (tj. Delphi) je naprosto v pohode.

Ja osobne bych v soucasnosti taky v Pascalu nechtel programovat, ale ne proto, ze bych ho nejak nenavidel (tim sem si prosel na gymplu ). Pascalu pro me potreby chybi siroka zakladna knihoven, kterou mi muj oblibeny Python poskytuje. Je ale potreba si uvedomit rozdil mezi jazykem urcenym pro _vyuku programovani_ (tj. mysleni) a jazykem primarne urcenym pro realne pouziti v praxi.

[mkoubik]

Jasne, nemuzes si vytvorit promennou jen pro jeden blok kodu, aniz bys ten blok kodu vystrcil do procedury/funkce, ale uprimne, jak casto potrebujes neco takoveho delat?

V každém for-cyklu? Ono for (int i=0;i<length;i++) je o trochu menší prasárna než int i; for (i=0;i<length;i++), ale nevim jak se to dělá v pascalu - neviděl jsem ho od maturity.

[Michal Kubeček]

Dost praktické to může být třeba i v definici makra, např.

#define SYSTEM_ERROR(x) { \
  std::ostringstream errmsg; \
  errmsg << x; \
  throw system_error(errmsg.str()); \
}

[rajcze]

To bysme si jeste meli ujasnit, jaky standard Ccka berem v uvahu (ne, dobre, tohle bylo jen zlovolne rypnuti, chapu tvuj priklad). Na druhou stranu, proc ti prijde lepsi deklarovat a definovat ridici promennou cyklu v hlavicce cyklu, nez vyrobit si ji "na zacatku" (u vsech ostatnich deklaraci promennych)?

[Michal Kubeček]

Je to stylově čistší v tom, že je tím jasně deklarováno, že proměnná je lokální pro daný cyklus a pokud se někde později vyskytne stejnojmenná proměnná, nemá s ní naprosto nic společného. Někdy to třeba může pomoci odhalit zapomenutou inicializaci, kterou by její nechtěná inicializace předchozím for cyklem zamaskovala.

Za sebe můžu říct, že postupem času mi začala filosofie "deklarovat až když je potřeba a jen tam, kde je potřeba" být trochu bližší než původní "všechno se nadeklaruje na začátku" a jsem docela rád, že C99 tuhle možnost z C++ převzalo.

[Michal Kubeček]

Dále mi přijde jako naprostá blbost používat pro přiřazení := a pro porovnání = to je pro mě naprosto nelogická věc.

IMHO je to dost logické, ale nepříliš praktické. Dokonce bych řekl, že takové detaily dobře ilustrují rozdíl mezi Wirthovým a K&R přístupem: Kernighan a Ritchie ve své knize dokonce uvádějí, že když se rozhodovali, udělali si na nějakém vzorku svých programů statistiku a zjistili, že přiřazení je podstatně víc než porovnání na rovnost. Proto zvolili jednodušší symbol pro přiřazení. Naopak Wirth se podle všeho rozhodoval spíš podle logiky a přirozenosti. Takových příkladů se dá najít víc - např. nikoho, kdo se aspoň na chvíli zamyslel nad praktickou stránkou věci, by nemohlo napadnout dát logickým operátorům vyšší prioritu než porovnání; Wirth to očividně neudělal, takže se každý test, zda hodnota leží v intervalu, musí závorkovat.

[Saljack]

No právě z toho důvodu, že přiřazuješ víc než porovnáváš mi to příjde nelogické.

[Michal Kubeček]

Z hlediska logiky "uděláme to tak, aby to bylo praktické" ano. Ale měl jsem na mysli trochu jinou logiku. Když člověku nezatíženému programováním vysvětlím, co je to proměnná, ukážu mu nápis "a = 3" a zeptám se ho, jak by si ho vyložil, většina ho IMHO bude považovat za porovnání, ne za přiřazení. Pro přiřazení se spíš nabízí něco jako "a ← 3" nebo ještě spíš "3 → a". Dokonce naopak řada matematiků převzala pascalové "a := 3" a používá ho pro "položme a rovno třem".

[Saljack]

Ono mezi námi tomu kdo se učí programovat je celkem u p..., že = je přiřazení pro ně je to to samé jako a se rovná 3, tudíž je zde to rovná se správně .

[Vskutečnosti Saýc]

No jasne. V matice kde se fakt prirazuje (takovy eukleiduv algoritmus, atd) taky najdes :=, a = je znak normalni rovnosti.

[Kvakor]

Ano, u "prvního jazyka" je dilema, jestli je lepší mít první jazyk vysokoúrovňový nebo spíš nízkoúrovňový. V tom prvním je výhoda, že se při jejich použití nemusí řešit žádné nízkoúrovňové problémy, ale na mnohá proč musíte odpovídat stylem "Protože bagr".

To u nízkoúrovňových jazyků není problém, tam se to dá vysvětlit přes samotné fungování počítače (jako např. rozdíl předávání hodnoutou vůči předávání odkazem), ale za cenu všech nevýhod nízkoúrovňového přístupu, kdy jazyk podporuje jen nutné minimum a zbytek si musíte dodělat sami, plus problémy s laděním, hlavně dynamických chyb.

Jako jediné rozumné řešení mi zatím vychází začít sice s vysokoúrovňovým jazykem, ale přidat nějaký nízkoúrovňový tak brzo, jak je to jen možné, plus alespoň základní vysvětlení funkce počítače. V opačném případě na konci vyleze buď programátor, který bude používat metodu "kanón na vrabce" a páchat pomalá a paměťově nenažraná monstra, nebo naopak bude mít tendenci kopat Panamský průplav polévkovou lžící, protože nebude znát vhodnější nástroje.

Pascal mi z toho vychází jako pokus smrsknou tyto dva kroky do jednoho - jazyk, který je sice relativně nízkoúrovňový, ale většina potenciálně nebezpečných konstrukcí je zakázána (alespoň ne ve stadnardní verzi). Jsou tu i vlastnosti z vyšších jazyků, kde se překladač sám postará o nízkoúrovňové záležitosti (např. procedury Write/WriteLn a jejich magické "automatické" parametry), ale je jich relativně málo.

Jako jazyk "sám o sobě" není špatný, pokud se použije pro výuku neprogramátorů, ale v opačném případě je tu prbklém právě v té "kočkopsovitosti" - pro ty, co pak budou programovat v něčem jiném (což budou téměř určitě tak jako tak muset), to bude znamenat nutnost odnaučit se zbytečně mnoho věcí.

Je to jako učit se jezdit na tříkolce - je bezpečná a na první pohled má to nejlepší z obou světů, ale budoucí (moto)cyklisti se na ní nenaučí držet rovnováhu a pro automobilisty je to zas příliš podobné kolu.

[rajcze]

Nemuzu nesouhlasit :) Jen mi prijde, ze ta "kockopsovitost" neni zas tak kriticka. Na druhou stranu je otazkou, jestli to muzu objektivne posoudit - ja sem se zacal ucit programovani v SGP Baltazar, ktery me naucil myslet a Pascal na gymplu ve me IMHO nezanechal pocit, ze bych se musel neco odnaucovat - jenze jak rikam, pro me jazyk neni vic nez syntakticky cukr, ktery vice nebo mene usnadnuje konkretni vyjadreni abstraktnich myslenek...

[Michal Vyskočil]

V Pythone, či Jave sa nikdy nenaučím o smerníkoch, či v C++ nikdy o Lambda výrazoch (v C++0x že vraj budú).

No vzhledem k tomu, že drtivá většina výuky C směrníky používá ve smyslu obyčejné reference někam, tak si troufám říct, že se o nich člověk nic moc nenaučí ani v C.

BTW: Java RealTime Specification umožňuje přímý přístup k paměti .

[Saljack]

Ale proč přistupovat v Jave přímo k paměti? Nejen, že je to "nebezpečné" ale Java ani tak navrhnuta není. Od tohoto jsou právě jiné jazyky. Já si stejně myslím čím míň se do toho člověk sere tím míň může posrat .

[Michal Vyskočil]

Tak taková komunikace s HW se bez přímého přístupu do paměti neobejde a RTS umožňuje psát i ovladače pro zařízení v Javě. Tuším, že J2ME má něco podobného.

Ale hlavně to ilustruje, jak jsou proklamace typu V Pythone, či Jave sa nikdy nenaučím o smerníkoch zavádějící. Nejenže směrníky jsou při troše dobré vůle i v té Javě, tak především z prakticky žádné výuky jazyka C se nedostaneme nad to, co by reference z ostatních jazyků nezvládaly taky.

[trekker.dk]

Mě osobně ta bezzávorková begin-end syntax přijde krajně nepřehledná.

Naprosto jasně: begin znamená začátek, end znamená konec. Na první pohled je z toho zjevné, co to má znamenat.

Závorka je jenom obrázek, jehož význam si musíš domyslet.

Begin a end jsou klasická slova, takže mi v kódu dost splývala se zbytkem a bylo to pro mě dost nepřehledné (a na odsazení nezáleželo).

Od toho existují editory se zvýrazňováním syntaxe (nebo přesněji existují editory, které zvýrazňovat syntaxi neumí, i když teď mě žádný nenapadá)

[Saljack]

Tenhle argument pořád nechápu. Pascal je podle mě má nejhorší syntaxi ze všech jazyků co znám. Myslím si, že pascal opravdu ani ve výuce nemá místo natož v "pořádném" (teď se zase strhne flame). Ale hlavně si myslím aspoň u nás na střední to tak bylo, že se v pascalu všichni plácali. Nevidím důvod, proč nyní již od začátku nezačít s nějakým objektově orientovaným jazykem (kor na vysoké škole). Přitom je tolik jazyků, které jsou 100x vhodnější pro začátečníky např. C nebo Python. Hlavně Python se mi jeví jako nejlepší volba pro začátečníka. To, že se tvrdilo, že Pascal je vhodný pro začátečníka před 20 lety, za 1. již dnes naprosto neplatí a je to hrozný blábol a za 2. už v té době to byl blábol protože C mi příjde daleko přívětivější a jednoduší na pochopení než Pascal.

[Radek Miček]

Nevidím důvod, proč nyní již od začátku nezačít s nějakým objektově orientovaným jazykem

Nevidím důvod, proč začínat s objektově orientovaným jazykem

Pascal je podle mě má nejhorší syntaxi ze všech jazyků co znám

Ale většina knih i článků o algoritmizaci používá velice podobnou syntaxi.

Osobně si myslím, že pro začátečníka je důležitá jednoduchost (a logičnost) syntaxe a sémantiky.

[Saljack]

Proč začínat s objektově orientovaným jazykem? Třeba proto, že skoro všechno je napsáno za pomocí objektově orientovaných jazyků nebo při pochopení principu to dost usnadňuje práci a bez znalosti objektového programování se nikam nehnete.
Většina knih a článků se pouze tváří jako že jsou o algoritmizaci ve skutečnosti jsou to pouze učebnice určitého jazyku. Logičnost syntaxe u Pascalu v porovnání s třeba C nebo Pythonem snad nemá ani cenu komentovat.

[Vskutečnosti Saýc]

Neucit lidi programovat objektove od zacatku ma svoje vyhody 1) je mensi sance ze budou produkovat priserny bloatware 2) objektove programovani je pro spoustu problemu (dost mozna vsechny krom GUI) slepa ulicka 3) u jednoduchych jazyku se snadno uci algoritmy, protoze muzu vyzkouset jak pracuji

Zalezi pochopitelne na tom, koho chcete vyprodukovat, jaky druh programatora. Namezdny busic javy nebo php jsou neco jineho nez nekdo kdo ma programovat vnitrky operacnich systemu nebo AI, zejo.

Pokud jde o algoritmizaci, zase, nizsi jazyky jsou pro tyhle ucely lepsi pomucka. Pochoptelne ze "webovy inzenyr" nepotrebuje vedet jak funguje ten rb strom, kdyz ma v php asociativni pole ktere ty rb stromy samo obsahuje (pokud si dobre vzpominam. mozna to jsou jiny stromy), nebo jak funguje dijkstra. Ale nekdo taky pise PHP nebo idos, zejo.

Tomu o tech knizkach moc neverim, vetsina knizek je budto "naucte se programovat v pythonu" (tedy "zaklady programovani + zaklady pythonu"), design patterny, kecy okolo (coz muze byt snadno nejlepsi literatura kolem, jako "art of unix programming" a podobne), a nebo drsna teorie, kterou snad dneska ani nikdo necte :)

[Saljack]

Objektové programování se dá využít skoro všude a u psaní různých věcí, které budou dále použity hlavně. Umělá inteligence je úplně něco jiného. Není totiž problém to pochopit, ale najít někoho kdo vám to vysvětlí a úplně nejhorší příklad na vysvětlování je ten klasický s kružnicí a bodem z toho to snad nikdo nikdy nepochopil a stejně to profesoři znovu a znovu vykládají na tomhle příkladu. To s těma knížkami jsem myslel přesně jak jsi napsal ty. Hlavně nechápu proč třeba u nás na FEL je předmět algoritmizace, když je to normálně základy javy.
Ještě bych dodal, že nechápu proč se na FELu vyučuje jako první jazyk Java, který je pro tento účel naprosto na nic, prostě by se mělo učit C a C++ a až potom Java.

[Vskutečnosti Saýc]

Objektove programovani ale neni vselek, a spousta kusu software o kterych se da rict ze nemaji konkurenci nemaji s objektovym pristupem mnoho spolecneho, takove openssl, apache, vnitrek linuxu, klasicke unixove nastroje a tak dal.

U FELu a jinych programovacich kurzu (kursu? nekdo me kdyztak opravte) jde o jinou vec, ony to jsou fakt naproste zaklady, a pokud uz vis co je cyklus, jak funguji podminky, co je to datovy typ a jak vypada spojovy seznam (pokud si tu Algoritmizaci pamatuju spravne :) ), tak ti to musi nutne pripadat jako zaklady javy, ale ten predmet je fakt urceny pro lidi kteri nevi co je cyklus.

A pro tyhle ucely se libovolny (imperativni, atd) jazyk hodi skoro stejne, a rozhoduji takove veci jako jak snadno se da dostat k vyvojovym nastrojum a tak, a nakolik muze byt pro nekoho zvykleho na unix s cc(1) vzdy na dosah ruky sokujici, pro Windows to s vyvojovymi nastroji neni tak zhave. Vyvojovych nastroju pro javu je pritom dost, a daji se provozovat na kdecem.

Ale pro tohle by python mozna byl lepsi, to je fakt. U predmetu jako DSA (na felu) uz bych si jisty nebyl.

[trekker.dk]

kterych se da rict ze nemaji konkurenci nemaji s objektovym pristupem mnoho spolecneho, takove openssl, apache, vnitrek linuxu, klasicke unixove nastroje a tak dal.

Vnitřek Linuxu je hodně objektově orientovaný. Jenom na to nepoužívá objektový jazyk

[mkoubik]

Jaký příklad s kružnicí a bodem? Asi jsem byl systémem vzdělávání zanedbán. Jinak algoritmizace je totální výsměch. Polovina lidí tam nikdy neprogramovala a je cílem je za 13 cvičení naučit vytvářet projekt v NetBeans, opisovat kód z tabule a spouštět kompilaci. Zbytek programovat umí a nudí se tam u výkladu cyklů.

Nerozhodnutelnost problému výuky objektového vs. procedurálního programování lze krásně ilustrovat na jave: "Takhle se vypisuje na výstup, takhle se dělá podmínka, takhle cyklus, toho class Abc si zatím nevšímejte" vs. "Takhle se definuje třída, takhle se vytváří objekt, toho public static void main si zatím nevšímejte".

[Vskutečnosti Saýc]

V jave, zejo. Ucit se v pascalu proceduralne, ve smalltalku objektove, v haskellu funkcionalne ... to by bylo pekny, ale dost studentu by zesilelo :)

[Radek Miček]

Asi, že kružnice není speciální případ bodu, takže by kružnice neměla být potomkem bodu.

[Vskutečnosti Saýc]

Ono to vubec s napasovavanim objektovych paradigmat na realitu neni tak zhave. U GUI (okna obsahuji okna, tlacitka, menu, podokna, blabla, vsechno jsou to potomci grafickeho objektu, OK je potomkem tlacitka, atd.) to jde fakt dobre, a OOP tam nema konkurenci.

Jinde uz je to horsi, Zvlast kdyz "mutable state" a "concurrency" jsou veci ktere se nemaji moc rady.

[mkoubik]

Záleží co s těmi objekty chceš dělat, dovedu si představit, že za určitých okolností by to mělo smysl. Závěr: ilustrovat programátorské poučky na objektech z reálného světa, navíc vytržených z kontextu je blbost.

[Radek Miček]

Já jen objasňoval, oč zřejmě jde.

[Saljack]

Myslím něco jako je tady, už jenom proto, že je to "navrženo špatně". Hlavně kvůli tomu, že ten kdo to nikdy neviděl, tak to z tak debilního příkladu nikdy nepochopí, to je tak těžké vymyslet jiný příklad. Někde byl krásný příklad se zvířaty, z kterého to pochopí každý, také náš přednášející na objektové modelování má krásné příklady, z kterých to opravdu pochopí každý.

[rajcze]

Dovolim si s tvym tvrzenim o "privetivejsim" Ccku nesouhlasit. Rozhodne pro zacatecnika privetivejsi neni.

Mozna bysme si meli nejprv ujasnit, kdo ze je to ten "zacatecnik" a co ho chces naucit - zacatecnik je clovek, ktery neumi programovat - tj. neumi _spravne myslet_ a _nerozumi tomu, jak vevnitr funguje pocitac_.

Kdyz vezmu jen tak hloupy priklad, jako nacteni neceho ze vstupu - v packalu naprosto jednoduche a prime Read(), v Ccku uz musis tusit, co ze je to ukazatel.

Lepsi priklad - predavani parametru proceduram odkazem - zkus zacatecnikovi vysvetlit jak funguje reference/dereference - v tomhle jsou ochotni delat blbosti i vysokoskolaci. V pascalu opet velmi primocare odliseni v definici hlavicky funkce.

Z meho pohledu neexistuje pro splneni cile _naucit lidi myslet jako programator_ lepsi jazyk, nez pascal. Ve chvili, kdy umis myslet, je ti naprosto sumak, jak vypada syntakticky cukr toho daneho jazyka (a ano, pravdepodobne ti bude vadit desiva ukecanost pascalu, tak jako me treba vadi ukecanost javy...)

Co se pythonu tyka, rozhodne je to lepsi volba nez Ccko, ale taky ma svoje mouchy (predevsim mutable/immutable objekty) (nez se zeptas - python je muj nejmilejsi jazyk).

[Andrej]

Packal je podle mě nejhorší odpad mezi programovacími jazyky. Kdyby nevznikl, mohlo být na školách (a možná i na světě) lépe.

Packal kombinuje nevýhody nízkoúrovňových jazyků (nemá garbage collection, negarantuje konzistentní paměťové reference, podpora pro dynamicky alokované struktury je ubohá, rozumná práce se stringy prakticky neexistuje) s nevýhodami vysokoúrovňových jazyků ((téměř) žádná přímá práce s pamětí, žádná aritmetika pointerů). K tomu přidává další (těžko klasifikovatelné) nevýhody, například nesmyslné indexování polí od 1 a hloupou volací konvenci, která (mimo jiné) předem vylučuje variadické funkce.

Packal vymyslel teoretik, který netušil, jak má jazyk vypadat, a všechno zpackal. Cokoliv je lepší. Všechny ostatní jazyky mají jakousi rozumnou ideu. Drtivá většina jejich nevýhod se dá ospravedlnit výhodami, které z toho plynou. Packal má jen samé nevýhody a na oplátku nenabízí vůbec nic.

[Saljack]

Pěkně si to shrnul. Tohle by si měl přečíst každý profesor, který chce učit Pascal.

[Radek Miček]

například nesmyslné indexování polí od 1

Indexuje se od čísla, které si určí programátor, navíc se může indexovat i výčtovými typy.

Novější Pascaly, co se dnes učí na školách, si v některých věcech polepšily.

[Andrej]

Pravda, poznámku ohledně indexování beru zpět. To jsem si spletl s jiným nepovedeným jazykem.

Nevím, které Packaly se dnes učí. Já jsem zažil FPC a GPC. Samozřejmě je pěkné mít v Packalu pointerovou aritmetiku nebo operátory typu +=. Ale není pak lepší prostě místo toho použít C?

Pokud se těmi „novějšími Packaly“ rozumí něco kolem Lazarusu nebo (už dávno mrtvého) Delphi, ani tohle není žádná výhra. O zásadních chybách v návrhu ObjectPackalu by se daly napsat celé stránky. Nemyslím si, že by se něco takového mělo učit.

[Radek Miček]

Ano, myslel jsem nové Delphi případně Delphi Prism. Bohužel ty jazyky nejsou vzájemně kompatibilní.

[Ladicek]

Ha, díky za odkaz na Delphi Prism, to vypadá jako moc pěkný jazyk! Jinak ale bohužel souhlasím s tímhle.

[Andrej]

BTW, přece jen tam s tím indexováním byl nějaký problém, ale týkal se pouze stringů. Pokud si to správně pamatuju, stringy měly maximálně 255 B a na indexu 0 byl byte s délkou stringu. Tudíž string samotný byl indexovaný od 1. Pokud vím, některé implementace byly navržené tak nesmyslně, že všechny stringy kromě konstantních se alokovaly napevno po 256 bytech bez ohledu na skutečnou délku.

V novějších Packalech se samozřejmě objevila jiná reprezentace, která už nesmyslná omezení nemá.

[Milan Lajtoš]

Na FMFI UK. Ono to bolo tak, že sa využívalo najmä Delphi alebo Turbo Delphi, no nejako zmizla free verzia, takže hľadali alternatívu a keďže Lazarus je asi pre nich najprijateľnejší, resp. takmer to isté, tak nemali čo riešiť.

[Martin Matějek]

Zajímavé. Teď zrovna píšu úkol, kde se používá binární strom (vyhledávání musí mít složitost log(N)), tak by mě zajímalo v čem je Červeno-černý strom specifický od binárního. Nebo co že to vlastně je... zas tolik se v tom nevyznám. Jinak pěkné, já bych neměl nervy na to psát gui. Určitě bych strávil víc času psaním gui než samotných algoritmů.

[Milan Lajtoš]

V binárnom strome môžeš mať vyhľadávanie O(log n), no musíš ho mať vyvážený. Predstav si binárny vyhľadávací strom, ktorý je ako reťaz (všetky vnútorné vrcholy majú len pravého/ľavého syna) - v tomto prípade bude mať vyhľadávanie zložitosť O(n). Pri vyvážených stromoch máš zaručené, že sa ti niečo také nestane a teda budeš mať garantovanú zložitosť O(log n).

A čo sa týka toho GUI - tvoj názor je správny, viac kódu je pre vykresľovanie a veci okolo. ;)

[Vskutečnosti Saýc]

Kolega uz psal ze binarni strom musi byt vyvazeny, ja doplnim, ze rb strom se vyvazuje sam, a s i docela jednoduchym algoritmem ti garantuje, ze ten strom nebude hlubsi (hur vyvazey) nez je minimalni mozna hloubka (nejvetsi vyvazenost) krat nejaka konstanta (tusim (1.42?), takze se chova predvidatelne a tak.

Je to oblibeny peklo pro mlade studenty CS :) ale dost se to pouziva, treba sociativni posle ve sposute dynamickych jazyku maji uvnitr rb stromy.

[xxx]

To chci. Strom co se vyvazuje sam. Jako, ze se na nej podivam a on se vyvazi :) Ja bych spis rek, ze se po vlozeni podivam co vzniklo a nekterych pripadech provedu rotace.

[Vskutečnosti Saýc]

Myslim pri pohledu zvenku, samozreme :)

[ivan]

RB stromy predstavuji rozumny kompromis mezi casem postrebnym pro usporadani struktury a casem na vyhledani. Predstav si, ze cerne vrcholy RB stromu tvori idealne vyvazeny binarni strom a ceverne jsou vlastne jen takovej bordel kterej do toho stromu muzes pridavet aniz bys' musel ten strom nejakam narocne dovyvazovat.

Dalsi uzitecna vlastnost RB stromu je minimalni(konecny) pocet rotaci, ke kterym dochazi pri vyvazovani. Kazdy vrchol muze nest navic nejakou zajimavou informaci(napr. "je v mem podstromu prvocislo?, "vede z meho listu cesta k nejakemu jinemu RB stromu?") takovou informaci je nutne aktualizovat prave pouze pokud dochazi k rotaci.

[Vskutečnosti Saýc]

Hashtabulky maji casto rychlejsi pristup pro zapis i cteni. Vyhodou stromu je, ze nemusim predem vedet kolik dat je (kdezto u hashtabulky byva problem kdyz mam najednou prijde trikrat vic dat nez jste pocital), a stromy se lip iteruji, protoze kdyz ho projdu a vysypu data, dostanu je usporadane, kdezto z hashtabulky mi vypadnou vicemene nahodna data. Stromu je taky jedno, jaka v nem ukladam data, kdezto hashovani ma tendeci se obcas nahodou rozbijet, kdyz vam system z niceho nic zacne generovat divna id programu a dalsi veci ktere neovlivnite.

(fakt tu delame distribuovanou prednasku o datovych strukturach?)

[Martin Matějek]

Děkuji všem za distribuovanou přednášku Zase jsem o něco chytřejší

[Radek Miček]

Když už jsme u vkládání do červeno-černých stromů, tak takhle to lze udělat v jazycích, které mají pattern matching (toto je Haskell):

data Color = R | B
data RB a = E | T Color (RB a) a (RB a)

insert :: Ord a => a -> RB a -> RB a
insert x s = T B a z b
  where
    T _ a z b = ins s
    ins E = T R E x E
    ins s@(T B a y b) | x<y       = balance (ins a) y b
                      | x>y       = balance a y (ins b)
                      | otherwise = s
    ins s@(T R a y b) | x<y       = T R (ins a) y b
                      | x>y       = T R a y (ins b)
                      | otherwise = s

balance :: RB a -> a -> RB a -> RB a
balance (T R a x b) y (T R c z d) = T R (T B a x b) y (T B c z d)
balance (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance a x b = T B a x b

Kód jsem si půjčil ze stránky Red Black Trees

[Senior Database Programmer]

No a čo ste dostali za známku keď vám tam polovica vecí chýbala?

[Robert Krátký]

Viz také popis v JN: Red-black stromy.

[Jardík]

Proč jsou ty ikony kostrbatý? U mě na Windows normálně Lazarus umí alpha kanál ...