Python. - Lokalizowanie najbliższy znacznik czasu

Question

Mam timestamp datetime Python i dużą dict (indeks), gdzie klucze są znaczniki czasu, a wartości są inne informacje Jestem zainteresowany

muszę odnaleźć datetime (klucz) w indeksie, który jest najbliżej znacznika czasu, tak skutecznie, jak to możliwe.

W tej chwili robię coś takiego:

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

który działa, ale trwa zbyt długo - mój indeks DICT ma miliony wartości, a robię tysiące wyszukiwania razy. Jestem elastyczny w strukturach danych i tak dalej - znaczniki czasowe są z grubsza sekwencyjne, więc jestem iteracji od pierwszego do ostatniego znacznika czasu. Podobnie znaczniki czasowe w pliku tekstowym, które ładuję do dyktafonu, są sekwencyjne.

Wszelkie pomysły na optymalizację byłyby bardzo mile widziane.

Answer 1

Słowniki nie są zorganizowane do skutecznych wyszukiwań w pobliżu miss. Są one przeznaczone do dokładnych dopasowań (przy użyciu hash table).

Być może lepiej sobie radzisz z utrzymaniem osobnej, szybko porządanej struktury.

Prostym sposobem na rozpoczęcie jest użycie bisect module do szybkiego O (log N) wyszukiwania, ale wolniej O (N) wstawki:

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)) 

Bardziej wyrafinowane podejście nadaje się do non-static, dynamicznie aktualizowane dyktować, będzie używał blist, który wykorzystuje strukturę drzewa do szybkiego wstawiania i wyszukiwania O (log N). Potrzebujesz tego tylko wtedy, gdy dyktatura zmieni się z czasem.

Jeśli chcesz pozostać z podejściem słowniku oparte rozważmy dict-of-list, że klastry wpisy z pobliskich znaczników czasu:

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)) 

Uwaga, do dokładnych wyników pobliżu granic klastra sklepu bliską-to- graniczne znaczniki czasu zarówno w klastrze podstawowym, jak i w sąsiednim klastrze.

Answer 2

Jeśli Twoja lista jest prawdziwie posortowana, a nie tylko "z grubsza sekwencyjnie", możesz użyć wyszukiwania binarnego. Zajrzyj do bisect module documentation, aby uzyskać więcej informacji.

Answer 3

obiektów datetime są porównywalne do siebie, więc upewnij posortowaną listę swoich par klucz/wartość takiego:

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

Dla każdego elementu myPairs[i], myPairs[i][0] jest kluczem datetime i myPairs[i][1] jest wartością.

Możesz szukać tej listy efektywne wykorzystanie bisect_left:

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

Element myPairs[i] jest elementem o najniższej nie wcześniej niż targetDatetime datetime. Ale poprzedni element (jeśli taki istnieje) może być bliżej w czasie do targetDatetime. Lub targetDatetime może być późniejszy niż kiedykolwiek w myPairs.Musisz więc sprawdzić:

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