Найти целочисленного ближайшего соседа в 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 

Есть ли питонический способ сделать это? (Я предполагаю, что это можно сделать, перейдя по всему 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 , т. Е. Ближайший сосед в 2D-плоскости.

Что-то похожее на это:

 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 

Обновление . После сопоставления двух подходов в этом ответе второй подход значительно лучше, до такой степени, что он должен быть строго предпочтительным.


Следующий подход обрабатывает 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) 

Обратите внимание: если ключ существует, поиск не медленнее, чем поиск стандартного словаря. Если ключ не существует, вы вычисляете расстояние между каждым существующим ключом. Ничто не кэшируется, хотя вы можете это сделать, я полагаю.

Редактировать:

Из подхода, предложенного ответом Кастры, следующий подход реализует тот же класс, что и выше, с помощью scipy 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) (regen on insert) и KDDict(False) (defer regen)), я кратко проверил их.

Я провел 3 разных теста. Параметры, которые остались неизменными во всех тестах:

  • Количество тестовых итераций: я каждый раз тестировал 5 раз и занимал минимальное время. (Примечание: timeit.repeat умолчанию timeit.repeat 3).
  • Границы точек: я создал целые ключевые точки в диапазоне 0 <= x <1000
  • Количество поисковых запросов: Я приурочил вставки и поиск по отдельности. Три теста ниже всех используют 10000 поисковых запросов.

В первом тесте использовались ключи из 4-х измерений и 1000 вставок.

 {'NDIMS': 4, 'NITER': 5, 'NELEMS': 1000, 'NFINDS': 10000, 'DIM_LB': 0, 'DIM_UB': 1000, 'SCORE_MUL': 100}
 Вставить :: БлижайшийDict 0.125
 вставить :: KDDict (regen) 35.957
 вставить :: KDDict (отложить) 0.174
 поиск :: БлижайшийDict 2636.965
 поиск :: KDDict (реген) 49.965
 поиск :: KDDict (отложить) 51.880

Во втором тесте использовались ключи из 4-х измерений и 100 вставок. Я хотел бы изменить количество вставок, чтобы увидеть, насколько хорошо эти два подхода выполняются по мере изменения плотности словаря.

 {'NDIMS': 4, 'NITER': 5, 'NELEMS': 100, 'NFINDS': 10000, 'DIM_LB': 0, 'DIM_UB': 1000, 'SCORE_MUL': 100}
 Вставить :: БлижайшиеDict 0.013
 insert :: KDDict (regen) 0.629
 вставить :: KDDict (отложить) 0.018
 поиск :: БлижайшиеDict 247.920
 поиск :: KDDict (regen) 44.523
 поиск :: KDDict (отложить) 44.718

В третьем тесте использовалось 100 вставок (например, второе испытание), но 12 измерений. Я хотел видеть, как подходы, выполняемые в качестве ключевой размерности, увеличились.

 {'NDIMS': 12, 'NITER': 5, 'NELEMS': 100, 'NFINDS': 10000, 'DIM_LB': 0, 'DIM_UB': 1000, 'SCORE_MUL': 100}
 Вставить :: БлижайшиеDict 0.013
 вставить :: KDDict (regen) 0.722
 вставить :: KDDict (отложить) 0.017
 поиск :: БлижайшийDict 405.092
 поиск :: KDDict (regen) 49.046
 поиск :: KDDict (отложить) 50.601

обсуждение

KDDict с непрерывной регенерацией ( KDDict(True) ) либо дробно быстрее (в поиске), либо значительно медленнее (при вставке). Из-за этого я оставляю это вне обсуждения и фокусируюсь на NearestDict и KDDict(False) , теперь называемом просто KDDict

Результаты были неожиданно в пользу KDDict с отсроченной регенерацией.

Для ввода во всех случаях KDDict выполнялся чуть хуже, чем NearestDict. Этого следовало ожидать из-за дополнительной операции добавления списка.

Для поиска во всех случаях KDDict выполнялся значительно лучше, чем NearestDict.

По мере уменьшения разрешенности словаря / плотности производительность NearestDict снизилась в гораздо большей степени, чем KDDict. При переходе от 100 ключей до 1000 ключей время поиска NearestDict увеличилось на 9,64 раза, а время поиска KDDict увеличилось всего на 0,16x.

По мере увеличения размерности словаря производительность NearestDict уменьшилась до большей степени, чем KDDict. При переходе от 4 до 12 измерений время поиска NearestDict увеличилось на 0,64x, а время поиска KDDict увеличилось всего на 0,13x.

В свете этого и относительно равной сложности двух классов, если у вас есть доступ к scipy toolkit, настоятельно рекомендуется использовать подход KDDict .

Опция 1:

Ведите отдельный и упорядоченный список ключей (или используйте OrderedDict ). Найдите ближайший ключ, используя двоичный поиск. Это должно быть O (log n) .

Вариант 2: (Если данные не очень большие и разреженные)

Поскольку вы упомянули, что dict статичен, пройдите через dict, чтобы заполнить все недостающие значения один раз . Поддерживайте максимальные и минимальные ключи и переопределяйте __getitem__ чтобы клавиши выше максимального или __getitem__ минимума возвращали правильное значение. Это должно быть 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 

Предыдущий ответ – это питонический ответ, который я предложил, но если вы ищете быстрый способ, вы можете использовать scipy.spatial.KDTree :

class scipy.spatial.KDTree (данные, leafsize = 10)

kd-дерево для быстрого поиска ближайших соседей

Этот класс предоставляет индекс в набор k-мерных точек, которые можно использовать для быстрого поиска ближайших соседей любой точки.

Также ознакомьтесь с 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

Пример Untested 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) 

Двумерный случай значительно более раздражает (вам нужно хранить ключи, упорядоченные в квадранте), но возможно аналогичным образом.

Я не кодировал удаление, чтобы иметь также поведение «близости», но вы тоже можете это сделать.

Здесь приходит одно 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-измерения с небольшой работой.