Μιλήσαμε σήμερα κάπως γενικά την πρώτη ώρα για το πώς μετράμε την αποδοτικότητα (ταχύτητα κυρίως) ενός αλγορίθμου για τη λύση ενός προβλήματος. Είδαμε ότι συνήθως μετράμε το χρόνο που κάνει να τρέξει ο αλγόριθμος (στη χειρότερη περίπτωση) ως συνάρτηση του μεγέθους της εισόδου. Το μέγεθος της εισόδου είναι ουσιαστικά το πόσο χώρο μας παίρνει στη μνήμη του υπολογιστή για να κρατήσουμε την είσοδο του αλγορίθμου.
Αν έχουμε μια λίστα ακεραίων μήκους N και θέλουμε να βρούμε αν κάποιος ακέραιος x είναι μέσα, και πού είναι αν είναι, τότε, αν η λίστα μας δεν είναι διατεταγμένη σε αύξουσα ή φθίνουσα σειρά αλλά τα διάφορα στοιχεία της μπορούν να είναι βαλμένα μέσα με οποιοδήποτε τρόπο, τότε είμαστε ουσιαστικά περιορισμένοι να εξετάσουμε όλα τα στοιχεία της λίστας αυτής, ένα προς ένα, π.χ. κινούμενοι από την αρχή ως το τέλος, για να βρούμε το x ή να αποφανθούμε ότι δεν είναι μέσα στη λίστα. Αυτή διαδικασία, την οποία ονομάζουμε γραμμικό ψάξιμο μπορεί να πάρει μέχρι και χρόνο N για να τελειώσει (π.χ. τόσο παίρνει όταν το x δεν είναι μέσα στη λίστα).
Αν όμως γνωρίζουμε εξ αρχής ότι η λίστα μας είναι διατεταγμένη, π.χ. σε αύξουσα σειρά, τότε μπορούμε να την ψάξουμε πιο αποτελεσματικά, με το λεγόμενο δυαδικό ψάξιμο (binary search). Για να βρούμε μια θέση του x στη λίστα L (μπορεί να είναι και σε περισσότερες από μία θέσεις, αλλά εμείς θα αρκεστούμε να βρούμε μια, οποιαδήποτε, από αυτές) ή για να αποφανθούμε ότι το x δεν ανήκει στα στοιχεία της L, κοιτάμε πρώτα το στοιχείο στο μέσο της λίστας (ή περίπου στο μέσο της λίστας μια και το N μπορεί να είναι είτε περιττό είτε άρτιο) και το συγκρίνουμε με το x.
Αν είναι ίσο με το x έχουμε τελειώσει αφού έχουμε βρεί μια θέση του x στην L και απιστρέφουμε αυτή τη θέση. Αλλιώς, αν το στοιχείο στο μέσο της L είναι μεγαλύτερο του x τότε είμαστε σίγουροι ότι το x, αν είναι μέσα στην L, θα είναι στο πρώτο μισό της L. Σε αυτή την περίπτωση επαναλαμβάνουμε την ίδια διαδικασία αλλά περιορίζοντας την προσοχή μας στο αριστερό μισό της L. Αν πάλι το στοιχείο στο μέσο της L είναι μικρότερο του x τότε καταλαβαίνουμε ότι το x θα είναι στο δεύτερο μισό της L, αν είναι στην L, και επαναλαμβάνουμε την ίδια διαδικασία με το δεξί μισό της L.
Αυτή την επανάληψη τη σταματάμε αν το μήκος της λίστας είναι μικρό, π.χ. 10, και σε αυτή την περίπτωση απλά ψάχνουμε τα στοιχεία αυτής της μικρής λίστας ένα προς ένα (γραμμικό ψάξιμο).
Είναι φανερό ότι το μήκος της λίστας την οποία ψάχνουμε κάθε φορά υποδιαιρείται διά 2, έως ότου γίνει \(\le 10\). Αν το αρχικό μήκος της λίστας είναι \(N\) τότε παίρνει το πολύ \[ \log_2N \] επαναλήψεις μέχρι να σταματήσει αυτή η διαδικασία, και άρα αυτός είναι ο χρόνος που παίρνει το δυαδικό ψάξιμο στη χειρότερη περίπτωση. Αυτό ο χρόνος είναι πολύ μικρότερος από \(N\) που είναι ο χρόνος που παίρνει το γραμμικό ψάξιμο στη χειρότερη περίπτωση. Αν π.χ. \(N=2^{10}=1024\) τότε \(\log_2N =10\).
Στο παρακάτω πρόγραμμα συγκρίνουμε το χρόνο που παίρνει το γραμμικό με το δυαδικό ψάξιμο μιας λίστας και βλέπουμε ότι το δυαδικό ψάξιμο είναι δραματικά γρηγορότερο (για μεγάλες λίστες).
import random
import time
def linsearch(x, L):
"""Γραμμικό ψάξιμο της L για να βρούμε το x. Επιστρέφει μια θέση του x, ή -1 αν δεν υπάρχει."""
for i in range(len(L)): # Διανύουμε τη λίστα από την αρχή μέχρι να βρούμε το x ή να τελειώσουν τα στοιχεία της
if L[i]==x:
return i # Αν βρούμε το x επιστρέφουμε τη θέση του
return -1 # Αν δεν το έχουμε βρει επιστρέφουμε -1
def binsearch(x, L):
""" Δυαδικό ψάξιμο του ακεραίου x στην ταξινομημένη σε αύξουσα σειρά λίστα ακεραίων L.
Επιστρέφει μια θέση του x, ή -1 αν δεν υπάρχει. """
N = len(L)
# Κάθε φορά ψάχνουμε τη λίστα L από τη θέση low έως τη θέση high
# Συγκρίνουμε με το μέσο αυτού του κομματιού της λίστας και ανάλογα με το αν θέλουμε να περιοριστούμε
# στο αριστερό ή το δεξί μισό της λίστας μετακινούμε μόνο το high ή μόνο το low.
low = 0
high = N-1
while high >= low+10:
m = (low+high)/2 # Το μέσο της λίστας
y = L[m] # Η τιμή στο μέσο της λίστας
if x == y:
return m # Το βρήκαμε
if x<y: # περιοριζόμαστε στο αριστερό μισό
high = m
else: # περιοριζόμαστε στο δεξί μισό
low = m
# Αν η λίστα είναι μικρή την ψάχνουμε σειριακά
for i in range(low, high+1):
if L[i] == x:
return i
# Αφού φτάσαμε ως εδώ δεν το έχουμε βρει και άρα επιστρέφουμε -1
return -1
# Εδώ, για να δοκιμάσουμε τις παραπάνω δύο μεθόδους αναζήτησης, δημιουργούμε μια λίστα N ακεραίων
# που τα στοιχεία της είναι τυχαίο ακέραιοι από το διάστημα 0 .. 100*Ν
l = []
N = 100000
for i in range(N):
l.append(random.randint(1, 100*N))
# Ταξινομούμε τη λίστα σε αύξουσα σειρά
l.sort()
x = 100*N+1 # Αυτό το στοιχείο είμαστε σίγουροι ότι δεν είναι μέσα στην L, οπότε αναζητώντας αυτό θα δούμε τους
# χειρότερους χρόνους αναζήτησης
t1 = time.time()
binsearch(x, l)
t2 = time.time()
print "Binary search took",t2-t1,"sec"
t1 = time.time()
linsearch(x, l)
t2 = time.time()
print "Linear search took",t2-t1,"sec"