Pogledaj KMP i Boyer-Moore algoritme, za pattern matching, mada nisam siguran da su optimalni za to sto tebi treba. Imas cini mi se i probabilisticne algoritme za te namene koji nisu egzaktni, ali ne znam puno o tome.

ok....ajde ovako: ko zeli da proba program koji demonstrira moj algoritam neka me obavesti i ja cu mu poslati na mail moze?

A da malo pojasnis taj algoritam pre toga?
Sta radi, kako radi...

ma on ne trazi zeljeni text po celoj listi nego samo po delovima liste za
koje predpostavlja da se u njima nalazi taj zeljini text (text koji trazimo)

Ajde ti decko pogledaj malo Knuth Morris Pratt algoritam, pa nam onda reci da li je to ono sto tebi treba, posto te ja bas i ne shvatam...

Ne.Nije to to.Sustina mog algoritma je u tome sto on "razbija" svaku stavku
liste po kojoj trazi na pojedinacna slova i zapisuje tu "slovnu"
strukturu.Zatim na osnovu te strukture uporedjuje svaku stavku sa trazenim
textom.

Pa kako mislis "razbija". Ono, uploaduj negde program koji demonstrira i daj pregled algoritma, slozenost, dobitak u odnosu na neka druga resenja... ne kapiram koji je cilj postavljanja teme uopste.

evo vam link:
http://www.taraba.org/forum/viewtopic.php?p19#1219

Ako vam gornji link ne bude radio idite na:

www.taraba.org -> forum -> Internet -> Hosting

tamo je fajl koji sam "zalepio"

A što ga jednostavno ne okačiš ovde, nije valjda veći od 200KB ?

Moze?Nisam znao da mogu i ovde da ga okacim....kako to da uradim?

Ispod svakog tvog posta imaš sledeće opcije [ Upload uz poruku |Izmena/Brisanje | Odgovor na temu ] e tebi treba ova prva.

Jel ovako?

I?
Sta mislite o brzini?
Imajte na umu da je SVE radjeno u VB 6

Evo nekoliko stvari samo u pauzi...

1) CITAT> ma on ne trazi zeljeni text po celoj listi nego samo po delovima liste za
koje predpostavlja da se u njima nalazi taj zeljini text (text koji trazimo) < KRAJ CITATA

Da, da kako da ne, sto ce racunar da ti pretpostavi nesto, nista ako bar nema jedan prolaz kroz ceo tekst, znaci ti sigurno imas dva, znaci da gubis igru :)

2) CITAT> Ne.Nije to to.Sustina mog algoritma je u tome sto on "razbija" svaku stavku
liste po kojoj trazi na pojedinacna slova i zapisuje tu "slovnu"
strukturu.Zatim na osnovu te strukture uporedjuje svaku stavku sa trazenim
textom. > KRAJ CITATA

Ukoliko sam dobro razumeo, ovo je najgori brute-force, prodjes kroz listu, za svaki element liste koji je string, razbijes string na charove (slovne strukture), zatim to isto i za drugu listu i onda uporedjujes slovo po slovo :) KMP je majka za ovo :) Bar se nadam da sam dobro razumeo :)

3) Nije sustina u tome da ti nama za tvoj algoritam das source, u stvari ne das source nego das exe i da kazes super to je to i to radi stvar :) U ostalom nije ni bitno da li je to isprogramirano u VBu ili Cu, kada pravis novi algoritam, pises ga u meta-jeziku, zatim matematicki dokazujes da je korektan i kada to dokazes, onda racunas njegovu slozenost u Big O notaciji... Kada dobijes tvoju slozenost, tek onda mozes da se meris sa nekim od "najbrzih algoritama" :) Tek onda ga implementiras *tek da se uveris da to radi i sa tehnicke strane, a i da pokazes sebi, i drugima da znas da programiras*
Druga stvar, to sto ce da malko brze radi u C-u jer se C kompajlira a VB interpretira, ne znaci da je tvoj algoritam brzi ili sporiji... Isto bi bilo kao da si rekao, e sada sam pustio moj algoritam na procesoru od 300mhz, a onda cu na 400mhz i naravno da ce brze da radi :) To su sve relativne mere brzine... Opet ponavljam prava mera je BIG O... Ovakva mera koju nam dajes, posebno bez source-a je krajnje nemerodavna da se ista, ali bilo sta zakljuci o tvom algoritmu :) Uostalom i ne znamo kako si implementirao onaj algoritam sa kojim poredis svoj... Buduci da ocigledno nisi upucen u teorijske pozadine problema, ko zna sta si nam podvalio :)

4) Probao sam programce, i radi isto i u jednom i u drugom slucaju :)
5) Mislim da si malo preambiciozno usao u celu stvar :) Ne znas kako rade osnovi algoritmi iz doticne oblasti, a vec se hvalis da imas bolji i brzi algoritam :) To se tako ne radi... prvo se sedne pa se prouci sva materija, i tek posle toga krece kreativni deo... jer od ideje do pravog algoritma za koji bi hteo da nosi tvoje ime puno je suza, znoja, tuge i patnje

pozdravi Milos

BRZINA:kad kazem folder sa dosta fajlova mislio sam na foldere sa 1500 i +
fajlova.

Kad uporedjujem foldere sa po 2000 fajlova,klasican algoritam koji
uporedjuje svaku
stavku jedne liste sa svakom stavkom druge liste odradi posao za 15-ak
sekundi dok
moj deo koda isti posao odradi za max 2 sekunde.

Kad pokrenete program unesite kao prvi i drugi folder system32 folder (u
kome ima oko 2000
fajlova) pa ce te videti.Kad su folderi sa malim brojem fajlova u pitanju
radi istom
brzinom kao i bilo koji drugi algoritam (mozda cak i sporije)

Algoritam na pocetku napravi jedan prolaz kroz celu listu da "popise"
stavke.Tada ih on ne razbija na charove nego im samo uzima prvo slovo (jedna
linija koda).Kasnije pravi prolaze ali NE kroz celu listu nego samo kroz
delove.(recimo kroz 50-ak stavki)

E da - matematika mi i ne ide bas od ruke :)

Probajte ga sa folderima gde ima oko 2000 fajlova (ili jos bolje ako ih ima
vise).

A koji je to klasicni algoritam? I koliko traje to "razvrstavanje"? Moracu da upotrebim vec skoro zaboravljnu alatku, sveti konvertor (http://zombie.codewalkers.com/2004/06/14/sveti_konvertor) da ovih 2 sekunde preracunam i dobijem rezultat u nekoj od za to koriscenih notacija :)

Sta mislis, da li je taj tvoj najbrzi algoritam brzi od Google-ovog? Hm... da vidimo... koliko ono google ima indeksiranih stranica? I kolika je prosecna velicina stranice? Verujem da cemo doci na vise od 2000. I da, google definitivno vraca rezultate za manje od 2 sekunde :)

Nego, daj ti ovde pseudo kod tog algoritma, pa da pricamo dalje. Inace nema smisla.

Ti hoces da kazes da na osnovu prvog slova tvoga stringa iz liste reci ti znas sta da gledas iz druge liste... Da te odmah razocaram to je okrnjena varijanta KMP-a, a i KMP radi bolje jel ne gleda samo prvo nego i drugo, trece... koliko je potrebno slova... Znaci opet topla voda, znaci vrati se prvo na osnovne algoritme pa onda pogledaj kako oni rade, pa kada stvarno shvatis kako rade, e onda dodjes pa pricas pricicu... Ne ide tebi matematika slabo od ruke, jel matematika potrebna tebi u ovom slucaju je mizerna, nego algoritamski nacin razmisljanja tebi ide malo losije :) I ceo proces proizvodnje koji se mora ispostovati ako hoces dobar algoritam :)
Drugo nikada ne znas kroz koliki broj stavki prolazi tvoj algoritam jer to zavisi od frekfencije pocetnih slova... U tvom slucaju prolazi kroz sve jer ti sve reci pocinju na c:\, znaci nedostaje ti i malo zdrave logike...
Svoj algoritam ne mozes uporedjivati sa googletovim jer google odradi indeksiranje, pretrage se vrse na osnovu indeksa, pa zato radi brze, a indeksiranje se radi na klasterima racunara sa velikom procesorskom snagom i ko zna koliko se tu vremena potrosi... Ako neces na mostu izgubis na cupriji...
Pod klasicnim algoritmom verovatno podrazumevas brute-force, bar tako rekonstruisem tvoj opis, a to i nije klasican algoritam, nego SILOVANJE...
I da, sto su ti liste, liste fajlova, sto nisu obicne tekstualne datoteke... I to recimo datoteke u kojima nemas EOLN, e onda je tvoj algoritam nisto drugo nego cist brute-force....

pozdravi Milos

ok...prva stvar: nisam rekao da je moj algoritam najbolji,najbrzi itd.samo
sam hteo vase misljenje o onom programu koji sam nakacio i da mi kazete koji
sve algoritmi postoje koji rade slican posao. :)

druga stvar: ...."jer ti sve reci pocinju na c:" - ne pocinju.on ne stavlja
u listu adresu fajla nego samo ime fajla

Rekli smo ti koji algoritmi rade to. A da bismo ocenili kako radi tvoj "Algoritam", moramo da znamo kako radi taj algoritam, a ne uzme reci, stravi u strukturu, bum tras i eto, gotovo.

I kako mislis da recimo ja na linuxu ocenim tvoj program?

Ako pricamo o algoritmu, onda daj pseudokod. Ako se radi o programu, mislim da si promasio forum.

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:



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

U brate kolki post! :)
Ja sam hteo da napravim nesto sto ce da radi ovo ali mnogo brze:

for tt=0 to list1.listcount
if list1.list(tt)="bla" then msgbox "fgdgf"
next tt

to sam podrazumevao pod "klasicnim algoritmom"

Prvo, to sto si ti napisao nije algoritam za poredjenje dva stringa, a kamoli za nalazenje podstringova, nego za pronalazak konstante u listi, sto je klasican algoritam sekvencijalnog pretrazivanja, slozenosti O(n) koji se moze unaprediti ako su ti elementi liste uporedivi na O(logn) (* binarno pretrazivanje *).... Samo jos jedan dokaz da si promasio celu pricu....

pozdravi Milos