Python -. Localización de la marca de tiempo más cercano

Question

tengo una marca de tiempo de fecha y hora Python y un diccionario grande (índice) donde las claves son marcas de tiempo y los valores son alguna otra información que me interesa

Tengo que encontrar la fecha y hora (la clave) en el índice más cercano a la marca de tiempo, de la manera más eficiente posible.

En el momento que estoy haciendo algo como:

for timestamp in timestamps: 
    closestTimestamp = min(index,key=lambda datetime : abs(timestamp - datetime)) 

que funciona, pero toma demasiado tiempo - mi índice dict tiene millones de valores, y estoy haciendo los de búsqueda miles de veces. Soy flexible con las estructuras de datos y demás, las indicaciones de tiempo son más o menos secuenciales, de modo que estoy iterando desde la primera hasta la última marca de tiempo. Del mismo modo, las marcas de tiempo en el archivo de texto que cargué en el dict son secuenciales.

Cualquier idea para la optimización sería muy apreciada.

Answer 1

Los diccionarios no están organizados para realizar búsquedas eficientes de casi errores. Están diseñados para coincidencias exactas (usando un hash table).

Es posible que sea mejor mantener una estructura ordenada de búsqueda rápida separada.

Una forma sencilla de empezar es utilizar el bisect module para O rápido (log N) búsquedas, pero O más lento (N) inserciones:

def nearest(ts): 
    # Given a presorted list of timestamps: s = sorted(index) 
    i = bisect_left(s, ts) 
    return min(s[max(0, i-1): i+2], key=lambda t: abs(ts - t)) 

Un enfoque más sofisticado adecuado para no estático, actualizados dinámicamente dicts, sería usar blist que emplea una estructura de árbol para inserciones y búsquedas rápidas O (log N). Solo necesita esto si el dict va a cambiar con el tiempo.

Si desea quedarse con un enfoque basado en diccionario, considere un diccionario-de-listas que los cúmulos entradas con marcas de tiempo cercanas:

def get_closest_stamp(ts): 
     'Speed-up timestamp search by looking only at entries in the same hour' 
     hour = round_to_nearest_hour(ts) 
     cluster = daydict[hour]   # return a list of entries 
     return min(cluster, key=lambda t: abs(ts - t)) 

Nota, para obtener resultados exactos cerca de los límites de racimo, almacenar cerca-a las marcas de tiempo del límite tanto en el clúster primario como en el clúster adyacente.

Answer 2

Si su lista está realmente ordenada y no solo "aproximadamente secuencial", puede utilizar una búsqueda binaria. Eche un vistazo a bisect module documentation para más información.

Answer 3

objetos de fecha y hora son comparables entre sí, por lo que hacen una lista ordenada de sus pares clave/valor como esto:

myPairs = list(dict.iteritems()) 
myPairs.sort() 

Para cada elemento myPairs[i], myPairs[i][0] es la clave datetime y myPairs[i][1] es el valor.

Puede buscar en esta lista de manera eficiente utilizando bisect_left:

import bisect 
i = bisect.bisect_left(myPairs, targetDatetime) 

El elemento myPairs[i] es el elemento que no tenía antes de la fecha y hora targetDatetime más bajo. Pero el elemento anterior (si hay uno) podría estar más cerca en el tiempo a targetDatetime. O targetDatetime podría ser posterior a cualquier momento en myPairs.Entonces necesita verificar:

if i > 0 and i == len(myPairs): 
    i -= 1 
elif i > 0 and targetDatetime - myPairs[i-1][0] < myPairs[i][0]- targetDatetime: 
    i -= 1