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

Question

给定一个整数列表,我想找到哪个数字最接近我输入的数字:

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

有没有快速的方法来做到这一点？

Answer 1

如果我们不确定列表是否已排序,我们可以使用内置min()函数来查找与指定数字的距离最小的元素.

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

请注意,它也适用于带有int键的dicts,例如{1: "a", 2: "b"}.此方法需要O(n)时间.

如果列表已经排序,或者您只需支付一次排序数组的价格,请使用@ Lauritz的答案中所示的二分法,该答案仅需要O(log n)时间(注意检查列表是否已经排序为O) (n)和排序是O(n log n).)

Answer 2

如果你的意思是快速执行而不是快速写入,take_closest那么除非在一个非常狭窄的用例中,否则它不应该是你的首选武器.该min解决方案需要检查列表中的每一个数字,并做到每个号码的计算.min相反,使用几乎总是更快.

"几乎"来自于bisect.bisect_left需要将列表分类才能工作的事实.希望您的用例是这样的,您可以对列表进行一次排序,然后不管它.即使不是,只要你不需要在每次打电话之前进行排序bisect_left,take_closest模块就可能会排在最前面.如果您有疑问,请尝试两者并查看现实世界的差异.

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

Bisect通过反复减半列表并bisect通过查看中间值找出哪一半必须进入.这意味着它的运行时间为O(log n),而不是最高投票答案的O(n)运行时间.如果我们比较两种方法并提供两种方法,则结果如下:myNumber

$ 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

所以在这个特定的测试中,myList速度快了近20倍.对于更长的列表,差异会更大.

如果我们通过删除bisect必须排序的前提来平衡比赛场地怎么办？假设我们每次 myList调用时都会对列表进行排序,同时保持take_closest解决方案不变.使用上述测试中的200项列表,min解决方案仍然是最快的,但只有约30%.

考虑到排序步骤为O(n log(n)),这是一个奇怪的结果!bisect失败的唯一原因是排序是在高度优化的c代码中完成的,而min必须为每个项目调用lambda函数.随着min规模的增长,myList解决方案最终会更快.请注意,我们必须堆叠所有有利于min解决方案才能获胜.

Answer 3

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

一个拉姆达是写一个"匿名"功能(即没有名称的功能)的一种特殊方式.您可以为其指定任何名称,因为lambda是一个表达式.

编写上述内容的"长"方式是:

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

Answer 4

def closest(list, Number):
    aux = []
    for valor in list:
        aux.append(abs(Number-valor))

    return aux.index(min(aux))

此代码将为您提供列表中最接近的Number数的索引.

KennyTM给出的解决方案总体上是最好的,但是在你无法使用它的情况下(比如brython),这个函数将完成工作

Answer 5

迭代列表并将当前最接近的数字与abs(currentNumber - myNumber)：

def takeClosest(myList, myNumber):
    closest = myList[0]
    for i in range(1, len(myList)):
        if abs(i - myNumber) < closest:
            closest = i
    return closest