在字典中查找整数最近邻

Find integer nearest-neighbour in a dict

我有一个 dict 接受整数键:

a = {}
a[1] = 100
a[55] = 101
a[127] = 102

我希望问的时候能取最近的邻居:

a[20] # should return a[1] = 100
a[58] # should return a[55] = 101
a[167] # should return a[127] = 102

有没有 pythonic 的方式来做到这一点?(我想这可以通过循环所有 dict 来完成,但这可能不是最优雅的解决方案?)


与双索引(也是整数)相同的问题:

 b[90, 1] = 100, b[90, 55] = 101, b[90, 127] = 102
 b[70, 1] = 40, b[70, 45] = 41, b[70, 107] = 42

我希望能够得到 b[73, 40] = b[70, 45] = 41, 即二维平面中的最近邻。

与此类似的内容:

class CustomDict(dict):
    def __getitem__(self, key):
        try:
            return dict.__getitem__(self, key)
        except KeyError:
            closest_key = min(self.keys(), key=lambda x: abs(x - key))
            return dict.__getitem__(self, closest_key)

或者这样:

class CustomDict(dict):
    def __getitem__(self, key):
        if key in self:
            return dict.__getitem__(self, key)
        else:
            closest_key = min(self.keys(), key=lambda x: abs(x - key))
            return dict.__getitem__(self, closest_key)

两者都给出了这个结果:

a = CustomDict()
a[1] = 100
a[55] = 101
a[127] = 102

print a[20] # prints 100
print a[58] # prints 101
print a[167] # prints 102

对于双索引版本:

class CustomDoubleDict(dict):
    def __getitem__(self, key):
        if key in self:
            return dict.__getitem__(self, key)
        else:
            closest_key = min(self.keys(), key=lambda c: (c[0] - key[0]) ** 2 + (c[1] - key[1]) ** 2)
            return dict.__getitem__(self, closest_key)


b = CustomDoubleDict()
b[90, 1] = 100
b[90, 55] = 101
b[90, 127] = 102
b[70, 1] = 40
b[70, 45] = 41
b[70, 107] = 42

print b[73, 40]  # prints 41
print b[70, 45]  # prints 41

一维情况下未经测试的 O(log n) 示例:

import collections
import bisect


class ProximityDict(collections.MutableMapping):
    def __init__(self, *args, **kwargs):
        self.store = dict()
        self.ordkeys = []
        self.update(dict(*args, **kwargs))

    def __getitem__(self, key):
        try: return self.store[key]
        except KeyError:
            cand = bisect.bisect_left(self.ordkeys, key)
            if cand == 0: return self.store[self.ordkeys[0]]

            return self.store[
                min(self.ordkeys[cand], self.ordkeys[cand-1],
                    key=lambda k: abs(k - key))
            ]

    def __setitem__(self, key, value):
        if not key in self.store: bisect.insort_left(self.ordkeys, key)
        self.store[key] = value

    def __delitem__(self, key):
        del self.store[key]
        del self.keys[bisect.bisect_left(self.ordkeys, key)]

    def __iter__(self):
        return iter(self.store)

    def __len__(self):
        return len(self.store)

二维情况明显更烦人(您需要存储在四叉树中排序的键),但可以通过类似的方式实现。

我没有编写代码删除也有 'proximity' 行为,但你也可以这样做。

选项 1:

维护一个单独且有序的键列表(或使用 OrderedDict)。使用二进制搜索找到最近的键。这应该是 O(log n)

方案二:(如果数据不是很大且稀疏)

既然你提到字典是静态的,那么通过字典来填充所有缺失值一次。维护最大和最小键,并覆盖 __getitem__ 以便键高于最大值或低于最小值 return 的正确值。这应该是 O(1).

选项 3:

每次都对键使用循环,它将是 O(n)。在您的应用程序中尝试一下,您可能会发现这个简单的解决方案非常快速且足够。

如何使用 min 和适当的键功能:

>>> b ={(90, 55): 101, (90, 127): 102, (90, 1): 100}
>>> def nearest(x,y):
...   m=min(((i,j) for i,j in b ),key= lambda v:abs(v[0]-x)+abs(v[1]-y))
...   return b[m]
... 
>>> nearest(40,100)
102
>>> nearest(90,100)
102
>>> b
{(90, 55): 101, (90, 127): 102, (90, 1): 100}
>>> nearest(90,10)
100

前面的答案是我建议的 pythonic 答案,但如果你想寻找一种快速的方法,你可以使用 scipy.spatial.KDTree :

class scipy.spatial.KDTree(data, leafsize=10)

kd-tree for quick nearest-neighbor lookup

This class provides an index into a set of k-dimensional points which can be used to rapidly look up the nearest neighbors of any point.

也看看http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html#scipy-spatial-ckdtree

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html#module-scipy.spatial.distance

Update:在对本答案中的两种方法进行基准测试后,second 方法明显更好,以至于它应该 几乎 严格首选。


以下方法以相同的方式处理 n 维度:

class NearestDict(dict):
    def __init__(self, ndims):
        super(NearestDict, self).__init__()
        self.ndims = ndims

    # Enforce dimensionality
    def __setitem__(self, key, val):
        if not isinstance(key, tuple): key = (key,)
        if len(key) != self.ndims: raise KeyError("key must be %d dimensions" % self.ndims)
        super(NearestDict, self).__setitem__(key, val)

    @staticmethod
    def __dist(ka, kb):
        assert len(ka) == len(kb)
        return sum((ea-eb)**2 for (ea, eb) in zip(ka, kb))

    # Helper method and might be of use
    def nearest_key(self, key):
        if not isinstance(key, tuple): key = (key,)
        nk = min((k for k in self), key=lambda k: NearestDict.__dist(key, k))
        return nk

    def __missing__(self, key):
        if not isinstance(key, tuple): key = (key,)
        if len(key) != self.ndims: raise KeyError("key must be %d dimensions" % self.ndims)
        return self[self.nearest_key(key)]

演示:

a = NearestDict(1)
a[1] = 100
a[55] = 101
a[127] = 102
print a[20]    # 100
print a[58]    # 100
print a[167]   # 102
print a.nearest_key(20)     # (1,)
print a.nearest_key(58)     # (55,)
print a.nearest_key(127)    # (127,)

b = NearestDict(2)
b[90, 1]   = 100
b[90, 55]  = 101
b[90, 127] = 102
b[70, 1]   = 40
b[70, 45]  = 41
b[70, 107] = 42
print b[73, 40] # 41
print b.nearest_key((73,40)) # (70, 45)

请注意,如果键存在,查找速度不会比标准字典查找慢。如果键 存在,则计算每个现有键之间的距离。什么都没有缓存,尽管我想你可以添加它。

编辑:

根据 the following approach implements the same class as above using scipy's cKDTree建议的方法:

请注意,还有一个额外的可选参数,regenOnAdd 允许您推迟(重新)构建 KDTree,直到您完成(大部分)插入:

from scipy.spatial import cKDTree

class KDDict(dict):
    def __init__(self, ndims, regenOnAdd=False):
        super(KDDict, self).__init__()
        self.ndims = ndims
        self.regenOnAdd = regenOnAdd
        self.__keys = []
        self.__tree = None
        self.__stale = False

    # Enforce dimensionality
    def __setitem__(self, key, val):
        if not isinstance(key, tuple): key = (key,)
        if len(key) != self.ndims: raise KeyError("key must be %d dimensions" % self.ndims)
        self.__keys.append(key)
        self.__stale = True
        if self.regenOnAdd: self.regenTree()
        super(KDDict, self).__setitem__(key, val)

    def regenTree(self):
        self.__tree = cKDTree(self.__keys)
        self.__stale = False

    # Helper method and might be of use
    def nearest_key(self, key):
        if not isinstance(key, tuple): key = (key,)
        if self.__stale: self.regenTree()
        _, idx = self.__tree.query(key, 1)
        return self.__keys[idx]

    def __missing__(self, key):
        if not isinstance(key, tuple): key = (key,)
        if len(key) != self.ndims: raise KeyError("key must be %d dimensions" % self.ndims)
        return self[self.nearest_key(key)]

输出与上述方法相同。

基准测试结果

为了了解三种方法(NearestDictKDDict(True)(插入时重新生成)和KDDict(False)(延迟重新生成)的性能,我简要地对它们进行了基准测试。

我运行 3 种不同的测试。在测试中保持不变的参数是:

  • 测试迭代次数:我每个测试都做了 5 次并且用了最短的时间。 (注意timeit.repeat默认为3)。
  • 点边界: 我在 运行ge 0 <= x < 1000
  • 中生成整数关键点
  • 查找次数: 我分别对插入和查找计时。下面的三个测试都使用了 10,000 次查找。

第一次测试使用了 4 个维度的键,以及 1,000 次插入。

{'NDIMS': 4, 'NITER': 5, 'NELEMS': 1000, 'NFINDS': 10000, 'DIM_LB': 0, 'DIM_UB': 1000, 'SCORE_MUL': 100}
insert::NearestDict       0.125
insert::KDDict(regen)    35.957
insert::KDDict(defer)     0.174
search::NearestDict    2636.965
search::KDDict(regen)    49.965
search::KDDict(defer)    51.880

第二个测试使用了4个维度和100次插入的键。我想改变插入的次数,看看这两种方法在字典密度变化时的表现如何。

{'NDIMS': 4, 'NITER': 5, 'NELEMS': 100, 'NFINDS': 10000, 'DIM_LB': 0, 'DIM_UB': 1000, 'SCORE_MUL': 100}
insert::NearestDict       0.013
insert::KDDict(regen)     0.629
insert::KDDict(defer)     0.018
search::NearestDict     247.920
search::KDDict(regen)    44.523
search::KDDict(defer)    44.718

第三个测试使用了 100 个插入(与第二个测试一样)但是 12 个维度。我想看看这些方法如何随着关键维度的增加而执行。

{'NDIMS': 12, 'NITER': 5, 'NELEMS': 100, 'NFINDS': 10000, 'DIM_LB': 0, 'DIM_UB': 1000, 'SCORE_MUL': 100}
insert::NearestDict       0.013
insert::KDDict(regen)     0.722
insert::KDDict(defer)     0.017
search::NearestDict     405.092
search::KDDict(regen)    49.046
search::KDDict(defer)    50.601

讨论

KDDict 连续再生 (KDDict(True)) 要么稍微快一点(在查找中),要么 显着 慢(在插入中) .因此,我将其排除在讨论之外并专注于 NearestDictKDDict(False),现在简称为 KDDict

结果出人意料地支持延迟再生的 KDDict。

对于插入,在所有情况下,KDDict 的表现都比 NearestDict 稍差。这是意料之中的,因为额外的列表追加操作。

对于搜索,在所有情况下,KDDict 的表现明显优于 NearestDict

随着字典的稀疏度降低/密度增加,NearestDict 的性能下降幅度比 KDDict 大得多。从 100 个键到 1000 个键时,NearestDict 搜索时间增加了 9.64 倍,而 KDDict 搜索时间仅增加了 0.16 倍。

随着字典维度的增加,NearestDict 的性能下降幅度大于 KDDict。从 4 维到 12 维时,NearestDict 搜索时间增加了 0.64 倍,而 KDDict 搜索时间仅增加了 0.13 倍。

鉴于此,并且两者 类 的复杂性相对相等,如果您可以访问 scipy 工具包,强烈建议使用 KDDict 方法。

这是一个主要依赖map/filter操作的pythonic解决方案

class NeirestSearchDictionnary1D(dict):
    """ An extended dictionnary that returns the value that is the nearest to 
    the requested key. As it's key distance is defined for simple number 
    values, trying to add other keys will throw error. """
    def __init__(self):
        """ Constructor of the dictionnary.
        It only allow to initialze empty dict """
        dict.__init__(self)

    def keyDistance(self, key1, key2):
        """ returns a distance between 2 dic keys """
        return abs(key1-key2)

    def __setitem__(self, key, value):
        """ override  the addition of a couple in the dict."""
        #type checking
        if not (isinstance(key, int) or isinstance(key, float)):
            raise TypeError("The key of such a "+ type(self) + "must be a simple numerical value")
        else:
            dict.__setitem__(self, key, value)

    def __getitem__(self, key):
        """ Override the getting item operation """
        #compute the minial distance
        minimalDistance = min(map(lambda x : self.keyDistance(key, x), self.keys()))
        #get the list of key that minimize the distance
        resultSetKeys = filter(lambda x : self.keyDistance(key, x) <= minimalDistance, self.keys())
        #return the values binded to the keys minimizing the distances.
        return list(map(lambda x : dict.__getitem__(self, x), resultSetKeys))

if __name__ == "__main__":

    dic = NeirestSearchDictionnary1D()
    dic[1] = 100
    dic[55] = 101
    dic[57] = 102
    dic[127] = 103
    print("the entire dict :", dic)
    print("dic of '20'", dic[20])
    print("dic of '56'", dic[56])

显然,您可以轻松地将其扩展到 2D 维度。