假设我们要找到两个值最接近10的项:
A = {'abc': 12.3, 'def': 17.3, 'dsfsf': 18, 'ppp': 3.2, "jlkljkjlk": 9.23}
它适用于:
def nearest(D, centre, k=10):
return sorted([[d, D[d], abs(D[d] - centre)] for d in D], key=lambda e: e[2])[:k]
print(nearest(A, centre=10, k=2))
[['jlkljkjlk', 9.23, 0.7699999999999996], ['abc', 12.3, 2.3000000000000007]]
但是当dict有更大的尺寸(几十万个条目)时,有没有Python内置的方法来实现这一点和/或更优化的版本?
您可以使用^{} :
就时间复杂性而言,它在
O(n log(k))
时间内运行,而不是在基于字典排序的解决方案的O(n log(n))
时间内运行。你知道吗如果您不介意使用熊猫:
如果您需要经常执行查找,我们可以将此算法设置为O(log n)算法,首先将数据存储在排序的列表中:
然后对于每个项目,我们可以使用^{} 点来确定插入点。然后我们可以检查周围的两个值,以检查最小值,并返回相应的键。也有可能
上面的内容看起来可能不是一个改进,但是在这里,我们将始终计算
sorted(..)
中最多三个元素,并且bisect_left
将计算对数个元素。你知道吗例如:
因此,“加载”阶段采用O(n logn)(元素数为n)。如果我们将上述方法推广到提取k元素(通过增加切片),则需要O(logn+klogk)来执行查找。你知道吗
相关问题 更多 >
编程相关推荐