Python中用于存储和搜索数千个编号事件的每日发生情况的算法？

Question

我正在研究存储和查询大量物品的历史事件发生记录的解决方案。

这是简化的情况：我每天获得200,000个街灯（标记为sl1至sl200000）的日志，显示该灯是否在当天正常运行。不重要的是灯的使用时间有多长，只要它在给定的日历日里开启即可。

还为每个灯存储了其他信息，Python类的开头看起来像这样：

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

我的py-foo不太好，我想避免使用过多的磁盘/内存空间。因此，一个包含(年份，月份，日期)元组字典的解决方案可能是一种选择，但我希望得到更有效的解决方案的指针。

记录可以存储为位流，每个位代表从1月1日开始的一年中的一天。因此，如果一个灯在2010年的前三天运行，那么记录可以如下表示：

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

跨年搜索需要合并，闰年是一个特殊情况，另外我需要编码/解码一些东西来完成这个自制的解决方案。看起来不太对。我遇到了有趣的帖子：speed-up-bitstring-bit-operations、how-do-i-find-missing-dates-in-a-list 和 finding-data-gaps-with-bit-masking。我还调查了python-bitstring并进行了一些搜索，但似乎没有真正适合的。

此外，我希望搜索“间隙”成为可能，例如“三天或更长时间停机”，而且将标记的日期转换为实际日历日期非常重要。

我会欣赏任何想法或指向可能解决方案的指针。进一步详细说明，后端DB使用的是ZODB和纯Python对象，可以被pickle。

- Axial

Answer 1

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

import numpy as np

nbLamps = 200000
nbDays = 365

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

这将非常节省内存，并且您可以轻松聚合天数和灯具。

为了更好地操作天数，请查看scikits.timeseries。它们将允许您使用datetime对象访问日期。

- eumiro

---

感谢指出scikits.timeseries库。它似乎支持我必须做的大部分分析。将一年中所有灯存储在一个数组中不太可行，因为我宁愿将一个灯的记录存储在实例化对象中。但是，这应该很容易适应，并且使用numpy，我无需重新发明轮子。只有Python新手才会忽视这个包;-) - Axial

值得知道的是，numpy中的布尔型数据存储为一个完整的字节，因此这可能并不像看起来那样内存高效。 - Scott Griffiths

Answer 2

我会使用字典来存储灯的状态变化列表，其中第一个元素是变化时间，第二个元素是自那时起有效的值。

这样，当你到达下一个样本时，除非与上一个项目相比状态发生了变化，否则不做任何操作。

搜索快速高效，可以在时间上使用二进制搜索方法。

持久化也很容易，您可以将数据附加到现有运行系统中而不会出现任何问题，还可以对灯状态列表进行字典处理以进一步减少资源使用。

如果要搜索间隙，只需遍历所有项目并比较下一个和前一个时间-如果决定对状态列表进行字典处理，则每个不同列表只需执行一次，而不是每个灯，然后获取所有具有相同“离线”状态的灯，这可能有时会有所帮助。

- RnR

---

谢谢！我喜欢这个解决方案很容易扩展。记录可以很好地存储。不过，我还需要编写一些脚手架代码，这些可能已经存在于pyland（也许是某些科学数据计算模块）中。 - Axial