Λιγο βοήθεια με τη C

[Dimitris Mexis]

On Fri, 02 Jun 2006 18:50:32 +0300, Giorgos Keramidas wrote:

> On 2006-06-01 23:26, Dimitris Mexis <m65 at vivodinet.gr> wrote:
>> Exo ton parakato kodika, pistevo oti tha nai efkolo poli, se
>> kapoion na to trexi me ena gcc apla...
> 
> Πρώτα από όλα, το πρόγραμμά σου δεν είναι C.  Χρησιμοποιεί C++
> features (όπως το 'cout' και οι δηλώσεις μεταβλητών σε τυχαία
> σημεία), οπότε με C compiler ούτε κατά διάνοια δεν παίζει.
> 
> Αυτό δεν είναι πρόβλημα όμως.  Το πρόβλημα είναι τα 'λάθη' που
> έχει το πρόγραμμα.  Κοίτα παρακάτω τα σχόλια γραμμή-προς-γραμμή
> και διόρθωσέ τα πριν ασχοληθείς με πιο δύσκολα πράγματα.
> 
>       1 void freq_array( double mtx[], int elements ){
>       2 //The mtx is a ghost of the matrix I transfer, VORSICHT!!!
> 
> Τι εννοείς 'ghost';  Και τί σημαίνει το `VORSICHT!!!' ακριβώς;

Epeidi den eimai...erasitexnis xrisimopoio kapoies "taftotites" otan leo
mtx einai ghost (fadasma) enoo, oti einai referenced, giati den ithela na
xehaso tin epidrasi!To...VORSICHT!,....achtung san na leme? :-)

> 
>       3
>       4         selsort( mtx, elements );
> 
> Δεν υπάρχει visible prototype για την selsort εδώ.
> Αυτό σημαίνει πως ο compiler δε μπορεί
> ακόμα να κάνει σωστά type-checking στα
> ορίσματα που της περνάς.

To xero, den me enoxlouse pros to paron, outos i allos ola tha ta kano
meta class...opote cool....

> 
> Επίσης, γιατί ακριβώς χρειάζεται να
> ΤΑΞΙΝΟΜΗΣΕΙΣ τον πίνακα πριν μετρήσεις
> τις συχνότητες εμφάνισης των αριθμών;

Sigouria oti ola pane cool, kai se kapoio debugging, na vlepo ti perno?
> 
>       5
>       6         int found = 0;
>       7
> 
> Δεν υπάρχει κανένας καλός λόγος αυτό το
> declaration να είναι χύμα σε κάποιο «τυχαίο»
> σημείο του πηγαίου κώδικα.  Είτε βάλ' το
> στην αρχή της συνάρτησης (όπως συνήθως
> γίνεται σε C προγράμματα), είτε εκεί που
> χρησιμοποιείται.
> 
>       8         cout << "...after!" << endl;
> 
> Παρακαλώ;  Τι ρόλο ακριβώς εξυπηρετεί
> αυτό το μήνυμα;

Einai to debuging pou sou elega? Eidika se kapoies katastaseis atermonon
loop, kai polon function-jumping....

> 
>       9         for ( int i = 0; i < elements; i++ ){
>      10                 for ( int x = 0; x < elements; x++ ){ 11
>                      if ( mtx[x] == mtx[i] ){ 12
>              found++; 13                                 }
>      14                 }
>      15                 cout << "Found value :" << mtx[i] << ", times :"
>      << found << endl; 16                 found = 0; 17         } 18 }
> 
> Αυτός ο αλγόριθμος είναι
> πολυπλοκότητας O(N^2).  Αν ο πίνακας έχει
> μέγεθος 100, θα κάνει 100 * 100 συγκρίσεις. Αν
> έχει μέγεθος 1000, θα κάνεις ένα
> εκατομμύριο.  Αν έχει μέγεθος 1,000,000,
> φτιάξε καφέ όσο θα τρέχει... θα
> περιμένεις πολύ.
> 

Nai to paratirisa stis 100000, 64bit kai tentothike... xmm....mipos den
axizoun oi 64bitoi? :-p

> Είναι ο πιο απλός να υλοποιήσει κανείς
> όμως όταν ξέρει ότι ο πίνακας `mtx' θα
> έχει σχετικά μικρό μέγεθος.  Ολες οι
> εναλλακτικές λύσεις που είναι πιο
> γρήγορες κοστίζουν είτε σε χώρο είτε σε
> πολυπλοκότητα του αλγορίθμου.
> 
> Ο τρόπος που το υλοποίησες όμως έχει
> ένα πρόβλημα.  Το found δεν αρχικοποιείται
> σε μηδέν για κάθε στοιχείο mtx[i] του
> πίνακα mtx[]. Αυτό σημαίνει ότι στις
> εμφανίσεις του mtx[x] καταλογίζεις και
> όλες τις εμφανίσεις του mtx[x-1], mtx[x-2], ...
> mtx[0].
> 
> Είμαι σχεδόν σίγουρος ότι δεν ήθελες
> κάτι τέτοιο :)
> 

Oxi...

> Αντίθετα, κάτι σαν αυτό, θα δουλέψει πιο
> σωστά:
> 
>     for (int i = 0; i < elements; i++) {
>         int nitems = 0;
>         for (k = 0; k < elements; k++) {
>             if (mtx[i] == mtx[k])
>                 nitems++;
>         }
>         cout << "Value " << mtx[i] << " found " << nitems << " times."
>         << endl;
>     }
>     }

Nomizo oti apla xrisimopoio tin found = 0 akrivos kato apto proto
for...opote mipos leme ta idia pramata edo?

> Ακόμα κι αυτό όμως έχει πρόβλημα.  Δε
> μπορείς έτσι απλά να συγκρίνεις `double'
> τιμές με το == operator.  Για περισσότερες
> πληροφορίες σχετικά με την floating-point
> αριθμητική και τα προβλήματα που έχει η
> αναπαράσταση των floating point αριθμών σε
> τέτοιες συγκρίσεις, σου προτείνω
> ανεπιφύλακτα το:
> 
>     David Goldberg, ``What Every Computer Scientist Should Know About
>     Floating-Point Arithmetic''.  Appendix to ``Numerical Computation
>     Guide'' by Sun Microsystems.  Published in the March, 1991 issue of
>     Computing Surveys. Copyright 1991, Association for Computing
>     Machinery, Inc.
> 
>     http://docs.sun.com/source/806-3568/ncg_goldberg.html
> 
> Πρέπει να βρεις κάποιο πιο καλό τρόπο
> να κάνεις αυτές τις συγκρίσεις.
> 

Edo arxizoune ta daoulia...

> Πως μπορείς τώρα να κρατήσεις αυτές τις
> `nitems' τιμές σε ένα άλλο πίνακα, που έχει
> το ίδιο μέγεθος με τον mtx[]?  Ισως με κάτι

Giati na kratiso tis times? an vlepo 2,2,2 kratao ton arithmo 3, pou na
afora to stoixeio, 2. ara prepei na xei ligoteres times, san
grouparismenes pou tha einai...mipos to xasa edo?

> σαν:
> 
>     void
>     freq_array(size_t elements, double mtx[], double freq[]) {
>         size_t i, k, count;
> 
>         for (i = 0; i < elements; i++) {
>             count = 0;
>             for (k = 0; count < elements; k++) {
>                 if (cmpdouble(mtx[i], mtx[k]) == 0)
>                     count++;
>             freq[i] = count;
>         }
>         }
>         }
> Τώρα το μόνο που μένει είναι να
> φτιάξεις το cmpdouble(a, b) function, το οποίο θα
> συγκρίνει δυο `double' αριθμούς και θα
> επιστρέφει:
> 
>     -1    Αν το a είναι μεγαλύτερο από το b
>     τόσο που να μην πέφτει μέσα
>           στο threshold που θεωρείς ότι δεν έχει
>           σημασία για σένα.
> 
>      0    Αν η διαφορά του a από το b είναι
>      πολύ μικρή, κάτω από το
>           threshold που έχει σημασία για σένα.
> 
>      1    Αν το α είναι μικρότερο από το b
>      (σύμφωνα, πάντα, με το
>           threshold που σε ενδιαφέρει.
> 
> Αφού διαβάσεις το ``What Every Computer Scientist Should
> Know About Floating-Point Arithmetic'' δε θα είναι
> δύσκολο να γράψεις κάτι τέτοιο. Δε θα
> είναι δύσκολο να γράψεις ακόμα και την
> freq_array() να παίρνει ως παράμετρο αυτό το
> threshold.
> 

Diladi, aporia...otan thes na pareis ta apotelesmata enos peiramatos, mias
pirinikis adidraseis.....ti tha peis, "E.....exasa to sosto threshold,
kai gia afto tinaxa to miso planiti! den ixera oti eihe simasia to 10^23
psifio stin strogilopoiisi? Kalo! :-)

> 19
>      20 //Selection Sort function
>      21 //Takes two parameters:
>      22 //int *array- the array with the numbers to be sorted 23 //int
>      size- the size of the array
> 
> Τα μεγέθη αντικειμένων δεν είναι σωστό
> να τα αποθηκεύεις σε `int'. Ο σωστός τύπος
> είναι `size_t'.  Αυτό σημαίνει βέβαια ότι
> πρέπει να γράφεις κάτι σαν:
> 

Dose daskale! den to gnoriza peri size_t, alla eixa dei se kapoia
tutorials oti eprepe na pernas ton arithmo ton stoixeion outos i allos,
san variable...(eleeino, na min eheis dinamiko elegho stis arrays (praise
VB, PHP ) 

>     void
>     selsort(double *array, size_t nelem)
>     {
>         size_t k;
> 
>         if (array == NULL)
>             return;
>         for (k = 0; k < nelem; k++)
>             ...
> 
>      24 void selsort( double *array,int size){ 25         int min;int b;
>      26         //This loop goes through the whole array 27         for(
>      int a = 0; a < size-1; a++ ){ 28                 b=a; 29
>           min=array[b];   //Get the current value 30
>                                //...and check if any of the rest numbers
>      is lower
> 
> Είναι ΠΟΛΥ ΚΑΚΗ ΙΔΕΑ να αποθηκεύεις ένα
> double value, όπως το array[b], σε ένα `int'.
> 

Den thelo kai na katastrepso ton planiti, tha to xo varos stin sinidisi!

>      31                 for(int j=a+1;j<size;j++){ 32
>           if( array[j]< min ){
> 
> Λάθος σύγκριση, με χρήση του < operator, για
> floating-point τιμή.
> 
>      33                                 b = j; 34
>               min = array[b]; //...and if yes, then get it
> 
> Επίσης.
> 
>      35                         }
>      36                 }
>      37                 //Switch the values... 38 array[b]=array[a]; 39
>                     array[a]=min;
> 
> Λάθος ανάθεση `int' σε θέση που έχει τύπο
> `double'.
> 
>      40         }
>      41 }
>      42
>      43 int main(int argc, char *argv[])
>      44 {
>      45         double matrix[10];
>      46         cout << "before..." << endl; 47         for ( int i = 0;
>      i < 10; i++ ){ 48                 matrix[i] = 10 - i; 49
>           matrix[3] = 3;
>      50                 matrix[4] = 3;
>      51                 matrix[1] = 2;
>      52                 matrix[0] = 0;
>      53                 cout << matrix[i] << endl; 54                 }
>      55         freq_array( matrix, ( sizeof( matrix )/sizeof( matrix[0]
>      ) ) ); 56
>      57         exit(0);
>      58 }
> 
>> To provlima einai oti stelno loipon, mia matrix[] array stin sinartisi
>> selsort(), mou sortari tin array, pame kala, stelno meta tin matrix[]
>> array sto freq_array() kai pragmati petixeno na perno, poses times ehei
>> vrei...OMOS. Exo kolisi sto pos telika na paro mia struct(?), array(?),
>> list(? den xero kai STL ), me tis metavlites kai tin sixnotita apla pou
>> emfanizontai...diladi mia nea isos matrix,
> 
> Πολύ απλά, όπως έδειξα στην freq_array()
> παραπάνω:
> 
>     void
>     freq_array(size_t elements, double mtx[], double freq[]) {
>         size_t i, k, count;
> 
>         for (i = 0; i < elements; i++) {
>             count = 0;
>             for (k = 0; count < elements; k++) {
>                 if (cmpdouble(mtx[i], mtx[k]) == 0)
>                     count++;
>             freq[i] = count;
>         }
>         }
>         }
> Αρκετά απλός τρόπος, αλλά θα πρέπει να
> περάσεις στην freq_array() ΔΥΟ ΠΙΝΑΚΕΣ...