寻找一种有效的方式来存储历史数据

Question

数据是一个 Python 字典，表示随时间缓慢变化的某种状态。值经常更改，通常一次更改一两个项目。键也可以改变，但这是一个罕见的事件。每次更改后，都会记住新数据集以备将来检查。

结果是一个带有增加时间戳的长序列。“b”打开和关闭再打开的一个非常简单的例子：

(timestamp1, {'a':False, 'b':False, 'c':False}),
(timestamp2, {'a':False, 'b':True, 'c':False}),
(timestamp3, {'a':False, 'b':False, 'c':False}), 
(timestamp4, {'a':False, 'b':True, 'c':False}),

这个序列使用起来非常方便，但显然效率很低。几乎相同的数据被一遍又一遍地复制。真正的 dict 大约有 100 项。这就是为什么我正在寻找一种不同的方式来将数据历史存储在内存和磁盘上。

我很确定这个问题在过去已经解决过很多次了。这个问题有什么标准/推荐的方法吗？解决方案不一定是完美的。足够好就足够了。

---

这就是我会做的，除非某个善良的灵魂显示出更好的方法。仅存储增量更改可节省空间：

(timestamp1, FULL, {'a':False, 'b':False, 'c':False}),
(timestamp2, INCREMENTAL, {'b':True}),
(timestamp3, INCREMENTAL, {'b':False}),
(timestamp4, INCREMENTAL, {'b':True}),

然而，数据并不容易访问，因为它必须从最后的 FULL 状态分几个步骤恢复。为了限制缺点，每个第 N 条记录将存储为 FULL，所有其他记录为 INCREMENTAL。

我可能会添加这个小改进：添加对已记录的相同状态的引用以防止重复：

(timestamp1, FULL, {'a':False, 'b':False, 'c':False}),
(timestamp2, INCREMENTAL, {'b':True}),
(timestamp3, SAME_AS, timestamp1),
(timestamp4, SAME_AS, timestamp2),

Answer 1

一种更节省空间的方法是为每个“列”数据保留一组。也就是说，我们为 、 和 列保留a一b组c。该集跟踪列值的时间戳True。例如，对于数据：

(timestamp1, {'a':False, 'b':False, 'c':False}),
(timestamp2, {'a':False, 'b':True, 'c':False}),
(timestamp3, {'a':False, 'b':False, 'c':False}), 
(timestamp4, {'a':False, 'b':True, 'c':False}),

列的集合a将为空，列的集合b将包含时间戳 2 和 4，并且列的集合c将再次为空。

请注意，这或多或少是存储稀疏二进制向量可能采取的方法。我们不存储整个向量，而是只跟踪向量为 1 的位置。事实上，您可能需要考虑使用稀疏矩阵数据类型SciPy中的稀疏矩阵数据类型。

集提供高效（恒定时间）的成员资格查找，因此这也是一种节省时间的方法。

为了使数据易于访问，您可以编写一个包装集合的小类。例如：

class SparseStates(object):

    def __init__(self, columns):
        self.data = {col: set() for col in columns}

    def __getitem__(self, key):
        row, column = key
        return row in self.data[column]

    def turn_on(self, row, column):
        self.data[column].add(row)

用法：

>>> states = SparseStates(['a', 'b', 'c'])
>>> states.turn_on(2, 'b')
>>> states.turn_on(4, 'b')
>>> states[2, 'a']
False
>>> states[2, 'b']
True
>>> states.data['a']
{}
>>> states.data['b']
{2, 4}