[csidc:2003] - Re: MilanSt. by "Savic Andjelija" <andjas@EUnet.yu>

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

  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.  

  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.

  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.

  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. 

  Nisam znao da se stvar radi na klijentu. Mislio sam da je u pitanju PC, a tu nema problema sa vecim brojem cvorova jer Dajkstrin algoritam radi vrlo brzo (probao sam mali milion puta, verujte mi). Sa klijentom ne znam kako stvari stoje.

    Mislim da sam na ovo odgovorila gore. Ako si probao, jos bolje. Ja sam za sada probala na malom broju cvorova ( 135 ) i ne mogu nista da kazem za veci broj kad nisam probala. Moja dilema potice od trenutaka testiranja. Kad sam generisala grupu slucajnih parova, mogu ti reci da vreme nije bilo bas zanemarivo, ali to su tri algoritma paralelno plus jos i cinjenica da je broj pozivanja algoritama bio jako veliki. Vrlo verovatno da je moja zabrinutost plod ciste panike i da nema bas neku realnu podlogu osim ako realnim ne zovemo i ocekivanje najgoreg...

  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.

  Pozdrav, Andjelija

  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 ?