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

Kako ti implementiras to stablo?
Ajde stavi kod na CVS, bez obzira da li radi kako treba ili ne.

  ----- Original Message ----- 
  From: Savic Andjelija 
  To: Csidc@Titan.Etf.Bg.Ac.Yu 
  Sent: Wednesday, January 22, 2003 11:47 AM
  Subject: [csidc] Radi?!


       Nije bilo govora o binarnom hipu. Juce sam napisala klase za rad sa m-arnim stablom. Performanse zavise od log(m,N), ne od log(2,N), sto je super. Lose je sto cak ni sa tom implementacijom nisam zadovoljna. 
      Sto se tice tog m-arnog stabla... m treba nastimati da proizvede optimalno ponasanje, to cu izvesti kad budem imala vise vremena. Jos nesto, funkcije koje umecu i brisu vrednosti pisane su tako da ne dozvoljavaju nepune cvorove, samo listove ( jednostavnija je logika rada sa stablom ). Ocekivala sam da  ce tako visina stabla biti manja, medjutim, ispostavilo se da nije. Vrednosti se vecinom umecu u rastucem poretku, pa se dobija "degenerisano" stablo, ekstremno nagnuto u desnu stranu. To treba popraviti i mogu se ocekivati znacajno bolje performanse. 
      Fajlovi su .xml iz dva razloga. Prvi, sadrzaj im je razumljiv i vidljiv, sto mi odgovara jer treba posle menjati te fajlove u skladu sa dozvoljenim/zabranjenim smerovima. Drugi, dozvoljavaju strukturiranost, sema susednosti jasno je ugnjezdena u semu cvorova. Pokusala sam da sve bude u  jednom fajlu ali tako mu stvarno treba vecnost da iscita sve odjednom, pa je iscepkano na isti nacin kao i mapa. Najveci deo vremena algoritam provede citajuci ove informacije, nazalost neophodne. Ipak, to se radi samo jednom za sve parove cvorova. Vreme koje provede u "korisnom radu" za cvorove koji su maksimalno udaljeni je otprilike 0.1 s !!!!!!!!! s ?!!!??!!!! Ipak, ima 17121 cvor pa se moze reci da sam nemocna.
      Ima tu jos posla, prvenstveno prohodnost i smerovi. Npr. sinoc sam probala za neke parove cvorova za koje znam sta da ocekujem, izbacio je putanje za koje bih zivot dala da nisu najkrace, za neke i ne znam da postoje, a za jednu cak znam ali isto tako znam i koliko je neprohodna ( Zvezdara, suma ! ).
  Uz algoritam ide i deo koji graficki prikaze resenje sto je savrseno nepotrebno, osim sto je meni tako lakse da uocim greske.

  Pozdrav, Andjelija