Τα πάντα για την C

[Ilias95]

Ας πούμε ότι θέλουμε να γράψουμε μια function με prototype:

Κώδικας: Επιλογή όλων

int inner_product(int a[], int b[], int n)

Οι a, b είναι arrays που θα έχουν τον ίδιο αριθμό στοιχείων.
Η συνάρτηση πρέπει να επιστρέφει το "a[0] * b[0] + a[1] * b[1] + ... a[n-1] * b[n-1]".


Αν την έγραφα χρησιμοποιώντας subscripting θα έγραφα κάτι τέτοιο:

Μορφοποιημένος Κώδικας: Επιλογή όλων

int inner_product1(int a[], int b[], int n)
{
    int i, inner_product = 0;
    
    for (i = 0; i < n; i++)
        inner_product += a[i] * b[i];
    
    return inner_product;
}

Αν απ' την άλλη αν έπρεπε να την γράψω χρησιμοποιώντας pointer arithmetic θα έγραφα κάτι σαν:

Μορφοποιημένος Κώδικας: Επιλογή όλων

int inner_product2(int a[], int b[], int n)
{
    int *p, *q, inner_product = 0;
    
    for (p = a, q = b; p < a + n; p++, q++)
        inner_product += *p * *q;
    
    return inner_product;
}

Στην τελευταία με προβληματίζει το ότι χρησιμοποιώ 2 pointers. Μπορεί να γραφεί αλλιώς;

Αν όχι, ποια απ' τις δύο συναρτήσεις θα εκτελεστεί πιο γρήγορα;

[migf1]

Βασικά ο compiler μετατρέπει το 1ο στο 2ο, το οποίο είναι ταχύτερο (δεν γίνεται με λιγότερους από 2 δείκτες)... οπότε αν σου είναι πιο ευανάγνωστο το 1ο, κράτα το 1ο (έτσι κι αλλιώς θα μεταφραστεί αυτόματα στο 2ο, εσωτερικά )

[stamatiou]

Βρήκα τον αλγόριθμο Insertion Sort (http://en.wikipedia.org/wiki/Insertion_sort) και νομίζω πως τον έχω καταλάβει, αλλά με αυτόν το pseudocode δεν τα βγάζω πέρα!

Δεν καταλαβαίνω πως λειτουργούν οι γραμμές 1 έως και 8 :/

[migf1]

Βρήκα τον αλγόριθμο Insertion Sort (http://en.wikipedia.org/wiki/Insertion_sort) και νομίζω πως τον έχω καταλάβει, αλλά με αυτόν το pseudocode δεν τα βγάζω πέρα!

Δεν καταλαβαίνω πως λειτουργούν οι γραμμές 1 έως και 8 :/

Δεν έχει εμφανιστεί η εικόνα. Πέρα από την εικόνα, τι περιμένεις να σου βγάλουν οι γραμμές που αναφέρεις στην έξοδο και τι σου βγάζουν λάθος;

[stamatiou]

Βρήκα τον αλγόριθμο Insertion Sort (http://en.wikipedia.org/wiki/Insertion_sort) και νομίζω πως τον έχω καταλάβει, αλλά με αυτόν το pseudocode δεν τα βγάζω πέρα!

Δεν καταλαβαίνω πως λειτουργούν οι γραμμές 1 έως και 8 :/

Δεν έχει εμφανιστεί η εικόνα. Πέρα από την εικόνα, τι περιμένεις να σου βγάλουν οι γραμμές που αναφέρεις και τι σου βγάζουν στην έξοδο;

http://imageshack.us/photo/my-images/20 ... otgqb.png/

[migf1]

Οκ, ποιο είναι το πρόβλημα; Ποια γραμμή συμπεριφέρεται διαφορετικά από ότι περιμένεις;

[stamatiou]

Οκ, ποιο είναι το πρόβλημα; Ποια γραμμή συμπεριφέρεται διαφορετικά από ότι περιμένεις;

Απλά δεν καταλαβαίνω τι ακριβώς κάνουν οι γραμμές 5 ως 8

[migf1]

Δημιουργούν τη θέση που θα μπει το key, στο ήδη ταξινομημένο τμήμα του πίνακα A.

[migf1]

@migf1
Μου πήρε αρκετή ώρα αλλά τελικά νομίζω ότι επιτέλους κατάλαβα πως δουλεύει.

Το κλειδί στην κατανόησή του είναι η κατανόηση του πως δουλεύει το pointer-arithmetic.

Από τη στιγμή που...

α) ο 2-διάστατος πίνακας a[NROWS][NCOLS] όπως ξέρουμε εσωτερικά υλοποιείται μονοδιάστατα σε συνεχόμενη μνήμη, συνολικού μεγέθους (NROWS * NCOLS) * sizeof(int) bytes

β) το p ορίζεται δείκτης σε πίνακα NCOLS ακεραίων (δηλαδή ανά πάσα στιγμή δείχνει σε τμήμα μνήμης μεγέθους NCOLS * sizeof(int) bytes)

τότε κάθε p++ προχωράει στη μνήμη κατά NCOLS ακέραιους, που επί της ουσίας είναι μια γραμμή του πίνακα a[ ] [ ] (το p-- θα πήγαινε πίσω κατά NCOLS ακέραιους).

Δηλαδή κάθε ++ του p προχωράει αυτόματα τον p κατά NCOLS * sizeof(int) bytes στη μνήμη

[migf1]

Για να υπάρχει και σε κώδικα στο φόρουμ, φαντάσου την εξής υλοποίηση, που ορίζει απευθείας τον 2-διάστατο πίνακα μονοδιάστατα (όπως το κάνει έτσι κι αλλιώς ο compiler)...

Μορφοποιημένος Κώδικας: Επιλογή όλων

#include <stdio.h>

#define NROWS		3
#define NCOLS		3

int main( void )
{
	int n, i=1, a[ NROWS*NCOLS ] = {1, 2, 3, 4, 5, 6, 7, 12, 14 };
	const int NELEMS = NROWS*NCOLS;	/* για να μην υπολογίζεται συνεχώς στη συνθήκη του loop (περιττή καθυστέρηση) */

	for ( n=0; n < NELEMS; n += NCOLS )
		a[n+i] = 0;

	return 0;
}

ΥΓ. Και πάλι τσέκαρέ το, γιατί το έγραψα από μνήμης.