Ερωτήσεις για C

[Star_Light]

Στον BUbble sort το inner loop ειναι οι συγκρισεις ενω το εξωτερικο ειναι ποσες φάσεις συγκρισεων θα κάνει.... πχ

 

αν κανει 2 φάσεις των 4 συγκρισεων τοτε συνολικα θα κάνει 8 συγκρισεις. Εμενα η απορια μου ηταν πως ξερουμε εξαρχης ποσες φάσεις των n-1 συγκρισεων χρειαζομαστε..... για να διαμορφωσουμε το outer loop . Mια απαντηση ηταν οταν δεν μπει στο if.... εκει έχεις τελειώσει οκ . Αυτο για τον optimized ομως.

[migf1]

Δεν έχω καταλάβει τι ρωτάς Κώστα.

 

Πάντως ξεκίνησα από χτες να βάζω κι άλλους αλγόριθμους σε εκείνο τον κώδικα που σου είχα ποστάρει για την bubble-sort. Κλασικά αποδεικνύεται δυσκολότερο εγχείρημα από ότι υπολόγιζα αρχικά (λέω ούτε μια μέρα δεν θα με πάρει, και τελικά είμαι στην 2η μέρα κι ακόμα δεν μπορώ να βγάλω άκρη).

 

Τα νούμερα πρέπει να είναι άλλα αντί άλλων, γιατί νομίζω αλλού μετράω και iterations μαζί με comparisons, κι αλλού τα μετράω ξεχωριστά

 

Για το μόνο που είμαι σίγουρος πως είναι εντάξει από πλευράς κώδικας είναι το execution time (τελευταία ένδειξη) το οποίο το έχω βάλει στα optimized versions. Α, ψέμματα... και για τα swaps (swp) κείμαι σίγουρος πως είναι ακριβή τα νούμερα. Για τα recursive-calls (rsv) ως νούμερο είμαι επίσης σίγουρος, αλλά δεν είμαι σίγουρος αν βγαίνουν σωστά τα υπόλοιπα stats στις recursive εκδόσεις.

 

Το παρακάτω είναι ένα snap-shot από 50000 ακεραίους, με τιμές από -100 έως 100...

 

 

 

 

 

 

Θα ποστάρω και τον κώδικα (πιθανότατα αύριο) για να το δει και κάνας άλλος αν θέλει. Θέλω πρώτα να ξανα-δω τα iterations (itr), comparisons (cmp) με καθαρό μυαλό και θα το ποστάρω.

 

ΥΓ. Του χω βάλει όριο μέχρι 10.000.000 ακέραιους, αλλά ήδη στις 100.000 έχω υπομονή να περιμένω μονάχα τις Insertion και Quick.

 

Ο λόγος είναι πως τρέχει όλες τις εκδόσεις του κάθε αλγόριθμου (π.χ. vanilla, optimized) για να βγάλει τα stats και μετά ξανατρέχει την "καθαρή" υλοποίηση της optimized αποκλειστικά για να μετρήσει το execution speed (χωρίς δηλαδή να κάνει περιττούς υπολογισμούς για άλλου είδους stats).

 

Οπότε π.χ. η bubble-sort που έχει 3 εκδόσεις (vanilla, optimized & starlight) τρέχει ουσιαστικά 4 φορές πάνω στο unsorted data-set (και αν το 'βαζα να υπολογίζει net execution speed για όλες τις εκδόσεις, θα έτρεχε 6 φορές συνολικά την bubble ).

 

Η selection σε 100.000 elements κάνει περίπου 25-30 secs στην pure της έκδοση (και ξανατρέχει για τα υπόλοιπα stats).

 

 

Merge sort δεν έχω βάλει ακόμα.

 

[imitheos]

Γενικά δεν έχει και ιδιαίτερο νόημα αν δεν εξετάσεις 4-5 compilers και επίσης διαφορετικά patterns όπως να είναι ο πίνακας σχεδόν ταξινομημένος, να είναι αντίστροφα ταξινομημένος, κτλ. Παρόλα αυτά, αφού έχεις τη περιέργεια να δεις τι παίζει καλά κάνεις και το φτιάχνεις.

 

Σίγουρα θα το ξέρεις ήδη αλλά ένα πολύ γνωστό site που δείχνει πως δουλεύει ο κάθε αλγόριθμος και την ταχύτητά του (όχι όμως αριθμό iteration, swap, κτλ) είναι αυτό.

[migf1]

Γενικά δεν έχει και ιδιαίτερο νόημα αν δεν εξετάσεις 4-5 compilers και επίσης διαφορετικά patterns όπως να είναι ο πίνακας σχεδόν ταξινομημένος, να είναι αντίστροφα ταξινομημένος, κτλ. Παρόλα αυτά, αφού έχεις τη περιέργεια να δεις τι παίζει καλά κάνεις και το φτιάχνεις.

 

Σίγουρα θα το ξέρεις ήδη αλλά ένα πολύ γνωστό site που δείχνει πως δουλεύει ο κάθε αλγόριθμος και την ταχύτητά του (όχι όμως αριθμό iteration, swap, κτλ) είναι αυτό.

 

Ναι, το point ήταν τα iterations, comparisons, κλπ... αυτά δηλαδή στα οποία έχω αρχίσει να χάνω την μπάλα

 

(ήδη ταξινομημένους και αντίστροφα ταξινομημένους θα βάλω, δεν είναι τίποτα... με το round-up πρέπει να βρω τρόπο να μην κάνει 10 αιώνες )

 

 

[jimisvog]

Εδω πιο ειναι το προβλημα και εχω φαει ολο το απογευμα να το βρω.. :/

>
int main()
{
int n1,n2,n3;
int A[n1],B[n2],C[n3],i;
printf("Dwse to megethos tou 1ou pinaka");
scanf("%d", &n1);
for (i=0;i<=(n1-1);i++){
 printf("Dwse to stoixeio %d tou pinaka", &i);
 scanf("%d", &A[i]);
}
printf("Dwse to megethos tou 2ou pinaka");
scanf("%d", &n2);
for (i=0;i<=(n2-1);i++){
 printf("Dwse to stoixeio %d tou pinaka", &i);
 scanf("%d", &B[i]);
}
printf("Dwse to megethos tou 3ou pinaka");
scanf("%d", &n3);
for (i=0;i<=(n3-1);i++){
 printf("Dwse to stoixeio %d tou pinaka", &i);
 scanf("%d", &C[i]);
}
}

Με το που ανοιγει η γραμμη εντολων βγαζει σφαλμα.. :/

[albNik]

A,B, C είναι πινάκες και πρέπει να έχουν προκαθορισμένο μέγεθος.

Πρέπει να τους ορίσεις σαν δείκτες σε int* και να παραχωρήσεις δυναμικά μνήμη.

[jimisvog]

Δηλαδη πριν απο την δηλωση τους να βαλω τον * (καπως ετσι int*A[n1], κ.λ.π?)

[albNik]

int* A;

 

Αφού πάρεις το n1

 

A=(int*)malloc(sizeof(int)*n1);

 

Επίσης βγάλε τo '&' από την printf("..." ,&i)

To i<=(n3-1) μπορείς να το γράψεις και i<n3

[imitheos]

Εδω πιο ειναι το προβλημα και εχω φαει ολο το απογευμα να το βρω.. :/

>
int main()
{
1) int n1,n2,n3;
2) int A[n1],B[n2],C[n3],i;
printf("Dwse to megethos tou 1ou pinaka");
3) scanf("%d", &n1);
4)  printf("Dwse to stoixeio %d tou pinaka", &i);

Με το που ανοιγει η γραμμη εντολων βγαζει σφαλμα.. :/

Δηλαδη πριν απο την δηλωση τους να βαλω τον * (καπως ετσι int*A[n1], κ.λ.π?)

 

Καταρχήν στο 4 στο printf γιατί έχεις βάλει & ? Θέλεις να τυπώσεις την τιμή του i όχι την διεύθυνσή του. Στην scanf καλά τα έχεις.

 

Όσον αφορά τώρα το πρόβλημα. Ένας τρόπος να δηλώσεις ένα πίνακα είναι να τον δηλώσεις στατικά πχ "int a[7]". Ένας άλλος τρόπος είναι αυτός που ανέφερε ο albNik να το κάνεις δυναμικά.

 

Το πρότυπο C99 πρόσθεσε την έννοια της VLA με την οποία μπορείς να ορίζεις ένα πίνακα όπως το έχεις κάνει εσύ δηλαδή με "int a[k]" αντί για σταθερό αριθμό στοιχείων όπως είχαμε πριν με το 7. Ας δούμε τώρα τι κάνεις εσύ.

 

Στο 1) δηλώνεις την ακέραια μεταβλητή n1 στο 2) δηλώνεις ένα πίνακα με n1 στοιχεία. Τι τιμή έχει όμως η μεταβλητή n1 ? Μπορεί να έχει οποιαδήποτε τιμή οπότε για να δουλέψει σωστά με την μέθοδο των VLA, θα πρέπει να μεταφέρεις τη δήλωση του κάθε πίνακα μετά το scanf με το οποίο ζητάς τιμή για την μεταβλητή (πχ για τον πίνακα Α μετά το 3)). Έτσι θα δουλέψει σωστά (αν ο compiler σου υποστηρίζει VLAs) αλλά με την μέθοδο του albNik έχεις καλύτερο έλεγχο.

[migf1]

Εδω πιο ειναι το προβλημα και εχω φαει ολο το απογευμα να το βρω.. :/

 

 

>
int main()
{
int n1,n2,n3;
int A[n1],B[n2],C[n3],i;
printf("Dwse to megethos tou 1ou pinaka");
scanf("%d", &n1);
for (i=0;i<=(n1-1);i++){
printf("Dwse to stoixeio %d tou pinaka", &i);
scanf("%d", &A[i]);
}
printf("Dwse to megethos tou 2ou pinaka");
scanf("%d", &n2);
for (i=0;i<=(n2-1);i++){
printf("Dwse to stoixeio %d tou pinaka", &i);
scanf("%d", &B[i]);
}
printf("Dwse to megethos tou 3ou pinaka");
scanf("%d", &n3);
for (i=0;i<=(n3-1);i++){
printf("Dwse to stoixeio %d tou pinaka", &i);
scanf("%d", &C[i]);
}
}

Με το που ανοιγει η γραμμη εντολων βγαζει σφαλμα.. :/

 

 

 

Όπως το έχεις, αλλά μετακίνησε τους ορισμούς των πινάκων μετά από το διάβασμα του n3 (ενεργοποίησε και το C99 support στον compiler σου... αν είναι gcc: gcc -std=c99 bla bla)

[jimisvog]

Το εφτιαξα.. Απλα μολις μαθαινω το n1, n2 n3 αντιστοιχα απο κατω δηλωνω και τον πινακα με το μεγεθος τoυ..

[migf1]

Το εφτιαξα.. Απλα μολις μαθαινω το n1, n2 n3 αντιστοιχα απο κατω δηλωνω και τον πινακα με το μεγεθος τoυ..

 

Yeap. Απλώς κράτα πως αυτό δουλεύει μόνο αν ο compiler σου υποστηρίζει C99 ή μεταγενέστερη.

[imitheos]

Το εφτιαξα.. Απλα μολις μαθαινω το n1, n2 n3 αντιστοιχα απο κατω δηλωνω και τον πινακα με το μεγεθος τoυ..

Δηλαδη πριν απο την δηλωση τους να βαλω τον * (καπως ετσι int*A[n1], κ.λ.π?)

 

Ωραίος. Τώρα που έπαιξε μπορούμε να έρθουμε σε αυτό που έκανα bold. Η δήλωση αυτή έχει πολύ μεγάλη διαφορά από αυτό που πρότεινε ο albNik. Πιθανώς να κάνω λάθος φυσικά αλλά διαβάζοντας κάποιος το μήνυμα έρχεται στο συμπέρασμα ότι δεν έχεις καταλάβει καλά κάποιες έννοιες. Όταν βρεις χρόνο ξαναδιάβασε στο βιβλίο σου τα κεφάλαια που μιλάνε για πίνακες και για δείκτες και ρώτησε αν δεν καταλάβεις κάτι ή έχεις αμφιβολίες ότι το κατάλαβες τέλεια.

[fonsde]

με μπερδευει κατι οταν κανουμε typedef struct .

 

1. γιατι δεν μπορουμε να κανουμε typedef struct foo*{...}; ?

 

2. στο typedef struct foo{...}foo2; τι σχεση εχουν τα foo/foo2 τι διαφορα εχει οταν βαζουμε το foo2 και δεν το αφησουμε κενο.

Ειναι καλη τακτικη να τα εχουμε και τα 2 foo?

[jimisvog]

Φιλε @imitheos ειμαι ακομα πρωταρης.. Σημερα κιολας ειχαμε το μαθημα για τους pointers και τις δηλωσεις και ακομα δεν τα εχω εμπεδωσει καλα.. Εξου και η (προφανως βλακεια) απαντηση μου..