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

Question

给定一个整数列表，我想找到离输入的数字最接近的数字：

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

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

- Ricky Robinson

---

也可以返回该事件发生在列表中的索引。 - Charlie Parker

可能是在未完全排序的列表中查找最接近值的项的索引的重复问题。 - sancho.s ReinstateMonicaCellio

@sancho.s 发现得不错。虽然这个问题的答案比那个问题上的答案要好得多。所以我会投票关闭另一个问题，将其作为此问题的重复。 - Jean-François Corbett

Answer 1

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

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

请注意，它还可以与具有整数键的字典一起使用，例如 {1: "a", 2: "b"}。此方法需要 O(n) 时间。

---

如果列表已经排序，或者您只想付出一次排序数组的代价，请使用@Lauritz's answer中所示的二分法，该方法仅需要O(log n)的时间（但请注意，检查列表是否已经排序是O(n)，排序是O(n log n)）。

- kennytm

---

说得更简单一些，这是一个“O(n)”的复杂度，如果你的输入数组已经排序，使用“bisect”进行一点小hack就可以将其显著提高到“O(log n)”。 - mic_e

这只是Lauritz的回答。 - kennytm

也返回该事件在列表中发生的索引位置，可以吗？ - Charlie Parker

@CharlieParker 请创建自己的 min 实现，将其应用于字典 (items())，并在最后返回键而不是值。 - Dustin Oprea

еҸҜд»ҘдҪҝз”Ёnumpy.argminд»ЈжӣҝminжқҘиҺ·еҸ–зҙўеј•иҖҢдёҚжҳҜеҖјгҖӮ - user7345804

Answer 2

我将把函数take_closest重命名以符合PEP8命名规范。

如果你的意思是快速执行而不是快速编写的话，除了一个非常狭窄的用例之外，min不应该是你的首选。 min解决方案需要检查列表中的每个数字并为每个数字进行计算。使用bisect.bisect_left几乎总是更快的。

“几乎”源于bisect_left要求对列表进行排序才能工作。希望您的用例使您可以对列表进行一次排序，然后让其保持不变。即使不能这样做，只要您不需要在每次调用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

Bisect通过重复将列表减半并查找中间值以确定myNumber应该在哪一半，这意味着它的运行时间为O(log n)，而不是最高得票答案的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解决方案才能获胜。

- Lauritz V. Thaulow

---

排序本身需要O(N log N)的时间复杂度，因此当N变得很大时，它会变得更慢。例如，如果您使用a=range(-1000,1000,2);random.shuffle(a)，您会发现takeClosest(sorted(a), b)会变得更慢。 - kennytm

@KennyTM 我承认这一点，并在我的答案中指出。但是，只要 getClosest 可能会被每次排序调用多次，这将更快，并且对于仅排序一次的情况，这是一个不言而喻的选择。 - Lauritz V. Thaulow

还可以返回此事件在列表中发生的索引吗？ - Charlie Parker

如果myList已经是np.array，那么使用np.searchsorted替换bisect会更快。 - Michael Hall

如果我想返回的不是最接近的值，而是它的ID呢？ - AAAA

@LauritzV.Thaulow 我认为你在回答的结尾处打错了一个字，因为你说“随着mylist的增长，min解决方案最终会更快”。然而，从你回答的其他部分推断出来，min应该变得越来越慢。 - Leander

Answer 3

>>> 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))

- Burhan Khalid

---

请注意，根据PEP 8，不建议将lambda分配给名称。 - Evert Heylen

Answer 4

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

    return aux.index(min(aux))

这段代码将为你提供列表中最接近目标数字的索引。

KennyTM提供的解决方案是最好的，但在某些情况下无法使用（例如brython），这个函数可以胜任。

- Gustavo Lima

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

- João Silva

---

你也可以返回索引。 - Charlie Parker

错误！应该是 if abs(myList[i] - myNumber) < abs(closest - myNumber): closest = myList[i];。不过最好事先将该值存储起来。 - lk_vc

毫无疑问，该函数已经返回了最接近的索引。为了满足OP的要求，倒数第二行不应该是closest = myList[i]吗？ - Paula Livingstone

Answer 6

def find_nearest(array, value):
    array = np.asarray(array)
    idx = (np.abs(array - value)).argmin()
    return array[idx]

使用以下方式运行它

price_near_to=find_nearest(df['Close'], df['Close'][-2])

- user8017857

---

这里的 np 是什么意思？ - munmunbb

@munmunbb 这是numpy。它是Python计算的一个包。import numpy as np - Sahil Shah

Answer 7

重要的是要注意，Lauritz的建议使用bisect并不会实际上找到MyList中最接近MyNumber的值。相反，bisect会在MyList中寻找下一个在顺序中MyNumber之后的值。因此，在OP的情况下，您实际上会得到44的位置而不是4的位置。

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

为了获得最接近5的值，您可以尝试将列表转换为数组，并使用numpy中的argmin，如下所示。

>>> import numpy as np
>>> myNumber = 5   
>>> myList = [1, 3, 4, 44, 88] 
>>> myArray = np.array(myList)
>>> pos = (np.abs(myArray-myNumber)).argmin()
>>> myArray[pos]
...
4

我不知道这会有多快，我猜想速度可能会很慢。

- jmdeamer

---

Lauritz的函数运行正确。你只是使用了bisect_left，但Lauritz建议使用一个名为takeClosest(...)的函数来进行额外的检查。 - Kanat

如果您要使用NumPy，可以使用np.searchsorted代替bisect_left。而@Kanat是正确的 - Lauritz的解决方案确实包括选择哪个候选者更接近的代码。 - John Y

Answer 8

如果我可以补充@Lauritz's answer

为了避免运行错误，在bisect_left行之前不要忘记添加条件：

if (myNumber > myList[-1] or myNumber < myList[0]):
    return False

因此完整的代码将如下所示：

from bisect import bisect_left

def takeClosest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.
    If two numbers are equally close, return the smallest number.
    If number is outside of min or max return False
    """
    if (myNumber > myList[-1] or myNumber < myList[0]):
        return False
    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

- umn

Answer 9

扩展Gustavo Lima的答案。不需要创建全新的列表，也可以完成相同的操作。在FOR循环进程中，列表中的值可以替换为微分值。

def f_ClosestVal(v_List, v_Number):
"""Takes an unsorted LIST of INTs and RETURNS INDEX of value closest to an INT"""
for _index, i in enumerate(v_List):
    v_List[_index] = abs(v_Number - i)
return v_List.index(min(v_List))

myList = [1, 88, 44, 4, 4, -2, 3]
v_Num = 5
print(f_ClosestVal(myList, v_Num)) ## Gives "3," the index of the first "4" in the list.

- JayJay123

Answer 10

def takeClosest(myList, myNumber):
    newlst = []
    for i in myList:
        newlst.append(i - myNumber)
    lstt = [abs(ele) for ele in newlst]
    print(myList[lstt.index(min(lstt))])

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

- Sawndes

---

请提供一些解释。 - Akshay