Найти ближайшего целого числа в dict

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

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)

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

Изменить:

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

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

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

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

{'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,64x, в то время как время поиска KDDict увеличилось только на 0,13x.

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

Вариант 1:

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

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

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

класс scipy. пространственное.KDTree(данные, leafsize=10)

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

Этот класс предоставляет индекс набора 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

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