Evo ovako da zavrsimo ovu pricicu, da vidimo gde se to kriju greske u razmisljanju...
BM, KMP i QuickSearch su algoritmi koji u datom stringu nalaze ili ne nalaze dati string kao podstring (a sto si ti i naveo kao razlog pisanja algoritma, pretrazivanje velikih tekstualnih fajlova, bla, bla, bla, bla)... Medjutim sta si ti uradio. Ti tvoja dva stringa ne posmatras kao stringove nego kao liste stringova i ceo problem si sveo ustvari na UPOREDJIVANJE JEDNAKOSTI DVA STRINGA... A tu su stvari relativno jasne i ne postoji algoritam koji to radi brze i bolje od standardnog, a to je upravo ovaj algoritam:
Code:
FOR EACH Element IN List L1 = s1
FOR EACH Elemement in LIST L2 = s2
i := 0;
WHILE s1[i] == s2[i] DO
INC(i);
END;
IF i == LENGTH(s1) == LENGTH(s2) THEN :)
ELSE :( END;
END;
END;
Evo na primer uzmi da u prvoj listi imas string "abba" a u drugoj "bb", tvojim algortmom nalatis na prvu rec, zatim naletis na drugu, pitas da li su im prva slova ista, nisu, kazes super, predjes na sledecu rec, medjutim sta, bb je podstring od abba, a to tvoj ekstra algoritam nece moci da ustanovi :) Znaci nemas NIKAKAV ALGORITAM, NE NAJBRZI, NE NAJBOLJI, NE OSREDNJI, NE NAJGORI, NEGO NIKAKAV ALGORITAM KOJI TI RESAVA PROBLEM IZ OBLASTI KOJU SI SAM SEBI NAMETNUO...
Upravo zato sto stringove ne posmatras kao stringove nego string rasparcas sa \n i onda ne trazis odgovarajuce podstringove nego gledas da li ti se delovi stringova izmedju dva najbliza \n poklapaju :) Ti na taj nacin kazes super, moj string je ustvari moja lista, ja sam je izdelio super i posmatras element kao podstring, i mislis da imas algoritam za nalazenje podstringova, ali ga nemas, jer \n nisu pravi delimiteri koji tebi odredjuju da li je nesto kvalifikovano da bude podstring ili ne (na primer s1 = "abbbba" i s2 = "bbbb" i neka si ih "isparcelisao" naprimer ovako: s1 = "abb\nbba\n" i s2 = "bbbb", s2 je podstring od s1, medjutim ti to ne bi uocio jer ti kao moguce kandidate za podstringove posmatras abb i bba, a sto je upravo posledica tvog "parcelisanja"). Znaci to NIJE TO, to NIJE PROBLEM, to je DEBILITET koji je TRIVIJALNO RESIV...
E sada ti kazes da ti gledas samo prvo slovo, e to nije specijalan slucaj KMP-a, kao sto sam vec negde napomenuo (mada se moze posmatrati i kao tako za KMP failure function od jednoslovnog prefiksa kada kao podstring samo uzimas ceo drugi string, medjutim to je debilitet jer ti onda ne treba KMP, jer ne trazis podstringove(to je isto kao kada bi primenjivao algoritam za sortiranje na nesto za sta vec unapred znas da je sortirano jer tvoja spoljna sredina koja tebi prosledjuje ulaz u algoritam to namece i ti to dobro znas medjutim opet sortiras i sortiras i tako do besvesti i mislis da si nesto pametno uradio)), nego je TVOJ ALGORITAM SPECIJALNI SLUCAJ STANDARDNOG ALGORITMA... Naime nije potrebno gledati samo prvo slovo, nego gledas onoliko slova koliko ti je potrebno, kada dodje do neslaganja onaj WHILE ce da se prekine (uostalom ta petlja zato i sluzi)
Sada se ja pitam, sta je onda kod tebe standardni algoritam, kada si ti napravio specijalni slucaj standarnog algoritma... Ne znam sta si radio, da li si koristio neku od standardnih funkcija iz VB biblioteke ili nesto tako slicno, ali to uostalom nije ni bitno za celu pricu, bitno je da si ti PRICU PROMASIO...
I da kada smo vec spomenuli google, i da tu pricu polako zavrsimo... Naime sto se tice pretrazivanja stringova i nalazenja podstringova tu su stvari nekih 30-tak godina vec jasne i tesko je da ce neko smisliti nesto pametnije. Ako se u medjuvremenu i pojavi neki novi paper na tu temu, kao i na temu sortiranja, pojavi se za neke specijalne klase entropija ulaza za te algoritme *jedan paper se skoro pojavio bas za sortiranje na reviziji za stampanje, pogledati
http://xxx.lanl.gov*, ali neko resenje za "opste" slucajeve i random entropije tu je stvar potpuno kristalno jasna, jasnija da ne moze bolje od nlogn... Znaci ako zelis time da se bavis onda moras duboko da zaglibis i da pogledas sta je vec odradjeno i da se potrudis da pronadjes neke specijalne topologije u tvojim stringovima gde bi mozda i mogao da se nadje neki bolji algoritam, ali da takve topologije nisu trivijalne (a u nauci je uvek tako, uvek onaj ko pokrene nesto odradi fine stvari, cija su resenja eleganta i lepa, ostatak price je mucenje i silovanje do besvesti)... E sada google, a i svi ostali pretrazivaci koriste verovatno iste algoritme za nalazenje podstringa u stringu i upravo to nije fakt koji stavlja google ispred nekog drugog pretrazivaca... Ono u cemu je google bolji od ostatka sveta jeste u nacinu rangiranja rezultata, tj. preferencijalniji HTML cvor u web mrezi (* onaj koji ima vise ulaznih linkova *) jeste bolje rangiran... Cela prica jeste posledica relativno nove nauke koju pokrenuse fizicari a koja se zove networking i koja se bavi modeliranjem i karakteristikama kompleksnih mreza... Poenta cele price jeste da su sve realne kompleksne mreze za koje mi znamo scale-free, pocev od interneta kao najvece, preko svih drustvenih i bioloskih mreza na svim nivoima (za detalje pogledati radove Alberta Barabasia ili recimo moj rad koji sam radio na institutu za fiziku, sajt je
http://scl.phy.bg.ac.yu, pa negde tamo u training ima moje ime, slika i link na neki ppt)...
toliko, pozdravi Milos
Re: Najbrzi algoritmi
