用Python实现存储和查询数千个编号事件每日发生情况的算法？

Question

我正在研究如何存储和查询大量物品的历史事件记录。

这是一个简化的场景：我每天会收到20万个路灯的日志（从sl1到sl200000），记录每盏灯在那一天是否正常工作。只要知道某一天灯是亮的就可以，不用关心它工作了多长时间。

每盏灯还有其他一些信息，Python类的开头大概是这样的：

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

我的Python水平不太高，希望能找到一种不太占用磁盘和内存的解决方案。所以用一个包含（年、月、日）元组的字典可能是一个办法，但我希望能找到更高效的方案。

可以把记录存储为一个比特流，每个比特代表一年中的一天，从1月1日开始。因此，如果一盏灯在2010年的前面三天是亮的，那么记录可能是：

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

跨年查询需要合并，闰年是个特殊情况，而且我还需要自己编写很多代码来编码和解码这个自制的方案。感觉这样不太对。加速比特串操作、如何在排序日期列表中找到缺失的日期和使用位掩码查找数据缺口是我看到的一些有趣的帖子。我还研究了python-bitstring，并做了一些搜索，但似乎没有什么真正合适的。

另外，我希望能够搜索“缺口”，比如“连续三天或更多天没有工作”，而且必须能够将标记的日期转换为真实的日历日期。

我会很感激任何想法或可能的解决方案的提示。补充一下，使用的后端数据库是ZODB，优先考虑可以被序列化的纯Python对象。

Answer 1

我可能会把灯的状态放在一个字典里，每个灯都有一个状态变化的列表，列表的第一个元素是变化发生的时间，第二个元素是从那个时间开始有效的状态值。

这样，当你处理下一个样本时，只有在状态和上一个样本不一样的时候才需要做什么。

查找状态变化很快也很高效，因为你可以用二分查找的方法来查找时间。

保存这些数据也很简单，你可以在一个正在运行的系统中添加数据而不会出现问题，同时把灯的状态列表放在字典里，这样可以进一步减少资源的使用。

如果你想查找状态之间的间隔，只需遍历所有的项，比较前后两个时间。如果你把状态列表放在字典里，那么你只需要对每个不同的列表进行一次比较，而不是每个灯都比较一次，这样就能一次性找到所有状态为“离线”的灯，这样有时会更有效率。

Answer 2

在Numpy中创建一个二维数组：

import numpy as np

nbLamps = 200000
nbDays = 365

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

这样做会非常节省内存，而且你可以很方便地对天数和灯具进行汇总。

为了更好地处理日期，可以看看 scikits.timeseries。这个工具可以让你用日期时间对象来访问日期。