Ich habe mir einige der MIT Opencourseware-Quizfragen durchgelesen, und sie hatten eine Frage, die wie folgt lautet:
6) Betrachten Sie die beiden unten angegebenen Funktionen, die zum Spielen eines "Zahlenratespiels" verwendet werden.
def cmpGuess(guess):
"""Assumes that guess is an integer in range(maxVal). returns -1 if guess is < than the magic number, 0 if it is equal to the magic number and 1 if it is greater than the magic number."""
def findNumber(maxVal):
"""Assumes that maxVal is a positive integer. Returns a number, num, such that cmpGuess(num) == 0."""
Write a Python implementation of findNumber that guesses the magic number defined by cmpGuess. Your program should have the lowest time complexity possible. """Hier ist meine Umsetzung:
def find(maxVal):
ceiling = maxVal
floor = 0
while 1:
med = ((ceiling + floor) / 2)
res = cmp(med)
if res == 1:
ceiling = med
elif res == -1:
floor = med
else:
return medUnd hier ist der Antwortbogen, den die Lehrerin oder der Lehrer zur Verfügung gestellt hat:
def findNumber(maxVal):
""" Assumes that maxVal is a positive integer. Returns a number, num, such that cmpGuess(num) == 0 """
s = range(0, maxVal)
return bsearch(s, 0, len(s) -1)
def bsearch(s, first, last):
if (last-first) < 2:
if cmp(s[first]) == 0:
return first
else:
return last
mid = first + (last -first)/2
if cmp(s[mid]) == 0:
return s[mid]
if cmp(s[mid]) == -1:
return bsearch(s, first, mid -1)
return bsearch(s, mid + 1, last)Dies ist die cmp-Funktion, die laut Spezifikation von unseren beiden Funktionen verwendet wird:
def cmp(guess):
if guess > num:
return 1
elif guess < num:
return -1
else: return 0Ein großer Unterschied besteht darin, dass meine Lösung iterativ ist und die des Lehrers rekursiv. Ich habe 1000 Durchläufe unserer beiden Funktionen mit einem maxVal = 1.000.000 gemessen. Hier ist ein Ausschnitt der Zeitmessung:
t = timeit.Timer('find(1000000)', 'from __main__ import find,cmp')
t1 = timeit.Timer('findNumber(1000000)', 'from __main__ import findNumber,bsearch')
print str(t.timeit(1000))
print str(t1.timeit(1000))Mein Lauf dauerte: 0.000621605333677s Der Lauf des Lehrers dauerte: 29.627s
Das kann unmöglich richtig sein. Ich habe die Zeit mehrmals hintereinander gemessen, und in allen Fällen kam die zweite Funktion mit lächerlichen 30s-Ergebnissen an. Ich habe die Lösungsfunktion direkt aus dem vom MIT zur Verfügung gestellten Dokument kopiert und eingefügt. Hat jemand eine Idee?
