14.1.4 Ταχύτητα

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

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

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

Προφανώς το πρόβλημα λύνεται με δύο εμφωλευμένα ΑΝ (τρεις έξοδοι).

Οι παρακάτω λύσεις είναι όλες αποδεκτές.

ΑΝ number>0 ΤΟΤΕ θ ΑΛΛΙΩΣ_ΑΝ number ΑΛΛΙΩΣ μ ΤΕΛΟΣ_ΑΝ ΑΝ number ΑΛΛΙΩΣ_ΑΝ number>0 ΤΟΤΕ θ ΑΛΛΙΩΣ μ ΤΕΛΟΣ_ΑΝ ΑΝ number=0 ΤΟΤΕ μ ΑΛΛΙΩΣ_ΑΝ number ΑΛΛΙΩΣ θ ΤΕΛΟΣ_ΑΝ

Ποια θα πρέπει να θεωρήσουμε ταχύτερη λύση;

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

Παράδειγμα 6 Δίνεται πίνακας 1000 κωδικών αριθμών. Ζητείται να σχεδιαστεί πρόγραμμα που θα δέχεται έναν κωδικό από το πληκτρολόγιο, θα τον αναζητά στον πίνακα και θα δίνει τη θέση του πίνακα που βρέθηκε ο κωδικός. Η αναζήτηση σε ένα πίνακα είναι θέμα το οποίο έχει ήδη αναπτυχθεί στο κεφάλαιο 3. Έτσι εδώ δεν θα λύσουμε το πρόβλημα, αλλά θα αναπτύξουμε μία ιδέα για την βελτίωση του χρόνου επεξεργασίας, που μπορεί να χρησιμοποιηθεί σε κάθε περίπτωση. Είτε δηλαδή ο πίνακας είναι ταξινομημένος πίνακας και κάνουμε δυαδική αναζήτηση, είτε είναι μη ταξινομημένος και κάνουμε σειριακή αναζήτηση.

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

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

Έστω ότι έχουμε πενταψήφιους κωδικούς και ένας από αυτούς είναι ο 12345. Ένας τρόπος για την παραγωγή του 6ου ψηφίου είναι ο εξής: Ψ6 =(Ψ1*1+Ψ2*3+Ψ3*5+Ψ4*7+Ψ5*13) mod 11 =(1*1+2*3+3*5+4*7+5*13) mod 11 =(1+6+15+28+65) mod 11 = 5.

Άρα ο κωδικός που θα πληκτρολογείται θα είναι ο 123455. Με τον ίδιο κανόνα το πρόγραμμα θα ελέγχει, μετά την πληκτρολόγηση, αν ο εισαγόμενος 6ψήφιος, πλέον, κωδικός είναι αποδεκτός και μετά θα προχωρά στην αναζήτησή του στον πίνακα των 1000 θέσεων.

Ο κανόνας δημιουργίας του 6ου ψηφίου είναι ο εξής: Πολλαπλασιάζονται όλα τα ψηφία του κωδικού με έναν πρώτο αριθμό, και προστίθονται τα γινόμενα. Το άθροισμα διαιρείται με 11. Το υπόλοιπο της διαίρεσης είναι το ψηφίο ελέγχου. Το υπόλοιπο της διαίρεσης με το 11 είναι από 0 μέχρι 10. Αν βρεθεί υπόλοιπο 10, το 6ο ψηφίο είναι 0.

Υπάρχουν πολλοί τρόποι για τη δημιουργία του ψηφίου ελέγχου με πλεονεκτήματα και μειονεκτήματα.

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

Η μέθοδος εφαρμόζεται στους κωδικούς τραπεζικών λογαριασμών, στον κωδικό ΑΦΜ, στον κωδικό ISBN και γενικά όπου οι κωδικοί πληκτρολογούνται και η αναζήτηση τους πρόκειται να γίνει σε πολύ μεγάλους πίνακες ή αρχεία.