从整数列表中，获取最接近给定值的数字

Question

给定一个整数列表，我想找出哪个数字最接近我在输入中给出的数字：

>>> myList = [4, 1, 88, 44, 3]
>>> myNumber = 5
>>> takeClosest(myList, myNumber)
...
4

有什么快速的方法吗？

Answer 1

如果不确定列表是否已排序，则可以使用built-in ^{} function来查找与指定数字的最小距离的元素。

>>> min(myList, key=lambda x:abs(x-myNumber))
4

注意，它还可以与带int键的dict一起使用，比如{1: "a", 2: "b"}。这种方法需要O（n）时间。

---

如果列表已经排序，或者您可以只对数组进行一次排序，请使用@Lauritz's answer中所示的等分方法，该方法只需要O（log n）时间（注意，检查列表是否已经排序是O（n），排序是O（logn）。）

Answer 2

>>> takeClosest = lambda num,collection:min(collection,key=lambda x:abs(x-num))
>>> takeClosest(5,[4,1,88,44,3])
4

lambda是编写“匿名”函数（没有名称的函数）的一种特殊方式。因为lambda是一个表达式，所以可以为它指定任何名称。

写上述内容的“长”方法是：

def takeClosest(num,collection):
   return min(collection,key=lambda x:abs(x-num))

Answer 3

我将重命名函数take_closest，以符合PEP8命名约定。

如果您的意思是快速执行，而不是快速编写，min应该而不是是您选择的武器，除非在一个非常狭窄的用例中。min解决方案需要检查列表中的每个数字，并对每个数字进行计算。而使用^{}几乎总是更快。

“几乎”来自这样一个事实：需要对列表进行排序才能工作。希望您的用例是这样的，您可以对列表进行一次排序，然后就不用管它了。即使不需要，只要每次调用take_closest之前不需要排序，bisect模块很可能会出现在顶部。如果你有疑问，试试两者，看看现实世界的差异。

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

“对分”的工作原理是重复地将一个列表减半，并通过查看中间值来找出必须包含的那一半myNumber。这意味着它的运行时间为O（log n），而不是highest voted answer的运行时间O（n）。如果我们比较这两种方法并用排序后的myList提供这两种方法，则会得到以下结果：

$ 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

所以在这个特殊的测试中，bisect几乎快了20倍。对于较长的列表，差异将更大。

如果我们通过取消myList必须排序的先决条件来平衡竞争环境呢？假设我们每次调用take_closest时都对列表的副本进行排序，而不改变min解决方案。使用上述测试中的200个项目列表，bisect解决方案仍然是最快的，尽管只有大约30%。

这是一个奇怪的结果，考虑到排序步骤是O（n log（n））！min仍然失败的唯一原因是，排序是在高度优化的c代码中完成的，而min必须为每个项费力地调用lambda函数。随着myList大小的增加，min解决方案最终会更快。请注意，我们必须把所有有利于它的东西放在一起，才能使min解决方案获胜。