O alkoholu, namyšlenosti a trošce sázení...

18.04.2003 19:20

Před časem se v oblíbené brněnské hospodě udála zajímavá věc. Sešlo se tam několik programátorů (a neologism). Mezi těmito programátory byl i stanojr.Stanojr řešil zajímavou úlohu se kterou nás tenkrát seznámil. Já jsem, díki své namyšlenosti a egoismu, okamžitě prohlásil, že vymyslím a nakóduju řešení, které bude řádově rychlejší a obecně daleko lepší. Stanojr (který už ten program měl hotový a byl oslněn svým řešením) navrhl uzavřít sázku. Ve své nadutosti jsem samozřejmě souhlasil. A jelikož mi hrdost nedovolila to vzdát, tak jsem začal< >
vymýšlet a kódovat. Tuto sázku jsem prohrál. Mám sice řešení, které je řádově rychlejší a lepší (O(n) versus O(log(n), paměťová náročnost n versus 0), ale nezveřejním zdrojové kódy (což, jak řekl the, je podmínka sázky) a tudíž by mé vítězství bylo neprůkazné (i když the-ův argument o použití asembleru považujiza dementní kokotinu).

Problém, který jsme měli řešit:
Ulohou je napisat program, ktory vypocita najkratsiu vzdialenost medzi bunkami(vzdialenost je ze kolko krat musi skocit na inu bunku, az sa dostane na tu cielovu). Priklad: jedna z najkratsich ciest medzi 19 a 30 ma vzdialenost 5. A musi prejstcez bunky 19 ? 7 ? 6 ? 5 ? 15 ? 30. Pocet buniek moze byt 1 az 10000. (neologismovo řešení funguje neomezeně) Program musi byt v Ccku a zadavaju sa 2 argumenty, bunka 1 a bunka 2. Vystup bude cislo, co bude vzdialenost medzi 2 bunkamy. (neologismovo řešení ještě popř. vypíše nejkratší cestu - resp. jednu z mnoha

Buňky jsou uspořádány následujícím způsobem:

Popis neologismova řešení:
Své řešení popisovat nebudu, nicméně uvedu důvody, které mne k tomu vedou. Také
popíšu některé věci, které mne při řešení zaujaly.
Proč nechci zveřejnit své řešení?
Řešení, které jsem vymyslel, je špatné. Principielně špatné. Po dlouhém a důkladném zkoumání problému jsem došel k názoru, že stanovo řešení (resp. jeho myšlenka) je nejlepší možné. Čest mi ovšem nedovoluje použít cizí řešení (přestože ...). Nehledě na špatnost mého nápadu, je zde další důvod, kvůli kterému své řešení, potažmo zdrojové kódy, nezveřejním - v případě některých subproblému jsem nedokázal vymyslet optimální řešení, použil jsem tedy řešení suboptimální (=příšerně dementní) (tento důvod už padl). Poslední důvod (nejzávažnější) pro neuveřejnění zdrojových je to, že prakticky pro žádnou svou myšlenku nemám důkaz. Nemám prakticky žádné vzdělání v geometrii (navíc neeuklidovské v diskrétním neeuklidovském prostoru) a má inteligence je v této oblasti také velice slabá :-( V podstatě vycházím z myšlenky, že nejkratší spojnicí dvou bodů je přímka - což nemusí (a není!!) být pravda.

Zajímavé postřehy:
Jsem přesvědčen, že existuje řešení (založené na stanově), které se dá napsat na dva řádky (zpětná lineární forma + neeuklidovská Pythagorova věta). Toto řešení má ovšem tu nevýhodu (předpokládám), že nedokáže vypsat cestu - pouze její délku. Také bylo zajímavé pracovat v systému tří kvasi-ortogonálních polorovin (oproti běžně používaným dvěma (třemi) ortogonálním rovinám) - navíc diskrétních. Toto si vyžádala speciální povaha hexagonů. Naštěstí toto bylo třeba jen při druhé heuristice... Obecně bylo zajímavé studovat diskrétní neeuklidovský (v jednom bodě vícerovnoběžných přímek) hexagonální prostor.

závěrem bych rád poděkoval :wumpscut: a Hocico za to, že mne celé dny udržovaly v depresi (a tím umožňili pracovat) a Danušce za to, že mne večer těch depresízbavovala (a navíc vydržela poslouchat moje matematické řeči :-)

P.S. Ke konci programování (když už mne hanba fackovala z obou stran) jsem se odhodlal překopat algoritmus do podoby, za kterou bych se nemusel styďět - výsledkem je vysoce experimentální \"cosi\" co se vyznačuje extrémní rychlostí (vzdálenost mezi buňkami 2 500 000 000 a 1 spočíta za cca 200ms) a extrémní chybovostí (v oblasti do 100 mld je počet správných řešení cca 2.16*PI/4*10^14+120000 tj. 0.00001696 promile (hrubý odhad) :-) Ovšem přemýšlím dál a snad se to podaří.

P.S.2. Tak jsem dokončil ono ultra-rychlé řešení. Škoda, že až po odevzdání..
Tento se vyznačuje doopravdy zajímavýmy parametry co se týče rychlosti.

Metriky:
Počet řádek: 279
Velikost binárky: 6793 (FreeBSD 80386 ELF not-stripped, dynamically linked

Popis stanova řešení:
Najskor objasnil par veci.
Tento problem sa vyskitol v jednom levely vo wargame na hackerslab.org, co je v podstate taka sutaz, kde sa treba postupne \"hackovanim\" dostat do vyssich levelov. Na konci vas caka odmena a budete v Hall of Fame (super, ze jo :). Tento level je v podstate jediny v ktorom sa nejedna o \"hacking\" ale treba aj trochu porozmyslat. Samozrejme ze ja by som to sam nevedel vymysliet, tak som pohladal nejaku napovedu na boardoch na hackerslabe. Nejaky tipek tam pisal, ze treba skusit vygooglit \"hexagonal coordinates\". A tak sa aj stalo. To co som nasiel bolo v podstate skoro cele riesenie. Na obrazku vydime jednotlive hexagonaly a k nim priradene cisla - suradnice.

Dalsiu vec co som nasiel na tej istej stranke bola rovnica ako zistit vzdialenost dvoch hexagonov. (nazvanu \"light distance\" na vygooglenom sajte) 1/2 * [ Abs(x1-x2) + Abs(y1-y2) + Abs(z1-z2) ] Poslendy problem je priradit cisla, ktore su v zadani k jednotlivym x,y,z koordinatom. Poriesil som to tak, ze som postupne prechadzal po cislach zo zadania a priradoval x,y,z suradnice. (vid zdrojak, link je na konci) Suradnice som priradil k cislam 1 az 10000. Tymto sa vytvorilo niekolko MB velke pole a ked som chcel zistit suradnice k nejakemu cislu, mal som ich v podstate hned. Problem je ten, ze keby som chcel vzdialenosti povedzme milionov, potreboval by som obrovske mnozstvo pamati.

Podla nasho zadania sa ale program musi spustit s 2 argumentami (cislami hexagonov zo zadania)a na stdin vypisat vzdialenost Tym padom je moj program strasne pomaly (podla zadania), lebo pri kazdom spusteni musi zistit suradnice vsetkych hexagonov (10000).
Samozrejme dalo by sa to jednoducho optimalizovat, ze by prechadzal vsetkymi hexagonmi a ulozil si iba tie 2 zo zadania. Ale je tu dalsi problem a to je strasne dementne napisany algoritmus priradovania tychto suradnic, pretoze potrebujem dve polia. A musim vzdy zistovat suradnice od zaciatku. Ale to je jedno. Tento program uvadzam taky ako som ho napisal cca pred cca 1 rokom, iba som ho trochu okomentoval. Vtedy som nebol dobry programator a niesom ani dnes, takze mi nenadavajte :). Pred rokom mi islo o funkcnost a nie o rychlost.

Testy:
Testování (neologismovo) probíhalo ve dvou fázích:
1 fáze)
Programy byly modifikovány tak, aby četly data ze stdin. Byl vytvořen souborobsahující 1000000 náhodných dvojic (čísla do 10000). Poté byly programy na těchto datech otestována. Stanův (díki modifikaci - pole se generovalo pouze jednou) program data spracoval za cca 19 sekund. Můj tatáž data spracovával přes dvě minuty (ultra-rychlá modifikace za minutu a 12 sekund). Výsledky z obou programů byly porovnány a shledány stejnýmy. Toto je empirický důkaz správnosti řešení (comparison testing).

2 fáze)Následoval test \"podle pravidel\". Opět byla použita náhodná testovací data. Tentokrát jich bylo pouze 10000. K samotnému testování byl použit jednoduchý script (perlovský), který spustil instanci programu a předal mu vstup ze souboru. Podotýkám, že tato procedura je SILNĚ dementní a pomalá!! Každá iterace totiž zahrnuje fork+exec+exit a forkuje se perl!! Můj program spracovával data 1 minutu a 16 sekund. (ultra-rychlá varianta 58 sekund) Stanův jsem bezmyšlenkovitě spustil a čekal... Po asi 2 minutách čekání mne napadlo si spočítat jak dlouho to bude asi trvat - vyšlo mi 11 hodin a tak jsem test neukončil...

K testům bych poznamenal jen toto. První test jasně dokazuje, že stanovo řešení (jeho idea) je nejlepší možne - implementace bohužel této dokonalosti zdaleka nedosahuje. Použití pole má výhodu v prakticky okamžitém spočítání vzdálenosti,nevýhodu ovšem v obrovských nárocích na paměť a dobe výpočtu. Toto by šlo obejít (ale čest mi v tom brání). Ke svému programu bych jen dodal, že i v takto, pro něj, špatných podmínkách si vedl relativně obstojně. Jeho časová složitost roste logaritmicky, takže je při takto malých hodnotách znevýhodněn (relativně), navíc pokaždé počítá cestu znova (výsledky se znova nepoužívají). Druhý test (ten \"podle pravidel\") můj program jasně vyhrává.

Dále bych dodal, že jsem, čistě ze zájmu, testoval svůj program pro čísla v řádu miliard - konkrétně 1 500 000 000 a 14 000 (neptejte se mne jak jsem je vybral), výpočet trval lehce přes 4 minuty. A to je oblast, kde by stanův program potřeboval dny (odhaduju) na spočítání pole a desítky gigabajtů paměti. (ultra-rychlá modifikace potřebuje pro buňky 2*10^9 a 1 pouze 50ms!!! Větší čísla jsem netestoval, protože se mi nechce měnit 32bitové typy na 64bitové) Výsledky bych shrnul asi takto: stanův program obsahuje bezkonkurenční myšlenku, která je nesmírně ...hloupě... implementována. Mé řešení je více \"do života\", přece jen od počítačů vyžadujeme aby spracovávaly relativně vysoké hodnoty (což tisíce nejsou).

Metriky: Linux, gcc 3.2 (-O3), glibc 2.3, Pentium 200 MMX 64MB EDO RAM
(vyvoj a veskere \"zajimave\" testovani probihalo na FreeBSD

Ja by som este dodal par veci: Neologism vyssie pise, ze sazku prehral a to z dovodu ze neuverejni svoje zdrojaky a nevysvetli riesenie. Ja si ale myslim ze sazku vyhral, pretoze to mal stejnak rychlejsie a funguje mu to do velkych cisel. Neologism sa nakoniec rozhodol, ze svoje zdrojaky uverejni. (Po chvile presviedcania :)
Potom pastne link na board.
Ked sme sa neskor stretli v hospode, dvekravy nam oznamil, ze ma rychlejsie riesenie ako neologism
a moze ho aj matematicky dokazat. pouziva tiez hexagonalnu suradnicovu sustavu a ma velmi rychli algoritmus, ako zistit suradnice k cislu zo zadania. Ale to vam sam povie v novom clanku, alebo to poastne na board.
Nakoniec by som chcel podakovat vsetkym zucastnenim.< >

stanojr | neologism

Linky:
Neologismov program pre FreeBSD (binarka)
Neologismov program pre Linux (binarka)
Stanojrov program - zdrojak

Hexagonal coordinatesneologism | stanojr