Thuật toán trong Python để lưu trữ và tìm kiếm sự xuất hiện hàng ngày cho hàng nghìn sự kiện được đánh số?

Question

Tôi đang điều tra các giải pháp lưu trữ và truy vấn hồ sơ lịch sử về các sự kiện xảy ra đối với một số lượng lớn các mục.

Đây là kịch bản đơn giản: Tôi nhận nhật ký hàng ngày 200 000 đèn đường (có nhãn sl1 đến sl200000) cho biết đèn có hoạt động vào ban ngày hay không. Nó không quan trọng trong bao lâu thì đèn chỉ phục vụ cho nó trong một ngày dương lịch nhất định.

bit thông tin khác được lưu trữ cho mỗi đèn là tốt và đầu của lớp Python trông giống như sau:

class Streetlamp(object): 
    """Class for streetlamp record""" 
    def __init__(self, **args): 
     self.location = args['location'] 
     self.power = args['power'] 
     self.inservice = ??? 

My py-foo không phải là quá lớn và tôi muốn tránh một giải pháp đó là quá tham lam trên đĩa/bộ nhớ lưu trữ. Vì vậy, một giải pháp với một dict của (năm, tháng, ngày) tuples có thể là một trong những giải pháp, nhưng tôi hy vọng sẽ nhận được con trỏ cho một giải pháp hiệu quả hơn.

Một hồ sơ có thể được lưu trữ như một dòng bit với mỗi bit đại diện cho một ngày của một năm bắt đầu với Jan 1. Do đó, nếu một chiếc đèn đã hoạt động trong ba ngày đầu tiên của năm 2010, sau đó các bản ghi có thể là:

sl1000_up = dict('2010': '11100000000000...', '2011':'11111100100...') 

Tìm kiếm qua các ranh giới năm sẽ cần hợp nhất, năm nhuận là trường hợp đặc biệt, cộng với tôi cần mã/giải mã bit công bằng với giải pháp được trồng tại nhà này. Có vẻ như không yên tĩnh. speed-up-bitstring-bit-operations, how-do-i-find-missing-dates-in-a-list và finding-data-gaps-with-bit-masking nơi các bài đăng thú vị tôi đã xem qua. Tôi cũng điều tra python-bitstring và đã làm một số googling, nhưng không có gì có vẻ thực sự phù hợp.

Ngoài ra, tôi muốn tìm kiếm 'các khoảng trống' để có thể, ví dụ: 'ba ngày trở lên không hoạt động' và điều quan trọng là ngày gắn cờ có thể được chuyển đổi thành ngày theo lịch thực.

Tôi sẽ đánh giá cao ý tưởng hoặc gợi ý cho các giải pháp khả thi. Để bổ sung thêm chi tiết, nó có thể được quan tâm mà DB back-end được sử dụng là ZODB và các đối tượng Python thuần túy có thể được chọn được ưu tiên.

Answer 1

Tạo một 2D-mảng trong NumPy:

import numpy as np 

nbLamps = 200000 
nbDays = 365 

arr = np.array([nbLamps, nbDays], dtype=np.bool) 

Nó sẽ rất nhớ hiệu quả và bạn có thể tổng hợp một cách dễ dàng những ngày và đèn.

Để thao tác ngày tốt hơn, hãy xem scikits.timeseries. Chúng sẽ cho phép bạn truy cập ngày tháng với các đối tượng datetime.

Answer 2

Tôi có thể đã từ điển các loại đèn và mỗi danh sách chứa danh sách các thay đổi trạng thái trong đó phần tử đầu tiên là thời gian thay đổi và giá trị thứ hai hợp lệ kể từ thời điểm đó.

Bằng cách này, khi bạn đến mẫu tiếp theo, bạn không làm gì trừ khi trạng thái thay đổi so với mục cuối cùng.

Tìm kiếm nhanh chóng và hiệu quả vì bạn có thể sử dụng phương pháp tìm kiếm nhị phân vào các thời điểm.

Tính bền vững cũng dễ dàng và bạn có thể nối dữ liệu vào hệ thống hiện có và đang chạy mà không gặp bất kỳ vấn đề nào cũng như từ điển danh sách trạng thái đèn để giảm mức sử dụng tài nguyên.

Nếu bạn muốn tìm kiếm một khoảng trống bạn chỉ cần xem qua tất cả các mục và so sánh thời gian tiếp theo và trước - và nếu bạn quyết định từ điển danh sách trạng thái thì bạn sẽ có thể thực hiện nó một lần danh sách thay vì sau đó mỗi đèn và sau đó nhận được tất cả các đèn có trạng thái "ngoại tuyến" giống nhau chỉ với một lần lặp đôi khi có thể giúp