找到k个最接近给定数的数

Question

假设我有一个列表[1,2,3,4,5,6,7]。我想找出3个最接近的数字，比如说，6.5。那么返回的值将是[5,6,7]。

在python中，找到一个最接近的数字并不是那么困难，可以使用

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

但我不想绕着这个圈找到k个最接近的数字。有没有一种Python的方法来完成上述任务？

Answer 1

简短的回答

heapq.nsmallest()函数将灵活高效地执行此操作：

>>> from heapq import nsmallest
>>> s = [1,2,3,4,5,6,7]
>>> nsmallest(3, s, key=lambda x: abs(x-6.5))
[6, 7, 5]

从本质上说，“给我三个输入值，它们与数字的绝对差值最小。”。

算法及其运行时间

nsmallest的算法对数据进行单次传递，在任何时候都不会在内存中保留超过最佳值的值（这意味着它可以与任何输入迭代器一起工作，具有缓存效率和空间效率）。

算法只在找到新的“最佳”值时向堆中添加新值。因此，它将所做比较的次数减至最少。例如，如果要在1000000个随机输入中寻找100个最佳值，则通常会进行少于1008000个比较（比使用min()查找单个最佳值多出约0.8%的比较）。

min（）、nsmalest（）和sorted（）的key functions都保证键函数在输入iterable的每个值中只调用一次。这意味着这项技术对于更复杂、更有趣的n-最近值问题（即sound the most alike、最近colors、smallest diffs、最少的遗传突变、欧氏距离等）的例子将是有效的。

nsmallest（）和sorted（）都将返回一个按接近度排序的列表秩（关系由最先看到的值确定）。

对于那些感兴趣的人来说，有一个对期望的比较数量here和here的分析。快速总结：

• 随机输入的平均情况：n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))
• 升序输入的最佳情况：n + k * log(k, 2)
• 降序输入的最坏情况：n * log(k, 2)

优化重复查找

在评论中，@Phylliida询问如何优化具有不同起点的重复查找。关键是对数据进行预排序，然后使用bisect定位小搜索段的中心：

from bisect import bisect

def k_nearest(k, center, sorted_data):
    'Return *k* members of *sorted_data* nearest to *center*'
    i = bisect(sorted_data, center)
    segment = sorted_data[max(i-k, 0) : i+k]
    return nsmallest(k, segment, key=lambda x: abs(x - center))

例如：

>>> s.sort()
>>> k_nearest(3, 6.5, s)
[6, 7, 5]
>>> k_nearest(3, 0.5, s)
[1, 2, 3]
>>> k_nearest(3, 4.5, s)    
[4, 5, 3]
>>> k_nearest(3, 5.0, s)
[5, 4, 6]

bisect（）和nsmalest（）都利用排序后的数据。前者运行O（log2 k）时间，后者运行O（n）时间。