python - python字典浮动搜索范围内

Question

假设我有某种像这样的字典结构（或另一个代表相同事物的数据结构。

d = {
  42.123231:'X',
  42.1432423:'Y',
  45.3213213:'Z',
  ..etc
}

我想创建一个这样的函数：

f(n,d,e):
    '''Return a list with the values in dictionary d corresponding to the float n
    within (+/-) the float error term e'''

所以如果我用上面的字典调用这样的函数：

f(42,d,2)

它会回来

['X','Y']

然而，虽然用循环编写这个函数很简单，但我不想做一些遍历字典中的每个值并彻底检查它的事情，但我希望它以某种方式利用索引结构（或甚至可以使用排序列表）以使搜索更快。

Answer 1

字典是一个错误的数据结构。写一个搜索树。

Answer 2

带有数字键的字典通常按键值排序。但是您可能 - 为了安全起见 - 将其重新排列为 OrderedDictionary - 你只做一次

from collections import OrderedDict
d_ordered = OrderedDict(sorted(d.items(), key =lambda i:i[0]))

然后过滤值相当简单 - 它会在上边界停止

import itertools    
values = [val for k, val in 
          itertools.takewhile(lambda (k,v): k<upper, d_ordered.iteritems()) 
          if k > lower]

正如我已经说过的，排序字典并不是真正必要的——但有些人会说这个假设是基于当前的实现，并且将来可能会改变。

Answer 3

Python 字典是一个 hashmap 实现。它的键不能像在搜索树中那样进行比较和遍历。因此，如果不实际检查所有键，您根本无法使用 python 字典来做到这一点。