查找与给定数字最接近的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个最接近的数字。有pythonic方法可以完成上述任务吗？

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]

本质上是这样说的：“给我三个与 6.5 绝对差值最小的输入值”。

算法及其运行时间

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

该算法仅在找到新的“最佳”值时才向堆中添加新值。因此，它使进行比较的次数最小化。例如，如果要从1,000,000个随机输入中寻找100个最佳值，则通常进行的比较少于1,008,000（与使用
min（）
查找单个最佳值相比，比较大约多0.8％）。

的 主要功能 为
分钟（） ， nsmallest（） ，和 排序（）
所有保证该键功能在输入可迭代称为每次值一次。这意味着该技术对于n值最近的问题的更复杂和有趣的示例（即听起来最相似，最接近的颜色，最小的差异，最少的基因突变，欧几里得距离等）将非常有效。

无论 nsmallest（） 和 排序（） 将返回一个列表等级排序由贴近（联系结算由值是第一次看到）。

对于那些感兴趣的人，这里和这里都存在对比较预期数量的分析。快速总结：

• 随机输入的平均大小写： n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))
• 递增输入的最佳情况： n + k * log(k, 2)
• 输入下降的最坏情况： n * log(k, 2)

优化重复查找

@Phylliida在评论中询问如何针对起点不同的重复查找进行优化。关键是对数据进行预排序，然后使用二等分法找到一个小的搜索段的中心：

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]

这两个 对开（） 和 nsmallest（） 排序的数据占据优势。前者运行 O（log2 k） 时间，而后者运行 O（n） 时间。