[es] - Optimizacija pretrage dupliranih fajova

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.microsoft.com

+18 Profil

Re: Optimizacija pretrage dupliranih fajova

^{17.09.2003. u 18:48 - pre 251 meseci}

Citat:

Mikky:
Znaci za onaj posao sto mi je prva rutini radila 10 minuta a Windows Commander za samo 2 minuta (znaci 5x brze), sad mi treba samo 1 sekund a mozda i manje, nisam tacno merio
Znaci ubrzanje... 600 puta u odnosu na prvobitnu rutinu, odnosno 120 puta u odnosu na wincmd :)

Cekaj, Windows Commander procita ceo disk (tj dirove) i onda uradi sort i to sve zavrsi za ta 2 minuta.
Tvoj program samo sortira iste te podatke za par sekundi. Ali gde je tu citanje diska? Siguran sam da tvoj program ne moze da procita sve direktorijume za 1 sekundu.

Tj. otkud znas da i commander ne odradi sort (ili bilo koj vec algoritam) za istu tu 1 sekundu?

Takodje, redosled je bitan. Kada jedanput protrcis kroz sve direktorijume, Windows ce da kesira njihov sadrzaj, tako da ako prvo benchmarkujes Commander pa onda tvoj program dobices bitno razlicit rezultat nego da resetujes kompjuter, pa onda uradis istu stvar obrnutim redom.

Super je to sto si uradio, nego samo da utvrdimo objektivne mere...

Odgovor na temu

Mikky

Član broj: 18
Poruke: 1563
*.vdial.verat.net

ICQ: 44582291

+58 Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 01:12 - pre 251 meseci}

Rajko, ok ideja da umesto niza struktura imam niz pointera zvuci kao jos vece ubrzanje, samo trenutno sam ovim zadovoljan tako da me trenutno mrzi da opet prepravljam dosta toga ali uradicu i to uskoro

-zombie-, problem je sto u programu moze da se bira da li ce u kriterijum poredjenja ubaciti i creation/modify date/time tako da to xorovanje bi bilo ok u tom slucaju ali ove opcije uglavnom se nece koristiti jer ti kad kopiras fajl na drugo mesto njemu se promeni creation (ili bese modify) vreme tako da on ne bi bio prepoznat kao duplikat ako bih im poredio i ta vremena.
Uveo sam da uvek proverava po velicini i imenu, znaci te opcije nemogu da se menjaju a ove ostale mogu. Tako da mozda ako imas neki predlog sa ovakvom situacijom reci.

Reljam, znaci ovde pricam samo o uporedjivanju onoga u memoriji.. Naravno da je potrebno malo vise vremena da se ceo hdd pretrazi... khm, treba li da spominjem da sam i u tome prilicno nadmasio wincmd (u obzir je uzeto kesiranje hdd-a) ;)
Znaci 2 minuta treba wincmd da od trenutka kad zavrsi pretragu fajlova tj od trenutka kad pocne uporedjivanje do trenutka kad se zavrsi i izbaci rezultate duplih fajlova.
U tih 2 minuta on odradi sortiranje i uporedjivanje (pretpostavljam da sortiranje radi posle zavrsene pretrage mada moguce je i da sortira u letu, tj kako koji fajl nadje tako ga sortira)
A ovo sto sam ja napisao odradi quicksort za nesto ispod sekunde, a posle toga sledi uporedjivanje koje traje isto jako kratko ne vise od par sekundi. Znaci ceo posao odradi za par sekundi a wincmd za 2 min.
Naravno ovo su sve odokativne metode tako da ne drzite me za rec.

Sto se tice kesiranja, to ovde nisam uzimao u obzir jer je diskusija o onome sto se desava posle pretrage, tj ono sortiranje i uporedjivanje u memoriji, dakle brzina hdd-a ne utice.
Mada sam primetio da kad jednom uradim search sa mojim programom i posle jos jednom, taj drugi put hdd u opste se necuje, dok kad to isto uradim sa wincmd hdd se drugi put ipak malo cuje kad pretrazuje neke zabacenije folder.

Uradicu bas ovih dana malo preciznije merenje (mada nisam siguran kako to bas da izvedem najbolje) + jos malo optimizacije pa cu javiti rezultate.

-I know UNIX, PASCAL, C, FORTRAN,
COBOL, and nineteen other high-tech
words.

Odgovor na temu

bOkIcA
Bojan Abramovic
Novi Sad

Član broj: 1808
Poruke: 520
*.metrohive.net

Sajt: www.bokica.com

Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 01:20 - pre 251 meseci}

Probaj to da radis na network disku, mislim da se tada ne radi kesiranje.

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost

+5 Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 01:33 - pre 251 meseci}

hm.. da, shvatam. u tom slučaju ne bi moglo (btw, ne menja se vreme pri kopiranju).

elem, ako uvek porediš veličinu i ime, možeš recimo da xoruješ veličinu faja i jedan long (4 bajta) sastavljen od: dužine imena fajla (jedan bajt), i tri karaktera iz imena fajla (tri bajta).

e sad, još samo kako najbolje odabrati ta tri karaktera. recimo, bez mnogo filozofiranja, uzmi prvi, treći i poslednji karakter u imenu (naravno, reši spec. slučaj kada ime ima 2 ili manje karaktera nekako, sve jedno)

a što se merenja tiče, pa, najbolje je da onaj deo programa čiju brzinu meriš (a znaš i sam da ne valja meriti brzinu celog programa odjednom) ponoviš više puta, recimo 10 ili 100, i naravno, zapamtiš vreme pre izvršavanja i vreme posle, oduzmeš i podeliš sa 100.

to bi trebalo da je to.. ajde probaj, pa nam javi ;)

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
..g-c5300-3.dialup.nethere.net

+6 Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 02:25 - pre 251 meseci}

Citat:

Mikky:
Naravno sve ovo uradjeno u asembleru, pokusao sam sto manje da koristim promenljive u memoriji a sto vise registre

Nadam se da se ovo "sve" odnosi samo na funkciju koja sortira fajlove, jer praviti UI u asembleru nema baš nekog smisla.

Takođe, interesuje me koliko bi se izgubilo na performansama da si umesto qsort-a u asembleru koristio standardnu C++ std::sort() funkciju.

IOCC

Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.microsoft.com

+18 Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 02:31 - pre 251 meseci}

Nadam se da ako sortiras podatke, da ces sortirati niz pointera na podatke, a ne niz samih podatke (pointere bi naravno dereferencirao prilikom poredjenja). Ovo je mnogo brze od sortiranja samih podataka.

Odgovor na temu

Mikky

Član broj: 18
Poruke: 1563
*.vdial.verat.net

ICQ: 44582291

+58 Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 13:41 - pre 251 meseci}

Network disk nemam a i ne znam tacno sta je to, posto nemam iskustva sa mrezama
tako da ce to malo da saceka.

-zombie-, da li ja tebe dobro razumem:

Code:

1. poredjam po velicini
2. napravim xor hash od velicine i par karaktera

3. poredim po velicini,
   ako su isti
   {
   4. poredim hash, ako su isti
      5. poredim sve ostalo
   }

Dragi Tata, nazalost ja jednostavno ne znam da programiram GUI u c++ tj ceo taj oop
koncept programiranja mi je jako tezak, nemogu da se snadjem kad nevidim tok
programa, izgubim se kad gledam tu hijerarhiju klasa itd.. ali to je sad druga tema.
Tako da je meni sve u asm pa i UI ali MASM ima makroe koji odradjuju jako dobar
posao pa je asm u win32 prakticno kao C, samo sto daje bolje rezultate :)
npr ovo je cist asm bez makroa

Code:

cmp eax,0
jz do_stuff
jmp do_other_stuff

a ovo je sa MASM makroima

Code:

.if eax==0
; do stuff
.else
; do other stuff
.endif

Ovo ce MASM da prevede u onaj gore kod koji bi inace pisao rucno.
Takodje "invoke" makro
cist asm

Code:

push    parm2
push    parm1
call    API

C fazon

Code:

invoke API,parm1,parm2

A za std::sort() bi mogao da probam samo ne znam da li ona moze staticki da se linkuje
sa mojim programom, tj ako je to sve u sklopu neke klase (std?) onda ne znam da li ce moci?
A ako je to "standalone" C funkcija sa npr __stdcall nacinom pozivanja onda nije nikakav
problem jer sam vec radio slicne stvari.

Inace bas cu malo da pogledam po shareware trzistu utilite ovog tipa, bas da vidim ima
li neki koji radi ovaj posao brze od mene pa cu da javim :)

-I know UNIX, PASCAL, C, FORTRAN,
COBOL, and nineteen other high-tech
words.

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost

+5 Profil

Re: Optimizacija pretrage dupliranih fajova

^{18.09.2003. u 22:28 - pre 251 meseci}

Citat:

Mikky:

Code:

1. poredjam po velicini
2. napravim xor hash od velicine i par karaktera

3. poredim po velicini,
   ako su isti
   {
   4. poredim hash, ako su isti
      5. poredim sve ostalo
   }

najn. izračunaj hash za svaki fajl recimo kad ga učitaš u memoriju (tj podatke o njemu) i poređaj po tom hashu, a ne po veličini.

onda će (bar teorijski) da se u poređanom nizu jedan pored drugog, sa istim hashom, nađu samo fajlovi sa istom veličinom i istim imenom. time će ti broj poređenja biti mnogo manje nego ako ih ređaš samo po veličini...

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*

+6 Profil

Re: Optimizacija pretrage dupliranih fajova

^{19.09.2003. u 16:51 - pre 251 meseci}

Citat:

Mikky:

Dragi Tata, nazalost ja jednostavno ne znam da programiram GUI u c++ tj ceo taj oop
koncept programiranja mi je jako tezak, nemogu da se snadjem kad nevidim tok
programa, izgubim se kad gledam tu hijerarhiju klasa itd.. ali to je sad druga tema.

Nisam ni mislio na C++ i OOP, već na plain old C. Doduše, asembler sa makroima je već skoro C (hehehe), ali ipak mislim da je C udobniji.

IOCC

Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.verat.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Optimizacija pretrage dupliranih fajova

^{19.09.2003. u 17:03 - pre 251 meseci}

Citat:

Mikky:
A za std::sort() bi mogao da probam samo ne znam da li ona moze staticki da se linkuje
sa mojim programom, tj ako je to sve u sklopu neke klase (std?) onda ne znam da li ce moci?
A ako je to "standalone" C funkcija sa npr __stdcall nacinom pozivanja onda nije nikakav
problem jer sam vec radio slicne stvari.

Standardni C (ANSI, ISO, kako već ko voli da ga zove) obezbeđuje funkciju qsort kojoj prosleđuješ niz (preko početka i veličine elementa) i funciju za poređenje dva člana. Probaj sa tim da vidiš kakve rezultate daje :-)

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12851

+4784 Profil

Re: Optimizacija pretrage dupliranih fajova

^{19.09.2003. u 22:11 - pre 251 meseci}

Pratim sve vreme ovu temu i moram reci da sam primetio da ne uzimate u obzir mogucnost da fajlovi budu duplirani a da im ime (na primer) bude razlicito. Isto moze da bude slucaj sa datumom i svim ostalim osim sa veliciom tako da mi izgleda pogresno raditi sa hash-om koji se dobija iz velicine i jos necega ili uopste sa uporedjivanjem bilo cega osim velicine.
Naravno sve ovo ne vazi ako je program od pocetka i trebao da bude takav da pronalazi iste fajlove sa istim osobinama (a ne samo saadrzajem).
Ili sam ja nesto pogresno shvatio (a mislim da nisam)

...

Nebojsa Milanovic: Što se tiče Trumpa, smatram ga vrhunskim predsednikom i voleo bih da živim u državi na čijem je on čelu.
Nebojsa Milanovic: Rusija ne laže, ne vodi osvajačke ratove
Nebojsa Milanovic: Trump je svetla tačka u USA blatu.

Odgovor na temu