[csidc:2003] - Re: MilanSt. by "Milan Stanojevic" <milanst@ptt.yu>

Nigde nemas nikakav konstantni clan.
 Imas. U ovom konkretnom slucaju jedan je 1, a drugi bi bio 2 ( ipak ovo je aproksimacija ! )

Kako? U kom izrazu? Ma nebitno...


Vreme O(E + V*lgV) moze da se postigne koriscenjem Fibonachi heapa, 
 O tome ti pricam. Znam da je O (E + NlogN) najbrza. 

Fibonachi heap nisam nikad implementirao, mislim da nije tako jednostavno, 
Sto se tice komlikovanosti implementacije, ne znam zasto, ali to me ne plasi. Ne moze da bude toliko komplikovano, to je cista teorija. Jos uzmi u obzir da o tome citas iz neke knjige, a teoreticari su uglavnom teski kompleksasi koji obozavaju da jednostavne stvari koje rade predstave na komplikovan nacin, i plus, uz to jos vole i da ih zovu predugackim imenima koja podsecaju na latinske nazive... Ali to nema mnogo veze sa zivotom.  

Ma jeste teorija, ali mi se cini da imas boga nekih specijalnih slucajeva, seti se samo AVL ili crveno-crnih drveta. A za teoreticare nisi bas u pravu, ali da ne razvlacim pricu.


ali ne verujem da treba. 
 EEExcellent.    

A sta je klijent? I zasto sa klijenta (jel to zbog teme projekta, jer bi sve mnogo lakse bilo da je na serveru).

 Klijentom zovemo vozilo, laptop u vozilu. Jeste zbog teme projekta, da bi sto vise stvari radio klijent.

Pitam za broj cvorova, jer Dajkstra za mali broj cvorova radi trenutno. Doduse, sad zavisi sta je klijent, ali do par hiljada cvorova, uz uslov da klijent ima memoriju za to, sve bi trebalo da bude trenutno.

  Blago meni ako je trenutno. Ne zamaram se mnogo time kakve su karakteristike klijenta. Ja tezim da svoje performanse dovedem na maksimum, zahteve za resursima sitema ( ukljucujuci i vreme ) na mimimum, a klijent moze da bude i P IV. Bas me briga. Cak i da ima gigabajte RAM-a, ja necu na to da racunam. Zapravo, ne mogu sad ni ja bas mnogo da glumim heroja, u jednom trenutku ce mi se sve verovatno smuciti pa cu i reci : " Ma sve je super. Klijent to sigurno moze da izvuce. Pa to je hitna pomoc. Ako za njih ne odvoje sredstva ja ne znam za koga ce...", ili tako nesto. Tako ce verovatno i biti kad budem pocela da razmisljam kako da cuvam cvorove, ali cu videti da ne bude. Da se vratim na temu. Zanima te broj cvorova. To cu znati tacno kad zavrsim sa mapom. Za sada, ni na jednom .gif-u broj cvorova nije presao 135, osim na nekolicini. Jedan .gif je 1/256 grafa. Ipak, ima i .gif-ova koji daju jako mali broj cvorova ( do 10 ) pa u proseku ti vidi. Stvarno, kao sto vidis i nije strasno, pogledacu bas tacan broj, ali za sada uzimam u obzir samo najgori slucaj.

Znaci oko desetak hiljada cvorova. Ok, to nije malo, ali je 10^5 * lg(10^5) ipak sasvim pristojan broj cak i za laptop. 


Ovo nisam shvatio. ExtractMin je operacija nad heapom (podrazumevam takvu implementaciju) kojom uzimas cvor sa trenutnim najmanjim nadjenim rastojanjem od pocetne tacke (to je onda i konacno najmanje rastojanje). Sta tu hoces da poboljsas? To ne kapiram.
 E da. Doslo je vreme da definitivno rascistimo nesporazum. Evo ti sta sam ja shvatila iz tvoje price. Ja mislim da kad kazes ExtractMin, da zapravo pozivas metod koji ti vraca cvor sa najboljom procenom. Moras da vrsis neku vrstu pretrage da bi vratio rezultat. Ta pretraga traje. U ovoj implementaciji stvarno najkrace. Tu ne bih naravno nista dirala, nisam stvarno ambiciozna da smisljam bolji algoritam od toga, pogotovu sto su velike sanse da mi i ne treba. Ne mislim na ta poboljsanja. Po hiljadusedamstoti put, hip u mom slucaju nije implementiran. Kad kazem poboljsanje, mislim na poboljsanje SVOJE VERZIJE, na poboljsanje trazenja najboljeg cvora u SVOJOJ VERZIJI. Ono je trenutno lose. I to cu, ako bude bas trebalo poboljsati implementacijom tog vec cuvenog hipa. Nadam se da nece trebati, pa onda kad kazem poboljsanje mislim na to da se moja struktura cuvanja ne promeni, ali da se odvoji neko vreme za sortiranje vrednosti uz dobitak da najbolji cvor dohvatis odmah. U proseku, posto je na primer lista sortirana imaces N/2 prolaza, sto smanjuje konstantni clan ali ne menja red velicine. Uzmi ipak u obzir kako algoritam radi, tako da nece biti N/2 nego dosta manje i to mislim bas blisko logN. Ovo bi bilo blago poboljsanje za koje se nadam da je dovoljno i mislim da cu to realizovati cak i kada bi se Dijkstra ponasao idealno na velikom grafu.

Ok. Onda definitvno menjaj svoju verziju i napravi heap. Posao je definitivno mnogo manji od budzenja nekih heuristika a dobijas resenje koje treba. Kao sto ti rekoh, mozda i ne moras da pravis svoju verziju ako C# ima neko binarno drvo, mozda samo treba malo da sredis klase za cvorove i to je to (da dodas bolje sa rastojanjem i jedan Comparator po tom polju, bar je tako u javi).


Ideja je da uzmes neku povrsinu koja obuhvata obe tacke, dovoljno siroko da ne izgubis najkraci put, ali i dovoljno usko da nemas previse tacaka. Neka elipsa kojoj je duz izmedju dve tacka osa ili tako nesto. Sigurno neces da zaobilazis puno po gradu (reda kilometara).

    Jasno. Htela sam da kazem da je tako u 99.9999% slucajeva. U preostalom broju slucajeva algoritam ce izbaciti glupost. Sta da radis kad moras da garantujes za svih 100% ? Cak i da nije tih izuzetaka, pa ti si sam potegnuo temu oko prohodnosti, nekad zaobilazis ali je put prohodniji. 

Vidi koliko ce dugo da radi bez ogranicenja (ali napravi heap ili nesto slicno, jednostavno je neophodno) pa ako bas mora brze onda ogranicavaj.

Uglavnom, ja sam samo posmatrac i vi radite kako mislite, ja sam mislio samo da dam par sugestija ako sam nesto vec radio (a ovo oko grafova jesam).

    Nemoj da budes skroman. I treba da se mesas. Cak si dobrodosao. Ne volim da me nerviras, ali kad pogledas iz pticje perspektive, dobrodosao si. Uostalom, svi ostali su negde pobegli. Kad malo bolje razmislim, nije cak ni lose da me nerviras, mislim da me to posebno motivise ( samo ima "nekih dana u mesecu" o kojima treba da vodis racuna, pitaj devojku, ona ce ti objasniti ). Ja stvarno ne znam odakle ti toliko vremena za ovakve mailove pred ispitni rok. Ucis li ti nesto ? Ili su te nalozili na one price kako je cetvrta godina NAJLAKSA ? E da, ako ti neko kaze da se prevodioci spremaju za tri dana nemoj da im verujes. To ti kazem jer sve ostale price su poluistinite ali ova je bas laz, a cula sam je hiljadu puta, a narocito od starijih studenata koji bi kao trebali da su bolje upuceni... Znam da me nista nisi pitao, ali ovo je iz licnih razloga. Osecam da ispred mene stoji MISIJA unistavanja takvih neistina, posebno takvih.

Ja ucim kad moram. Ne mogu da se nateram da ucim dok mi ne bude bas frka, a to ce da bude za koji dan. A kad to dodje, onda nocu ucim, danju spavam po malo. Daje rezultate, mada je pogubno po zdravlje. Isto vazi i za godinu. U oktobru najvise ispita dajem (3 ili vise)
A cetvrta godina je mozda laksa u smislu da ne moram da se smaram sa glupim strujama, kako ih mrzim. I sa jw, to jos vise mrzim. Za tri dana ne verujem da mogu da se spreme prevodioci, ali ima ispita koji mogu (provereno :)


P.S. E, jos nesto sam htela da te pitam. Rekao si da je knjiga bas na glasu. Jel' ima mozda neko bolje resenje od Dijkstre ? Ili bar ideja za ono sto planiram da napravim kasnije ? 

A sta planiras da pravis kasnije? Generalno nemas neko bolje resenje od Dajkstre (tako se cita, covek je bio Holandjanin), mogu da pogledam i da vidim. Mozda imas neko asimptotski bolje resenje, ali ne verujem da daje drasticna prakticna ubrzanja. Znaci probaj Dajkstru sa hipom, pa onda budzi, to ti je moj savet.


                            Milan St.