Θέλω πιο γρήγορο κώδικα - C .

Red_Phantom · 7 Απριλίου 2010

Generaror

>
#include <stdio.h>

#define N 300000

int main(void)
{
       int i;
       int bage,dage;
       FILE *ifp=fopen("croco.in","w");

       fprintf(ifp,"%d\n",N);

       for(i=0;i<N;i++)
       {

               bage=rand()%200000-100000;
               dage=rand()%200000-100000;

               if( bage<dage)
                       fprintf(ifp,"%d %d\n",bage,dage);
               else
                       fprintf(ifp,"%d %d\n",dage,bage);
       }

       fclose(ifp);

return 0;
}

Βάζεις το YEAR που θες να μετρήσεις.

>
#include <stdio.h>


#define YEAR 98888

struct croc
{
       int byear;
       int dyear;
};

struct croc crockos[300000];

int main(int argc,char *argv[])
{
       FILE *in,*out;
       int n,i;
       int counter =0 ;


       if( (in=fopen("croco.in","r"))==NULL)  return -1;
       if( (out=fopen("croco.out","w"))==NULL)  return -1;

       fscanf(in,"%d",&n);


       for(i=0;i<n;i++)
               fscanf(in,"%d %d",&crockos[i].byear,&crockos[i].dyear);


       for(i=0;i<n;i++)
       {
               if( (crockos[i].byear<=YEAR) && (YEAR<crockos[i].dyear)) counter++;
       }



       printf("YEAR=%d Living=%d\n",YEAR,counter);
       fclose(in);
       fclose(out);
       return 0;
}

Στο pc μ

real 0m0.104s

user 0m0.090s

sys 0m0.010s

ARIANAROS · 7 Απριλίου 2010

To θέμα είναι ότι εμείς πρέπει να μετρήσουμε ΟΛΑ τα χρόνια ( 200.001 ) και να βρούμε ποιο έχει το μεγαλύτερο αριθμό κροκοδείλων , δηλαδή αυτό δεν μπορεί να λειτουργήσει .

virxen75 · 7 Απριλίου 2010

Μηπως αναφέρεσαι πριν κάνω την διόρθωση? Αν όχι, μου φαινεται σωστό

ποια η μέγιστη τιμή του rand()?

ποια η μέγιστη τιμή ενός ακεραίου στην c?

rand---> τιμές από 0 έως RAND_MAX

δες εδώ->http://www.cplusplus.com/reference/clibrary/cstdlib/rand/

μέγιστη τιμή ακεραίου ανάλογα με τον compiler και το περιβάλλον εργασίας

δες εδώ->http://www.cplusplus.com/reference/clibrary/climits/

και ένα προγραμματάκι για το κοιτάξεις στον compiler σου

>
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>

int main(){
   srand(time(NULL));
printf("\n maximum integer value is:%d",INT_MAX);
printf("\n maximum rand value is:%d",RAND_MAX); 
printf("\n press enter to continue");   
getchar();
for (int i=0;i<20000;i++){//υπολογίζω 20000 τυχαίες τιμές
   int a=rand()%200000;//με το όρισμα που δίνεις
   if (a>32767) printf("\n found rand greater than 32767,the number is=%d",a);//αν ο τυχαίος αριθμός που υπολογίζεις είναι >32767 εμφάνισε τον.Πόσους βρήκες?
}
printf("\n press enter to finish"); 
getchar();
return 0;   
}

epersidi · 7 Απριλίου 2010

Generator που να δουλεύει για όποιον ενδιαφέρεται ...

>
#include <stdio.h>
#include <stdlib.h>

#define N 300000  // Αριθμός κροκοδείλων

int main(void)
{
       int i;
       int bage,dage;
       FILE *ifp=fopen("croco.in","w");

       fprintf(ifp,"%d\n",N);
	srand(232);

       for(i=0;i<N;i++)
       {

               bage=rand()*6.10 - 100000;
               dage=rand()*6.10 - 100000;

               if( bage<dage)
                       fprintf(ifp,"%d %d\n",bage,dage);
               else
                       fprintf(ifp,"%d %d\n",dage,bage);
       }

       fclose(ifp);

return 0;
}

Η αρχική λύση που δόθηκε ελαφρώς τροποποιημένη (δουλεύει ...)

>
#include <stdio.h>
#include <stdlib.h>

int croc[200000]; //Extern, all data=0

int main ( void ) {
FILE *in = fopen ( "crocodiles.in" , "r" );
FILE *out = fopen ( "crocodiles.out" , "w" );
int N, crocodile[2] ;
register int i , j;

if(in==NULL) return 0; // File not found !

fscanf ( in , "%d" , &N ) ;


for ( i = 0 ; i < N ; i++ ) {
	fscanf ( in , "%d %d" , &crocodile[0] , &crocodile[1] ) ;
	crocodile[0] += 100000 ;
	crocodile[1] += 100000 ;
	for ( j = crocodile[0] ; j < crocodile[1] ; j++ ) {
		croc[j]++ ;
	}
}
for ( i = 0 , j = 0 ; i < 200000 ; i++ )  //Διορθώθηκε !
	if ( croc[i] > j )
		j = croc[i] ;

fprintf ( out , "%d\n" , j ) ;
fclose ( in );
fclose ( out );
return 0;
}

Ο χρόνος που απαιτείται καθορίζεται από το εμφωλευμένο for, δηλαδή από το διάστημα που ζουν οι κροκόδειλοι. Επειδή οι αριθμοί από το generator είναι τυχαίοι μπορεί να εμφανιστεί κάποιος κροκόδειλος που να έχει ζήσει π.χ. 200000 χρόνια δήλαδη από το -100000 μέχρι το 100000, πράγμα που είναι αδύνατο αφού οι κροκόδειλοι ζουν πολύ λιγότερα χρόνια.

Αν τροποποιηθούν τα δεδομένα έτσι ώστε να αντιπροσωπεύουν πραγματικές καταστάσεις (δηλ. χωρίς μαθουσάλες κροκόδειλους !) τότε πραγματικά ο παραπάνω αλγόριθμος τερματίζει σε λιγότερο από 1 δευτερόλεπτο ακόμα και δείγμα 300000 κροκοδείλων. Αν τα δεδομένα παραμείνουν εντελώς random τότε ο αλγόριθμος μπορεί να κάνει και αρκετά λεπτά (!) μέχρι να τερματίσει εξαιτίας του εμφωλευμένου for.

Αν υπάρχει κάποια άλλη ιδέα προς υλοποίηση (ακόμα και σε θεωρητικό επίπεδο αρκεί να περιγράφονται με σαφήνεια τα αλγοριθμικά βήματα) ευχαρίστως να την εξετάσουμε και να την υλοποιήσουμε ...

bnvdarklord · 8 Απριλίου 2010

....

Με λίγα λόγια αυτό που ειχα γράψει εφτανε μεχρι 99999 αντι για 100000. Θεμα % ηταν παντως...(το RAND_MAX δεν εχει σημασία διότι κανω % 200000 οποτε απο 0-199999 θα περνω)

ΥΓ. Μια χαρα δουλευει και το generator που εφτιαξα!!!

virxen75 · 8 Απριλίου 2010

Με λίγα λόγια αυτό που ειχα γράψει εφτανε μεχρι 99999 αντι για 100000. Θεμα % ηταν παντως...(το RAND_MAX δεν εχει σημασία διότι κανω % 200000 οποτε απο 0-199999 θα περνω)

ΥΓ. Μια χαρα δουλευει και το generator που εφτιαξα!!!

σαφώς και όχι.

το rand()%200000 δεν δίνει τιμές από 0-199999 όπως νομίζεις ή θα ήθελες,

αλλά από 0 έως RAND_MAX=32767 (σε μένα)

αφαιρώντας και το 100000 που λες,

έχεις τιμές από -100000 έως RAND_MAX-100000=-67233

για να το καταλάβεις καλύτερα άνοιξε το αρχείο που δημιουργείς και θα διαπιστώσεις

ότι όλα τα νούμερα είναι αρνητικά και στο παραπάνω όριο.

bnvdarklord · 8 Απριλίου 2010

Μια απορία : αυτά που μου λες τα ελέγχεις πρώτα? Επισυνάπτω την έξοδο από το πρόγραμμα που εγραψες εσυ

Το rand() δινει τιμές απο 0 - RAND_MAX, και αν κανω mod n θα παρω παντα τιμές απο 0 εως n-1...

exodos.txt.zip

virxen75 · 8 Απριλίου 2010

Μια απορία : αυτά που μου λες τα ελέγχεις πρώτα? Επισυνάπτω την έξοδο από το πρόγραμμα που εγραψες εσυ

Το rand() δινει τιμές απο 0 - RAND_MAX, και αν κανω mod n θα παρω παντα τιμές απο 0 εως n-1...

εσύ τι λες?

Υ.Γ. windows xp,wxDevC++ build 7.3.1.3

bnvdarklord · 8 Απριλίου 2010

εε πως γινεται αυτό? Ειδες εμενα τι βγαζει και εχω το g++...

tespa_2002 · 8 Απριλίου 2010

εε πως γινεται αυτό? Ειδες εμενα τι βγαζει και εχω το g++...

Βρε παιδιά, μα γι' αυτό ακριβώς υπάρχουν ορισμένες όλες αυτές οι συμβολικές σταθερές. Επειδή σε διαφορετικές υλοποιήσεις τα όρια είναι - πιθανότατα - διαφορετικά.

ARIANAROS · 8 Απριλίου 2010

Τι να πει κανείς .... λοιπόν , θα φροντίσω την Παρασκευή ( όχι αυτή , την επόμενη ) που δίνω για τον Διαγωνισμό να βρω κάποιον που να το έλυσε και θα βάλω τον κώδικα κι εδώ . Πολύ μας παίδεψε πάντως ρε παιδιά ! Και σιγά το πρόβλημα δηλαδή ( γ@*# το κ#λ! χρονικό όριό τους )

bnvdarklord · 8 Απριλίου 2010

Και η πλακα θα ειναι οτι η λυση θα ειναι γελοια

ARIANAROS · 8 Απριλίου 2010

Και η πλακα θα ειναι οτι η λυση θα ειναι γελοια

Η πλάκα είναι ότι όλοι είμαστε σίγουροι για αυτό !!!!

Ρε εσείς , εγώ πιστεύω κι ότι παίζει να το έβαλαν καταλάθος το χρονικό όριο σε αυτό το πρόβλημα , από συνήθεια .

firewalker · 8 Απριλίου 2010

Αποτυγχάνει σε όλα τα περάσματα που κάνει; Ή τα 5 πρώτα τα περνά και κολλά στα υπόλοιπα; Για δες, εκεί που αποτυγχάνει το N πόσο είναι;

---------- Προσθήκη στις 22:34 ---------- Προηγούμενο μήνυμα στις 21:44 ----------

Τώρα που το σκέφτομαι γιατί δεν δοκιμάζεις μία Divide & Conquer μέθοδο; Δοκίμασε να σπάσεις την αναζήτηση σε επιμέρους τμήματα.

tespa_2002 · 8 Απριλίου 2010

Μια γρήγορη ιδέα: Μήπως το πρόγραμμά σου δε γίνεται δεκτό γιατί στο μηχάνημα που τρέχει κάνει stack overflow? Ο πίνακας 200000 θέσεων croc επειδή είναι local στη main, έχει δεσμευθεί στη stack (και δεν είναι λίγος για τη stack). Δοκίμασε να τον δηλώσεις global. Εναλλακτικά μπορείς να τον δεσμεύσεις δυναμικά, με calloc, οπότε θα έχει γίνει και ο αρχικός μηδενισμός και δε χρειάζεται να τον αρχικοποιήσεις.

Μια καλύτερη αλγοριθμική λύση θα ήταν να χρησιμοποιήσεις ένα interval tree:

http://en.wikipedia.org/wiki/Interval_tree

Όμως:

α) Μου φαίνεται πολύ χοντρό να ζητάνε κάτι τέτοιο

β) Δε θα έπαιρνα και όρκο ότι θα τρέχει πιο γρήγορα από αυτό που έχεις κάνει ήδη.

Σύνδεση

Θέλω πιο γρήγορο κώδικα - C .

Προτεινόμενες αναρτήσεις

Red_Phantom

ARIANAROS

virxen75

epersidi

bnvdarklord

virxen75

bnvdarklord

virxen75

bnvdarklord

tespa_2002

ARIANAROS

bnvdarklord

ARIANAROS

firewalker

tespa_2002

Αρχειοθετημένο

Σύνδεση