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

2024-03-28 10:18:43 发布

您现在位置:Python中文网/ 问答频道 /正文

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

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

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

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


Tags: 方法lambdakey列表数字absminmynumber
3条回答

简短的回答

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、最近colorssmallest diffs、最少的遗传突变、欧氏距离等)的例子将是有效的。

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

对于那些感兴趣的人来说,有一个对期望的比较数量herehere的分析。快速总结:

  • 随机输入的平均情况: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)时间。

你可以计算距离,然后排序:

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

这将执行以下操作:

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

两个答案都是好的,格雷格是对的,雷蒙德的答案更高层次,更容易实现,但我基于格雷格的答案,因为它更容易操作,以满足我的需要。

以防有人正在寻找一种方法,从一个dict列表中找到n个最接近的值。

我的dict是这样的,其中npi只是一个标识符,我需要它和值一起:

mydict = {u'fnpi': u'1982650024',
 u'snpi': {u'npi': u'1932190360', u'value': 2672},
 u'snpis': [{u'npi': u'1831289255', u'value': 20},
  {u'npi': u'1831139799', u'value': 20},
  {u'npi': u'1386686137', u'value': 37},
  {u'npi': u'1457355257', u'value': 45},
  {u'npi': u'1427043645', u'value': 53},
  {u'npi': u'1477548675', u'value': 53},
  {u'npi': u'1851351514', u'value': 57},
  {u'npi': u'1366446171', u'value': 60},
  {u'npi': u'1568460640', u'value': 75},
  {u'npi': u'1326046673', u'value': 109},
  {u'npi': u'1548281124', u'value': 196},
  {u'npi': u'1912989989', u'value': 232},
  {u'npi': u'1336147685', u'value': 284},
  {u'npi': u'1801894142', u'value': 497},
  {u'npi': u'1538182779', u'value': 995},
  {u'npi': u'1932190360', u'value': 2672},
  {u'npi': u'1114020336', u'value': 3264}]}

value = mydict['snpi']['value'] #value i'm working with below
npi = mydict['snpi']['npi'] #npi (identifier) i'm working with below
snpis = mydict['snpis'] #dict i'm working with below

要获取[id, value]列表(不仅仅是值列表),我使用以下命令:

[[id,val] for diff, val, id in sorted((abs(x['value']-value), x['value'], x['npi']) for x in snpis)[:6]]

由此产生:

[[u'1932190360', 2672],
 [u'1114020336', 3264],
 [u'1538182779', 995],
 [u'1801894142', 497],
 [u'1336147685', 284],
 [u'1912989989', 232]]

编辑

我发现,如果你处理的是一个dict(或列表),那么操纵Raymond的答案也很容易。

from heapq import nsmallest
[[i['npi'], i['value']] for i in nsmallest(6, snpis, key=lambda x: abs(x['value']-value))]

这将产生与上述输出相同的结果。

还有这个

nsmallest(6, snpis, key=lambda x: abs(x['value']-value))将生成一个dict。

相关问题 更多 >