首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >查找k个值最接近某一值的字典条目

查找k个值最接近某一值的字典条目
EN

Stack Overflow用户
提问于 2018-10-15 03:24:57
回答 3查看 222关注 0票数 1

假设我们想要找到两个值最接近10的项目:

代码语言:javascript
复制
A = {'abc': 12.3, 'def': 17.3, 'dsfsf': 18, 'ppp': 3.2, "jlkljkjlk": 9.23}

它与以下各项配合使用:

代码语言:javascript
复制
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]

但是,当字典的大小更大(数十万个条目)时,有没有Python内置的方法和/或更优化的版本来实现这一点?

EN

回答 3

Stack Overflow用户

发布于 2018-10-15 03:27:44

如果您不介意使用Pandas:

代码语言:javascript
复制
import pandas as pd
closest = (pd.Series(A) - 10).abs().sort_values()[:2]
#jlkljkjlk    0.77
#abc          2.30
closest.to_dict()
#{'jlkljkjlk': 0.7699999999999996, 'abc': 2.3000000000000007}
票数 7
EN

Stack Overflow用户

发布于 2018-10-15 04:15:42

您可以使用heapq.nsmallest()

代码语言:javascript
复制
from heapq import nsmallest
A = {'abc': 12.3, 'def': 17.3, 'dsfsf': 18, 'ppp': 3.2, 'jlkljkjlk': 9.23}
def nearest(D, centre, k=10):
    return [[x, D[x], abs(D[x] - centre)] for x in nsmallest(k, D, key=lambda x: abs(D[x] - centre))]

print(nearest(A, centre=10, k=2))
# [['jlkljkjlk', 9.23, 0.7699999999999996], ['abc', 12.3, 2.3000000000000007]]

就时间复杂度而言,这是以O(n log(k))时间而不是基于字典排序的解决方案的O(n log(n))运行的。

票数 3
EN

Stack Overflow用户

发布于 2018-10-15 05:11:04

考虑到您需要经常执行查找,我们可以将其设置为O(log )算法,首先将数据存储在排序列表中:

代码语言:javascript
复制
from operator import itemgetter

ks = sorted(A.items(), key=itemgetter(1))
vs = list(map(itemgetter(1), ks))

然后,对于每个项目,我们可以使用点来确定插入点。然后我们可以检查周围的两个值,以检查最小的值,并返回相应的键。也有可能是

代码语言:javascript
复制
from bisect import bisect_left
from operator import itemgetter

def closests(v):
    idx = bisect_left(vs, v)
    i, j = max(0, idx-1), min(idx+2, len(ks))
    part = ks[i:j]
    return sorted([[*pi, abs(pi[-1]-v)] for pi in part], key=itemgetter(-1))[:2]

上面可能看起来不是一个改进,但在这里,我们将始终计算sorted(..)中最多三个元素,并且bisect_left将计算对数个元素。

例如:

代码语言:javascript
复制
>>> closests(1)
[['ppp', 3.2, 2.2], ['jlkljkjlk', 9.23, 8.23]]
>>> closests(3.2)
[['ppp', 3.2, 0.0], ['jlkljkjlk', 9.23, 6.03]]
>>> closests(5)
[['ppp', 3.2, 1.7999999999999998], ['jlkljkjlk', 9.23, 4.23]]
>>> closests(9.22)
[['jlkljkjlk', 9.23, 0.009999999999999787], ['abc', 12.3, 3.08]]
>>> closests(9.24)
[['jlkljkjlk', 9.23, 0.009999999999999787], ['abc', 12.3, 3.0600000000000005]]

因此,“加载”阶段需要O(n log n) (n是元素的数量)。然后,如果我们将上面的方法推广到获取k个元素(通过增加切片),那么执行查找将需要O(log + lookup )。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52806294

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档