为什么这两个功能之间的速度差异如此之大？

Question

我一直在阅读麻省理工学院的一些开放式课件,他们有一个问题是这样的:

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

一个主要的区别是我的解决方案是迭代的,而教师的解决方案是递归的.我使用maxVal = 1,000,000对两个函数进行了1000次运行.这是时间片段:

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秒结果.我直接从麻省理工学院提供的文件中复制粘贴解决方案功能.有任何想法吗？

Answer 1

我能看到的最明显的一点就是,每次你打电话和老师的作用时间它创造100万点的整数(假设的Python 2.x的)一个列表,然后当它返回时再次破坏该列表.

这需要一段时间.

Answer 2

您说您测试了两个脚本以确保它们给出相同的答案，但它们没有。正如您所写的，老师的脚本将始终返回最后一个元素。这是因为这些行：

def bsearch(s, first, last): 
    if (last-first) < 2: 
        if cmp(s[first]) == 0: 
            return first 
    else:
        return last

应该

def bsearch(s, first, last): 
    if (last-first) < 2: 
        if cmp(s[first]) == 0: 
            return first 
        else:
            return last

换句话说，有一个缩进错误，我意识到麻省理工学院网站上的 pdf 中也有这个错误。其次，老师的脚本仍然无法正常工作（它总是返回最后一个数字），因为他的二分搜索与 cmp 的结果方向错误。这是老师根据规范解决的问题，通过更改线路即可轻松修复

    if cmp(s[mid]) == -1:

到

    if cmp(s[mid]) == 1:

这并不是对缓慢问题的真正答案，这显然是（正如已经指出的）由于 O(N) 内存的分配（这是一个大的）、递归、列表查找、潜在地调用 cmp每个 bsearch 调用两次而不是一次并存储结果，并且必须明确检查(last - first) < 2每次调用是否bsearch，因为他使用的变量last包含在可能值的范围内，而不是比最高可能值多 1。顺便说一句，通过更改以下行，您自己的代码可以变得更快一点：

            floor = med

到

            floor = med + 1

这样您就可以将 med 从搜索范围中排除。您已经知道这不是基于 cmp 结果的值。顺便说一句，我不会使用作cmp​​为我自己的函数名称，因为它是一个 Python 内置函数（我知道它在cmpGuess规范中）。