Python中如何检查大型列表是否已更改

Question

简短地说：在Python中，检查一个巨大列表是否发生了改变的最快方法是什么？使用hashlib需要一个缓冲区，而构建该列表的字符串表示形式是不可行的。

长话短说：我有一个包含数据的巨大字典列表。我对这些数据进行了许多分析，但有一些元数据方面是所有分析都必需的，即受试者集合（列表中每个字典都有一个主题键，并且有时我只需要数据集中所有具有数据的主题列表）。所以我想要实现以下内容：

class Data:
    def __init__(self, ...):
        self.data = [{...}, {...}, ...] # long ass list of dicts
        self.subjects = set()
        self.hash = 0

    def get_subjects(self):
        # recalculate set of subjects only if necessary
        if self.has_changed():
            set(datum['subject'] for datum in self.data)

        return self.subjects

    def has_changed(self):
        # calculate hash of self.data
        hash = self.data.get_hash() # HOW TO DO THIS?
        changed = self.hash == hash
        self.hash = hash # reset last remembered hash
        return changed

问题在于如何实现has_changed方法，或更具体地说，get_hash方法（每个对象已经有一个__hash__方法，但默认情况下它只返回对象的id，当我们向列表中添加元素时，该值不会改变）。

- Manuel Ebert

---

你的 change_data 方法是什么样子的？另外，self.subjects 可以这样构建：self.subjects = set(datum['subject'] for datum in self.data)。 - eumiro

我认为你可能需要提供更多的细节。你是否有旧版本和新版本？你能使用frozendicts吗？顺序很重要吗？你的代码是否创建这些更改？ - Marcin

你可以创建一个 has_changed 实例变量，每当你更改 data 时设置它。否则，你可能需要一个代理对象来委托除了 has_changed 之外的所有操作给真正的 data。 - agf

除了问题本身，还有一个需要注意的地方：让你的Data类继承自"object"，否则你可能会在需要更多Python面向对象机制支持时遇到难以识别的微妙错误。 - jsbueno

更具体地说，识别列表是否发生了变化相对容易 - 如果该列表中包含的任何对象的ID发生变化，则会发生变化。您似乎需要被通知列表上所有可变嵌套元素的任何更改，是吗？ - jsbueno

Answer 1

一个更加复杂的方法是使用代理数据元素而不是本地列表和字典，这些元素可以标记其属性的任何更改。为了使其更灵活，您甚至可以编写回调函数以在发生任何更改时使用。

因此，假设您只需要处理数据结构上的列表和字典 - 我们可以使用从dict和list继承的类，并在访问对象上的任何数据更改方法时使用回调。完整的方法列表在http://docs.python.org/reference/datamodel.html中。

# -*- coding: utf-8 -*-
# String for doctests and  example:
"""
            >>> a = NotifierList()
            >>> flag.has_changed
            False
            >>> a.append(NotifierDict())
            >>> flag.has_changed
            True
            >>> flag.clear()
            >>> flag.has_changed
            False
            >>> a[0]["status"]="new"
            >>> flag.has_changed
            True
            >>> 

"""


changer_methods = set("__setitem__ __setslice__ __delitem__ update append extend add insert pop popitem remove setdefault __iadd__".split())


def callback_getter(obj):
    def callback(name):
        obj.has_changed = True
    return callback

def proxy_decorator(func, callback):
    def wrapper(*args, **kw):
        callback(func.__name__)
        return func(*args, **kw)
    wrapper.__name__ = func.__name__
    return wrapper

def proxy_class_factory(cls, obj):
    new_dct = cls.__dict__.copy()
    for key, value in new_dct.items():
        if key in changer_methods:
            new_dct[key] = proxy_decorator(value, callback_getter(obj))
    return type("proxy_"+ cls.__name__, (cls,), new_dct)


class Flag(object):
    def __init__(self):
        self.clear()
    def clear(self):
        self.has_changed = False

flag = Flag()

NotifierList = proxy_class_factory(list, flag)
NotifierDict = proxy_class_factory(dict, flag)

2017更新

人终究是要不断学习的：本地列表可以通过绕过魔术方法的调用来改变。一个防错系统采用相同的方法，但是继承自collections.abc.MutableSequence，并将本地列表作为代理对象的内部属性。

- jsbueno

---

我十分赞同这种方法。如果事后检测变化太昂贵（你的描述明确表明是这种情况），那就随着变化追踪它们。使用哈希指纹作为Nkosinathi最初尝试的原因在于，如果您需要保留多个版本的缓存并需要一种唯一标识它们的方式。如果您只是检测更改，则此方法更加适合。 - Patrick M

Answer 2

您可以使用pickle库轻松获取任何对象的字符串表示形式，然后像您所说的那样将其传递给hashlib：

import pickle
import hashlib

data = []
for i in xrange(100000):
    data.append({i:i})

print hashlib.md5(pickle.dumps(data))

data[0] = {0:1}
print hashlib.md5(pickle.dumps(data))

所以，这是一种方法，我不知道它是否是最快的方式。它适用于任意对象。但是，正如agf所说，在您的情况下，如果您可以使用变量has_changed，每次实际修改数据时都会修改该变量，那么肯定会更有效率。

- François

---

确实可以工作，但速度非常慢。 问题在于我并不总是知道操作是否会改变列表（而且我使用的许多分析都是其他人编写的，更改所有这些分析是不可行的）。 函数甚至不必完全准确，快速执行“has_probably_changed”即可。 - Manuel Ebert

Answer 3

hashlib需要一个缓冲区，并且构建该列表的字符串表示不可行。您可以分多步update哈希值。

>>> import hashlib
>>> m = hashlib.md5()
>>> m.update("Nobody inspects")
>>> m.update(" the spammish repetition")

所以，您不需要将整个列表转换为字符串表示。您只需迭代它，只转换一个项目为字符串并调用update即可。

- warvariuc