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

[Giorgos Keramidas]

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!!!' ακριβώς;

      3
      4         selsort( mtx, elements );

Δεν υπάρχει visible prototype για την selsort εδώ.  Αυτό σημαίνει
πως ο compiler δε μπορεί ακόμα να κάνει σωστά type-checking στα
ορίσματα που της περνάς.

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

      5
      6         int found = 0;
      7

Δεν υπάρχει κανένας καλός λόγος αυτό το declaration να είναι χύμα
σε κάποιο «τυχαίο» σημείο του πηγαίου κώδικα.  Είτε βάλ' το στην
αρχή της συνάρτησης (όπως συνήθως γίνεται σε C προγράμματα), είτε
εκεί που χρησιμοποιείται.

      8         cout << "...after!" << endl;

Παρακαλώ;  Τι ρόλο ακριβώς εξυπηρετεί αυτό το μήνυμα;

      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, φτιάξε καφέ όσο θα
τρέχει... θα περιμένεις πολύ.

Είναι ο πιο απλός να υλοποιήσει κανείς όμως όταν ξέρει ότι ο πίνακας
`mtx' θα έχει σχετικά μικρό μέγεθος.  Ολες οι εναλλακτικές λύσεις που
είναι πιο γρήγορες κοστίζουν είτε σε χώρο είτε σε πολυπλοκότητα του
αλγορίθμου.

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

Είμαι σχεδόν σίγουρος ότι δεν ήθελες κάτι τέτοιο :)

Αντίθετα, κάτι σαν αυτό, θα δουλέψει πιο σωστά:

    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;
    }

Ακόμα κι αυτό όμως έχει πρόβλημα.  Δε μπορείς έτσι απλά να συγκρίνεις
`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

Πρέπει να βρεις κάποιο πιο καλό τρόπο να κάνεις αυτές τις συγκρίσεις.

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

    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.

     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'.  Αυτό σημαίνει βέβαια ότι πρέπει να
γράφεις κάτι σαν:

    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'.

     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() ΔΥΟ
ΠΙΝΑΚΕΣ...