Niz od n x n elemenata je jednodimenzionalan i referenciraš ga preko jednog pointera (na taj niz).

Kad imamo više od jednog "subscript operatora" (uglate zagrade), čime označavamo višedimenzionalnu matricu, da bi mogli koristiti referenciranje kroz više dimenzija, moramo imati (u slučaju 2D matrice) niz pointera na niz pointera. To nam u konačnici omogućava pisanje nečeg poput A[x][y]. Naravno, uvijek možemo zavrzlamu svesti na jednodimenzionalni niz pa pisati nešto poput A[x*broj_stupaca+y]. U praksi, potonje rješenje znači da za pristupiti pojedinom elementu matrice moramo obaviti jednu računsku operaciju više (množenje), što znači da je sporije.

I da, znam, još jedno golublje govno. Ali golub po golub pa više ni Lt. Gruber ne bi znao gdje je parkirao svoj dragi tenk.

Dobro si shvatio. Ispravnije bi bilo ovako kako si napisao malloc ((n-1)*(n-1)*sizeof(double), ali tada gubiš mogućnost korištenja [i][j] notacije, već moraš preći na [i*n+j], odnosno "simuliranje" dvodimenzionalne korištenjem jednodimenzionalne.

Pristup je (teoretski) neispravan, jer u nastavku rekurzivno uredno prenosi samo m, odnosno adresu prvog elementa polja. Teoretski, svaki malloc može zauzeti komad memorije nepovezan sa onim prijašnjim, i na opterećenom stroju sa malo memorije to će se dogoditi, a tada prenošenjem polja napravit će katastrofu. U praksi će sva memorija biti lijepo posložena jedna za drugom i nema problema.




Stjecajem okolnosti neko vrijeme sam dosta programirao web aplikacije. I dobivao probleme koji su se lako mogli riješiti rekurzijom. Problemi koji, kad se skalira broj korisnika i broj rekurzivnih poziva (jer ono što testiraš na testnom stroju nikad nije jednako onome u produkciji) završe na ponovnom programiranju, bez rekurzije, sa cachiranjem sličnih međurezultata (što se u slučaju determinante može napraviti) itd.

Rekurzija se, ako je moguće, treba izbjegavati. Naravno da je nećeš izbjegavati ako si u cajtnotu, ali korisnik će i za 100ms biti sretan ako se isti algoritam obavlja 100-200-1000 puta. Zato postoje verzije 2.0, 3.0 itd

Pointerska aritmetika ne radi ništa bolje množenje i zbrajanja od obične aritmetike, a nekak se mora doći do m[i][j]-tog polja što će interno isto dati i*max+j. Teza o množenju tu pada o vodu. A da ne kažem kako je sporije napraviti x (npr 10) malloca nego 1

Golub po golub . .

Primjer je takav kakav je jer je školski da ga svi kuže. Da je optimalan - daleko od toga, ali očito autor zna objasnit svojim studentima kako to radi pa bi mu zbog toga nabacio karmu

Zašto bi palo u vodu ako govorimo o pointerima na pointere (za 2D matricu)? Svaki redak (ili stupac, nebitno) je pohranjen u jedan niz. I imamo pointer na njega. A imamo i pointer na niz tih pointera. Dakle, do svakog elementa možemo doći bez množenja. Sve to skupa pod pretpostavkom da imamo valjani razlog za uopće čuvati toliko pointera, u što ne ulazim.

stajpZg je napisao:


To su svakako okolnosti u kojima već ta razlika u utrošku resursa i vremena više nije ni u praksi beznačajna. Onda je tu netko tko će odlučiti što je jeftinije - platiti vrijeme potrebno za razvoj optimalnog rješenja jednokratno, ili plaćati potrebu za jačim resursima stalno. Ako je jeftinije dati stvar na ponovno programiranje (odnosno potrošiti 2, 5, 10 ili 20x više vremena na razvoj), napravit će se tako, naravno. Web aplikacije s ogromnim brojem korisnika svakako jesu dobar praktičan primjer za takvu situaciju. Ono što sam ja radio nisu bile mrežne, nego single user aplikacije koje su korisniku štedjele 95% vremena u odnosu na utrošak vremena pri korištenju Excela ili nekog sličnog (za tu svrhu) polualata. Tim će korisnicima zauvijek ostati nevažno da li su sa 1h utrošak vremena sveli na 2'30" ili na 2'31".

To je taj praktični aspekt kojem bi trebao poučiti svoje studente. Bezuvjetno reći "izbjegavajte rekurziju ako se može ikako drugačije" znači stvoriti im ogradu u razmišljanju, a to znači stvoriti od njih loše inženjere.

Predavao sam i ja na faksu. Znao sam jako dobro da studenti dobivaju i previše teorije i zato sam se trudio dati im što više praktičnih pogleda na tu teoriju. Mnogi su me upravo zbog toga zapamtili po dobrom.

Djipi je napisao:


To ovisi o tome kako compiler prevodi taj kôd, zar ne? Da li se to prevodi kao indirektno relativno adresiranje ili kao množenje, zbrajanje i onda direktno apsolutno adresiranje?

I to je jedan od razloga zašto mi je C bljak. Glumi neki sistemaški low level i kenja s tim polurješenjima (kao ovo s prosljeđivanjem matrice), a s druge strane zapravo nemaš pojma kako se to prevodi na jezik procesora. Ti se možeš ubiti od optimiranja, a što na kraju ispadne - nitko ne zna.

Djipi je napisao:


Da, teoretski - originalno polje m[i] sadrži adrese na prve (nulte) elemente svakog pojedinog retka. Što bi bila pointerska aritmetika sa zbrajanjem. Onda uzme taj broj, i od njega ponovno napravi pointersku aritmetiku sa zbrajanjem. U praksi, sve je nakalemljeno jedno na drugo, i svaki bolji optimizator koda (a nažalost, svaki C kompiler ima takvo što u sebi) će pretvoriti to u preračunavanje koje bi obavili ručno. A ako i ne bi, i dalje je jedan malloc brži od 10 malloca, i to puno brži nego što bi netko mogao reći da je i*max + j sporo

smayoo je napisao:


Studenti su zato dobili uvid u kojim situacijama je rekurzija dobra. Naravno da im je, u realnom svijetu sa realnim rokovima i realnim ograničenjima njihovog znanja i ideja, rekurzija još jedan od alata na raspolaganju - zato rekurziju i uče i dani su im primjeri. Ali ako mogu birati, ako je mogu izbjeći - neka je izbjegavaju. Lakše je napraviti hummer nego tenk. OK, tenk će ići svugdje, raznijet skoro svakog neprijatelja, ali hummer je brži, pokretljiviji, i u većini slučajeva - posve dostatan da razvali neprijatelja.

Da, a ako nam se ne svidi ono što dobijemo, uvijek možemo ubaciti vlastiti asm blok u C kod pa imati potpunu kontrolu. Siguran sam da te ideja veseli.


Svakako bih očekivao ovo prvo. Ali s obzirom da nisam siguran bih li znao ispravno pročitati asemblirani kod za x86, neću se truditi testirati. Mogu jedino pojasniti zašto bih uopće očekivao to što bih očekivao - "pointerska aritmetika" (točnije, zbrajanje) iz perspektive opcodova je "besplatna" utoliko što adresnom registru (a pointer u jednom trenutku seli u njega) možemo pristupiti s "displacementom" - neki opcod tipa "move #42,8(a0)" u samo jednoj instrukciji upiše vrijednost 42 na adresu pohranjenu u adresnom registru a0 (naš pointer na niz), uvećanu za 8 bajtova (što bi bio neki index [1], za double). Zato očekujem da u adresnom registru završi pointer i isto tako očekujem da se konkretnom indexu pristupi s displacementom unutar jednog jedinog opcoda. Alternativa s korištenjem niza za n x n povlači za sobom kalkulaciju finalne adrese koju MC68000 ne bi mogao obaviti u jednom koraku. Možda x86 ima instrukciju i za to (tipa "pomnoži i pribroji" ) - ne bi me iznenadilo. Što nas već vodi k zaključku da je u konačnici bitno i za koju arhitekturu kompajler uopće optimizira kod. Pa je najbolje s tim se previše ne zamarati.

Istina.

Djipi je napisao:




Ali zapravo ne. Ne veseli me. Ili programiram u ASM-u, ili u nekom normalnom jeziku. Ne volim hibridna rješenja.

I, BTW, ubacivanje ASM kôda se može i u Pascalu (Borlandovom, za druge ne znam).



Odgojen na Motoroli, kao i ja Zadnji puta kad sam proučavao (što je bilo još u vrijeme 80486), Intelov procesor nije imao takvo što. A kamoli 8 32-bitnih adresnih registara. Pa su me mentor i kolege nagovarali da diplomski napišem u C-u, na MC68030 platformi. Fuj! Odupro sam se toj inicijativi i napisao cijeli program (adaptivni fuzzy regulator brzine motora) u ASM-u, a oni su se poslije čudili kako je to na Motoroli lako. Jer je na Intelu bilo mission impossible