अजगर -। निकटतम टाइमस्टैम्प

Question

मैं एक अजगर datetime टाइमस्टैम्प और एक बड़े dict (इंडेक्स) है जहां कुंजी timestamps हैं और मूल्यों कुछ अन्य जानकारी मैं में दिलचस्पी रखता हूँ कर रहे हैं पता लगाने

मैं datetime को खोजने के लिए (की जरूरत है कुंजी) इंडेक्स में जो टाइमस्टैम्प के सबसे नज़दीक है, जितनी संभव हो उतनी कुशलता से।

पल मैं की तरह कुछ कर रहा हूँ पर

:

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

जो काम करता है, लेकिन बहुत समय लगता है - मेरी सूचकांक dict मूल्यों के लाखों लोगों की है, और मैं समय की खोज हजारों कर रहा हूँ। मैं डेटा संरचनाओं के साथ लचीला हूं और इसी तरह - टाइमस्टैम्प लगभग अनुक्रमिक हैं, ताकि मैं पहले से आखिरी टाइमस्टैम्प से पुनरावृत्ति कर रहा हूं। इसी प्रकार पाठ फ़ाइल में टाइमस्टैम्प जो मैं निर्देश में लोड करता हूं अनुक्रमिक होता है।

अनुकूलन के लिए कोई भी विचार बहुत सराहना की जाएगी।

Answer 1

शब्दकोश मिस खोजों के पास कुशलता के लिए व्यवस्थित नहीं हैं। वे सटीक मिलान के लिए डिज़ाइन किए गए हैं (hash table का उपयोग करके)।

आप एक अलग, तेज़-खोज योग्य आदेश संरचना को बनाए रखने के लिए बेहतर हो सकते हैं।

शुरू करने के लिए एक आसान तरीका तेजी से हे के लिए bisect module उपयोग करने के लिए है (लॉग एन) खोजें लेकिन धीमी हे (एन) सम्मिलन:

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

एक और अधिक परिष्कृत गैर स्थिर के लिए उपयुक्त दृष्टिकोण, गतिशील रूप से अद्यतन dicts, blist का उपयोग करना होगा जो तेजी से ओ (लॉग एन) सम्मिलन और लुकअप के लिए वृक्ष संरचना को नियोजित करता है। यदि आप समय के साथ बदलना चाहते हैं तो आपको केवल इसकी आवश्यकता है।

आप एक शब्दकोश आधारित दृष्टिकोण के साथ रहना चाहते हैं, एक dict के- सूचियों कि आस-पास के टाइमस्टैम्प के साथ प्रविष्टियों समूहों पर विचार करें:

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

ध्यान दें, क्लस्टर सीमाओं के निकट सटीक परिणाम के लिए, दुकान बंद हैं- प्राथमिक क्लस्टर और आसन्न क्लस्टर दोनों में सीमा टाइमस्टैम्प।

Answer 2

यदि आपकी सूची वास्तव में क्रमबद्ध है और न केवल "लगभग अनुक्रमिक" है, तो आप एक बाइनरी खोज का उपयोग कर सकते हैं। अधिक जानकारी के लिए bisect module documentation पर एक नज़र डालें।

Answer 3

datetime वस्तुओं एक दूसरे से तुलना के योग्य हैं, इसलिए इस तरह अपने कुंजी/मान जोड़े का एक क्रमबद्ध सूची बनाने: प्रत्येक तत्व myPairs[i] लिए

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

, myPairs[i][0]datetime कुंजी है और myPairs[i][1] मूल्य है।

आप इस सूची कुशलतापूर्वक bisect_left का उपयोग करके खोज कर सकते हैं:

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

तत्व myPairs[i] न्यूनतम datetime targetDatetime से पहले कोई साथ तत्व है। लेकिन पूर्व तत्व (यदि कोई है तो) targetDatetime पर समय के करीब हो सकता है। या targetDatetimemyPairs में किसी भी समय बाद में हो सकता है।तो आपको यह जांचना होगा:

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