<p>我将重命名函数<code>take_closest</code>,以符合PEP8命名约定。</p>
<p>如果您的意思是快速执行,而不是快速编写,<code>min</code>应该<strong>而不是</strong>是您选择的武器,除非在一个非常狭窄的用例中。<code>min</code>解决方案需要检查列表中的每个数字,并对每个数字进行计算。而使用<a href="http://docs.python.org/library/bisect.html#bisect.bisect_left" rel="noreferrer">^{<cd4>}</a>几乎总是更快。</p>
<p>“几乎”来自这样一个事实:需要对列表进行排序才能工作。希望您的用例是这样的,您可以对列表进行一次排序,然后就不用管它了。即使不需要,只要每次调用<code>take_closest</code>之前不需要排序,<code>bisect</code>模块很可能会出现在顶部。如果你有疑问,试试两者,看看现实世界的差异。</p>
<pre><code>from bisect import bisect_left
def take_closest(myList, myNumber):
"""
Assumes myList is sorted. Returns closest value to myNumber.
If two numbers are equally close, return the smallest number.
"""
pos = bisect_left(myList, myNumber)
if pos == 0:
return myList[0]
if pos == len(myList):
return myList[-1]
before = myList[pos - 1]
after = myList[pos]
if after - myNumber < myNumber - before:
return after
else:
return before
</code></pre>
<p>“对分”的工作原理是重复地将一个列表减半,并通过查看中间值来找出必须包含的那一半<code>myNumber</code>。这意味着它的运行时间为<strong>O(log n)</strong>,而不是<a href="https://stackoverflow.com/a/12141207/566644">highest voted answer</a>的运行时间<strong>O(n)</strong>。如果我们比较这两种方法并用排序后的<code>myList</code>提供这两种方法,则会得到以下结果:</p>
<pre>
$ python -m timeit -s "
from closest import take_closest
from random import randint
a = range(-1000, 1000, 10)" "take_closest(a, randint(-1100, 1100))"
100000 loops, best of 3: 2.22 usec per loop
$ python -m timeit -s "
from closest import with_min
from random import randint
a = range(-1000, 1000, 10)" "with_min(a, randint(-1100, 1100))"
10000 loops, best of 3: 43.9 usec per loop
</pre>
<p>所以在这个特殊的测试中,<code>bisect</code>几乎快了20倍。对于较长的列表,差异将更大。</p>
<p>如果我们通过取消<code>myList</code>必须排序的先决条件来平衡竞争环境呢?假设我们每次调用</em><code>take_closest</code>时都对列表的副本进行排序,而不改变<code>min</code>解决方案。使用上述测试中的200个项目列表,<code>bisect</code>解决方案仍然是最快的,尽管只有大约30%。</p>
<p>这是一个奇怪的结果,考虑到排序步骤是<strong>O(n log(n))</strong>!<code>min</code>仍然失败的唯一原因是,排序是在高度优化的c代码中完成的,而<code>min</code>必须为每个项费力地调用lambda函数。随着<code>myList</code>大小的增加,<code>min</code>解决方案最终会更快。请注意,我们必须把所有有利于它的东西放在一起,才能使<code>min</code>解决方案获胜。</p>