Estoy usando defaultdicts para almacenar listas de valores donde keys son períodos para los que se pueden observar valores. Al buscar en una lista de todos los períodos de interés, me gustaría encontrar el período más cercano en mi defaultdict (NB: no todos los períodos se almacenan en el defaultdict).

Sin embargo, como los dictados predeterminados no están ordenados, el siguiente enfoque no devuelve el valor correcto.

¿Hay alguna forma diferente de devolver la clave disponible más cercana para los códigos predeterminados?

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)

Esto devuelve lo siguiente:

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
0
Andreas 16 feb. 2017 a las 11:28

4 respuestas

La mejor respuesta

Según tengo entendido, ¿quieres una salida similar a esta?

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

Por lo anterior, la lógica sería

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

Especificar el parámetro opcional key para las funciones integradas de Python es útil en situaciones como estas.

1
septra 16 feb. 2017 a las 08:42

Estoy de acuerdo con @septra en que necesita la distancia euqlidean, pero eso también se puede lograr con 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])
1
Piotr Kamoda 16 feb. 2017 a las 08:51

Con un OrderedDict y claves ordenadas, puede usar una búsqueda binaria. Para una gran cantidad de claves, la búsqueda sería mucho más rápida que su método actual.

Como desea la tecla más cercana, necesitaría encontrar la tecla más a la derecha más baja que x y la tecla más a la izquierda más alta que x. Después de encontrar el índice i para la tecla más a la derecha más baja que x, el otro candidato (la tecla más a la izquierda más alta que x) estará en el índice i+1.

Debe asegurarse de que esos índices todavía estén en su matriz.

Finalmente, solo necesita calcular la distancia a x de esos 2 valores.

Aquí está el documento para bisect y np.searchsorted

2
Eric Duminil 16 feb. 2017 a las 08:57

Como dijo Eric, para hacer esto de manera eficiente, debería usar una búsqueda binaria. Sin embargo, si el número de teclas es pequeño, la búsqueda lineal simple puede ser adecuada. No es necesario usar un defaultdict o un OrderedDict, solo ordena las claves.

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)

salida

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
1
PM 2Ring 16 feb. 2017 a las 09:02