<p>如果您需要经常执行查找,我们可以将此算法设置为<em>O(log n)</em>算法,首先将数据存储在<em>排序的</em>列表中:</p>
<pre><code>from operator import itemgetter
ks = sorted(A.items(), key=itemgetter(1))
vs = list(map(itemgetter(1), ks))
</code></pre>
<p>然后对于每个项目,我们可以使用<a href="https://docs.python.org/3.7/library/bisect.html#bisect.bisect_left" rel="nofollow noreferrer"><strong>^{<cd1>}</strong></a>点来确定插入点。然后我们可以检查周围的两个值,以检查最小值,并返回相应的键。也有可能</p>
<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>
<p>上面的内容看起来可能不是一个改进,但是在这里,我们将始终计算<code>sorted(..)</code>中最多<em>三个元素,并且<code>bisect_left</code>将计算<em>对数</em>个元素。你知道吗</p>
<p>例如:</p>
<pre><code>>>> 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]]
</code></pre>
<p>因此,“加载”阶段采用<em>O(n logn)</em>(元素数为<em>n</em>)。如果我们将上述方法推广到提取<em>k</em>元素(通过增加切片),则需要<em>O(logn+klogk)</em>来执行查找。你知道吗</p>