blocks|key|2590604|text|如果您不介意使用Pandas：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2590605|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}|code-block|syntax|javascript|2590606|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

If you do not mind using Pandas:

<pre><code>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}
</code></pre>

blocks|key|2590608|text|您可以使用heapq.nsmallest()|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2590609|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]]|code-block|syntax|javascript|2590610|就时间复杂度而言，这是以O(n+log(k))时间而不是基于字典排序的解决方案的O(n+log(n))运行的。|2590611|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/3.7/library/heapq.html#heapq.nsmallest^0|5|H|5|H|0|0|0|C|B|14|B|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]]|D|@$9|X|A|Y|1|Z]]|E|$]]|$1|F|3|G|5|H|7|10|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|11|8|@$9|12|A|13|B|C]|$9|14|A|15|B|C]]|D|@]|E|$]]|$1|M|3|-4|5|6|7|16|8|@]|D|@]|E|$]]]|N|$O|$5|P|Q|R|E|$S|T]]]]

You could use <a href="https://docs.python.org/3.7/library/heapq.html#heapq.nsmallest" rel="nofollow noreferrer"><code>heapq.nsmallest()</code></a>:

<pre><code>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]]
</code></pre>

As far as time complexity, this runs in <code>O(n log(k))</code> time instead of <code>O(n log(n))</code> of the solution based on sorting the dictionary.

blocks|key|2802614|text|考虑到您需要经常执行查找，我们可以将其设置为O(log+)算法，首先将数据存储在排序列表中：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2802615|from+operator+import+itemgetter

ks+=+sorted(A.items(),+key=itemgetter(1))
vs+=+list(map(itemgetter(1),+ks))|code-block|syntax|javascript|2802616|然后，对于每个项目，我们可以使用点来确定插入点。然后我们可以检查周围的两个值，以检查最小的值，并返回相应的键。也有可能是|2802617|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%2B2,+len(ks))
++++part+=+ks[i:j]
++++return+sorted([[*pi,+abs(pi[-1]-v)]+for+pi+in+part],+key=itemgetter(-1))[:2]|2802618|上面可能看起来不是一个改进，但在这里，我们将始终计算sorted(..)中最多三个元素，并且bisect_left将计算对数个元素。|offset|length|style|CODE|2802619|例如：|2802620|>>>+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]]|2802621|因此，“加载”阶段需要O(n+log+n)+(n是元素的数量)。然后，如果我们将上面的方法推广到获取k个元素(通过增加切片)，那么执行查找将需要O(log+%2B+lookup+)。|2802622|entityMap^0|0|0|0|0|Q|A|1A|B|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|10|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|12|8|@$M|13|N|14|O|P]|$M|15|N|16|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|17|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|18|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|19|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|X|$]]

Given you need to perform a lookup quite often, we can make this an O(log n) algorithm, by first storing the data in a sorted list:

<pre><code>from operator import itemgetter

ks = sorted(A.items(), key=itemgetter(1))
vs = list(map(itemgetter(1), ks))
</code></pre>

Then for each item we can use the <a href="https://docs.python.org/3.7/library/bisect.html#bisect.bisect_left" rel="nofollow noreferrer"><code>bisect.bisect_left</code></a> point to determine the insertion point. We can then check the two surrounding values, to check the smallest, and return the corresponding key. It is also possible that 

<pre><code>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]
</code></pre>

The above might not look as an improvement, but here we will always evaluate at most three elements in the <code>sorted(..)</code>, and <code>bisect_left</code> will evaluate a logarithmic number of elements.

For example:

<pre><code>&gt;&gt;&gt; closests(1)
[['ppp', 3.2, 2.2], ['jlkljkjlk', 9.23, 8.23]]
&gt;&gt;&gt; closests(3.2)
[['ppp', 3.2, 0.0], ['jlkljkjlk', 9.23, 6.03]]
&gt;&gt;&gt; closests(5)
[['ppp', 3.2, 1.7999999999999998], ['jlkljkjlk', 9.23, 4.23]]
&gt;&gt;&gt; closests(9.22)
[['jlkljkjlk', 9.23, 0.009999999999999787], ['abc', 12.3, 3.08]]
&gt;&gt;&gt; closests(9.24)
[['jlkljkjlk', 9.23, 0.009999999999999787], ['abc', 12.3, 3.0600000000000005]]
</code></pre>

The "loading" phase thus takes O(n log n) (with n the number of elements). Then if we generalize the above method to fetch k elements (by increasing the slice), it would take O(log n + k log k) to perform a lookup.

Let's say we want to find the 2 items which have their value the closest to 10:

<pre><code>A = {'abc': 12.3, 'def': 17.3, 'dsfsf': 18, 'ppp': 3.2, "jlkljkjlk": 9.23}
</code></pre>

It works with:

<pre><code>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))
</code></pre>

<blockquote>
 [['jlkljkjlk', 9.23, 0.7699999999999996], ['abc', 12.3, 2.3000000000000007]]
</blockquote>

But is there a Python built-in way to do this and/or a more optimized version when the dict has a much larger size (hundreds of thousands of items)?

Find the k dict items whose values are the closest to a certain value

数据存储

Python

假设我们想要找到两个值最接近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...

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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