wz

HeapSort - Tajemství odhaleno :)

Ξ February 28th, 2007 | → 24 Comments | ∇ Uncategorized |

Před pár dny jsem se začal zabývat HeapSortem, protože je to neskutečně rychlý (jeden z nejrychlejších vůbec), paměťově nenáročný (nerekurzivní) třídící algoritmus. Ku příkladu pole, které má BubbleSort seřízené za 2 sekundy, má heapsort za 16 milisekund. Dlouho jsem nemohl přijít na to, jak funguje a štvalo mě to. Teď, když jsem sám ručně setřídil pomocí heapsortu 14timístné číslo (na gauči :)), jsem spokojen.

Základem HeapSortu je datová struktura nazývaná Heap. Heap je vlastně takový strom, jehož jedna větev má pouze dva potomky a potomci potomků mají také pouze dva potomky. Z číselné řady vytvoříte Heap tak, že vezmete první číslo - to bude rodič a přiřadíte mu dvě další po sobě jdoucí nepoužitá čísla jako potomky (nepoužitá zn. nepoužitá do heapu ani jako rodič ani jako potomek). Následně vezmete další číslo (jeden z potomků prvního rodiče) a přiřadíte mu další dva nepoužitá čísla jako potomky. Takto postupujte až do konce řady. Rodič může mít dva, jednoho nebo žádného potomka. Uvedu příklad Heapu:

Heap z řady 65873159 :
6
5    8
7 3  1 5
9

Doufám, že je vám nyní naprosto jasné jak uděláte Heap, neboť teď popíšu samotný HeapSort.

Postupujeme odzdola: Je-li jeden z potomků větší, než jeho rodič, dochází ke switchovací příležitosti a potomek se vymění s rodičem. To samé provedem s paralelními větvemi. Pokud již v nejnižší úrovni větví neexistuje žádná switchovací příležitost, uděláme to samé s další úrovní (pokaždé, když dojde k výměně ve vyšší úrovni, je pravděpodobné, že výměna způsobila výskyt switchovací příležitosti v levelu nižším. pakliže tato příležitost nastala, přerušíme operace s vyšší úrovní a switchujeme tu, ve které nastala příležitost. Jestliže v žádném z levelů již nejsou switchovací příležitosti, pokračujeme s vyššími levely). Výsledkem této operace bude základní Heap, který na vrcholu obsahuje nejvyšší číslo. Jestliže máme tento základní Heap, můžeme začít třídit. Označme si nejvyšší prvek Heapu jako hlavní prvek a očíslujme si prvky heapu posupně sériově přes řady zleva od jedničky. Hlavní prvek
prohodíme s prvkem, který má nejnižší číslo. Na prvku
s nejnižším
číslem bude nyní nejvyšší číslo z řady. Tento prvek zalockujeme, to znamená, že ho vyřadíme z heapu. Změnou hlavního prvku došlo v Heapu ke switchovací příležitosti na druhé úrovni. Postupně switchujeme prvky od nejvyšší úrovně k nejnižší (nejvyšší úroveň vždy obsahuje jediný prvek - hlavní prvkek). Jsou-li všechny switchovací příležitosti využity, switcheme hlavní prvek s nejnižším (tentokrát to bude druhý) a následně onen prvek zalockujeme. Takto postupujeme až na konec algoritmu, kdy jsou zalockovány všechny prvky. Prvky jsou nyní seřazeny od nejnižšího (hlavní) po nejvyšší (první).

Napsal jsem ukázku třídění menšího pole HeapSortem:

 

Leviathan’s great computer benchmark

Ξ February 24th, 2007 | → 1 Comments | ∇ Uncategorized |

Prof. Štěrbík ve mně před pár týdny probudil zájem o prgm. jazyk C (C++), na který jsem kdysi zanevřel, protože jsem si myslel, že postrádá dynamická, dynamicky multidimenzionálně přeallokovatelná pole. Prof. Štěrbík mě ale přesvědčil o opaku a tak jsem se tomuto jazyku začal opět věnovat. Zvolil jsem si ale trochu lepší verzi tohoto jazyka - prakticky nejnovější (rok 2005) - C++/CLI (C++/Common Language Interface), která dovoluje využívat obrovskou sílu Microsoft .NET Frameworku a kombinovat managed a unmanaged kód.

Začal jsem hned s dynamickými poli a přes odpoledne jsem vytvořil program, který obsahuje 5 algoritmů na třídění polí: Bubble Sort, Shell Sort, Exchange Sort, Selection Sort a Insertion Sort. U každého algoritmu měří čas zpracování pole o velikosti 20 000 integerů naplněných náhodným číslem o velikosti 0 až 999. Následně zprůměruje tyto časy a vytvoří koeficient kalkulační kapacity processoru.

(Kód + Download v Read More)

(more…)

 

,,bez komentáře” :)

Ξ February 21st, 2007 | → 13 Comments | ∇ Uncategorized |

 

Sny

Ξ February 20th, 2007 | → 6 Comments | ∇ Uncategorized |

Viděli jste někdy Final Fantasy: Spirits Within? Ne jo? Fakt? No nic … Renderovaná n1 chick tam měla takový zařízení na záznam snů. Říkal jsem si, že by se mi taky hodilo … zatím mi stačí jenom tužka a papír. Když se probudim po (upozorňuji obyčenjém, pro rejpaly) snu, většinou si ho už po pár minutách nepamatuju, protože nervové synapse vytvořené snem rychle chladnou … a tak si zapisuju klíčový body, abych si ty sny pak mohl oživit :)

Dřív jsem míval každou noc živé sny, takže jsem se třeba probudil na stole, nebo na chodbě. Je to opravdu zvláštní pocit, mít živý sen :). Někdy se tomu ráno sám směju … například: Zdálo se mi, že jsem v hospodě s různýma n1 chicks, který znám a měl jsem na sobě župan (lol?). Problém byl v tom, že ten župan neměl rukávy, ale já jsem je pořád beznadějně hledal. Potom jsem si v tom snu uvědomil, co vůbec dělám v hospodě v županu a začalo mě to pěkně štvát. Zlostně jsem hledal ty rukávy a pak jsem se probudil a zjistil jsem, že sedím na posteli a celou dobu hledám rukávy v pěřině :)

To jsou jenom slaboučký sny, oproti tomu, co jsem míval. Jednou, když mi bylo ještě hodně málo a spal jsem v horní části dvoupatrové postele se mi zdál neskutečně živý sen. Zdálo se mi, že proti mě ze zdi jedou auta a já jsem nemohl nikam uhnout, v tu chvíli jsem byl přesvědčen, že jestli z té postele nevyskočím, umřu. Vyskočil jsem tedy přes zábradlí a dopad jsem tehdy na bok a pak jsem tejden nešel do školy :)
Mnohdy jsem bloumal po bytě a myslel jsem si, že jsem ve škole a ani svit baterky mě neprobudil. Prostě hrozný.

Sny se opakovali pořád a pokaždé v jiném prostředí. Naposledy jsem bloudil po pokoji a narážel do věcí a myslel jsem si, že jsem ve vlaku a zapomněl jsem vystoupit v Trocnově. Našel jsem závěs od okna a myslel jsem si, že je to nějaká deka v lůžkovym kupé, tak jsem ho strhnul dolů a uviděl jsem dvorek. Potom mi okamžitě všechno došlo :)

To ovšem nic není proti mým hororovým snům. Poslední hororovej živák si pamatuju úplně přesně. Probudil jsem se a vidím, jak po nočním stolku lezou pavouci nebo podobná stvoření a jak se po mně sápe lampička. Okamžitě jsem vyskočil, popadnul jsem budík a lampičku jsem sejmul. Sejmul jsem pro jistotu taky knížku a utekl jsem do rohu pokoje. Zdálo se mi, že se pod postelí hemží ti pavouci a pak jsem najednou dostal odvahu a vyběhnul jsem směrem k posteli. Když jsem zjistil, že tam nic není, uvědomil jsem si, že to je jenom další živák :).
V dobu kdy ten sen prožívám, se mi nic z toho nejeví jako nesmysl, naopak to vnímám, jako naprosto potvrzenou racionální věc.

Poslední dobou se to děje v menším měřítku, ale před pár lety se setra zamykala v pokoji, protože se mě bála kvůli těm snům :)

 

leviathan, pátek a absinth :)

Ξ February 16th, 2007 | → 1 Comments | ∇ Uncategorized |

Deleted on 12.4.2008 by leviathan himself … sakra, jak jsem mohl psát takový kraviny …

 

Debata na úrovni

Ξ February 14th, 2007 | → 1 Comments | ∇ Uncategorized |

 

KONEČNĚ !

Ξ February 10th, 2007 | → 2 Comments | ∇ Uncategorized |

article has been deleted by leviathan itself

 

Audio přehrávač CDD1 - Co Dům Dal verze 1

Ξ February 9th, 2007 | → 4 Comments | ∇ Uncategorized |

ironicky

Dnes si ukážeme jak sestavit špičkový přehrávač a to pouze z odpadních materiálů a nepotřebných věcí. A navíc je to adrenalinová zábava - nikdy nevíte, kdy dostanete ránu od neuzeměného kovového přepínače !! To je věc !!

Budeme potřebovat:
1x ATX pulsní zdroj k PC (nejlépe s nefungujícím větrákem)
1x Vysoce výkonná vietnamská stereo soustava
1x Stará maximálně osmirychlostní CD-ROM mechanika
1x Externí větráček (nejlépe vymontovaný ze vzduchotechniky starého automobilu)
1x Stabilizovaný zdroj napětí (musí mít maximální odběr proudu menší než větráček při napětí dvakrát větším než udává větráček)
1x Přívodní kabel ke zdroji (Made in Hong Kong)
2x Propojovací kabely mezi stabilizovaným zdrojem a externím větráčkem

Postup výroby:
1)Všechny věci umístíme tak, aby bylo riziko vzniku požáru co možná největší (tzn. Přístroje postavíme na koberec, těsně vedle sebe a pokud možno, aby se co nejvíce kovových částí dotýkalo).

2)Oholíme konce přívodních vodičů a to pouze ostrým nožem, přičemž pravděpodobnost, že se říznete musí být větší než 60% (případnou krev nechme odkapat na plošný spoj pulzního zdroje - který provozujeme zamozžejmě otevřený, zaprášený a neaklimatizovaný)

3)Připojíme jednu dvojici konců drátů na svorky zdroje (pamatujte, vyšší napětí než požaduje větráček abysme dosáhli aroma palícího se prachu) a druhou dvojici připojíme na svorky externího větráčku. Nic nepájíme, pouze kroutíme (čím větší přechodový odpor, tím lepší bude výsledný přehrávač)

4) Zapojíme ATX zdroj i stabilizovaný zdroj do zásuvek a počkáme, jestli nevypadnou jističe. Jestli ano, vyjmeme jistič z rozvodní skříně, nahradíme ho hřebíkem a opakujeme krok 4.

5) Pokud jistič nevypadne, zapojíme jeden z konektorů ATX zdroje do mechaniky (je to vždycky ten, který se tam nejméně hodí) a nastavíme větráček na transformátor ATX zdroje (musíme ho pořádně zapřít, protože bude mít při startu velký ráz).

6)Zapojíme stereo soustavu do sítě a jack konektor zapojíme do mechaniky. Zapneme soustavu.

Přehrávač je hotový! Nyní si ukážeme jak lehce se aktivuje:

Aktivace:
Jednou rukou držíme externí větráček a druhou rukou zapneme stabilizovaný zdroj. Pokud se rozsvítí dioda oznamující přetížení, je to správně:

Překonáme ráz větráčku a umístíme ho tak, aby se nepohyboval (nevšímáme si kolísavé tendence otáček). Následně zapneme atx zdroj (pozor - vysoká pravděpodobnost elektrického šoku, proto se před tímto krokem chytněte hromosvodu). Nyní je přehrávač spuštěn. Můžeme vložit Audio CD a poslouchat hudbu do doby, než některá z částí přehrávače neodejde, nexploduje nebo neshoří.

(v “read more” hi-res fotografie mého CDD1)

(more…)

 

Najděte soubor za pár sekund, ne minut

Ξ February 9th, 2007 | → 0 Comments | ∇ Uncategorized |

Také vás rozčiluje nesmírně zdlouhavý proces hledání souborů v systémech windose? Objevil jsem malý trik, jak najít hledaný soubor během pár sekund. Musíte vlastnit pouze textový editor s pokročilým hledáním. Spočívá to v tom, že si vytvoříte cmd skript, který vám indexuje všechny soubory do jednoho ascii kódovaného texťáku. Jděte na nejvyšší možnou úroveň disku a vytvořte soubor omfgwtf.cmd, který bude obsahovat:

@echo off
tree /F /A >> abc.txt

Soubor spusťte a počkejte než se skript provede. Otevřete si ve svém editoru nově vytvořený soubor abc.txt. Vyhledejte si potřebný soubor a podle cestiček z ascii znaků rychle zjistíte, kde se soubor v hierarchii složek nachází.

Ave

 

Ideální myšlení :)

Ξ February 8th, 2007 | → 0 Comments | ∇ Uncategorized |

Pro tento článek bude stěžejní jedna krásná citace:

“Real integrity is doing the right thing, knowing that nobody’s going to know whether you did it or not.”
Oprah Winfrey (*1954)

Přičemž integrity je myšleno mravní integrita.
Já osobně neznám žádného člověka, který by toto naprosto splňoval a naopak každý den narážím (samozřejmě i u sebe) na přesný opak tohoto motta. Když udělám nějakou dobrou (nebo správnou) věc, vědomě se snažím o to, aby o tom vědělo co nejvíce lidí a hlavně, aby věděli že jsem ji udělal já.

Jednoduše řečeno, když člověk něco udělá, chce z toho mít prospěch nebo slávu. Kdyby udělal nějakou velkou věc a nepochlubil se s tím, k čemu by mu to potom bylo? Všechno úsilí, které do toho vložil by padlo jenom na “dobrý pocit”, který by u většiny lidí stejně nenastal, dokud by jim tu práci někdo nepochválil.

Tím pádem jdeme do háje buď my ( i křesťané, protože se spoléhají na to, že je ‘bůh’ odmění v ‘ráji’ ), nebo ten co to psal. :) . Popsal ideální myšlení a lidé jsou v tom případě hodně neideální prvky (jako cívky - elektrikáři ví).

Ave.

 

Next Page »

Leviathan

    kdo je Leviathan

    Jsem student aktuálně čtvrtého ročníku střední průmyslové školy strojní a elektrotechnické v českých budějovicích

     


 


RSS Zdroj

    ::

    RSS 2.0 < ZDE

    Přidejte si můj zdroj do vaší RSS čtečky

     

Statistiky