Δημοσιεύτηκε: 05 Μαρ 2012, 12:52
Καλή φάση Κώστα 
(όχι ξεροσφύρι, ξεσκίστηκα στα θαλασσινά )
Κοίταγα πριν τον κώδικα της 2ης λύσης κι έχει bug στην συνάρτηση avail_count().
Η γραμμή...
πρέπει να αλλάξει σε...
Την διόρθωσα και στο ideone.com.
Το γιατί είναι ταχύτερη αυτή η υλοποίηση από την πρώτη το στηρίζω αφενός στο ότι εδώ χρησιμοποιούμε απευθείας το 1ο αποτέλεσμα της rand() και αφετέρου στο ότι ότι κατά μέσο όρο χρησιμοποιούμε μικρότερο όριο στην rand() ... αυτό δεν είμαι σίγουρος αν όντως βελτιώνει την ταχύτητα, διότι δεν ξέρω πως υλοποιείται εσωτερικά η συνάρτηση rand(). Επίσης κάνουμε δραματικά μικρότερο αριθμό συγκρίσεων.
Μέσα στο κεντρικό loop της main() η 1η υλοποίηση κάνει συγκρίσεις α) με το macro ISBLOCKED() β) με τη συνάρτηση: get_nextpos() και γ) στη συνθήκη του φωλιασμένου do-while loop. Επίσης καλεί συνέχεια την rand() μέχρι να βρει διαθέσιμο τετράγωνο
Ας πούμε για παράδειγμα ότι υπάρχουν 2 διαθέσιμα τετράγωνα γειτονικά του τρέχοντος. Με την 1η υλοποίηση η rand() μπορεί κάλλιστα τις πρώτες 10 φορές να "βαρέσει" στα 2 άλλα μη-διαθέσιμα, οπότε θα χρειαστεί να επαναλάβει 11 φορές τόσο τις συγκρίσεις της get_nextpos() όσο και τη σύγκριση της συνθήκης του do-while loop.
Αντίθετα, η 2η υλοποίηση θα κάνει μια και μόνη φορά τις συγκρίσεις της avail_count() και κατόπιν χρησιμοποιήσει την επιστρεφόμενη τιμή της συνάρτησης ως όριο μιας και μόνης κλήσης της rand(). Η 2η υλοποίηση έχει ένα έξτρα overhead το γέμισμα του πίνακα avail[] μέσα στην avail_count(), το οποίο όμως είναι πολύ μικρό τίμημα συγκριτικά με τις τόσο πολύ περισσότερες συγκρίσεις που κάνει η 1η υλοποίηση.
Για επιβεβαίωση/διάψευση πρέπει να συγκρίνουμε τις 2 υλοποιήσεις με κάποιον καλό profiler, ιδανικά με μεγάλους πίνακες, μεγάλα αλφάβητα και πολλές φορές την κάθε υλοποίηση (για να βγει μέσος όρος για την κάθεμια).
(όχι ξεροσφύρι, ξεσκίστηκα στα θαλασσινά )Κοίταγα πριν τον κώδικα της 2ης λύσης κι έχει bug στην συνάρτηση avail_count().
Η γραμμή...
- Μορφοποιημένος Κώδικας: Επιλογή όλων
-
/* is row-dn'ed pos available? */
if ( ROW(pos) < NROWS && ...
πρέπει να αλλάξει σε...
- Μορφοποιημένος Κώδικας: Επιλογή όλων
-
/* is row-dn'ed pos available? */
if ( ROW(pos) < NROWS-1 && ...
Την διόρθωσα και στο ideone.com.
Το γιατί είναι ταχύτερη αυτή η υλοποίηση από την πρώτη το στηρίζω αφενός στο ότι εδώ χρησιμοποιούμε απευθείας το 1ο αποτέλεσμα της rand() και αφετέρου στο ότι ότι κατά μέσο όρο χρησιμοποιούμε μικρότερο όριο στην rand() ... αυτό δεν είμαι σίγουρος αν όντως βελτιώνει την ταχύτητα, διότι δεν ξέρω πως υλοποιείται εσωτερικά η συνάρτηση rand(). Επίσης κάνουμε δραματικά μικρότερο αριθμό συγκρίσεων.
Μέσα στο κεντρικό loop της main() η 1η υλοποίηση κάνει συγκρίσεις α) με το macro ISBLOCKED() β) με τη συνάρτηση: get_nextpos() και γ) στη συνθήκη του φωλιασμένου do-while loop. Επίσης καλεί συνέχεια την rand() μέχρι να βρει διαθέσιμο τετράγωνο
Ας πούμε για παράδειγμα ότι υπάρχουν 2 διαθέσιμα τετράγωνα γειτονικά του τρέχοντος. Με την 1η υλοποίηση η rand() μπορεί κάλλιστα τις πρώτες 10 φορές να "βαρέσει" στα 2 άλλα μη-διαθέσιμα, οπότε θα χρειαστεί να επαναλάβει 11 φορές τόσο τις συγκρίσεις της get_nextpos() όσο και τη σύγκριση της συνθήκης του do-while loop.
Αντίθετα, η 2η υλοποίηση θα κάνει μια και μόνη φορά τις συγκρίσεις της avail_count() και κατόπιν χρησιμοποιήσει την επιστρεφόμενη τιμή της συνάρτησης ως όριο μιας και μόνης κλήσης της rand(). Η 2η υλοποίηση έχει ένα έξτρα overhead το γέμισμα του πίνακα avail[] μέσα στην avail_count(), το οποίο όμως είναι πολύ μικρό τίμημα συγκριτικά με τις τόσο πολύ περισσότερες συγκρίσεις που κάνει η 1η υλοποίηση.
Για επιβεβαίωση/διάψευση πρέπει να συγκρίνουμε τις 2 υλοποιήσεις με κάποιον καλό profiler, ιδανικά με μεγάλους πίνακες, μεγάλα αλφάβητα και πολλές φορές την κάθε υλοποίηση (για να βγει μέσος όρος για την κάθεμια).