Check if huge list in python has changed

问题:

In short: what's the fasted way to check if a huge list in python has changed? hashlib needs a buffer, and building a string representation of that list is unfeasible.

In long: I've got a HUGE list of dictionaries representing data. I run a number of analyses on this data, but there are a few meta-data aspects that are required by all of the analyses, ie. the the set of subjects (each dict in the list has a subject key, and at times I just need a list of all subject who have data present in the data set.). So I'd like to implement the following:

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

The question is how to implement the has_changed method, or more specifically, get_hash (each object already has a __hash__ method, but by default it just returns the object's id, which doesn't change when we e.g. append an element to a list).

回答1:

A more sophisticated approach there would be to work with proxy data elements instead of native lists and dictionaries, which could flag any change to their attributes. To make it more flexible, you could even code a callback to be used in case of any changes.

So, assuming you only have to deal with lists and dictionaries on your data structure - we can work with classes inheriting from dict and list with a callback when any data changing method on the object is accessed The full list of methods is in 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 update

One does live and learn: native lists can be changed by native methods by calls that bypass the magic methods. The fool proof system is the same approach, but inheriting from collections.abc.MutableSequence instead, nd keeping a native list as an internal attribute of your proxy object.

回答2:

You can easily get the string representation of any object using the pickle library, and then pass it to hashlib, as you said:

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))

So, that's a way, I don't know if it's the fastest way. It will work for arbitrary objects. But, as agf said, in your case it would certainly be more efficient if you could use a variable has_changed that you modify each time you actually modify data.

回答3:

hashlib needs a buffer, and building a string representation of that list is unfeasible.

You can update hash in many steps:

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

So, you don't need to convert all the list to a string representation. You just iterate over it, converting to string only one item and calling update.