2024-03-28 10:18:43 发布
网友
假设我有一个列表[1,2,3,4,5,6,7]。我想找出3个最接近的数字,比如说,6.5。那么返回的值将是[5,6,7]。
[1,2,3,4,5,6,7]
[5,6,7]
在python中,找到一个最接近的数字并不是那么困难,可以使用
min(myList, key=lambda x:abs(x-myNumber))
但我不想绕着这个圈找到k个最接近的数字。有没有一种Python的方法来完成上述任务?
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)时间。
你可以计算距离,然后排序:
[n for d, n in sorted((abs(x-myNumber), x) for x in myList)[:k]]
这将执行以下操作:
(d, x)
d
k
两个答案都是好的,格雷格是对的,雷蒙德的答案更高层次,更容易实现,但我基于格雷格的答案,因为它更容易操作,以满足我的需要。
以防有人正在寻找一种方法,从一个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, 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。
nsmallest(6, snpis, key=lambda x: abs(x['value']-value))
简短的回答
heapq.nsmallest()函数将灵活高效地执行此操作:
从本质上说,“给我三个输入值,它们与数字的绝对差值最小。”。
算法及其运行时间
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定位小搜索段的中心:
例如:
bisect()和nsmalest()都利用排序后的数据。前者运行O(log2 k)时间,后者运行O(n)时间。
你可以计算距离,然后排序:
这将执行以下操作:
(d, x)
,其中d
是到目标的距离k
元素两个答案都是好的,格雷格是对的,雷蒙德的答案更高层次,更容易实现,但我基于格雷格的答案,因为它更容易操作,以满足我的需要。
以防有人正在寻找一种方法,从一个dict列表中找到n个最接近的值。
我的dict是这样的,其中npi只是一个标识符,我需要它和值一起:
要获取
[id, value]
列表(不仅仅是值列表),我使用以下命令:由此产生:
编辑
我发现,如果你处理的是一个dict(或列表),那么操纵Raymond的答案也很容易。
这将产生与上述输出相同的结果。
还有这个
nsmallest(6, snpis, key=lambda x: abs(x['value']-value))
将生成一个dict。相关问题 更多 >
编程相关推荐