找到最接近给定数字的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询问如何针对具有不同起点的重复查找进行优化.关键是对数据进行预排序,然后使用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]

两者平分()和nsmallest()采取排序的数据的优势.前者运行O(log2 k)时间,后者运行O(n)时间.

Answer 2

您可以计算距离，并排序：

[n for d, n in sorted((abs(x-myNumber), x) for x in myList)[:k]]

这将执行以下操作：

1. 创建一系列元组(d, x)，其中d到目标的距离
2. 选择该k列表的第一个元素
3. 仅从结果中提取数值，丢弃距离