Forum@DeGiorgi :: Pogledajte temu - Problem s alokacijom matrica reda 8k i vise

Problem s alokacijom matrica reda 8k i vise

through

[^/[Print]\]

Forum@DeGiorgi -> Programiranje 1 i 2

#1: Autor/ica: kkarlo,

Postano: 12:34 sub, 2. 11. 2013
—
Pošto je ovdje bilo govora o mallocu i slično da postavim svoje pitanje koje me muči već nekoliko dana...

Imam problem sa mallocom u rekurziji kada se pojavi n=8192.
Da ne stavljam cijeli kod, ovako otprilike izgleda program:
U mainu se zauzmu 3 matrice veličine n*n te se s njima poziva rekurzija.
U rekurziji se ide do n=4, a pri svakom pozivu se zauzme još 6*matrica veličine (n/2)*(n/2). U svakom pozivu rekurzije se pozove 7 puta rekurzija sa matricama n/2.
Riječ je o Strassenovom algoritmu za množenje matrica i sve funkcionira dobro do 4096 no trebam ga testirat i za matrice reda: 8192,16384 i 32786...
Već sam iscrpio google i stvarno neznam što da više radim.
Imam Win 7 64 sa 8GB RAM-a, i uspio sam u visual studiu pokrenut program ali nakon što je radio nekih 15 sati sam ga ugasio sa zaključkom da neće ni završit.
Ima netko neku ideju?
Rolling Eyes

#2: Autor/ica: venovako,

Postano: 17:18 sub, 2. 11. 2013
—
Jesi li siguran da kompajliraš 64-bitni, a ne 32-bitni EXE?
Inace, kani se malloc()iranja u rekurziji, bit će brže ako alociraš jednom izvan.

P.S. I sigurno imaš sve pripadne free() pozive na pravim mjestima?

Inače, 32k * 32k * 3 = 3G, pa ako koristiš iole veći tip podataka (sizeof(T) >= 4) imat ćeš vrlo zanimljivu situaciju već na startu.
Razmisli malo o tome.

#3: Autor/ica: kkarlo,

Postano: 18:06 sub, 2. 11. 2013
—

venovako (napisa):

Jesi li siguran da kompajliraš 64-bitni, a ne 32-bitni EXE?
Inace, kani se malloc()iranja u rekurziji, bit će brže ako alociraš jednom izvan.

P.S. I sigurno imaš sve pripadne free() pozive na pravim mjestima?

Inače, 32k * 32k * 3 = 3G, pa ako koristiš iole veći tip podataka (sizeof(T) >= 4) imat ćeš vrlo zanimljivu situaciju već na startu.
Razmisli malo o tome.

Znam da će bit brže ako alociram vani, ali ne znam kako bi to izveo kad su mi za svaki poziv rekurzije nužne nove pomocne matrice...
Imam sve free() pozive na pravim mjestima naravno... Mislim da mi ne bi radilo i za puno manje n-ove, a za recimo matricu 4096x4096 radi sve normalno.

I radi se o double matricama.
A nisam siguran gdje da podesim na 64 bitnu verziju? Probao sam sa Code Blocksom mi se ruši program, a u Microsoft Visual Studiu se ne sruši al čini mi se da nema kraja...
Sada sam pokrenuo malo prepravljenu verziju pa ću vidjet do sutra ujutro hoće li izbacit kakav rezultat. Laughing

Ako može savjet gdje mogu podesit na 64-bitnu verziju bilo bi super!
Very Happy

A nek za početak proradi za 8000, možda i to bude dovoljno pa neću trebat dalje ni računat...

#4: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 20:43 sub, 2. 11. 2013
—
Tesko je znati bez koda. Ako sam dobro shvatio tvoj opis, tvoj bi program trebao pojesti cca 1GB memorije za n = 8192, i faktor 4 za svaki iduci (duplo veci) n, sto znaci da bi trebao raditi kako spada ako imas 8GB RAMa.

Ako mislis da je kod prevelik za ovdje, pitaj na StackOverflow-u. Community je ogroman i rjesenja obicno brzo stizu i kvalitetna su.

#5: Autor/ica: venovako,

Postano: 21:42 sub, 2. 11. 2013
—

kkarlo (napisa):

Znam da će bit brže ako alociram vani, ali ne znam kako bi to izveo kad su mi za svaki poziv rekurzije nužne nove pomocne matrice...

Fino.
Prvo izračunaš koliko ti ukupno memorije treba za sve nivoe rekurzije.
Alociraš izvana toliko veliko polje i imaš pokazivač na prvi neiskorišteni element u toj velikoj alokaciji.
Kad ti zatreba nova matrica, uzmeš taj pokazivač kao početak nove matrice i povećaš ga za broj elemenata nove matrice.
Kad ti više ne treba nova matrica, smanjiš pokazivač za isti broj elemenata.
Zapravo radiš "ručni" malloc i free.

kkarlo (napisa):

A nisam siguran gdje da podesim na 64 bitnu verziju?

Otprilike ovako, varira od verzije VSa:
Klik na Solution, Properties, tamo nađeš Configurations i dodaš x64 konfiguraciju.
Postaviš je kao aktivnu.
Ako to ne možeš, znači da tvoj VS ne podržava 64-bitne aplikacije, a onda ćeš imati malo veću zabavu...

#6: Autor/ica: kkarlo,

Postano: 0:14 ned, 3. 11. 2013
—

venovako (napisa):

kkarlo (napisa):

Znam da će bit brže ako alociram vani, ali ne znam kako bi to izveo kad su mi za svaki poziv rekurzije nužne nove pomocne matrice...

kkarlo (napisa):

A nisam siguran gdje da podesim na 64 bitnu verziju?

Hvala!

Samim tim alociranjem izvana mislim da bi moj problem trebao nestati jer će program postat znatno brži pa neću ni trebat računat za tako velike matrice.
A izgleda da ne mogu podesit na 64-bitnu verziju no kao što rekoh neće mi ni trebat.
Hvala još jednom!

#7: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 0:21 ned, 3. 11. 2013
—

vsego (napisa):

Ako sam dobro shvatio tvoj opis, tvoj bi program trebao pojesti cca 1GB memorije za n = 8192,...

Fulah u procjeni; 2.5GB je blize stvarnosti. Ako je suditi prema prvom odgovoru ovdje, 32bita na 64bit Win moze ici do 2GB (ne bas, ali po defaultu... vidi link za detalje). Dakle, moguce je da stvarno to neces moci alocirati.

#8: Autor/ica: kkarlo,

Postano: 1:06 ned, 3. 11. 2013
—

vsego (napisa):

Ako sam dobro shvatio tvoj opis, tvoj bi program trebao pojesti cca 1GB memorije za n = 8192,...

Prepravih program pa više i nije potrebno, ali svejedno hvala...
Nadam se da se neću puno susretat sa takvim problemima, ali opet, dobro je znati.
Cool

Napisah malu rekurziju za izračunavanje potrebne memorije koja je zapravo toliko jednostavna da je moram podijelit.

int velicina(int n)
{
if(n==2)return 0;
return(velicina(n/2)+3*n);
}

Laughing

I da, kada sam u VS-u enable-ao large adresses onda mi se prestao rušit za 8192x8192.

Hvala još jednom.
Very Happy

Forum@DeGiorgi -> Programiranje 1 i 2

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.