在字典中查找整数最近邻
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)]
输出与上述方法相同。
基准测试结果
为了了解三种方法(NearestDict
、KDDict(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)
) 要么稍微快一点(在查找中),要么 显着 慢(在插入中) .因此,我将其排除在讨论之外并专注于 NearestDict
和 KDDict(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 维度。
我有一个 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)
请注意,如果键存在,查找速度不会比标准字典查找慢。如果键 不 存在,则计算每个现有键之间的距离。什么都没有缓存,尽管我想你可以添加它。
编辑:
根据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)]
输出与上述方法相同。
基准测试结果
为了了解三种方法(NearestDict
、KDDict(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)
) 要么稍微快一点(在查找中),要么 显着 慢(在插入中) .因此,我将其排除在讨论之外并专注于 NearestDict
和 KDDict(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 维度。