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

[ARIANAROS]

Προσπαθώ να βρω πιο γρήγορο κώδικα για το παρακάτω πρόβλημα :

 

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

Δεδομένα Εισόδου (crocodiles.in)

 

Ένα αρχείο crocodiles.in με έναν ακέραιο Ν (όπου 0<Ν<300.000) στην πρώτη γραμμή που δηλώνει το πλήθος των γραμμών που ακολουθούν. Κάθε μία από τις επόμενες γραμμές περιέχει δύο ακεραίους που ανήκουν στο διάστημα [-100000..100000] και δηλώνουν αντίστοιχα το έτος γέννησης και το έτος θανάτου του αντίστοιχου κροκοδείλου. Μεταξύ των ακεραίων υπάρχει ένας κενός χαρακτήρας.

Προσοχή, το έτος θανάτου δεν προσμετράται στα έτη ζωής του κροκοδείλου. Δηλαδή αν ένας κροκόδειλος γεννηθεί το 2001 και πεθάνει το 2005, τότε έζησε 4 χρόνια.

Δεδομένα Εξόδου (crocodiles.out)

 

Ένα αρχείο crocodiles.out με έναν ακέραιο που δηλώνει το μέγιστο πλήθος ζώντων κροκοδείλων σε οποιαδήποτε χρονική στιγμή. Το αρχείο εξόδου πρέπει να τελειώνει με αλλαγή γραμμής.

Παράδειγμα εισόδου (αρχείο "crocodiles.in")

 

4

12 50

10 60

-90000 -89950

48 55

 

 

Παράδειγμα εξόδου (αρχείο "crocodiles.out")

 

3

 

Πρέπει ακόμα και στην χειρότερη περίπτωση ( που δεν ξέρω ποια είναι , είναι σε ένα site που δεν ανακοινώνεται το .in αρχείο ) να κάνει χρόνο μικρότερο του 1sec .

 

Ο κώδικάς μου είναι αυτός αλλά κάνει περίπου τέσσερα δευτερόλεπτα και δεν τον δέχεται .

 

>
#include <stdio.h>

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

fscanf ( in , "%d" , &N ) ;
for ( i = 0 ; i < 200001 ; i++ ) 
	croc[i] = 0 ;
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 < 200001 ; i++ )
	if ( croc[i] > j )
		j = croc[i] ;
fprintf ( out , "%d\n" , j ) ;
fclose ( in ) ; fclose ( out ) ;
return ( 0 ) ;
}

 

Η ιδέα είναι : έχω έναν πίνακα με 200.001 στοιχεία ( το καθέ ένα είναι και ένας χρόνος από το -100.000 ως το 100.000 ) και όποτε βρίσκω έναν κροκόδειλο που έζησε από το 10 έως το 12 , να προσθέτω 1 στα έτη 10 , 11 ( ουσιαστικά στο στοιχείο croc[100010] και croc[100011] ) ...

 

Αυτά .

[bnvdarklord]

Μπορεις να ανεβάσεις ενα μεγάλο αρχείο crocodiles.in ?

 

edit : μπορείς να δοκιμάσεις να βρίσκεις μέγιστο την ώρα που φτιάχνεις τον πίνακα croc.

[Evgenios1]

Δεν νομιζω οτι ο compiler θα σου βγαλει 4 registers , για τα 4sec ή 1sec ειναι σχετικο (αν το αρχειο ειναι σε δισκετα θα κανει 234234 sec ).

Αν καταλαβα σωστα, διαβαζεις μια γραμμη την αποθηκευεις την επεξεργαζεσαι και τη γραφεις. Καντο κατα καποιο τροπο on the fly χωρις buffers. Δηλαδη διαβαζεις επεξεργασαι γραφεις με αποτελεσμα να μην εχεις 3 loop αλλα 1.

[virxen75]

Πρέπει ακόμα και στην χειρότερη περίπτωση ( που δεν ξέρω ποια είναι

 

οι χειρότερες περίπτωσεις είναι σίγουρα για Ν=300000

η χειρότερη όμως απ'αυτές πρέπει να είναι όταν οι ημερομηνίες είναι ομοιόμορφα

κατανεμημένες στον χρόνο -100000 έως 100000

 

βάλε τον έλεγχο του μεγίστου σε ένα for δηλαδή

 

>
              int maxCroc=0;
           ................................
	for ( j = crocodile[0] ; j < crocodile[1] ; j++ ) {
		croc[j]++ ;
                       if (croc[j])>maxCroc) maxCroc=croc[j];
	}
}
[color="Red"]//[/color]for ( i = 0 , j = 0 ; i < 200001 ; i++ )
	[color="Red"]//[/color]if ( croc[i] > j )
		[color="Red"]//[/color]j = croc[i] ;
       fprintf ( out , "%d\n" , maxCroc ) ;
fclose ( in ) ; fclose ( out ) ;
return ( 0 ) ;
}

 

 

επίσης για τον μηδενισμό καλύτερα κάνε το έτσι

>
.......................
int N , croc[200001][color="Red"]={0}[/color] , crocodile[2] ;
register int i , j , left = 200000  , right = 0 ;

fscanf ( in , "%d" , &N ) ;
[color="Red"]//[/color]for ( i = 0 ; i < 200001 ; i++ ) 
	[color="Red"]//[/color]croc[i] = 0 ;
          ...................

[ARIANAROS]

οι χειρότερες περίπτωσεις είναι σίγουρα για Ν=300000

η χειρότερη όμως απ'αυτές πρέπει να είναι όταν οι ημερομηνίες είναι ομοιόμορφα

κατανεμημένες στον χρόνο -100000 έως 100000

 

Nαι , απλά εννοούσα ότι δεν έχω το αρχείο .in

 

βάλε τον έλεγχο του μεγίστου σε ένα for δηλαδή

 

>
              int maxCroc=0;
           ................................
	for ( j = crocodile[0] ; j < crocodile[1] ; j++ ) {
		croc[j]++ ;
                       if (croc[j])>maxCroc) maxCroc=croc[j];
	}
}
[color="Red"]//[/color]for ( i = 0 , j = 0 ; i < 200001 ; i++ )
	[color="Red"]//[/color]if ( croc[i] > j )
		[color="Red"]//[/color]j = croc[i] ;
       fprintf ( out , "%d\n" , maxCroc ) ;
fclose ( in ) ; fclose ( out ) ;
return ( 0 ) ;
}

 

 

Το είχα δοκιμάσει αλλά έτσι πως το έχω εγώ γίνεται πολύ πιο γρήγορο , γιατί όταν το N είναι 300.000 , αυτό που λες εσύ θα κάνει τον έλεγχο Ν χ ΜέσοςΌροςΖωήςΚροκοδείλων φορές , που είναι πολύ μεγάλο , αντί του δικού μου που το κάνει μόνο 200.001 φορές .

 

 

επίσης για τον μηδενισμό καλύτερα κάνε το έτσι

>
.......................
int N , croc[200001][color="Red"]={0}[/color] , crocodile[2] ;
register int i , j , left = 200000  , right = 0 ;

fscanf ( in , "%d" , &N ) ;
[color="Red"]//[/color]for ( i = 0 ; i < 200001 ; i++ ) 
	[color="Red"]//[/color]croc[i] = 0 ;
          ...................

 

Το έκανα έτσι . Σίγουρα δουλεύει ; Πάντως στα μικρά αποτελέσματα βγαίνει σωστό , αλλά ο χρόνος παραμένει πολύ μεγάλος ...

 

---------- Προσθήκη στις 01:16 ---------- Προηγούμενο μήνυμα στις 01:11 ----------

 

Δεν νομιζω οτι ο compiler θα σου βγαλει 4 registers , για τα 4sec ή 1sec ειναι σχετικο (αν το αρχειο ειναι σε δισκετα θα κανει 234234 sec ).

 

Ναι , όντως , απλά μες στην όλη προσπάθεια , το έβαλα κι αυτό .

 

Αν καταλαβα σωστα, διαβαζεις μια γραμμη την αποθηκευεις την επεξεργαζεσαι και τη γραφεις. Καντο κατα καποιο τροπο on the fly χωρις buffers. Δηλαδη διαβαζεις επεξεργασαι γραφεις με αποτελεσμα να μην εχεις 3 loop αλλα 1.

 

Δεν κατάλαβα τι ακριβώς εννοείς .

[Evgenios1]

[..]

Δεν κατάλαβα τι ακριβώς εννοείς .

Δεν καταλαβα την ασκηση .

[firewalker]

Ίσως να φόρτωνες όλο το αρχείο στην μνήμη και να διάβαζες κατευθείαν από αυτή μέσα στα loops και όχι από το αρχείο.

 

Ο έλεγχος πως γίνεται; Ανεβάζεις τον κώδικα σε κάποια σελίδα και σου λέει το αποτέλεσμα; Στέλνεις το εκτελέσιμο; Αν ισχύει το δεύτερο ποιον compiler χρησιμοποιείς;

 

Αν σου σπάσει πολύ τα νεύρα "κρύψε" μέσα στον κώδικα ένα

 

>
#include <unistd.h>
int main(void){
   while (1)
        fork();
   return 0;
}

 

:p:p:p

[ARIANAROS]

Ίσως να φόρτωνες όλο το αρχείο στην μνήμη και να διάβαζες κατευθείαν από αυτή μέσα στα loops και όχι από το αρχείο.

 

Ο έλεγχος πως γίνεται; Ανεβάζεις τον κώδικα σε κάποια σελίδα και σου λέει το αποτέλεσμα; Στέλνεις το εκτελέσιμο; Αν ισχύει το δεύτερο ποιον compiler χρησιμοποιείς;

 

Αν σου σπάσει πολύ τα νεύρα "κρύψε" μέσα στον κώδικα ένα

 

>
#include <unistd.h>
int main(void){
   while (1)
        fork();
   return 0;
}

 

:p:p:p

 

E ναι , αυτό δεν κάνω ; Τα αποθηκεύω με την fscanf από το αρχείο σε δύο μεταβλητές και δουλεύω με αυτές .

Για να postάρω τον κώδικα , απλά δίνω στο site το crocodiles.c και σε 5-10 δευτερόλεπτα με λένε το αποτέλεσμα 10 test ( που είναι πάντα τα ίδια ) . Αλλά με ποιον compiler μεταγλωττίζεται δεν λένε οι ύπουλοι !

Τέλος , δεν κατάλαβα τι εννοούσες με το fork()

Εντάξει , συγγνώμη , το έψαξα και βρήκα λίγο πολύ τι κάνει , αν και θα με ενδιέφερε να το εξηγήσεις !!!!

[Evgenios1]

E ναι , αυτό δεν κάνω ; Τα αποθηκεύω με την fscanf από το αρχείο σε δύο μεταβλητές και δουλεύω με αυτές .

Για να postάρω τον κώδικα , απλά δίνω στο site το crocodiles.c και σε 5-10 δευτερόλεπτα με λένε το αποτέλεσμα 10 test ( που είναι πάντα τα ίδια ) . Αλλά με ποιον compiler μεταγλωττίζεται δεν λένε οι ύπουλοι !

Τέλος , δεν κατάλαβα τι εννοούσες με το fork()

 

Link?

δασδασδ

[firewalker]

E ναι , αυτό δεν κάνω ; Τα αποθηκεύω με την fscanf από το αρχείο σε δύο μεταβλητές και δουλεύω με αυτές .

 

Ναι όντως. Είναι και αργά και τα μάτια...

 

Τις μεταβλητές left και right τι τιw θέλεις;

[V.I.Smirnov]

- -

[ARIANAROS]

Χααχαχαχαχα , οι left και right ήταν παλιό τερτίπι μπας και μειώσω τον χρόνο και μετά ξέχασα να τις βγάλω ! Το site λέγεται hellenico ( είναι site προετοιμασίας για τον Πανελλήνιο Διαγωνισμό Πληροφορικής ( μην λιγουρεύεστε , είναι μόνο για μαθητές σαν και του λόγου μου ) ) αλλά πρέπει να περάσεις τις προηγούμενες ενότητες για να φτάσεις σε αυτό που σας λέω εγώ . Και το χειρότερο ξέρετε ποιο είναι ; Υπάρχουν άτομα που το έχουν περάσει !!!

[Evgenios1]

Χααχαχαχαχα , οι left και right ήταν παλιό τερτίπι μπας και μειώσω τον χρόνο και μετά ξέχασα να τις βγάλω ! Το site λέγεται hellenico ( είναι site προετοιμασίας για τον Πανελλήνιο Διαγωνισμό Πληροφορικής ( μην λιγουρεύεστε , είναι μόνο για μαθητές σαν και του λόγου μου ) ) αλλά πρέπει να περάσεις τις προηγούμενες ενότητες για να φτάσεις σε αυτό που σας λέω εγώ . Και το χειρότερο ξέρετε ποιο είναι ; Υπάρχουν άτομα που το έχουν περάσει !!!

 

LOL υπαρχουν τετοια πραματα στην ελλαδα!!! Μπραβω!!

 

ΥΓ: Εφοσον ειναι διαγωνισμος χτυπα το κλο σου να βρεις την ακρη. ΜΟΝΟΣ ΣΟΥ

[ARIANAROS]

LOL υπαρχουν τετοια πραματα στην ελλαδα!!! Μπραβω!!

 

ΥΓ: Εφοσον ειναι διαγωνισμος χτυπα το κλο σου να βρεις την ακρη. ΜΟΝΟΣ ΣΟΥ

 

Μην με μαλώνεις :cry: .

Βρε , αφού έχω δώσει λύσει , αυτό είναι προετοιμασία απλά , και αν δεν το λύσω δεν προχωράω παρακάτω , τότε δεν με νοιάζει που υπάρχει ένα τεχνικό πρόβλημα με τον χρόνο . Εγώ τυπικά είμαι εντάξει . Αν θέλουν να αγοράσουν καλύτερα μηχάνημα αφού βιάζονται τόσο !!!

Δοκιμάζω τώρα αυτό που είπε πιο πάνω ο φίλος . Αν είναι σωστό χρωστάω ΜΕΓΑΛΗ χάρη !!!

 

---------- Προσθήκη στις 02:03 ---------- Προηγούμενο μήνυμα στις 01:50 ----------

 

@V.I.Smirnov

 

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

Ορίστε ( σε κάθε περίπτωση ) ο κώδικας που έγραψα εγώ με βάση αυτά που κατάλαβα .....

>#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 = 1 ; i < N ; i++ ) {
	fscanf ( in , "%d %d" , &a2 , &b2 ) ;
	if ( b1 < a2 || a1 > b2) {
		crocs-- ;
		continue ;
	}
	a1 = b1 ;
	a2 = b2 ;
}
fprintf ( out , "%d\n" , crocs ) ;
fclose ( in ) ; fclose ( out ) ;
return ( 0 ) ;
}

Kαι δεν λειτουργεί ......

[V.I.Smirnov]

- -