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

[virxen75]

int a = rand()%200000 - 100000;

 

αυτό είναι λάθος.Δες το καλύτερα.

[bnvdarklord]

αυτό είναι λάθος.Δες το καλύτερα.

 

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

[pinball_elf]

Για δοκίμασε αυτό:

>
#include <stdio.h>

int main ( void ) {
FILE *in = fopen ( "crocodiles.in" , "r" ) , *out = fopen( "crocodiles.out" , "w" ) ;
int N , crocs , a1 , a2 , b1 , b2 ;
register int i ;

fscanf ( in , "%d" , &N ) ;
crocs = N ;
fscanf ( in , "%d %d" , &a1 , &b1 ) ;
for ( i = 2 ; i <= N ; i++ ) {
	fscanf ( in , "%d %d" , &a2 , &b2 ) ;
	if ( b1 < a2 || a1 > b2) {
		crocs-- ;
		continue ;
	}
	a1 = a2 ;
	b1 = b2 ;
}
fprintf ( out , "%d\n" , crocs ) ;
[color="Red"]exit(0);[/color]
}

[epersidi]

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

 

Τέλος επειδή κοίταξα λίγο το site που ανέφερες με το διαγωνισμό παρατήρησα ότι περιμένει κάποιες πολύ συγκεκριμένες λύσεις, δηλαδή δεν αρκεί να βρίσκεις το σωστό αποτέλεσμα και μέσα στον καθορισμένο χρόνο. Οπότε καταντάει λίγο βλακεία αφού πρέπει στην ουσία να μαντεύεις τί θέλανε αυτοί να γράψεις από το να εστιάζεις στη λύση του προβλήματος.

[bnvdarklord]

Είσαι σίγουρος? Βγάζει σωστά αποτελέσματα για καποια αρχεία που δοκίμασα...

[ARIANAROS]

Κυρίως για μένα το εγραψα, αλλα ειπα να το ποστάρω αν θελει να τεστάρει και κάποιος αλλος

 

Διόρθωσα ενα λαθάκι στον κώδικα επρεπε να βαλω % στον υπολογισμό a,b...

 

edit: στο αρκετά παλιό pc μου o κώδικας σου με το αρχείο 300000 καταχωρίσεων που εφτιαξα με τον κώδικα μου, κάνει περίπου μισό δευτερόλεπτο

 

edit: απο περιέργεια δοκίμασα και τον πρώτο σου κώδικα που λες κανει 4 δευτερόλεπτα... guess what? Εκανε περίπου ενα λεπτό(!) και εβγαλε και λαθος αποτελεσμα(υποθέτοντας οτι το αποτέλεσμα του τελευταίου σου προγράμματος ειναι σωστό)... Οποτε μαλλον το εχεις φτιαξει, αλλα καποια μαλακια γινεται με το site ...

 

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

[bnvdarklord]

Μπορείς αν μου δωσεις παράδειγμα εισοδου που βγάζει λαθος? Δοκιμαζω διάφορα και μου βγάζει σωστά αποτελέσματα :s

 

edit: ακυρο το βρηκα...

 

---------- Προσθήκη στις 15:44 ---------- Προηγούμενο μήνυμα στις 14:32 ----------

 

Λοιπον σκέφτηκα εναν τρόπο, αλλα δεν τον εχω γράψει σε κώδικα, οποτε δεν ξερω αν ειναι πιο γρήγορος.... Θα τον περιγράψω να τον δοκιμάσεις αν θες...

 

Λοιπον για ευκολία εστω οτι οι ηλικίες ειναι απο 0 εως 20 και εχουμε το εξής αρχείο:

 

>
6
0 5
1 9
2 3
2 11
8 17
10 15

 

Οταν διαβάζετε το αρχείο από το πρόγραμμα, κατασκευάζεται η εξής συνδεδεμένη λίστα:

(τα κόκκινα εξηγούνται παρακάτω)

 

>
0--->5  [color="Red"](3)[/color]
|
v
1--->9  [color="#ff0000"](3)[/color]
|
v
2--->3  [color="#ff0000"](3)[/color]
|
v
2--->11  [color="#ff0000"](6)[/color]
|
v
8--->17  [color="#ff0000"](4)[/color]
|
v
10--->15  [color="#ff0000"](3)[/color]
|
v
null

 

Μετά την κατασκευή της λίστας, διαβάζεται η λίστα και για κάθε ζευγάρι γεννησης-θανάτου ελεγχεται με πόσα απο τα υπόλοιπα εχει κοινά στοιχεία(σημειώνεται με κόκκινο παραπάνω), και βρίσκουμε το μέγιστο απο αυτά... Στην περίπτωση μας είναι το 6, οπου πράγματι ειναι το σωστό αποτέλεσμα....(δεν χρειάζεται να αποθηκευτούν πουθενα)

 

Η βασική διαφορά με τον αρχικό σου κώδικα ειναι οτι γλιτώνεις κάποια στοιχεία του πίνακα croc... Δεν ειμαι σίγουρος αν αξίζει τον κόπο όλο αυτό, ή αν γλιτώνεις σημαντικό χρόνο, αλλα αν θες δοκίμασε το... (Πιθανών να ειναι λίγο ταχύτερο αν στην λίστα ενώσεις τα στοιχεία με κοινό ετος γέννησης πχ 2->3->11)

[epersidi]

Μπορείς αν μου δωσεις παράδειγμα εισοδου που βγάζει λαθος? Δοκιμαζω διάφορα και μου βγάζει σωστά αποτελέσματα :s

 

edit: ακυρο το βρηκα...

 

---------- Προσθήκη στις 15:44 ---------- Προηγούμενο μήνυμα στις 14:32 ----------

 

Λοιπον σκέφτηκα εναν τρόπο, αλλα δεν τον εχω γράψει σε κώδικα, οποτε δεν ξερω αν ειναι πιο γρήγορος.... Θα τον περιγράψω να τον δοκιμάσεις αν θες...

 

Λοιπον για ευκολία εστω οτι οι ηλικίες ειναι απο 0 εως 20 και εχουμε το εξής αρχείο:

 

>
6
0 5
1 9
2 3
2 11
8 17
10 15

 

Οταν διαβάζετε το αρχείο από το πρόγραμμα, κατασκευάζεται η εξής συνδεδεμένη λίστα:

(τα κόκκινα εξηγούνται παρακάτω)

 

>
0--->5  [color="Red"](3)[/color]
|
v
1--->9  [color="#ff0000"](3)[/color]
|
v
2--->3  [color="#ff0000"](3)[/color]
|
v
2--->11  [color="#ff0000"](6)[/color]
|
v
8--->17  [color="#ff0000"](4)[/color]
|
v
10--->15  [color="#ff0000"](3)[/color]
|
v
null

 

Μετά την κατασκευή της λίστας, διαβάζεται η λίστα και για κάθε ζευγάρι γεννησης-θανάτου ελεγχεται με πόσα απο τα υπόλοιπα εχει κοινά στοιχεία(σημειώνεται με κόκκινο παραπάνω), και βρίσκουμε το μέγιστο απο αυτά... Στην περίπτωση μας είναι το 6, οπου πράγματι ειναι το σωστό αποτέλεσμα....(δεν χρειάζεται να αποθηκευτούν πουθενα)

 

Η βασική διαφορά με τον αρχικό σου κώδικα ειναι οτι γλιτώνεις κάποια στοιχεία του πίνακα croc... Δεν ειμαι σίγουρος αν αξίζει τον κόπο όλο αυτό, ή αν γλιτώνεις σημαντικό χρόνο, αλλα αν θες δοκίμασε το... (Πιθανών να ειναι λίγο ταχύτερο αν στην λίστα ενώσεις τα στοιχεία με κοινό ετος γέννησης πχ 2->3->11)

 

Μάλλον έχεις μπερδέψει την έννοια της λίστας. Όταν γράφεις π.χ. 2 -> 10 σημαίνει ότι έχεις μία λίστα με 2 στοιχεία (χωρίς τα ενδιάμεσα όπως το αντιλαμβάνεσαι μάλλον εσύ) δηλαδή το 2 και το 10.

 

Ξαναλέω πάντως και σε σχέση με το site του διαγωνισμού. Τα προβλήματα ΔΕΝ είναι προβλήματα βελτιστοποίησης, απλά θέλουν να γράψεις ένα πρόγραμμα που θα συμβαδίζει με τη δική τους λύση, σε γενικές γραμμές τουλάχιστον. Από τη στιγμή όμως που δε δίνει περισσότερες λεπτομέρειες για τον τρόπο υλοποίησης που θέλουν (π.χ. με ή χωρίς χρήση συναρτήσεων κτλ) τότε είναι πλέον και λίγο θέμα τύχης να πετύχεις αυτό που θέλουν, ειδικά σε πιο πολύπλοκα προβλήματα.

[bnvdarklord]

Μάλλον έχεις μπερδέψει την έννοια της λίστας. Όταν γράφεις π.χ. 2 -> 10 σημαίνει ότι έχεις μία λίστα με 2 στοιχεία (χωρίς τα ενδιάμεσα όπως το αντιλαμβάνεσαι μάλλον εσύ) δηλαδή το 2 και το 10.

 

To ξέρω. Μαλλον δεν κατάλαβες τι θελω να πώ... Σκεφτηκα να το κάνω με λίστα για να μην χρειάζεται να εχουμε τα ενδιάμεσα αποθηκευμένα...

[epersidi]

To ξέρω. Μαλλον δεν κατάλαβες τι θελω να πώ... Σκεφτηκα να το κάνω με λίστα για να μην χρειάζεται να εχουμε τα ενδιάμεσα αποθηκευμένα...

 

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

[ARIANAROS]

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

 

Γιατί καλέ , εμένα σωστός με φαίνεται . Απλά δεν είχα χρόνο να τον δοκιμάσω .

[epersidi]

Γιατί καλέ , εμένα σωστός με φαίνεται . Απλά δεν είχα χρόνο να τον δοκιμάσω .

 

Ε άμα το κάνεις να δουλέψει πες μας να μην το έχουμε αγωνία !

 

Τώρα επειδή είδα στο site ότι υποτίθεται ότι πρέπει να το κάνεις να χρησιμοποιεί όσο το δυνατό λιγότερη μνήμη μπορείς να δεσμεύσεις μνήμη για τον πίνακα σου δυναμικά κατά την εκτέλεση ανάλογα με το πλήθος των κροκοδείλων δλδ.

 

#include <stdio.h>

#include <stdlib.h>

 

int main(void) {

int *croc ;

.

.

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

croc = (int*)malloc(N);

 

Έτσι σίγουρα θα κερδίσεις και χρόνο αλλά κυρίως μνήμη. Επίσης δε χρειάζεται η αρχικοποίηση του πίνακα με 0 αφού θα αρχικοποιηθεί με τα δεδομένα του αρχείου. Δοκίμασε το ...

[ARIANAROS]

Μα η malloc αργεί συνήθως πολύ ( όχι , δεν το κατάφερα να δουλέψει το προηγούμενο ) .

Άσε που αφού το πρόβλημα είναι στα μεγάλα δεδομένα , είναι χίλιες φορές προτιμότερο να πάω με πίνακα που θα έχει δεσμεύσει εκείνες τις θέσεις . Τέλος , το πρόβλημα δεν είναι εκεί , στα μικρά δεδομένα , που αναγκαστικά δεσμεύουν πολύ μνήμη , κάνει 0.004 ή 0 δευτερόλεπτα , άρα δεν αργεί καθόλου σε αυτό .

[epersidi]

Μα η malloc αργεί συνήθως πολύ ( όχι , δεν το κατάφερα να δουλέψει το προηγούμενο ) .

Άσε που αφού το πρόβλημα είναι στα μεγάλα δεδομένα , είναι χίλιες φορές προτιμότερο να πάω με πίνακα που θα έχει δεσμεύσει εκείνες τις θέσεις . Τέλος , το πρόβλημα δεν είναι εκεί , στα μικρά δεδομένα , που αναγκαστικά δεσμεύουν πολύ μνήμη , κάνει 0.004 ή 0 δευτερόλεπτα , άρα δεν αργεί καθόλου σε αυτό .

 

Το πρόβλημα δεν λέει ότι το αρχείο εισόδου θα έχει οποσδήποτε 200000 εγγραφές. Οπότε το να δεσμεύεις όλο αυτό τον χώρο στη μνήμη από την αρχή χωρίς να ξέρεις αν θα σου χρησιμεύσει (μπορεί το αρχείο να έχει 3-4 εγγραφές όλες κι όλες !) είναι απλά λάθος + σίγουρα πιο χρονοβόρο από την malloc. Δοκίμασε το αλλά όχι μόνο για την ακραία περίπτωση των 200000 εγγραφών.

 

Επίσης αν θες να κερδίσεις πραγματικά σε ταχύτητα χρησιμοποίησε την fread αντί για την fscanf, επειδή διαβάζει με τη μία όλο το αρχείο στη μνήμη (μία κλήση συνάρτησης έναντι χιλιάδων) και μάλιστα σε πίνακα (με λίγη παραπάνω φασαρία από την fscanf).

[ARIANAROS]

Δεν έχω χρησιμοποιήσει ποτέ την fread , μπορείς να με δείξεις πώς ;

Επίσης , αυτό που λέω είναι ότι όταν τα δεδομένα είναι λίγα , έτσι κι αλλιώς δεν υπάρχει πρόβλημα , ενώ όταν είναι πολλά , που υπάρχει το πρόβλημα , δεν βολεύει η malloc .