Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Dinamicko alociranje memorije, rekurzija, sortiranje i performanse

[es] :: .NET :: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse

[ Pregleda: 5727 | Odgovora: 15 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Mikky

Član broj: 18
Poruke: 1563
..njuel-bg.customer.sbb.co.yu.

ICQ: 44582291


+58 Profil

icon Dinamicko alociranje memorije, rekurzija, sortiranje i performanse24.07.2006. u 16:23 - pre 215 meseci
Zanima me koji nacin bi bio najoptimalniji u smislu performansi (najveca brzina, najmanje memorije) da se u memoriju smesti veliki broj elemenata niza s tim sto broj elemenata nije u napred poznat?

Konkretno, ako pustim rekurzivnu funkciju koja trazi fajlove na sistemu i hocu da od svakog fajla sacuvam neke podatke (ime, velicina, datum) koje bi bilo najoptimalnije resenje za to? Na danasnjim racunarima broj fajlova je dosta velik, reda par stotina hiljada ili cak nekoliko miliona. Ako mi za svaki fajl prosecno treba oko 100bajtova memorije to je 100MB na milion fajlova, i niz od milion clanova. Kasnije bih trebao da taj niz sortiram (recimo po velicini).

Dakle koje su opcije, odakle poceti sa resavanjem ovog problema i na koji nacin bi bilo najefikasnije ovo uraditi u C#?
-I know UNIX, PASCAL, C, FORTRAN,
COBOL, and nineteen other high-tech
words.
 
Odgovor na temu

zulfy
BiH

Član broj: 102366
Poruke: 5
*.tel.net.ba.

Sajt: www.prozorama.com


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse25.07.2006. u 22:17 - pre 215 meseci
na pamet mi odmah padne implementacija liste? ili bilo što iz System.Collections..... ima mnogo toga što pomaže pri takvim stvarima.... liste, stogovi, redovi.... uređeni parovi i sl...
npr napravis strukturu nekog tipa i implementiraš listu tih struktura.... imaš i sortiranja po vlastitim kriterijima ako implementiraš interface IComparable (ako koristiš vlastite strukture)....

to su ugrađeni tipovi/funkcije za rad s listama i sortiranjima.... vjerojatno bi trebali biti i najbrži.... no možda postoji nešto brže....
Realizacija je umjetnost.....
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse26.07.2006. u 02:10 - pre 215 meseci
Radis indexer, ha?
Indexiras sve i onda puknes binary-search po sortiranom nizu, jeli to?

Mozes koristiti vektor, ali se prije pobrini da za sebe ima rezerviranu potrebnu kolicinu memorije da se ne mora cesto realocirati.
Ili koristi listu na koju isto mozes iplementirati binary search.
 
Odgovor na temu

Mikky

Član broj: 18
Poruke: 1563
*.dynamic.sbb.co.yu.

ICQ: 44582291


+58 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse31.07.2006. u 21:23 - pre 215 meseci
Ok malo sam eksprimentisao sa ArrayList i HashTable kao dinamickim strukturama da vidim koja ima bolje performanse. Napravio sam 2 identicne funkcije koje dodaju velik broj elemenata ovim strukturama i merio koliko im je potrebno da taj broj elemenata dodaju. Memory usage sam merio odokativno iz task managera. Ukratko zakljucak: Izgleda da je ArrayList bolji u svakom pogledu za ono sto meni treba.


Evo kako izgledaju benchmark funkcije:
Svaki elemnt koji sam dodavao u ArrayList i HashTable je niz od 100 clanova (slicne velicine kao klasa koja predstavlja elemente u mom programu). Svaki put sam pravio novi niz da bih izbegao da .NET Runtime uvek dodaje referencu na isti objekat (pokusavam da oponasam moj program gde je skoro svaki element razlicit).

Code:

        static public void arraytest(int count)
        {
            ArrayList a = new ArrayList();
            int[] b=new int[100];

            for (int i = 0; i < count; i++)
            {
                for (int j = 0; j < b.Length; j++) b[j] = i;

                a.Add(b);
            }
        }
        static public void hashtest(int count)
        {
            Hashtable a = new Hashtable(53);
            int[] b = new int[100];

            for (int i = 0; i < count; i++)
            {
                for (int j = 0; j < b.Length; j++) b[j] = i;

                a.Add(i,b);
            }
        }



Evo i koda koji poziva ove metode i prikazuje vreme izvrsavanja
Code:

            int count = 5000000;

            Win32.HiPerfTimer pt = new Win32.HiPerfTimer();    
            pt.Start();         
            arraytest(count);
            pt.Stop();  
            Console.WriteLine("\n\nDuration: {0} sec\n", pt.Duration); 

            pt = new Win32.HiPerfTimer();    
            pt.Start();         
            hashtest(count);
            pt.Stop();
            Console.WriteLine("\n\nDuration: {0} sec\n", pt.Duration);



Rezultati za razlicit broj elemenata (vrednost count promenljive)

Citat:

int count = 2000000;
Duration: 1.57137652969861 sec
Duration: 3.35605894045193 sec

int count = 3000000;
Duration: 2.64741831713248 sec
Duration: 5.56915110719379 sec

int count = 4000000;
Duration: 3.18958135740716 sec
Duration: 7.73513980128759 sec

int count = 5000000;
Duration: 4.42244223777044 sec
Duration: 11.8514084890677 sec


Probao sam i da mi count bude 10000000 (10 miliona) ali dok ArrayList to zavrsi za 10ak sekundi HashTable posle minut pojede svu memoriju (swap included) pa sam morao da ga ubijem iz task managera.
Klasu koju sam koristio za merenje vremena mozete naci ovde http://www.codeproject.com/csharp/highperformancetimercshar.asp

Dakle resenje za koje sam se odlucio: Rekurzivna pretraga fajlova i svaki nadjen fajl ce biti smesten u ArrayList kao element neke moje klase koja uzima ime fajla, velicinu, full path itd.

Eto pa ako neko ima neki komentar u vezi ovoga i eventualno da li sam negde pogresio u rezonovanju neka kaze.
-I know UNIX, PASCAL, C, FORTRAN,
COBOL, and nineteen other high-tech
words.
 
Odgovor na temu

radoica

Član broj: 12972
Poruke: 158
*.yubc.net.



+3 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse31.07.2006. u 22:26 - pre 215 meseci
Probaj klasu List<>
Trebalo bi da bude brza od ArrayList-a
Nalazi se u System.Collections.Generic namespace-u
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse01.08.2006. u 08:12 - pre 215 meseci
Bitno je da znas jednu stvar: Bottleneck ti je u IO::Directory::GetDirectories i IO::Directory::GetFiles.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse01.08.2006. u 15:07 - pre 215 meseci
Citat:
Mikky: Eto pa ako neko ima neki komentar u vezi ovoga i eventualno da li sam negde pogresio u rezonovanju neka kaze.


Imas malu gresku u rezonovanju, kad radis performance test onda pravis idealne uslove za funkcionisanje te klase, znaci koristis broj iteracija za koji je siguran da nece zagusiti sistem. Ako guras na gore dok sistem izdrzi, onad se to zove stress testing i nije primenljivo u tvojoj diskusiji. Znaci raditi trilion iteracija i ubacivati int[100]. Btw, int[] je referenca (objekat tipa Array), tako ce Array List raditi isto ubacivao ti u njega int, int[100] ili int[100000], razlika je samo koliko ces ometanja u merenju imati od memorijskog podsistema u njegovim pokusajima da smesti sve tvoje nizove. To ti bas i ne govori o tome koliko je brz sam Array List, zar ne?

Dalje, ArrayList je definitivno brzi od HashTable, to si mogo i da pitas, nisi morao da se patis Array list je baziran na obicnom Array-u samo dinamicki alocira velicinu niza (pocinje po defaultu od 4 elementa ako mu se drugacije ne kaze i duplira se po potrebi) i osigurava da su svi elementi reference.
Hash table sa druge strane za svaki element pravi kanticu (bucket) u koju ubaci hash kljuca (zato se i zove hash table), kljuc i vrednost, i onda ima kompleksnu logiku odrzavanja niza tih kantica kako bi elemnti mogli da se preuzimaju po kljucu. U tvom slucaju ubacivanje lementa u hashtable podrazumeva:
1) kreiranje hash-a za kljuc
2) provrava da li hash vec postoji u listi (zbog duplikata)
3) kreira bucket za tvoj element
4) provera da li je niz bucketa dovoljno velik i osigurava da postoji mesto i ubacuje lement (ovo je jedino sto array list radi)

Sve u svemu, nije bas brzo.


Citat:
radoica: Probaj klasu List<>
Trebalo bi da bude brza od ArrayList-a


Sto se tice funkcionisanja, ArrayList = List<Object>, nema vece razlike, isto koristi Array u pozadini, samo sto osigurava da elementi ne samo sto su reference, nego su i tipa T, sto olaksava programiranje dinamickih nizova i compile-time proveru.

Citat:
Mikky:  Ako mi za svaki fajl prosecno treba oko 100bajtova memorije to je 100MB na milion fajlova, i niz od milion clanova. Kasnije bih trebao da taj niz sortiram (recimo po velicini).


Hash table u startu ispada iz kombinacije, kao prvo uopste nema sortiranje.

List<T> ili ArrayList mogu da prikupe sve tvoje objekte, ali racunaj na oko 120-130Mb za milion fajlova ako ti je fajl objekat oko 100 bajtova. problem ces imati sa brzinom disk sistema (kao sto ti je NrmMyth rekao) i definitivno sa sortiranjem tih milion objekata Posto ces porediti polje iz objekta koje je u listi sa drugim takvim (u osnovnoj varijanti), na tvojoj masini ce sort na 5 miliona elemnata trajati oko 30-tak sekundi (poredeci tvoje rezultate sa mojima, pod uslovom da swap miruje ).
Ako ne koristis informacije o svih milion fajlova, mozda da razmislis o varijatni smestanja tih podataka u neku bazu i onda koriscenje SQL-a za filtriranje/sortiranje?


Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse01.08.2006. u 15:36 - pre 215 meseci
OT: Jeli ArrayList lista ili vektor?
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse01.08.2006. u 17:34 - pre 214 meseci
Citat:
NrmMyth: OT: Jeli ArrayList lista ili vektor?


Da bih ti to rekao, moras mi objasniti razliku izmedju liste i vektora , posto je na engleskom to jedno te isto. list, array i vector su sinonimi, bar sto se programiranja tice.

E sad, ja kontam da je u nasim jezicima bilo gomila prevodjenja, do-prevodjenja i re-intepretacija engleskih termina, ali da bi uklonio zabunu:

ArrayList (i List<T>) je array kojem nije unapred poznat broj elemenata. Ni jedan ni drugi nisu jezicke konstrukcije (kao sto je staticki Array), vec su klase tj. wrapperi oko System.Array objekta koji se staraju o realokaciji statickog niza u pozadini, dajuci iluziju da je niz dinamicki.
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse02.08.2006. u 07:38 - pre 214 meseci
To je onda vektor...

Mene je "teorija algoritama" naucila na ovakve nomenklature
vektor = obicno polje (array) koje zauzima cijeloviti blok memorije za clanove, potrebno ga je cijeloga relocirati za prosirenje, pristup clanovima je preko indexa u O(1)
lista = povezana lista (linked list), memorija za clanove se nezavisno alocira, po dodavanju novog clana, pristup clanovima se ostvaruje linerarnom pretragom od korijena liste u O(N)

STL koristi ovakvu nomenklaturu za svoje kontenjere - list<T>, vector<T>.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse02.08.2006. u 14:14 - pre 214 meseci
Citat:
NrmMyth: To je onda vektor...
Mene je "teorija algoritama" naucila na ovakve nomenklature
vektor = obicno polje (array)
lista = povezana lista (linked list)


Ok, fala. Apsolutno si u pravu, moj previd. Istina je sto kazu da se stvari zaboravljaju kad se ne koriste Povezane liste nisam video od vezbi na faksu .

List se ovde definitivno vise ne koristi u tom kontekstu, kao ni sam koncept povezanih lista (koristi se njen stariji brat n-arno drvce, ali same liste ne). Jednostavno, enkapsulacija je dozvolila kreiranje "emuliranih" dinamickih nizova sa statickim nizom (array) u pozadini koji uz optimizovanu realokaciju i bitblt elemnata niza pri add/insert/delete daju privid dinamickih nizova sa boljim performansama nego sto ih ima linked lista. Pride imas pristup bez pretrage preko indeksa. Ako bas hoces da "listas" elemente mozes iz objekta izvuci IEnumerator. Generalno, ono sto STL tretira kao vector<T>

Medjutim, nisam odavno cuo termin vector, bar ne u konceptu programiranja, to je vise termin koji matematicari koriste za array u linearnoj algebri. Ono sto se zaboravlja je da matematicki vektor nije samo niz elemenata, ima i dodatnu karakteristiku, moze se predstaviti kao "ispeglana" matrica velicine nx1 (column iliti vertikalni vektor) ILI 1xn (row iliti horizontalni vektor); u programiranju array predstavlja samo niz n elemnata, nema dvodimenzionu karakteristiku kakvu ima vektor u matematici (osim ako se ne deklarise kao dvodimenzioni niz), tek se kroz primenu u kodu (npr mnozenje dva vektora) odredjuje koji je niz horizontalni vektor a koji vertikalni. Zato nisam odusevljen tom nomenklaturom, array iliti niz je sasvim odgovarajuce i jednoznacno (uz podelu na staticke i "dinamicke" ).
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
*.lionbridge.com.



+6 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse02.08.2006. u 14:28 - pre 214 meseci
U teoriji se ne koristi izraz "vector" za nizove. To je STL terminologija, a nije mi jasno zašto i tamo nisu koristili izraz "array" - ludi Aleks Stepanov je uveo neke vrlo čudne naming konvencije :)

A lista je lista, iliti vezana lista (linked list) i tu je Stepanov u pravu, a Java i .NET drugari nisu.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse02.08.2006. u 16:45 - pre 214 meseci
Citat:
Dragi Tata: U teoriji se ne koristi izraz "vector" za nizove. To je STL terminologija.

Kad bolje promislim to istina, ali danas vektor i array su toliko izjednaceni u mojoj okolici, medju ljudima s kojima ja pricam.

Citat:
mmix: List se ovde definitivno vise ne koristi u tom kontekstu, kao ni sam koncept povezanih lista

Hocete reci da .NET class library nema ni jednu klasu implementiranu kao listu.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse02.08.2006. u 19:03 - pre 214 meseci
Citat:
NrmMyth: Hocete reci da .NET class library nema ni jednu klasu implementiranu kao listu.


Nije da nema, ali tek od .NET 2.0: LinkedList<T>, dvostruko uvezana lista, i koliko vidim prilicno dobra implementacija.
Iskreno ne bih ni obratio paznju da me nisi podsetio na to
Trenutno ga "fabricki" koriste TimerThread i Regex klase.

Zanimljivo je isto da postoji i dinamicko sortirano binarno drvce TreeSet<T>, ali je oznaceno kao internal i koristi ga samo SortedDictionary<T>. Vrlo sebicno moram priznati, ovo bi bas dobro doslo u nekim situacija; tebi narocito, jel izgleda da je stabilan sort

Citat:
Dragi Tata: A lista je lista, iliti vezana lista (linked list) i tu je Stepanov u pravu, a Java i .NET drugari nisu.


Ja znam za termin linked list, ali kad mi neko kaze lista, prva asocijacija mi ja na List control Deformacija, sta ces Ja i dalje stojim da lista nije isto sto i povezana lista
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Bope

Član broj: 62233
Poruke: 291
*.COOL.ADSL.VLine.verat.net.

Sajt: www.shortsms.me


+4 Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse02.08.2006. u 21:50 - pre 214 meseci
A da li je neko od vas racunao koliko bi trajalo sortiranje 5 000 000 clanova?
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse03.08.2006. u 07:15 - pre 214 meseci
Citat:
Bope: A da li je neko od vas racunao koliko bi trajalo sortiranje 5 000 000 clanova?

Kad sam na natjecanjima uzimam da mi 10^6 operacija prodje u sekundi, danas je to i 10^7 i 10^8, ali sigurno je sigurno.
Uglavnom ti to prodje za sekundu... osim ako nemas neku "tesku" comparison funkciju.

Citat:
mmix: Zanimljivo je isto da postoji i dinamicko sortirano binarno drvce TreeSet<T>, ali je oznaceno kao internal i koristi ga samo SortedDictionary<T>. Vrlo sebicno moram priznati, ovo bi bas dobro doslo u nekim situacija; tebi narocito, jel izgleda da je stabilan sort

Ako je SortedDictionary<T> isto sto i map<T1, T2> u STL-u onda nije tesko i preko toga izvesti sort.
No kako sam ja mlad i voljan ja cu pisati svoj... :)

LinkedList<T> je dosao tek u .NET 2.0... a dobro...
Znao sam da mora postojati struktura liste, makar i bila samo kao internal. Jer ona IMA svoju svrhu i bilo bi je glupo zanemarivati.
 
Odgovor na temu

[es] :: .NET :: Dinamicko alociranje memorije, rekurzija, sortiranje i performanse

[ Pregleda: 5727 | Odgovora: 15 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.