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

[virxen75]

επίσης κρατώντας το min,max από τις ημερομηνίες γέννησης-θανάτου

δεν θα χρειαστεί να ψάχνεις από -100000 έως 100000

αλλά μεταξύ min-max.

[ARIANAROS]

Παιδιά , ο κώδικας είναι σωστός σίγουρα . Δοκίμασα με global variables αλλά ίσα ίσα που αργεί και λίγο περισσότερο ( 0.008 δεύτερα σε μεγάλα Ν ) . Όταν αποτυγχάνει το Ν = 300.000 ( βασικά είχα βρει και πόσο ακριβώς είναι αλλά δεν θυμάμαι τώρα , νομίζω 274.000 και κάτι ψιλά ) . Αυτό που είπες για min και max δεν βοηθάει γιατί θα ελέγξει τόσες φορές για το min και το max που καλύτερα να μην υπήρχε .

[nplatis]

Αρχικά κάποιες παρατηρήσεις σχετικά με τον τελευταίο κώδικα που προτείνεται εδώ.

 

α) Αν ο πίνακας είναι

int croc[200000];

γιατί το

for ( i = 0 , j = 0 ; i < 200001 ; i++ )

τελειώνει έτσι και όχι με i < 200000 ;

 

β) Για να διαβαστούν οι ημερομηνίες γέννησης και θανάτου χρησιμοποιούνται τα δύο στοιχεία του πίνακα crocodile[2]. Αυτό όμως προκαλεί πρόσβαση σε στοιχεία πίνακα αρκετές φορές μέσα στο πρόγραμμα, όταν δύο απλές μεταβλητές θα έκαναν την ίδια δουλειά.

 

γ) Η επανάληψη θα μπορούσε να βελτιστοποιηθεί ως εξής (αν δεν κάνω κανένα λάθος από βιασύνη):

 

>
   for ( i = 0 ; i < N ; i++ ) {
       fscanf ( in , "%d %d" , &a , &b ) ;
       for ( j = a ; j < b ; j++ ) {
           croc[j+100000]++ ;
       }
   }

 

Και τώρα τα άσχημα νέα: αν ο κώδικας κάνει 4 δευτερόλεπτα και αυτοί ζητούν να κάνει 1, λογικά χρειάζεται εντελώς άλλο αλγόριθμο για να δουλέψει τόσο πιο γρήγορα -- εκτός και αν μπορεί να επιταχυνθεί δραματικά η ανάγνωση του αρχείου.

 

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

 

Update: Στον δικό μου υπολογιστή, με τις αλλαγές του (β) και (γ) ο χρόνος έπεσε από 6.55-6.60 σε 6.30-6.35 σε ένα παράδειγμα (αναφέρω τα νούμερα του time). Κάτι είναι, αλλά όχι σημαντικό.

 

Επίσης ο generator που προτείνεται δουλεύει μόνο για RAND_MAX==32768...

[V.I.Smirnov]

- -

[kagelos]

Με τι αρχείο μπορώ να τεστάρω μια λύση;

Πόσους κροκόδειλους έχει μέσα max ένα αρχείο;

Να πάρω έναν από τους generators που postαραν κάποιοι;

[ARIANAROS]

@V.I.Smirnov

 

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

 

@kagelos

 

Οι κροκόδειλοι είναι N , άρα το maximum είναι 300.000 κροκόδειλοι . Ναι , μπορείς να πάρεις έναν από τους generators που φτιάξαν τα παιδιά , φρόντισε όμως να βάλεις μικρό Ν για να μην περιμένεις τρία λεπτά για να τρέξει το πρόγραμμα .

[epersidi]

Με τι αρχείο μπορώ να τεστάρω μια λύση;

Πόσους κροκόδειλους έχει μέσα max ένα αρχείο;

Να πάρω έναν από τους generators που postαραν κάποιοι;

 

Πάρε τον δικό μου, δουλεύει αρκεί το RAND_MAX να είναι 32768 το οποίο είναι η default τιμή στην γλώσσα C. Μπορείς να το ελέγξεις κάνοντας search το RAND_MAX στο stdlib.h . Ξαναλέω πάντως ότι αποκλείεται να βρεθεί λύση <1sec με τα δεδομένα που δημιουργεί ο generator (300000 καταχωρήσεις με εντελώς random στοιχεία).

 

α) Αν ο πίνακας είναι

int croc[200000];

γιατί το

for ( i = 0 ' date=' j = 0 ; i < 200001 ; i++ )

τελειώνει έτσι και όχι με i < 200000 ; [/quote']

 

Έχεις δίκιο. Λάθος λόγω copy+paste ...

[kagelos]

Έγραψα έναν δικό μου σε C#

 

 

>[color="#2b91af"]StreamWriter[/color] sw = [color="#0000ff"][b]new[/b][/color] [color="#2b91af"]StreamWriter[/color]([color="#a31515"]"c:\\croc.txt"[/color], [color="#0000ff"][b]false[/b][/color], System.Text.[color="#2b91af"]Encoding[/color].ASCII);
[color="#0000ff"][b]const[/b][/color] [color="#8000ff"]int[/color] N = [color="#ff8000"]300000[/color];

[color="#2b91af"]Random[/color] rnd = [color="#0000ff"][b]new[/b][/color] [color="#2b91af"]Random[/color]();

sw.WriteLine(N.ToString());
[color="#8000ff"]int[/color] a, b, tmp;
[color="#0000ff"][b]for[/b][/color] ([color="#8000ff"]int[/color] i = [color="#ff8000"]0[/color]; i < N; i++)
{
   a = rnd.Next(-[color="#ff8000"]100000[/color], [color="#ff8000"]100001[/color]);
   b = rnd.Next(-[color="#ff8000"]100000[/color], [color="#ff8000"]100001[/color]);

   [color="#0000ff"][b]while[/b][/color] (b == a)
       b = rnd.Next(-[color="#ff8000"]100000[/color], [color="#ff8000"]100001[/color]);

   [color="#0000ff"][b]if[/b][/color] (b < a)
   {
       tmp = b;
       b = a;
       a = tmp;
   }

   sw.WriteLine(a + [color="#a31515"]" "[/color] + ;
}

sw.Close();

 

 

[epersidi]

@ARIANAROS

 

H ιδέα μου για την τομή των διαστημάτων πιστεύω είναι μια καλή αρχή διότι είναι πολύ κοντά σε αυτό που θέλεις και εγώ θα ξεκινούσα να ψάχνω από εκεί :

(1) Δίδεται :

- ένα σύνολο από n τμήματα στο ίδιο επίπεδο (στην περίπτωσή σου είναι και συγραμμικά) και

(2) Zητείται

- να βρεθούν όλα τα ζεύγη που τέμνονται μεταξύ τους καθώς και τα σημεία τομής.

(3) Eπιπλέον για την περίπτωσή σου, ζητείται

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

 

Το 2 δεν ζητήται. Μόνο το 3.

 

Όμως υπάρχει κι ένας πολύ πιο αποδοτικός τρόπος : ένας αλγόριθμος plane sweep που είναι Ο(n*logn), δηλ. πολύ ταχύτερος από τον απλοϊκό τρόπο που είναι O(n**2).

Η ιδέα είναι να μην εξετάζονται τμήματα που βρίσκονται μακριά μεταξύ τους και αποκλείεται να τέμνονται (επικαλύπτονται στην περίπτωσή σου).

 

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

 

Y.Γ. Για να αποφύγεις τον βρόγχο αρχικού μηδενισμού του πίνακα croc μπορείς να χρησιμοποιήσεις την εντολή calloc (κάποιος το είπε ήδη) :

int *croc=(int*) calloc(200001,sizeof(int)); // (ο μηδενισμός του πίνακα γίνεται από το σύστημα πιο γρήγορα)

με

#include <malloc.h>

 

Ξαναείπα (νομίζω) ότι αρκεί να δηλώσουμε τον πίνακα ως εξωτερικό αφού αυτόματα θέτονται όλα του τα στοιχεία ίσα με το 0.

[Directx]

Το ζήτημα μπορεί ενδεχομένως να έχει σχέση με το Algorithmic Patterns and the Case of the Sliding Delta του D. Ginat το οποίο έχει δημοσιευθεί στο SIGCSE.

 

Η διατύπωση του προβλήματος στο Google απέδωσε ένα τμήμα (fragment) από το συγκεκριμένο publication το οποίο αναφέρεται σε κάποιο πρόβλημα με Κροκόδειλους το οποίο ομοιάζει με το ζητούμενο. Λέω, υποθέτω, διότι δεν έχω βρει ολόκληρο το PDF διαθέσιμο ώστε να επιβεβαιώσω ότι πρόκειται όντος για το αυτό ζήτημα:

 

Crocodiles: Given the years of birth and death of each of N crocodiles, the goal is to calculate the maximal number of crocodiles that were alive at the same time. We assume for simplicity that all the input years are distinct. In addition, as crocodiles are on earth for many, many years, the range of each input [..]

 

Η διατύπωση είναι σε μεγάλο βαθμό κοινή ( ? ) και από ένα σημείο και πέρα πιο περιεκτική από ότι η Ελληνική εκδοχή - μετάφραση του.

 

Όποιος θέλει να το ψάξει ας δει εδώ.

 

Καλή τύχη!

 

Υ.Γ.

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

[kagelos]

(αφού στην εκφώνηση ΔΕΝ μας δίνεται κάποιο ανώτατο όριο ηλικίας για τους κροκόδειλους)

 

Ο κροκόδειλος μπορεί να είναι το πολύ 200.000 ετών (-100.000 έως 100.000 χρόνος γέννησης και θανάτου).

[parsifal]

Διάβασα λίγο στα πεταχτά την εκφώνηση και τα υπόλοιπα μηνύματα του thread, γι' αυτό συγχωρήστε με αν η ιδέα που θα παρουσιάσω έχει γραφτεί ήδη με άλλη διατύπωση.

 

Η ιδέα είναι η εξής: Αντιμετώπιση του προβλήματος εν είδει time simulation. Δε σε ενδιαφέρουν ηλικίες των κροκοδείλων, επικαλυπτόμενα διαστήματα και τα λοιπά. Μόνο πότε εμφανίζεται ένα εκ των δύο γεγονότων «πεθαίνει ένας κροκόδειλος» και «γεννιέται ένας κροκόδειλος», τα οποία επηρεάζουν άμεσα την τιμή του βασικού counter «Τρέχων αριθμός ζώντων κροκοδείλων» (και έμμεσα, του counter «Μέγιστος αριθμός ζώντων κροκοδείλων ever»). Δε σε νοιάζει όταν πεθαίνει κάποιος κροκόδειλος, πότε αυτός είχε γεννηθεί. Απλά, μειώνεις τον counter κατά 1. Τον αυξάνεις κατά 1 όταν συναντάς γεγονός γέννησης.

 

Χρειάζεται όμως να γίνει συγχώνευση (την κάνεις εξαρχής καθώς διαβάζεις το αρχείο εισόδου) των ημερομηνιών γεννήσεων/θανάτου σε έναν κοινό πίνακα (διάστασης Nx2, για να κρατάς στη δεύτερη στήλη το είδος του γεγονότος ή αν θέλεις με μονοδιάστατο πίνακα, εισάγεις σε αυτόν structs) και ταξινόμησή τους [Ο(NlogN) πολυπλοκότητα έχουν οι «καλοί» sorting αλγόριθμοι]. Τέλος, διατρέχεις μία ακόμη φορά τον πίνακα [Ο(N)] για την «προσομοίωση».

 

Από τα παραπάνω, νομίζω πως βγαίνει συνολική πολυπλοκότητα της τάξης O(NlogN), αντί της Ο(N^2) που δίνει το διπλά εμφωλευμένο for N επαναλήψεων της υφιστάμενης λύσης.

[virxen75]

και ένας generator που δουλεύει άσχετα με το RAND_MAX

 

>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define min(a, a<=b?a:b
#define max(a, a>=b?a:b
#define N 300000

int main(){
FILE *in = fopen("crocodiles.in", "w");
int i;
srand(time(NULL)); 
fprintf(in, "%d\n", N);
for(i = 1; i <= N; i++)	{
             int a=0,b=0;
             while (a=={
	  a = 10*(rand()%20001) - 100000;
	  b = 10*(rand()%20001) - 100000;     
             }
      fprintf(in, "%d %d\n", min(a,, max(a,);
}
fclose(in);
return 0;
}

[chiossif]

Διάβασα λίγο στα πεταχτά την εκφώνηση και τα υπόλοιπα μηνύματα του thread, γι' αυτό συγχωρήστε με αν η ιδέα που θα παρουσιάσω έχει γραφτεί ήδη με άλλη διατύπωση.

 

Η ιδέα είναι η εξής: Αντιμετώπιση του προβλήματος εν είδει time simulation. Δε σε ενδιαφέρουν ηλικίες των κροκοδείλων, επικαλυπτόμενα διαστήματα και τα λοιπά. Μόνο πότε εμφανίζεται ένα εκ των δύο γεγονότων «πεθαίνει ένας κροκόδειλος» και «γεννιέται ένας κροκόδειλος», τα οποία επηρεάζουν άμεσα την τιμή του βασικού counter «Τρέχων αριθμός ζώντων κροκοδείλων» (και έμμεσα, του counter «Μέγιστος αριθμός ζώντων κροκοδείλων ever»). Δε σε νοιάζει όταν πεθαίνει κάποιος κροκόδειλος, πότε αυτός είχε γεννηθεί. Απλά, μειώνεις τον counter κατά 1. Τον αυξάνεις κατά 1 όταν συναντάς γεγονός γέννησης.

 

Χρειάζεται όμως να γίνει συγχώνευση (την κάνεις εξαρχής καθώς διαβάζεις το αρχείο εισόδου) των ημερομηνιών γεννήσεων/θανάτου σε έναν κοινό πίνακα (διάστασης Nx2, για να κρατάς στη δεύτερη στήλη το είδος του γεγονότος ή αν θέλεις με μονοδιάστατο πίνακα, εισάγεις σε αυτόν structs) και ταξινόμησή τους [Ο(NlogN) πολυπλοκότητα έχουν οι «καλοί» sorting αλγόριθμοι]. Τέλος, διατρέχεις μία ακόμη φορά τον πίνακα [Ο(N)] για την «προσομοίωση».

 

Από τα παραπάνω, νομίζω πως βγαίνει συνολική πολυπλοκότητα της τάξης O(NlogN), αντί της Ο(N^2) που δίνει το διπλά εμφωλευμένο for N επαναλήψεων της υφιστάμενης λύσης.

 

72η δημοσίευση...

[C6WGMN]

Ο κροκόδειλος μπορεί να είναι το πολύ 200.000 ετών (-100.000 έως 100.000 χρόνος γέννησης και θανάτου).

 

Αν διαβάσεις προσεχτικά θα δεις ότι είναι το πολύ 199.999 ετών