Поиск ближайшего ключа в defaultdict

Question

Я использую defaultdicts для хранения списков значений, где keys - это периоды, для которых значения могут быть соблюдены. Когда вы просматриваете список всех периодов интереса, я хотел бы найти ближайший период в моем defaultdict (NB: не все периоды хранятся в defaultdict).

Так как defaultdicts не сортируются, то нижний подход не возвращает правильное значение.

Есть ли другой способ возврата ближайшего доступного ключа для defaultdicts?

from collections import defaultdict 
import numpy as np 

def_dict = defaultdict(list) 
# entries that will be stored in the defaultdict 
reg_dict = {0: ["a", "b"], 2: ["c", "d"], 5: ["k", "h"], -3: ["i", "l"]} 

# store items from regular dict in defaultdict 
for k, v in reg_dict.items(): 
    def_dict[k] = v 

# Lookup periods 
periods = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8] 

for period in periods: 

    # this approach does not return the right keys as defaultdicts are not sorted 
    closest_key = np.abs(np.array(list(def_dict.keys())) - period).argmin() 

    print("period: ", period, " - looked up key: ", closest_key) 

Это возвращает следующее:

period: -1 - looked up key: 0 
period: 0 - looked up key: 0 
period: 1 - looked up key: 0 
period: 2 - looked up key: 1 
period: 3 - looked up key: 1 
period: 4 - looked up key: 2 
period: 5 - looked up key: 2 
period: 6 - looked up key: 2 
period: 7 - looked up key: 2 
period: 8 - looked up key: 2 

Answer 1

То, как я понимаю, вы хотите вывод, подобный этому?

[0, 0, 0, 2, 2, 5, 5, 5, 5, 5] 

Для выше, логика была бы

closest_key = [min(def_dict.keys(), key = lambda x: abs(x - p)) for p in periods] 

Задание дополнительного key параметра для встроенных функций питона полезно в подобных ситуациях.

Answer 2

Я согласен с @septra, что вам нужно euqlidean расстояния, но это достижимо с NumPy, а также:

from collections import defaultdict 
import numpy as np 

def_dict = defaultdict(list) 
# entries that will be stored in the defaultdict 
reg_dict = {0: ["a", "b"], 2: ["c", "d"], 5: ["k", "h"], -3: ["i", "l"]} 

# store items from regular dict in defaultdict 
for k, v in reg_dict.items(): 
    def_dict[k] = v 

periods = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8] 
a = list(def_dict.keys()) 
for period in periods: 
    closest_key = np.sqrt(np.power(np.add(a, -period),2)).argmin() 
    # OR closest_key = np.abs(np.add(a, -period)).argmin() 

    print("period: ", period, " - looked up key: ", a[closest_key]) 

Answer 3

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

Поскольку вам нужен ближайший ключ, вам нужно найти как самую правую клавишу ниже, чем x, так и самую левую клавишу выше, чем x. После нахождения индекса i для самой правой клавиши ниже x, другой кандидат (крайняя левая клавиша выше x) будет на индексе i+1.

Вам необходимо убедиться, что эти индексы все еще находятся в вашем массиве.

Наконец, вам просто нужно вычислить расстояние до x от этих двух значений.

Вот документ для bisect и np.searchsorted

Answer 4

Как сказал Эрик, чтобы сделать это эффективно вы должны использовать бинарный поиск. Однако, если количество клавиш невелико, простой линейный поиск может быть достаточным. Нет необходимости использовать defaultdict или OrderedDict, просто отберите ключи.

import numpy as np 

# entries 
reg_dict = {0: ["a", "b"], 2: ["c", "d"], 5: ["k", "h"], -3: ["i", "l"]} 

keys = np.array(sorted(reg_dict.keys())) 
print('keys', keys) 

# Lookup periods 
periods = np.arange(-1, 9) 

for period in periods: 
    closest_key = keys[np.abs(keys - period).argmin()] 
    print("period: ", period, " - looked up key: ", closest_key) 

выход

keys [-3 0 2 5] 
period: -1 - looked up key: 0 
period: 0 - looked up key: 0 
period: 1 - looked up key: 0 
period: 2 - looked up key: 2 
period: 3 - looked up key: 2 
period: 4 - looked up key: 5 
period: 5 - looked up key: 5 
period: 6 - looked up key: 5 
period: 7 - looked up key: 5 
period: 8 - looked up key: 5