Triediace algoritmy
Začína sa nimi už v základoch programovania a nikto, kto to myslí s programovaním vážne sa bez nich nezaobíde. Poznáte všetky triediace algoritmy podľa ich efektivity?
Určite áno, kto nie, môže si pozrieť vizualizáciu v krátkom videu venujúcemu sa práve porovnaniu efektivity triediacich algoritmov.
Pre ostatných vypisujem súťaž o najNEefektívnejší triediaci algoritmus. Vyhrať môžte jedno veľké bezcenné plus, alebo tri menšie o nič viac cenné plusy. Aby ste to nemali také ľahké, v úvode uvádzam štyri, ktoré tým pádom nemôžete použiť:
- Bogo sort [AKA monkey sort, stupid sort, permutation sort, slowsort, shotgun sort...] → Trochu pomalší voči bubble sortu. Ide o algoritmus založený na náhodnom generovaní poradia prvkov, až kým sa netrafí správne zoradené poradie. Analógiou je vyhadzovanie balíčku kariet do vzduchu, až kým balíček nedopadne v zotriedenom poradí. Je často mylne považovaný za najmenej efektívny algoritmus.
- Stupid monkey sort → Môj vlastný vynález, aj keď pochybujem že som prvý kto mal tento úžasný nápad a možno ho poznáte pod iným názvom. Inšpirovaný Bogo sortom. Majme N prvkovú množinu, ktorej prvky náhodne generujeme, až kým prvok N1 < N2. Následne si odložíme prvok N1 do stacku a náhodne generujeme skupinu N-[N1] až kým nie je N2 < N3. Pozor, teraz príde krása tohto riešenia, pokiaľ je však prvok N2 > N3, tak si zo stacku odoberieme predtým odložený prvok N1. A takto postupujeme, až kým nebude zoradená celá skupina prvkov. Samozrejme, čím je prvkov v skupine viac, tým je tento algoritmus krajší a menej efektívny.
- Assumption sort → predpokladajme že je skupina prvkov zoradená a vráťme ju. Úspešnosť tohto algoritmu je síce zanedbateľná, ale zato je brutálne rýchly.
- Miracle sort → môj obľúbený. V loope kontrolujeme, či sú prvku zoradené, ak áno, vrátime výsledok, ak nie chvíľu počkáme a kontrolujeme znova.
Takže dokážete vymyslieť niečo ešte menej efektívne? :)
Pre pridávanie komentárov sa musíte prihlásiť.
Seems sorted sort - Zotriedi len prvych 10 percenet, clovek sa pozrie na zaciatok, vyzera to byt zotriedene, dalej nepozera
Blockchain sort - Zotriedi sa pomocou technologie Blockchain, je to velmi perspektivna technologia a ocakavaju sa velke vynosy, vzorky 10 predtriedenych poloziek ponukame na predaj za $200 este pred zverejnenim samotneho celkoveho poradia. Viac info viď whitepaper
Google sort - Bol zruseny
Apple sort - Pozerate sa na prvky mnoziny zle, je to zotriedene.
Oracle sort - prakticky bubble sort, platite za kazdy triedeny prvok ale ak ma vas procesor hyper threading platite 2x tolko
ROFL :D
:D :D
Bude aj pokračovanie?
Pripomenulo mi to starú otázku z pohovoru: Riešite javový servlet pre užívateľskú session. Ako zistíte najmenší a najväčší prvok z poľa?
Najhoršia odpoveď bola: Použijem internú funkcioanlitu javy na zotriedenie poľa, a vezmem krajné hodnoty.
Pri bežnom loade malého podnikového servera s cca 20k až 50k užívateľov by si na tom garbage collector vylámal zuby. Najsmutnejšie na tom je to, že z nedostatku kvalifikovaných ľudí ich prijali. Jediné pozitívum je, že ich nedali na backend. Výsledkom sú stránky kde človek použije na frontend minimálne 5 toolkitov a aj s CSS to zaberie 0.5M textu. Výsledný TAB v prehliadači bez problémov zožerie viac ako 0.5G RAM.
Uff :D
Pri review kodu juniorov narazam na rozne veci, tak si najzaujimavejsie z nich zacnem odkladat a ked ich bude dostatok, tak moze dojst aj k uverejneniu, samozrejme so suhlasom autorov. :)
Ved data zanonymizuj a suhlas Ti nebude treba?
Bude, firemný.
Ale inak na podobné veci je tu známa bugzilla.
pekna zbierka je aj na hovnokod.cz
Dobrý link. Pekná zbierka úplne bežného kódu.
Takých je veľa. Napríklad ukážka http://ioccc.org/2018/anderson/prog.c od jedného z tohoto ročných výhercov The International Obfuscated C Code Contest
no koli tomuto som prestal pracovat, ako web develop, lebo tieto web bludy "vystudovanych" neprogramatorov a uzivatelov kdeakych frameworkov ma vazne nebavilo riesit a hrabat sa v tych exkrementoch.
strasna hromada tagov, sialene hordy css, kopa js a uplne sialene php a nulova ochrana uzivatelskych dat, nulova bezpecnost webu ziadne escapovanie a ochrana vstupov a vystupov z databaz.
mrte stranok som v tedy radsej prerobil od znova, lebo to bolo "jednoduhsie" a ten ich sialeny vytvor - kod som dokazal v klude zredukovat aj o viac, ako 85%, kedz nic viac stranka uz nepotrebovala.
a hlavne, uz nikdy viac toto nechcem robit.
Sleep sort: In general, sleep sort works by starting a separate task for each item to be sorted, where each task sleeps for an interval corresponding to the item's sort key, then emits the item. Items are then collected sequentially in time.
Zotriedte nim pole {1, INT_MAX} a ked to zbehne sa ozvite.
moj postup je, ak je N vstup s nahodnymi cislami, kde dokonca rozne cisla mozu v klude chybat -
prejdenie celeho vstupu,kde sa beru cisla rad za radom, kde kazde nasledujuce cislo je testovane, ci je vacsie, ako to predosle, nieco v style -
if(nasledujuce N > aktualne N) najvissie N = nasledujuce N;
takto ziskame najvacsie cislo z N.
ulozene najvissie N spustit v cykle od nuly, nieco na styl -
for($i = 0;$i <= najvissie N;$i++) if($i existuje vo vstupe) zapis do poradia.
takto sa nam pekne zotriedia v poradi.
ma to aj svoje temne minusy, priklad - do vstupu dame iba 3 N - N1 = 371 N2 = 1 000 000 000 N3 = 2
tak toto by bolo trochu peklo, no pri hustejsich a lepsie zorganizovanych vstupoch, alebo pri kompletnom, hoci prehadzanom ciselnom poradi, je to vcelku lahodka.
na zaver dufam, ze som dobre pochopil clanok, ak nie, tak som trafil iba vedla :D
este dodam, ze ak vieme naisto, ze vstupy N su v lubovolnych prehadzanych rozpatiach, kde naisto nechyba ziadne cislo v poradi, staci nam iba zratat pocet rozhadzanych N, bez akejkolvek analyzy a hned mame zotriedenie hotove.
este dodam k predoslemu prispevku, ze sa logicky jedna o lubovolne rozhadzane rozpatia, zacinajucich nulou, alebo jednotkou.
jedna sa o relativne jednoduchy zasah pri pouziti 0/1 pri zaciatku rozpatia.
a cele by som to riesil takto -
prjdenim celeho vstupu od zaciatku do konca, kde -
prechadzanim vstupu N, kde -
$najnizsieN = prveN;
$najvyssieN = prveN;
if($najnizsieN < nasledujuceN)
$najnizsieN = nasledujuceN;
if($najvyssieN < nasledujuceN)
$najvyssieN = nasledujuceN;
a cele to zkopit v neakom cykle -
for($i=$najnizsieN; $i <= $najvyssieN; $i++)
if($i existuje kdesi vo vstupe N)
premenna neake poradie = $i;
vcelku vylepsena verzia prveho prispevku.
este mala oprava.
Nie -
ale -