Python -. Định vị các dấu thời gian gần nhất

Question

Tôi có một timestamp Python datetime và một dict lớn (index), nơi phím dấu thời gian và giá trị là một số thông tin khác Tôi quan tâm đến

tôi cần phải tìm ra datetime (khóa) trong chỉ mục gần nhất với dấu thời gian, càng hiệu quả càng tốt.

Tại thời điểm tôi đang làm một cái gì đó như:

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

mà làm việc, nhưng phải mất quá nhiều thời gian - index dict tôi có hàng triệu các giá trị, và tôi đang làm hàng ngàn tìm kiếm lần. Tôi linh hoạt với các cấu trúc dữ liệu và vân vân - các dấu thời gian gần như tuần tự, do đó tôi đang lặp lại từ lần đầu tiên đến dấu thời gian cuối cùng. Tương tự như vậy, dấu thời gian trong tệp văn bản mà tôi tải vào dict là tuần tự.

Mọi ý tưởng về tối ưu hóa sẽ được đánh giá rất nhiều.

Answer 1

Từ điển không được sắp xếp cho các tìm kiếm bỏ lỡ gần đúng hiệu quả. Chúng được thiết kế cho phù hợp chính xác (sử dụng hash table).

Bạn có thể cải thiện việc duy trì cấu trúc theo thứ tự riêng, có thể tìm kiếm nhanh.

Một cách đơn giản để bắt đầu là sử dụng bisect module cho O nhanh (log N) tìm kiếm nhưng O chậm (n) chèn:

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

Một cách tiếp cận phức tạp hơn thích hợp cho không tĩnh, tự động cập nhật dicts, sẽ sử dụng blist, sử dụng cấu trúc cây để chèn nhanh và tra cứu O (log N). Bạn chỉ cần điều này nếu dict sẽ thay đổi theo thời gian.

Nếu bạn muốn ở lại với một cách tiếp cận từ điển dựa, hãy xem xét một dict-of-danh sách mà cụm mục với thời gian lân cận:

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

Note, cho kết quả chính xác gần ranh giới cụm, cửa hàng gần-to- dấu thời gian ranh giới trong cả cụm chính và cụm liền kề.

Answer 2

Nếu danh sách của bạn thực sự được sắp xếp và không chỉ "gần như tuần tự", bạn có thể sử dụng tìm kiếm nhị phân. Hãy xem bisect module documentation để biết thêm thông tin.

Answer 3

đối tượng datetime có thể so sánh với nhau, do đó hãy chắc một danh sách sắp xếp các cặp khóa/giá trị của bạn như thế này:

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

Đối với mỗi phần tử myPairs[i], myPairs[i][0] là chìa khóa datetime và myPairs[i][1] là giá trị.

Bạn có thể tìm danh sách này một cách hiệu quả sử dụng bisect_left:

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

Yếu tố myPairs[i] là yếu tố với datetime thấp nhất không sớm hơn targetDatetime. Nhưng yếu tố trước (nếu có) có thể gần đúng hơn với thời gian targetDatetime. Hoặc targetDatetime có thể muộn hơn bất cứ lúc nào trong myPairs.Vì vậy, bạn cần phải kiểm tra:

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