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

[V.I.Smirnov]

@ARIANAROS

 

Φίλε μου ξανασκέφτηκα λίγο την ιδέα μου με τα διαστήματα και έχω να σου πω το εξής.

Αν δεν απαλλαγείς από το διπλό loop, ότι και να κάνεις, το πρόγραμμα ΔΕΝ θα τρέξει πιο γρήγορα διότι είναι O(n**2).

Για δες τι σκέφτηκα. Ξαναλέω για τους άλλους ότι το πρόβλημα όπως το σκέπτομαι εγώ, μπορεί να αναχθεί σε γεωμετρικό :

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

Στην περίπτωσή μας τα πέρατα των διαστημάτων είναι προφανώς οι ημερομηνίες γέννησης και θανάτου των κροκοδείλων.

 

Έστω Δ1,Δ2,..Δn είναι τα διαστήματα και έστω k είναι το πλήθος των επικαλύψεων που υπάρχουν.

Δηλ. αν έχεις πχ. 7 διαστήματα, μπορεί να επικαλύπτονται (τομή) τα 1,2, τα 2,4,5,6 και τα 6,7 οπότε k=3.

Πρόσεξε κάτι : επαγωγικά (ή αλλιώς μεταβατικά) εξασφαλίζεται μόνον "σύνδεση" των διαστημάτων που μας είναι αδιάφορη και πάντως όχι η επικάλυψή τους.

Αυτό ήταν το λάθος μου στην πρώτη μου απάντηση και γι αυτό την απέσυρα.

Το ότι επικαλύπτονται πχ. το 1 με το 2 και το 2 με το 4 σημαίνει ότι το 1 'συνδέεται' με το 4 μέσω του 2

ΑΛΛΑ ΟΧΙ ότι αναγκαστικά επικαλύπτονται (coverage) και το 1 με το 4 διότι αυτό εξαρτάται και από την έκτασή τους. Στο χαρτί μπορείς να το δεις αμέσως.

Έστω Si η κάθε επικάλυψη (τομή) που έχουν τα παραπάνω διαστήματα.

Δηλ. το Si μπορεί να είναι μια από τις τομές S1=(1,2), S2= (2,4,5,6) ή S3= (6,7).

 

(1) Ορίζεις έναν πίνακα COV που θα κρατά ΠΟΣΑ είναι τα διαστήματα που αποτελούν ("φτιάχνουν") κάθε Si.

Δηλ. το πλήθος των στοιχείων σε καθένα από τα S1, S2, S3.

Ο πινακας COV Θα έχει πραγματική έκταση (δηλ. πλήθος στοιχείων) όσο είναι το πλήθος των επικαλύψεων Si το οποίο αρχικά είναι άγνωστο.

Στο παραπάνω παράδειγμα θα είναι 3 διότι έχουμε 3 Si : τα S1,S2, S3.

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

( Νομίζω ότι o μέγιστος Si προκύπτει όταν τα ταξινομημένα διαστήματα επικαλύπτονται μόνον ανα δύο μεταξύ τους :

τότε υπάρχουν n-1 Si με δυο στοιχεία (διαστήματα) στο κάθε Si και ο COV έχει έκταση n-1. )

 

(2) Διαβάζεις τα διαστήματα από το αρχείο. Αυτό είναι χρονοβόρο O(n).

 

(3) Tαξινομείς τα διαστήματα κατά αύξουσα σειρά με κλεδί την αφετηρία τους.

Έτσι, τοποθετούνται διαδοχικά, ανάλογα με το σημείο απ' όπου ξεκινούν.

Προσοχή, η ταξινόμηση πρέπει να γίνει με quicksort διότι αυτή είναι O(nlogn).

Η C++ έχει έτοιμη συνάρτηση που το κάνει, την qsort (ή qsort_s) αν θυμάμαι καλά.

Πρέπει να δεις πώς θα την χρησιμοποιήσεις, το visual studio έχει παράδειγμα.

Όπως παρατήρησα παραπάνω, η επαγωγή-μεταβατικότητα στις συγκρίσεις των επικαλύψεων δεν ισχύει

και ουσιωδώς η ταξινόμηση βοηθά να αρθεί εν μέρη αυτός ο περιορισμός.

Όταν λέω "ταξινόμηση των διαστημάτων" υποτίθεται ότι αυτά είναι αποθηκευμένα σε έναν πίνακα Δ[n][2]

όπoυ n είναι το πλήθος των διαστηματων ενώ Δ[1], Δ[2] είναι η αρχή και το πέρας του διαστήματος i.

H ταξινόμηση πρέπει να γίνει κατά την αύξουσα σειρά των Δ[1].

 

(4)

Πρέπει να φτιάξεις τα Si και να βρεις ποιο έχει το μέγιστο πλήθος στοιχείων.

Στο παράδειγμά μας είναι το S2. Να ένας τρόπος O(n).

 

Βρίσκεις την επικάλυψη κάθε επόμενου διαστήματος, Δi+1, με την τρέχουσα, Si.

Προφανώς τα περιεχόμενα του Si θα αλλάζουν σε κάθε σύγκριση, εκτός αν δυο διαστήματα συμπίπτουν (δηλ. αν δυο κροκόδειλοι γεννήθηκαν και πέθαναν ταυτόχρονα).

Εκείνο που τελικά ενδιαφέρει εμάς δεν είναι τα στοιχεία του Si, δηλ. τα ποιά διαστήματα αποτελούν το Si (ή αλλιώς ποια είναι τα άκρα της τρέχουσας τομής Si),

αλλά μόνον το πλήθος τους, δηλ. πόσα περιέχει (πόσα "φτιάχνουν") το Si.

Aυτό το πλήθος πρέπει να αυξάνεται κάθε φορά που βρίσκεται ένα στοιχείο του Si και να αποθηκεύεται για το τρέχον Si πριν πάμε να βρούμε το επόμενο Si.

(Στο τέλος, θα πάρουμε το μέγιστο από αυτά τα πλήθη που αποθηκεύτηκαν και αυτό είναι η απάντηση.)

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

Δηλ. το Si περιέχει στην πραγματικότητα τα άκρα (τετμημένες) της τρέχουσας τομής.

Πχ. όταν γράφω S1=(1,2) εννοώ ότι έχω συγκρίνει τα πέρατα των διαστημάτων 1,2 και το S1 είναι το διάστημα (a, με πέρατα a,b το οποίο είναι κοινό για αμφότερα τα 1,2 (δηλ. είναι η τομή τους).

Όμοια, όταν όταν γράφω S2= (2,4,5,6) εννοείται ότι έχουν συγκριθεί τα διαστήματα αυτά και το S2 είναι το κοινό τμήμα (δηλ. έχουμε βρει τα άκρα του, τις τετμημένες) και για τα 4 (δηλ. είναι η τομή των 2,4,5,6).

Για να μην ψάχνεις, εφόσον είναι ταξινομημένα όπως είπαμε, αν το Si είναι το (a1,b1) και το Δi+1 είναι το (a2,b2),

-- τα Si και Δi+1 επικαλύπτονται όταν a2<b1 (προφανώς δεν μπορεί να είναι a1>a2 ή b2 λόγω της ταξινόμησης),

-- η τομή τους είναι το διάστημα με άκρα ( a2, min(b1,b2) ) .

Δες τα στο χαρτί.

 

Aρχικά θέτεις S=Δ1 και k=0. Έστω και μια βοηθητική bool μεταβλητή Counted.

To k είναι ένας μετρητής που θα δείχνει ποιο Si εξετάζεται.

Δηλ. αν φτιάχνουμε το S1 θα έχουμε k=1 και θα αποθηκεύουμε το πλήθος των στοιχείων του στο COV(k=1).

Για το S2, k=2 και αποθηκεύουμε το πλήθος των στοιχείων του στο COV(k=2) κλπ.

Πόσα Si υπάρχουν δεν είναι γνωστό αρχικά, τα βρίσκουμε εν διαβάσει (on the fly).

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

 

DO i=1,n-1

Tο επόμενο διάστημα Δi+1 και η τρέχουσα επικάλυψη Si, επικαλύπτονται ?

IF (ναι), // αυτό σημαίνει ότι συνεχίζουμε να επεξεργαζόμαστε το Si

- βρίσκεις την επικάλυψη Snew των Si, Δi+1 και θέτεις Si = Snew

- θέτεις COV(k) +=1; // το τρέχον Si έχει ακόμα ένα στοιχείο

- Counted = false;

Εnd if

IF (όχι),

// θα ξεκινήσεις να μετράς πλήθος στοιχείων σε νέα επικάλυψη , δηλ. πρέπει να πας στο επόμενο Si, οπότε το k πρέπει να αυξηθεί κατά 1

- if (!Counted) then

k +=1;

Counted = true;

end if

// για το νέο Si ξεκινάς από το τρέχον διάστημα όπως όταν ξεκινάει αρχικά ο βρόγχος, οπότε πρέπει Si = Δi και i = i-1

- i = i-1

- S = Δi;

end if

END IF

 

END DO

 

(5) Μετά το τέλος του βρόγχου (4), το k ισούται με το πλήθος των Si (τρία στο παράδειγμά μας).

Ο πίνακας COV περιέχει πόσα αρχικά διαστήματα "φτιάχνουν" την τομή-επικάλυψη που περιέχεται σε κάθε Si.

COV(1)=2, COV(2)=4, COV(3)=2

Θυμίζω ότι ο Si περιέχει στην πραγματικότητα το διάστημα που είναι η τομή-επικάλυψη μιας ομάδας αρχικών διαστημάτων και όχι τους δείκτες τους.

Σαρώνεις τον COV με ένα βρόγχο για να βρεις την μέγιστη τιμή του που είναι το ζητούμενο) (εδώ 4).

Το βήμα αυτό είναι επίσης O(n).

 

Μια παρατήρηση για την αύξηση του k :

Το τρέχον k δείχνει πόσες επικαλύψεις έχουν μετρηθεί και αυξάνεται κάθε φορά που ΔΕΝ βρίσκεται επικάλυψη υποθέτοντας ότι η επόμενη σύγκριση θα είναι επιτυχής, ότι δηλ. θα έχουμε επικάλυψη και θα ‘πάμε’ στο επόμενο Si.

Όταν, όμως, διαδοχικά δεν υπάρχουν επικαλύψεις περισσότερες από μια φορές, το k θα αυξηθεί περισσότερο από μια φορά και θα έχει λάθος τιμή.

Για να αποφευχθεί αυτό χρησιμοποιείται βοηθητικά το Counted ώστε να μην μπορεί να αυξηθεί διαδοχικά πάνω από μια φορά.

 

Έτσι ο χρόνος εκτέλεσης τελικά είναι k*O(n) + O(nlogn) , δηλ. πολύ μικρότερος από το O(n**2).

 

Η ταξινόμηση εξασφαλίζει ότι

--- άπαξ και σαρωθεί ένα διάστημα, ΔΕΝ χρειάζεται να ξανασαρωθεί διότι θα έχει ελεγχθεί σε σχέση με όλα τα προηγούμενά του. Έτσι, η δημιουργία/έλεγχος των Si μπορεί να προχωρήσει επαγωγικά.

--- δύο διαδοχικά διαστήματα Δi, Δi+1 που βρέθηκε ότι ΔΕΝ έχουν επικάλυψη εξασφαλίζουν ότι όλα τα προηγούμενα Δ(1 ως i-1) δεν επκαλύπτονται με τα επόμενά τους Δ(i+1 ως n),

άρα αυτές οι δυο ομάδες δεν χρειάζεται και να ελεγχθούν μεταξύ τους. Έτσι οι πολλαπλές συγκρίσεις αποφεύγονται.

Η ταξινόμηση όμως ΔΕΝ πρέπει να γίνει με O(n**2) τρόπο διότι τότε δεν κερδίζεις τίποτε. Aπ΄οτι θυμάμαι, η quicksort είναι O(nlogn).

 

Ο αλγόριθμος εύκολος αν καταλάβεις πως να χρησιμοποιήσεις τα διαστήματα.

Το μόνο δύσκολο είναι εφαρμόσεις σωστά την quicksort.

Μην επιχειρήσεις να γράψεις δική σου - είναι δύσκολο - πάρε την έτοιμη που έχει η βιβλιοθήκη. (Θέλει τα include <stdlib.h> ή <search.h>)

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

Mικρές αβλεψίες μπορούν να διορθωθούν εύκολα.

(β) Δοκίμασε να ταξινομήσεις έναν δισδιάστατο πίνακα Α[][] με quicksort με κλειδί το πρώτο στοιχείο της δεύτερης διάστασής του.

Αν τα (α),(β) πετύχουν είναι εύκολο να κάνεις το πρόγραμμα.

 

Καλή επιτυχία !!!

 

 

Ναι, έφτιαξα τον κώδικα ! Έχει κάποιες ελάχιστες διορθώσεις σε σχέση με ότι γράφω παραπάνω αλλά δουλεύει !!!

[nplatis]

Νομίζω ότι η απόλυτη ιδέα είναι αυτή του parsifal, ενώ η λύση του V.I.Smirnov προσπαθεί να κάνει κάτι παρόμοιο αλλά με αρκετά πιο πολύπλοκο τρόπο.

 

Το βασικό σκεπτικό είναι ότι γυρίζει την αντιμετώπιση ανάποδα: αντί να πηγαίνει με βάση τα δεδομένα των κροκοδείλων, πηγαίνει με βάση τον χρόνο.

 

Η υλοποίηση που ακολουθεί στον δικό μου υπολογιστή δίνει χρόνο 0.18 ενώ η αρχική λύση έδινε 6.35 !!! (για αρχείο με 300.000 εγγραφές)

 

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


typedef struct _date  {
   int year;
   int what;
} date;


int compdate(const void * d1, const void * d2)
{
   date* dd1 = (date*)d1;
   date* dd2 = (date*)d2;
   int y1 = dd1->year;
   int y2 = dd2->year;
   if (y1 == y2)  {
       return (dd1->what - dd2->what);
   }
   else  {
       return (y1-y2);
   }

}


int main ( void ) {
   FILE *in = fopen ( "crocodiles.in" , "r" );
   FILE *out = fopen ( "crocodiles.out" , "w" );
   int N, a, b ;
   register int i , j;
   int max = 0, alive = 0;

   date alldates[300000*2];
   
   if(in==NULL) return 0; // File not found !

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

   for ( i = 0 ; i < N ; i++ ) {
       fscanf ( in , "%d %d" , &a , &b ) ;
       alldates[i].year = a;
       alldates[i].what = 1;   // birth
       alldates[i+N].year = b-1;   // must be b-1 because crocodile stops existing on that year!
       alldates[i+N].what = 2;   // death
   }
   
   qsort(alldates, N*2, sizeof(date), compdate);
       
   for (i = 0; i < N*2; i++)  {
       if (alldates[i].what == 1)  {
           alive++;
       }
       else  {
           alive--;
       }
       if (alive > max)  {
           max = alive;
       }
   }
   

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

 

 

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

-- ΑΚΥΡΟ, δεν ισχύει αυτό καθώς μία quicksort έχει ασφαλώς μικρότερη πολυπλοκότητα από 2*Ν εισαγωγές σε ταξινομημένη δομή...

[V.I.Smirnov]

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

Έχεις δίκο. Οι glοbal και static μεταβλητές αρχικοποιούνται σε μηδέν.

 

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

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

 

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

Εδώ είσαι τελείως λάθος !!!

Ο αλγόριθμος που ανέφερα είναι ακριβής και λύνει το γεωμετρικό πρόβλημα πλήρως.

Είναι Ο((r+n)logn) όπου n το συνολικό πλήθος των διαστημάτων και r το πλήθος των διαστημάτων που τέμνοναι.

Δες πχ. Ο' Rourk "Computational Geometry in C" 2nd ed, theorem 7.7.1, σελ. 266 ή "Computational Geometry", deBerg 3rd ed., theorem 2.4, σελ 29.

 

Άσχετα από αυτό, είναι απίθανο να έχει τόσο δύσκολη λύση.

Σκεπτόμενος πάλι βρήκα κάτι που χρησιμοποιεί την quicksort και φαίνεται να δουλεύει.

Απέσυρα το προηγούμενο μου post και έδωσα πιο πανω ένα νέο με την λύση που σκέφτηκα...

 

 

Νομίζω ότι η απόλυτη ιδέα είναι αυτή του parsifal, ενώ η λύση του V.I.Smirnov κάνει κάτι παρόμοιο αλλά με αρκετά πιο πολύπλοκο τρόπο.

 

Το βασικό σκεπτικό είναι ότι γυρίζει την αντιμετώπιση ανάποδα: αντί να πηγαίνει με βάση τα δεδομένα των κροκοδείλων, πηγαίνει με βάση τον χρόνο.

 

Ο τρόπος που περιγράφω είναι απλός και σε έκταση όσο ο δικός σου αν γίνει κώδικας αλλά η φλυαρία υπάρχει για να περιγράψω τι ακριβώς θα κάνει.

Σκέφτηκα γεωμετρικά. Αλλά, ναι, του parsifal είναι πιο "ευθύς" στη σκέψη, πιο απλός και πιο κομψός.

 

Πάντως, η ταξινόμηση είναι το κλειδί της λύσης και εξηγώ γιατί στο post μου πιο πάνω.

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

[virxen75]

..............

#include <stdio.h>

#include <stdlib.h>

 

typedef struct _date {

int year;

int what;

} date;

 

............

date alldates[300000*2];

............

 

ξέρεις πόση μνήμη χρειάζεται να δεσμεύσει αυτό για να τρέξει?

[ARIANAROS]

Nαι !!!!!! ΣΑΣ ΑΓΑΠΑΩ !!!!! ΤΟ ΛΥΣΑΤΕ !!!!!!!!!!!

Τελικά δεν ήταν και τόσο απλό . Μπράβο ρε παιδιά !!!!!!!!!!!!!!!!!!!!!!!!!!!

[nplatis]

Ο τρόπος που περιγράφω είναι απλούστατος και σε έκταση όσο ο δικός σου αν γίνει κώδικας αλλά η φλυαρία υπάρχει για να περιγράψω τι ακριβώς θα κάνει.

Σκέφτηκα γεωμετρικά. Αλλά, ναι, ο δικός σου και του parsifal είναι πιο "ευθύς" στη σκέψη.

 

Ευχαριστώ αλλά ο τρόπος λύσης δεν είναι «δικός μου», εγώ μία υλοποίηση της ιδέας του parsifal προσέφερα, κυρίως για να την τρέξουν αυτοί που το ψάχνουν.

 

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

 

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

 

ξέρεις πόση μνήμη χρειάζεται να δεσμεύσει αυτό για να τρέξει?

 

Ναι! 6 φορές περισσότερη από την αρχική λύση. Όμως αυτό συμβαίνει μόνο όταν έχουμε 300000 δεδομένα (ή καλύτερα: η πρώτη λύση δεσμεύει χώρο που εξαρτάται από το εύρος ηλικιών, η δεύτερη ανάλογα με το πλήθος των δεδομένων).

 

Ε, για να κερδίσεις σε ταχύτητα κάτι πρέπει να χάσεις (μνήμη), δύσκολο να γίνεται αλλιώς

[virxen75]

στον δικό μου υπολογιστή για παράδειγμα δεν τρέχει για 300000 εγγραφές

[nplatis]

Μπορείς εύκολα να κόψεις τις απαιτήσεις της μνήμης στο μισό, με κάποιο κόστος στην ταχύτητα (μικρό): Καταργείς το struct και δημιουργείς δύο πίνακες (ακεραίων), έναν με τις γεννήσεις, έναν με τους θανάτους. Ταξινομείς τον καθένα σε αύξουσα σειρά. Διατρέχεις και τους δύο πίνακες «παράλληλα» προχωρώντας σε όποιον συναντάς το μικρότερο έτος, αυξάνοντας ή μειώνοντας το πλήθος των «επιζόντων» (και ενημερώνοντας το max).

[V.I.Smirnov]

Ευχαριστώ αλλά ο τρόπος λύσης δεν είναι «δικός μου», εγώ μία υλοποίηση της ιδέας του parsifal προσέφερα, κυρίως για να την τρέξουν αυτοί που το ψάχνουν.

 

Όμως δεν νομίζω ότι ο δικός σου τρόπος είναι ίδιος σε έκταση: δες τον κώδικα που δίνεις, βοηθητικές μεταβλητές κ.λπ., στη θέση του απλούστατου for που υπάρχει στον κώδικα (μετά την qsort).

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

 

Ο κώδικάς μου είναι σχεδόν ίδιος σε έκταση - τον έφτιαξα - αλλά κάπως πιο πολύπλοκος.

Δεν σκέφτηκα καν το time simulation, έδωσα μια γεωμετρική ερμηνεία και το έλυσα γεωμετρικά.

Η δική σου υλοποίηση είναι όντως πιο απλή και λιτή και την προτιμώ.

Το κλειδί της λύσης είναι η ταξινόμηση που κάνουμε κι οι δυο.

 

Και κάτι άσχετο. Πώς παραθέτετε κώδικα εδώ ; (για να βάλω κι εγώ...)

 

 

στον δικό μου υπολογιστή για παράδειγμα δεν τρέχει για 300000 εγγραφές

 

Δες μήπως φταίει το stack.

Και σε μένα δεν έτρεχε ο δικός μου και μόλις έβαλα stack 100 ΜΒ ήταν εντάξει.

 

 

@ARIANAROS

 

Mεγάλη η χάρη σου...

Το άλλο να το λύσεις μόνος σου..

[parsifal]

Δε χρειάζεται προκαταβολική δημιουργία του πίνακα στη στοίβα με μέγεθος 300.000. Αρκεί μία malloc για 2 * N structs, αμέσως μετά το σημείο του κώδικα που έχουμε διαβάσει την πρώτη γραμμή του crocodiles.in, οπότε και γνωρίζουμε πόσες γραμμές/κροκόδειλοι ακολουθούν.

[epersidi]

Καταρχήν συγχαρητήρια στον Parsifal που σκέφτηκε την πιο γρήγορη λύση.

 

 

Εδώ είσαι τελείως λάθος !!!

Ο αλγόριθμος που ανέφερα είναι ακριβής και λύνει το γεωμετρικό πρόβλημα πλήρως.

Είναι Ο((r+n)logn) όπου n το συνολικό πλήθος των διαστημάτων και r το πλήθος των διαστημάτων που τέμνοναι.

Δες πχ. Ο' Rourk "Computational Geometry in C" 2nd ed, theorem 7.7.1, σελ. 266 ή "Computational Geometry", deBerg 3rd ed., theorem 2.4, σελ 29.

 

Sorry αλλά μάλλον δεν ξέρεις τί ακριβώς είναι τα υπολογιστικά μαθηματικά και θεωρίες. Από τον ορισμό τους είναι μια προσπάθεια να βρεθεί μια προσεγγιστική λύση ενός προβλήματος χρησιμοποιώντας διάφορες υπολογιστικές τεχνικές π.χ. Πολυωνυμική παρεμβολή, Μέθοδος ελαχίστων τετραγώνων, Αριθμητική ολοκλήρωση κτλ. Όσο πιο πολλούς όρους βάζουμε σε αυτές τις μεθόδους τόσο πιο καλή προσέγγιση παίρνουμε του αποτελέσματος. Ψάξτο λίγο και θα δεις ότι έχω δίκιο ...

[V.I.Smirnov]

Καταρχήν συγχαρητήρια στον Parsifal που σκέφτηκε την πιο γρήγορη λύση....

 

Oι λύσεις που προτάθηκαν είναι δύο, του parsifal και η δική μου και είναι το ίδιο γρήγορες.

Και οι δύο έχουν κοινό χαρακτηριστικό την ταξινόμηση των διαστημάτων.

H λύση του parsifal έχει πιο απλή και ξεκάθαρη υλοποίηση γι' αυτό μου αρέσει περισσότερο και την προτιμώ.

Η δική μου είναι η αντιμετώπιση από γεωμετρική άποψη και είναι μεν το ίδιο γρήγορη - την δοκίμασα - αλλά σαν κώδικας είναι πιο στριφνή και πολύπλοκη .

 

 

Sorry αλλά μάλλον δεν ξέρεις τί ακριβώς είναι τα υπολογιστικά μαθηματικά και θεωρίες. Από τον ορισμό τους είναι μια προσπάθεια να βρεθεί μια προσεγγιστική λύση ενός προβλήματος χρησιμοποιώντας διάφορες υπολογιστικές τεχνικές π.χ. Πολυωνυμική παρεμβολή, Μέθοδος ελαχίστων τετραγώνων, Αριθμητική ολοκλήρωση κτλ. Όσο πιο πολλούς όρους βάζουμε σε αυτές τις μεθόδους τόσο πιο καλή προσέγγιση παίρνουμε του αποτελέσματος. Ψάξτο λίγο και θα δεις ότι έχω δίκιο ...

 

Ξέρω πολύ καλά τι είναι τα υπολογιστικά μαθηματικά, συγκεκριμένα η αριθμητική ανάλυση.

Εσύ μάλλον δεν ξέρεις τι είναι η υπολογιστική γεωμετρία.

Αυτό που λες εδώ είναι σωστό.

Για την συγκεκριμένη μέθοδο όμως, όχι, ΔΕΝ έχεις δίκιο.

Προφανώς συγχέεις την αριθμητική ανάλυση με την υπολογιστική γεωμετρία.

Η μέθοδος που αναφέρθηκε (sweepline) δίνει την ΠΛΗΡΗ λύση, όχι προσεγγιστική.

Και οι συγκεκριμένες αναφορές που παρέθεσα - και που προφανώς αγνόησες - το λένε ξεκάθαρα.

 

Η αριθμητική ανάλυση και η υπολογιστική γεωμετρία είναι διαφορετικά πράγματα !

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

[Portmaster]

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

int main (void)
{
int i;
int croco_birth;
int croco_death;

int N = 0;
int result = 0;
int current = 0;

int min_year = 100000;
int max_year = -100000;
int year[200001] = {0};

FILE *in = fopen("crocodiles.in", "r");
FILE *out = fopen("crocodiles.out", "w");

if(in == NULL || out == NULL)
	exit(1);

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

for(i = 0; i < N; i++) {
	fscanf (in ,"%d %d", &croco_birth, &croco_death);

	croco_birth += 100000;
	croco_death += 100000;

	if(croco_birth < min_year)
		min_year = croco_birth;

	if(croco_death > max_year)
		max_year = croco_death;

	year[croco_birth] += 1;
	year[croco_death] -= 1;
}

for(i = min_year; i < max_year; i++) {		
	current += year[i];

	if (current > result)
		result = current;
}

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

 

Σε εμένα είναι ~45% πιο γρήγορο από την λύση με το qsort, αν μπορεί κάποιος ας ελέγξει τα αποτελέσματα.

[epersidi]

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

int main (void)
{
int i;
int croco_birth;
int croco_death;

int N = 0;
int result = 0;
int current = 0;

int min_year = 100000;
int max_year = -100000;
int year[200001] = {0};

FILE *in = fopen("crocodiles.in", "r");
FILE *out = fopen("crocodiles.out", "w");

if(in == NULL || out == NULL)
	exit(1);

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

for(i = 0; i < N; i++) {
	fscanf (in ,"%d %d", &croco_birth, &croco_death);

	croco_birth += 100000;
	croco_death += 100000;

	if(croco_birth < min_year)
		min_year = croco_birth;

	if(croco_death > max_year)
		max_year = croco_death;

	year[croco_birth] += 1;
	year[croco_death] -= 1;
}

for(i = min_year; i < max_year; i++) {		
	current += year[i];

	if (current > result)
		result = current;
}

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

 

Σε εμένα είναι ~45% πιο γρήγορο από την λύση με το qsort, αν μπορεί κάποιος ας ελέγξει τα αποτελέσματα.

 

Πολύ καλή λύση και μάλιστα με γραμμική πολυπλοκότητα εν αντιθέσει με την λύση με qsort η οποία είχε O(nlogn). Δεν νομίζω να υπάρχει άλλος αλγόριθμος πιο γρήγορος από αυτόν ...

[virxen75]

πιο γρήγορη λύση από την προηγούμενη,απαιτεί λιγότερη δέσμευση μνήμης

και τα αποτελέσματα είναι τα ίδια και για τις 2 περιπτώσεις!