Το προφίλ μας στο Google Plus
1

Γνωριμία με τους αλγορίθμους: Δυαδική Αναζήτηση

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

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

  • Πώς κάνουμε μια αναζήτηση πιο γρήγορη και πιο αποτελεσματική;
  • Πώς μπορεί να υπολογίσει ένα GPS τη βέλτιστη διαδρομή προς κάποιον προορισμό;
  • Πώς υλοποιούμε το υποσύστημα Τεχνητής Νοημοσύνης ενός προγράμματος που παίζει σκάκι;

Για κάθε πρόβλημα που έχει ήδη επινοηθεί αλγόριθμος, η ιστορία δεν σταματά εκεί. Οι ερευνητές, βλέπετε, επιθυμούν κι αναλύουν την ταχύτητα των αλγορίθμων. Όπως και να το κάνουμε, είναι ένα πράγμα να γνωρίζουμε κάποιον αλγόριθμο ο οποίος φέρνει αποτελέσματα σε 12 μήνες, κι άλλο να επινοήσουμε αλγόριθμο που για το ίδιο πρόβλημα φέρνει αποτελέσματα σε 2 ώρες. Σε αντίθεση με τους Μαθηματικούς, οι οποίοι μένουν απόλυτα ικανοποιημένοι όταν γνωρίζουν πως ένα πρόβλημα έχει λύση, οι επιστήμονες της Πληροφορικής θέλουν να γνωρίζουν και πόσο γρήγορα φτάνουν σε μια λύση. Οι αναλύσεις και οι συζητήσεις περί ζητημάτων ύπαρξης κι αποδοτικότητας δεν εξαντλούνται, αλλά δεν αποτελούν το κεντρικό θέμα του άρθρου που τώρα διαβάζετε. Προς το παρόν, σημειώνουμε μόνο ότι για την ανάλυση της απόδοσης ή αλλιώς της πολυπλοκότητας των αλγορίθμων, στην επιστήμη της Πληροφορικής χρησιμοποιείται ο συμβολισμός του “big O”. Περισσότερα επ’ αυτού θα πούμε λίγο αργότερα.

Αξίζει να μελετάμε τους αλγορίθμους;
Η απάντηση είναι καταφατική, ασχέτως αν είμαστε επαγγελματίες προγραμματιστές ή ασχολούμαστε με τον προγραμματισμό ως χομπίστες. Σε κάθε περίπτωση, πολλές φορές οφείλουμε να έχουμε κατά νου την έννοια της επίδοσης (performance). Αυτό δεν σημαίνει ότι χρειάζεται ν’ ανακαλύπτουμε ξανά και ξανά τον τροχό, αφού όλοι οι βασικοί αλγόριθμοι είναι γραμμένοι από κάποιους άλλους και μάλιστα σε διάφορες γλώσσες προγραμματισμού. Πρέπει, ωστόσο, να έχουμε την ικανότητα ν’ απαντάμε σε ερωτήματα όπως τα ακόλουθα: Ποιον αλγόριθμο χρειάζομαι για το δεδομένο πρόβλημα; Αξίζει να καταφύγω στο Quick Sort ή να στραφώ στο Merge Sort; Θα πρέπει να χρησιμοποιήσω array ή list; Μόνον όταν είμαστε σε θέση να κατανοούμε τα πλεονεκτήματα και τα μειονεκτήματα των αλγορίθμων, θα επιλέγουμε σωστά αλγορίθμους ή/και δομές δεδομένων.

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

Τι χρειάζεται να ξέρει κανείς για ν’ ασχοληθεί;
Αν ακούτε για αλγορίθμους και τρέχετε μακρυά λόγω των μαθηματικών που βρίσκονται από πίσω, τότε βρίσκεστε στο σωστό μέρος. Για την κατανόηση όσων συζητάμε στο πλαίσιο του παρόντος άρθρου χρειάζονται μόνο βασικές γνώσεις Άλγεβρας και Συναρτήσεων, όπως τις μαθαίνουμε στο Γυμνάσιο. Για παράδειγμα, έστω ότι έχουμε τη συνάρτηση f(x) = 5*x. Αν αμέσως καταλαβαίνετε ότι f(10)=50, τότε άνετα μπορείτε να συνεχίσετε με την ανάγνωση του άρθρου. Επίσης, καλό θα ήταν να γνωρίζει κανείς μία γλώσσα προγραμματισμού. Ξεκινάτε τώρα και δεν μπορείτε ν’ αποφασίσετε με ποια πρέπει να καταπιαστείτε; Σας προτείνουμε την Python, καθώς αποτελεί εξαίσια επιλογή για αρχαρίους. Και τώρα που γνωρίζετε τα εφόδια που πρέπει να έχετε, μπορείτε να συνεχίσετε ακάθεκτοι με το υπόλοιπο του άρθρου. Σε λίγο θα υλοποιήσουμε τον πρώτο μας αλγόριθμο, ο οποίος ακούει στο όνομα binary search.

Δυαδική Αναζήτηση
Θυμόσαστε τους παλιούς τηλεφωνικούς καταλόγους; Ναι, εκείνο το μεγάλο χοντρό βιβλίο που μας μοίραζαν κάθε χρονιά στην είσοδο της πολυκατοικίας, κι έγραφε πάνω του “Χρυσός Οδηγός”. Φανταστείτε τώρα ότι δεν έχετε Internet και χρειάζεται να καταφύγετε σ’ αυτό το βιβλίο, ώστε να βρείτε το τηλέφωνο μιας συγκεκριμένης επιχείρησης το όνομα της οποίας αρχίζει από το γράμμα “Π”. Σαφώς, μπορεί κανείς να ξεκινήσει και να ξεφυλλίζει από την αρχή, μέχρι να φτάσει στο “Π”. Νομίζουμε ωστόσο ότι οι περισσότεροι θ’ άνοιγαν τυχαία τον τηλεφωνικό κατάλογο, κάπου στη μέση, καθώς το “Π” βρίσκεται στη μέση περίπου του αλφάβητου.

Όσοι δεν είχατε τη χαρά να χρησιμοποιήσετε το Χρυσό Οδηγό, μάλλον είχατε παρόμοια εμπειρία με κάποιο έντυπο λεξικό. Ας υποθέσουμε ότι κάποιος ψάχνει μια λέξη στ’ αγγλικά, η οποία αρχίζει από το γράμμα “O”. Ξανά, υποθέτουμε ότι ο περισσότερος κόσμος θ’ άνοιγε το λεξικό περίπου στη μέση. Στη συνέχεια θα ξεφύλλιζε μπρος-πίσω, έως ότου βρει το “Ο” και μετά τη λέξη που ψάχνει.

Αρκετά όμως με το παρελθόν και με τις ξεπερασμένες μεθόδους αναζήτησης. Επιστροφή στο σήμερα, όπου έχετε ανοίξει τον web browser και είστε έτοιμοι να κάνετε login στο Facebook. Πληκτρολογείτε, λοιπόν, τα στοιχεία σας κι αμέσως μετά κάνετε κλικ στο κουμπί “login”. Εκείνη τη στιγμή, το Facebook καλείται να πιστοποιήσει ότι όντως υπάρχει ένας τέτοιος λογαριασμός, δηλαδή ένας λογαριασμός με τα στοιχεία που μόλις πληκτρολογήσατε. Πώς το κάνει αυτό; Το Facebook πρέπει ν’ ανοίξει τη βάση δεδομένων με τους χρήστες του και να ψάξει σ’ αυτή. Όταν λέμε “βάση δεδομένων”, σκεφτείτε κάτι που μοιάζει με τον τηλεφωνικό κατάλογο. Μόνο που αντί για ονόματα έχει usernames, κι αντί για τηλέφωνα έχει passwords. Η δουλειά του Facebook είναι να εντοπίσει, μέσα σ’ αυτό το “βιβλίο”, το username και το password σας. Ας υποθέσουμε λοιπόν ότι το username σας είναι το obi-wan (https://en.wikipedia.org/wiki/Obi-Wan_Kenobi). Τίθεται το ερώτημα: Θα ξεκινήσει το Facebook να ψάχνει από το “Α” ή θα αρχίσει από κάπου στη μέση;

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

Ο αλγόριθμος του binary search επιδρά πάντα επί μιας ταξινομημένης λίστας στοιχείων. Ή, αλλιώς, λέμε ότι ο αλγόριθμος δέχεται στην είσοδό του μια ταξινομημένη λίστα. Ένα λεξικό, για παράδειγμα, είναι ταξινομημένο αλφαβητικά ως προς το επίθετο, επομένως επί του λεξικού είναι δυνατό να χρησιμοποιήσουμε τον αλγόριθμο του binary search. Αν το στοιχείο που αναζητάμε υπάρχει στη λίστα, τότε ο αλγόριθμος επιστρέφει τη θέση του στοιχείου. Αν πάλι το στοιχείο που αναζητάμε δεν υπάρχει στη λίστα, ο αλγόριθμος δεν επιστρέφει κάτι (ή επιστρέφει το “τίποτα”, NULL).

Για παράδειγμα, έστω ότι ψάχνουμε στον τηλεφωνικό κατάλογο την εταιρεία Parabing Creations. Αν επιστρατεύαμε τον binary search κι εκείνος την έβρισκε, θα μας έλεγε ότι το υπό αναζήτηση στοιχείο (Parabing Creations) βρίσκεται στη θέση τάδε (π.χ., 4424) του τηλεφωνικού καταλόγου. Αν η Parabing Creations δεν υπήρχε στον κατάλογο, τότε ο αλγόριθμος θα μας επέστρεφε το NULL (δηλαδή το “τίποτα”).

Πώς λειτουργεί η δυαδική αναζήτηση;
Αφού είδαμε το πρόβλημα που λύνει ο αλγόριθμος της δυαδικής αναζήτησης, τώρα ήρθε η στιγμή να δούμε και τη λογική πίσω από τη λύση. Αν φαντάζεστε ότι χρειάζονται τρομακτικά μαθηματικά, σίγουρα θα εκπλαγείτε με την απλότητα του όλου ζητήματος. Ας χρησιμοποιήσουμε ένα συγκεκριμένο παράδειγμα, έτσι, για να καταλάβουμε καλύτερα. Βάζουμε ένα νούμερο στο μυαλό μας, από το 1 μέχρι το 100. Τα επόμενα κουτάκια έχουν όλα τα νούμερα, από το 1 έως το 100, ταξινομημένα κατ’ αύξουσα σειρά:

Αναζήτηση εντός λίστας 100 στοιχείων

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

Αναγνώστης: Είναι το 1;
deltaHacker: Όχι, το 1 είναι μικρότερο από τον αριθμό μας.

Σειραϊκή αναζήτηση, προσπάθεια 1

Αναγνώστης: OK. Είναι μήπως το 2;
deltaHacker: Όχι, το 2 είναι μικρότερο από τον αριθμό μας.

Σειραϊκή αναζήτηση, προσπάθεια 2

…..

Αναγνώστης: Βρε ‘σείς, το 96 είναι;!
deltaHacker: Μπα που να μη σώναμε, όχι, το 96 είναι μικρότερο από τον αριθμό μας.

Σειραϊκή αναζήτηση, προσπάθεια 96

Τα παραπάνω λοιπόν αποτελούν μια πολύ συγκεκριμένη προσέγγιση στη λύση του προβλήματος της αναζήτησης. Θα συμφωνήσετε, φανταζόμαστε, ότι αυτή η σειραϊκή μέθοδος είναι εξαιρετικά αργή. Και είναι εξαιρετικά αργή γιατί μετά από κάθε λάθος προσπάθεια, ένα και μόνο ένα στοιχείο αφαιρείται από τη λίστα. Αν λοιπόν η λίστα έχει k το πλήθος στοιχεία, τότε στη χειρότερη περίπτωση χρειάζονται k το πλήθος προσπάθειες έως ότου εντοπίσουμε το επιθυμητό στοιχείο (ή έως ότου βεβαιωθούμε ότι δεν υπάρχει στη λίστα).

Ας δούμε μια καλύτερη προσέγγιση. Θυμηθείτε τι κάναμε στα παραδείγματα με τον τηλεφωνικό κατάλογο και το λεξικό: την αναζήτηση δεν την ξεκινούσαμε από την αρχή ή από το τέλος, αλλά από τη μέση. Σκεφτόμαστε λοιπόν έναν άλλον αριθμό μεταξύ 1 και 100, σας ζητάμε να τον μαντέψετε, εσείς δεχόσαστε. Μόνο που τώρα δεν εφαρμόζετε τη σειραϊκή μέθοδο, αλλά μία άλλη που παραπέμπει στο “διαίρει και βασίλευε”.

Αναγνώστης: Είναι το 50;
deltaHacker: (Ώπα!) Εχμ, όχι, μικρό είναι το 50.

Δυαδική αναζήτηση (λογική 'διαίρει και βασίλευε')

Είναι εντυπωσιακό, αλλά με μία μόνο αποτυχημένη προσπάθεια πετάξατε τη μισή λίστα. Ξεχνάτε λοιπόν τα στοιχεία μεταξύ 1 και 50 κι εστιάζετε την προσοχή σας στη λίστα με τα στοιχεία από το 51 έως το 100 — ή τουλάχιστον αυτό θα κάναμε εμείς, αν ήμασταν στη θέση σας.

Αναγνώστης: Μήπως είναι το 75;
deltaHacker: (Νταρν ιτ, χι μαστ μπι όντου σάμθινγκ.) Ε, όχι, όχι, μεγάλο είναι το 75.

Και πάλι δεν μαντέψατε τον αριθμό, αλλά τουλάχιστον ξεμπερδέψατε με το (δεύτερο) μισό του (δεύτερου) μισού που απέμεινε από την πρώτη προσπάθεια. Η επόμενη στάση σας είναι περισσότερο από αναμενόμενη. Η μέση μεταξύ 51 και 75 είναι το 63:

Αναγνώστης: Ελάτε, πείτε, το 63 είναι;
deltaHacker: Όχι, μεγάλο είναι το 63…

Έχει μείνει η λίστα με τα στοιχεία από το 51 έως και το 62, η μέση είναι το 57, οπότε ρωτάτε:

Αναγνώστης: Το 57 είναι;
deltaHacker: Ναι μωρέ, το 57 είναι, σπουδαίο κατόρθωμα — μπιγκ γουπ!

Κι αυτό, κυρίες και κύριοι, ήταν ο αλγόριθμος της δυαδικής αναζήτησης. Ναι, μόλις γνωρίσατε τον πρώτο σας αλγόριθμο, ο οποίος μάλιστα είναι και ιδιαίτερα αποδοτικός. Νομίζουμε ότι έχει ενδιαφέρον να δούμε πόσους αριθμούς αποκλείουμε σε κάθε βήμα μέχρι να μαντέψουμε τον αριθμό, λαμβάνοντας υπόψη τη χειρότερη περίπτωση. Στο πλαίσιο του παραδείγματός μας, μιλώντας για “χειρότερη περίπτωση” εννοούμε ότι βρίσκουμε τον αριθμό κάνοντας το μέγιστο δυνατό αριθμό προσπαθειών.

Πλήθος στοιχείων: 100
Προσπάθεια 1: αποκλείουμε 50 στοιχεία
Προσπάθεια 2: αποκλείουμε 25 στοιχεία
Προσπάθεια 3: αποκλείουμε 13 στοιχεία
Προσπάθεια 4: αποκλείουμε 7 στοιχεία
Προσπάθεια 5: αποκλείουμε 4 στοιχεία
Προσπάθεια 6: αποκλείουμε 2 στοιχεία
Προσπάθεια 7: αποκλείουμε 1 στοιχείο

Καταλαβαίνουμε, λοιπόν, ότι οποιονδήποτε αριθμό μεταξύ 1 και 100 προσπαθήσουμε να μαντέψουμε, θα τον βρούμε με επτά το πολύ προσπάθειες. Ας υποθέσουμε τώρα ότι ψάχνουμε τη θέση μιας συγκεκριμένης λέξης, μέσα σε ένα λεξικό με 200.000 λέξεις. Βάζοντας λοιπόν μια λέξη κατά νου, πόσες προσπάθειες θα χρειαστούμε στο χειρότερο δυνατό σενάριο πριν βρούμε τη θέση της στο λεξικό; Δείτε:

Πλήθος στοιχείων: 200.000
Προσπάθεια 1: αποκλείουμε 100.000 στοιχεία
Προσπάθεια 2: αποκλείουμε 50.000 στοιχεία
Προσπάθεια 3: αποκλείουμε 25.000 στοιχεία
Προσπάθεια 4: αποκλείουμε 12.500 στοιχεία
Προσπάθεια 5: αποκλείουμε 6.250 στοιχεία

Προσπάθεια 14: αποκλείουμε 13 στοιχεία
Προσπάθεια 15: αποκλείουμε 7 στοιχεία
Προσπάθεια 16: αποκλείουμε 4 στοιχεία
Προσπάθεια 17: αποκλείουμε 2 στοιχεία
Προσπάθεια 18: αποκλείουμε 1 στοιχείο

(Αν σε μία δεδομένη στιγμή έχουμε k το πλήθος στοιχεία, στην επόμενη προσπάθεια μένουν [k/2] το πλήθος στοιχεία. Με τα άγκιστρα εννοούμε ότι αν το αποτέλεσμα της διαίρεσης k/2 είναι δεκαδικός αριθμός, τότε παίρνουμε τον πλησιέστερο μεγαλύτερο ακέραιο. Παράδειγμα: Επειδή 13/2 = 6,5 (δεκαδικός αριθμός), ισχύει [13/2] = 7.

Χρησιμοποιώντας τη μέθοδο του binary search, λοιπόν, ψάχνοντας μια δεδομένη λέξη μέσα σε ένα λεξικό 200.000 λέξεων, βρίσκουμε τη θέση της –ή διαπιστώνουμε ότι δεν υπάρχει στο λεξικό–, με 18 προσπάθειες στη χειρότερη περίπτωση. Μιλάμε για τρομακτική βελτίωση σε σχέση με τη σειραϊκή αναζήτηση, η οποία στη χειρότερη περίπτωση θα έπαιρνε 200.000 προσπάθειες.

Γενικά, σε κάθε λίστα με k στο πλήθος στοιχεία, η δυαδική αναζήτηση χρειάζεται log2(k) το πλήθος βήματα πριν δώσει αποτέλεσμα — και πάντα στη χειρότερη περίπτωση.

Λογάριθμοι
Ως μαθητές σχεδόν πάντα ξεχνούσαμε την έννοια του λογαρίθμου, αλλά σχεδόν πάντα θυμόμασταν την έννοια των δυνάμεων. Όταν λοιπόν κάποιος σας ζητά να του πείτε το αποτέλεσμα του log10(100), αυτό που πραγματικά σας ρωτάει είναι: πόσα 10άρια πρέπει να πολλαπλασιάσω μεταξύ τους, έτσι ώστε όλα μαζί να δώσουν 100; Η απάντηση είναι 2, διότι 10 x 10 = 100. Ισχύει, λοιπόν, log10(100) = 2. Οι λογάριθμοι και οι δυνάμεις, είναι έννοιες που συνδέονται στενά. Γενικά, ισχύει:

x^y = z όταν και μόνον όταν logx(z) = y

Φαίνεται παράξενο ή δυσνόητο; Κάντε μερικές δοκιμαστικές αναθέσεις για τα x και y (το z είναι το αποτέλσμα του x εις την y) και δείτε μόνοι σας. Παράδειγμα: για x = 2 και y = 3, έχουμε 2^3 = 8 διότι log2(8) = 3. Επίσης: για x = 2 και y = 4, έχουμε 2^4 = 16 διότι log2(16) = 4.

Να σημειώσουμε εδώ ότι, μελετώντας τη βιβλιογραφία, θα διαπιστώνετε ότι αντί για log2(x) συχνά γράφεται logx. Η βάση 2, μ’ άλλα λόγια, συχνά υπονοείται και συνεπώς παραλείπεται. Διαφορετικά: Όταν κάποιος συγγραφέας γράφει logx, είναι πιθανό να εννοεί το δυαδικό λογάριθμο του x. (Σ.τ.Ε. Στη Μαθηματική και υπόλοιπη βιβλιογραφία, βέβαια, είθισται με logx να συμβολίζουμε το δεκαδικό λογάριθμο log10(x). Η διευκρίνιση κρίνεται απαραίτητη, ώστε να μη σας δημιουργήσουμε άθελά μας σύγχυση ως προς τους διαφορετικούς συμβολισμούς.)

Για το τέλος αυτής της σημείωσης, σας έχουμε ένα ερώτημα — ή μάλλον πρόκληση: Μπορείτε ν’ αποδείξετε *διαισθητικά* γιατί η δυαδική αναζήτηση μέσα σε μια λίστα k στοιχείων χρειάζεται log2(k) προσπάθειες στη χειρότερη περίπτωση; Τα όποια σχόλιά σας μπορείτε να τ’ αφήσετε στο site του περιοδικού, κάτω από τη σχετική δημοσίευση.

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

Για τη συγγραφή του κώδικα κάνουμε χρήση των arrays. Όσοι δεν είστε γνώστες της προαναφερθείσας δομής, μην ανησυχείτε. Αρκεί να γνωρίζετε ότι μπορείτε να αποθηκεύσετε μία ακολουθία στοιχείων σε μία σειρά από κουτάκια, την οποία σειρά ονομάζουμε array ή αλλιώς πίνακα. Η αρίθμηση των κουτιών του πίνακα ξεκινά από το μηδέν (0). Βλέπετε, σε αντίθεση με τους φυσιολογικούς ανθρώπους, οι προγραμματιστές ξεκινούν να μετράνε πάντα από το 0 κι όχι από το 1. Οπότε το πρώτο στοιχείο του πίνακα θα βρίσκεται στην θέση (κουτάκι) 0, το δεύτερο στοιχείο στην θέση 1, το τρίτο στοιχείο στη θέση 2 και γενικά το n-οστό στοιχείο στη θέση (n-1).

Ως δεδομένα εισόδου, ο αλγόριθμος binary search χρειάζεται δύο πράγματα από εμάς προκειμένου να λειτουργήσει:

  1. μια ταξινομημένη λίστα στοιχείων
  2. ένα στοιχείο, τη θέση του οποίου θα αναζητήσει εντός της ταξινομημένης λίστας.

Το αποτέλεσμα του αλγορίθμου, δηλαδή η έξοδός του, είναι είτε η θέση του υπό αναζήτηση στοιχείου στη λίστα (αν το στοιχείο υπάρχει) είτε το None (αν το στοιχείο δεν υπάρχει). Ο κώδικας που παραθέτουμε υλοποιεί τον αλγόριθμο της δυαδικής αναζήτης.

#!/usr/bin/python

def binary_search(list, guess):
  left = 0
  right = len(list) - 1
  while left <= right:
    mid = (left + right) / 2
    item = list[mid]
    if item == guess:
      return mid
    if item > guess:
      right = mid - 1
    else:
      left = mid + 1
  return None

theList = [1, 2, 5, 7, 11, 129, 49250]
print binary_search(theList, 5)
print binary_search(theList, 314)

Νομίζουμε ότι ο κώδικας δεν χρειάζεται επεξήγηση: ένα από τα καλά της Python είναι ότι “διαβάζεται” εύκολα, ακόμη κι από κάποιον που πρώτη φορά καταπιάνεται μαζί της. Υπάρχουν άλλωστε και τα σχόλια, τα οποία επίσης βοηθούν. Σας προτείνουμε να τον πληκτρολογήσετε και να τρέξετε το αντίστοιχο προγραμματάκι. Κάντε αν είναι κι αλλαγές, ειδικά στις τρεις τελευταίες γραμμές. Συγκεκριμένα, στην 3η από το τέλος γραμμή ορίζουμε τη λίστα επί της οποίας γίνονται οι αναζητήσεις. Στην προτελευταία γραμμή κάνουμε μια δοκιμαστική αναζήτηση για το στοιχείο 5. Το αποτέλεσμα θα είναι η θέση 2 (όπως τη βλέπει η Python) ή διαφορετικά η 3 (όπως τη μετράμε ξεκινώντας από τ’ αριστερά της λίστας). Στην τελευταία γραμμή κάνουμε άλλη μια δοκιμαστική αναζήτηση, αυτή τη φορά για το στοιχείο 314. Τώρα το αποτέλεσμα είναι None, αφού το 314 δεν υπάρχει στη λίστα. Και μια τελευταία παρατήρηση: Κάτω από το while, εκεί που υπολογίζεται το μέσο της λίστας με τη διαίρεση (left + right) / 2, έχετε υπόψη ότι, αν χρειάζεται, η Python στρογγυλοποιεί το αποτέλεσμα στον πλησιέστερο ακέραιο από πάνω.

Ο χρόνος τρέχει
Για ένα δεδομένο πρόβλημα το πιθανότερο είναι να υπάρχουν περισσότερες από μία γνωστές λύσεις, μ’ άλλα λόγια περισσότεροι από ένας γνωστοί αλγόριθμοι. Η επιλογή του κατάλληλου αλγορίθμου δεν είναι πάντα εύκολη υπόθεση, αφού εξαρτάται από τη φύση του προβλήματος, τα δεδομένα εισόδου, τις απαιτήσεις σε χώρο και χρόνο κ.ο.κ. Ένα από τα πλέον σημαντικά κριτήρια για την επιλογή αλγορίθμου είναι ο χρόνος εκτέλεσης (running time).

Ας πάρουμε όμως τα πράγματα από την αρχή. Όπως είδαμε στο παράδειγμα της σειραϊκής αναζήτησης, ελέγχοντας εξαντλητικά ένα προς ένα τα στοιχεία μιας λίστας, για 100 στοιχεία χρειαζόμαστε το πολύ 100 προσπάθειες. Ομοίως, για 10 δισεκατομμύρια στοιχεία χρειαζόμαστε το πολύ 10 δισεκατομμύρια προσπάθειες κ.ο.κ. Σε κάθε περίπτωση, είναι προφανές ότι μιλάμε για τη χειρότερη περίπτωση: το στοιχείο που ψάχνουμε είτε είναι στο τέλος της λίστας, είτε δεν υπάρχει καν στη λίστα. Η σειραϊκή αναζήτηση, λένε Μαθηματικοί κι Επιστήμονες της Πληροφορικής, αποτελεί ένα παράδειγμα αλγορίθμου γραμμικού χρόνου (linear time algorithm). Προφανώς, το κακό με τους αλγορίθμους γραμμικού χρόνου είναι ότι διαρκούν όλο και πιο πολύ, όσο το πλήθος των στοιχείων που πρέπει να ελέγχουν αυξάνει. Αν σας φαίνεται κακή η απόδοσή τους, σας λέμε ότι έχετε δίκιο: είναι πράγματι κακή. Υπάρχουν όμως και χειρότερα, όπως, π.χ., αλγόριθμοι τετραγωγικού χρόνου, όπου ο χρόνος ολοκλήρωσης για τη χειρότερη περίπτωση είναι ανάλογος του τετραγώνου του πλήθους των δεδομένων εισόδου. Αλλά ας μην προτρέχουμε.

Τα πράγματα είναι εντελώς διαφορετικά με τον αλγόριθμο του binary search. Είδαμε πως για μία λίστα 100 στοιχείων, χρειαζόμαστε 7 το πολύ προσπάθειες (τουλάχιστον 14 φορές πιο γρήγορος από τη σειραϊκή αναζήτηση, στη χειρότερη περίπτωση). Αν είχαμε 10 δισεκατομμύρια στοιχεία, θα χρειαζόμασταν 33 το πολύ προσπάθειες (τουλάχιστον 303 εκατομμύρια φορές πιο γρήγορος από τη σειραϊκή αναζήτηση, στη χειρότερη περίπτωση). Καταλαβαίνετε για τι διαφορά μιλάμε, έτσι δεν είναι; Σίγουρα το καταλαβαίνετε — και μόλις τώρα σας εξηγήσαμε την έννοια του λογαριθμικού χρόνου (logarithmic time).

Σύγκριση Σειραϊκής και Δυαδικής Αναζήτησης

Μπιγκ Όου!
Ο συμβολισμός big O, τον οποίο σιωπηρά εισαγάγαμε στην τελευταία γραμμή του προηγούμενου πίνακα, χρησιμοποιείται κατά κόρον στο πλαίσιο της βιβλιογραφίας των αλγορίθμων κι εκφράζει ένα από τα πιο σημαντικά πράγματα που απασχολούν –ή θα τουλάχιστον θα έπρεπε ν’ απασχολούν– κάθε προγραμματιστή: την ταχύτητα ενός αλγορίθμου. Αν λοιπόν πρόκειται να χρησιμοποιήσετε τον αλγόριθμο κάποιου άλλου προγραμματιστή, χρήσιμο θα ήταν να γνωρίζετε την ταχύτητά του. Έτσι, θα είστε σε θέση να τον συγκρίνετε με άλλους, γνωστούς ή άγνωστους αλγορίθμους και τελικά να επιλέξετε τον γρηγορότερο.

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

Ο κος Ντεβελοπερόπουλος αρχίζει να σκέφτεται για τον αλγόριθμο που θα πρέπει να υλοποιήσει. Προσπαθεί ν’ αποφασίσει μεταξύ της σειραϊκής αναζήτησης και της δυαδικής. Γνωρίζει, προφανώς, ότι η δυαδική αναζήτηση είναι πολύ πιο γρήγορη, ωστόσο ο κώδικας για την υλοποίηση θα είναι αρκετά πιο πολύπλοκος και πιθανώς να έχει bugs. Ο κος Ντεβελοπερόπουλος μόλις έπιασε δουλειά, οπότε το τελευταίο πράγμα που θα ήθελε στον κώδικά του είναι τα bugs. Σκέφτεται, λοιπόν, ότι ίσως πρέπει να υλοποιήσει μια απλή σειραϊκή αναζήτηση, αφού σ’ αυτή την περίπτωση η πιθανότητα για bugs είναι σαφώς μικρότερη.

Ο φίλος μας αποφασίζει να χρονομετρήσει, κατά κάποιον τρόπο, τους δύο αλγορίθμους. Γνωρίζει ότι το hardware που θα φιλοξενήσει τον κώδικά του χρειάζεται ένα χιλιοστό του δευτερολέπτου (1ms) για κάθε προσπάθεια. Για 100 στοιχεία, λοιπόν, με τη σειραϊκή αναζήτηση θα χρειαστούν 100ms και με τη δυαδική 7ms. Εντάξει, η δυαδική είναι πολύ πιο γρήγορη από τη σειραϊκή –για την ακρίβεια είναι 100/7 ή περίπου 15 φορές πιο γρήγορη–, όμως σε κάθε περίπτωση το πρόγραμμα επιστρέφει απάντηση εντός του επιτρεπτού χρονικού διαστήματος (10sec).

“Εδώ που τα λέμε βέβαια”, σκέφτεται ο κος Ντεβελοπερόπουλος, “σιγά μην έχω λίστα 100 στοιχείων. Κοτζάμ ι-ες-έι είν’ αυτή, οπότε για να ‘μαι μέσα ας λάβω υπόψη λίστα με ένα δισεκατομμύρια στοιχεία”. Αυτή τη φορά –κι επειδή τον γοητεύουν κάπως οι λογάριθμοι– υπολογίζει απευθείας το δυαδικό λογάριθμο του 1.000.000.000 και τον βρίσκει περίπου ίσο προς 32. Ώστε για ένα δις στοιχεία, το binary search χρειάζεται 32ms και η σειραϊκή αναζήτηση, που όπως υπολόγισε προηγουμένως είναι 15 φορές πιο αργή, θα χρειάζεται 32 x 15 = 480ms. “Μάλιστα. Ωραία. Ακόμη και με τόσα πολλά στοιχεία πάλι μένω εντός του χρονικού ορίου, άσχετα αν χρησιμοποιήσω binary search ή απλή, σειραϊκή αναζήτηση”.

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

Οι υπολογισμοί που *έπρεπε* να είχε κάνει ο κος Ντεβελοπερόπουλος

Για 1 δις στοιχεία η σειραϊκή αναζήτηση χρειάζεται 1 δις χιλιοστά του δευτερολέπτου, δηλαδή 1 εκατομμύριο δευτερόλεπτα ή αλλιώς εντεκάμιση περίπου μέρες! Γιατί όμως έκανε αυτό το λάθος ο φίλος μας; Πολύ απλά, διότι ο ρυθμός μεταβολής (επιτάχυνση) του χρόνου ολοκλήρωσης που παρατηρείται σε καθέναν από τους δύο αλγορίθμους, είναι διαφορετικός. Το λέμε κι αλλιώς: Ο γραμμικός χρόνος της σειραϊκής αναζήτησης αυξάνει γρηγορότερα σε σχέση με το λογαριθμικό χρόνο της δυαδικής αναζήτησης. Ακριβώς γι’ αυτό δεν δικαιούμαστε να βρούμε το λόγο τον χρόνων, π.χ., για 100 στοιχεία, και τον ίδιο λόγο να χρησιμοποιήσουμε και για τα 1 δις στοιχεία.

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

Γράφοντας, π.x., ότι ένας αλγόριθμος είναι O(n), εννοούμε ότι στη χειρότερη περίπτωση χρειάζεται χρόνο ανάλογο του πλήθους των στοιχείων επί των οποίων εφαρμόζεται. Άλλο παράδειγμα: Αν ένας αλγόριθμος είναι O(n2), τότε στη χειρότερη περίπτωση χρειάζεται χρόνο ανάλογο του τετραγώνου του πλήθους των στοιχείων επί των οποίων εφαρμόζεται. Από μια απλή γραφική παράσταση των συναρτήσεων f(x)=x και g(x)=x2 (χρησιμοποιήστε το WolframAlpha), βλέπουμε ότι η g μεγαλώνει πολύ πιο γρήγορα σε σχέση με την f (για x > 1). Έτσι, καταλαβαίνουμε ότι ένας αλγόριθμος O(n2) είναι πιο αργός σε σχέση με έναν αλγόριθμο O(n).

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

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

Καλή σας διασκέδαση!

One Response to “Γνωριμία με τους αλγορίθμους: Δυαδική Αναζήτηση”

  1. csts | 31/12/2016 at 05:33

    Ωραίο άρθρο!!!

    Μπορείτε ν’ αποδείξετε *διαισθητικά* γιατί η δυαδική αναζήτηση μέσα σε μια λίστα k στοιχείων χρειάζεται log2(k) προσπάθειες στη χειρότερη περίπτωση;

    Μήπως επειδή κάθε φορά τεμαχίζει στα δυο το κάθε νέο k σύνολο;

    οπότε είναι αντιστρόφως ανάλογο του τετραγώνου του πλήθους ;

Leave a Reply

You must be logged in to post a comment.

Σύνδεση

Αρχείο δημοσιεύσεων