Я читал некоторые тесты MIT opencourseware, и у них возник вопрос, который звучит так:
6) Рассмотрим две функции, указанные ниже, которые используются для «догадки».игра с числами ».
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. """
Вот моя реализация:
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 med
А вот реализация листа ответов, предоставленная учителем:
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)
Это функция cmp, используемая обеими нашими функциями, в соответствии со спецификацией:
def cmp(guess):
if guess > num:
return 1
elif guess < num:
return -1
else: return 0
Одно из основных отличий состоит в том, что мое решение является итеративным, а решение учителя - рекурсивным.Я рассчитал 1000 запусков обеих наших функций с maxVal = 1 000 000.Вот фрагмент времени:
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))
Мой забег занял: 0.000621605333677s Бег учителей занял: 29.627s
Это не может быть правильным.Я рассчитывал это несколько раз подряд, и во всех случаях вторая функция имела смешные результаты 30-х годов.Я скопировал и вставил функцию решения прямо из документа, предоставленного MIT.Есть идеи?