дельта-словарь / словарь с ревизией осведомленности в Python? - PullRequest
Новая
       9

дельта-словарь / словарь с ревизией осведомленности в Python?

3 голосов
/ 16 апреля 2010

Я хочу создать словарь с возможностями отката в Python. Словарь будет начинаться с номера ревизии 0, а ревизия будет увеличена только при явном вызове метода. Мне не нужно удалять ключи, только добавить и обновить ключ, пары значений, а затем откат. Мне никогда не нужно будет «катиться вперед», то есть при откате словаря все новые ревизии могут быть отброшены, и я могу снова начать пополнять счет. таким образом я хочу поведение как: 

>>> rr = rev_dictionary()
>>> rr.rev
0
>>> rr["a"] = 17
>>> rr[('b',23)] = 'foo'
>>> rr["a"]
17
>>> rr.rev
0
>>> rr.roll_rev()
>>> rr.rev
1
>>> rr["a"]
17
>>> rr["a"] = 0
>>> rr["a"]
0
>>> rr[('b',23)]
'foo'
>>> rr.roll_to(0)
>>> rr.rev
0
>>> rr["a"]
17
>>> rr.roll_to(1)
Exception ...

Просто чтобы прояснить, состояние, связанное с ревизией, является состоянием словаря непосредственно перед вызовом метода roll_rev(). таким образом, если я могу изменить значение, связанное с ключом, несколько раз «в пределах» ревизии и запомнить только последний из них.

Я хотел бы реализовать реализацию с эффективным использованием памяти: использование памяти должно быть пропорционально дельтам. Таким образом, просто наличие списка копий словаря не будет масштабироваться для моей проблемы. Надо полагать, что ключи исчисляются десятками тысяч, а редакции исчисляются сотнями тысяч.

Мы можем предположить, что значения неизменны, но не обязательно должны быть числовыми. Для случая, когда значения, например, целые числа, есть довольно простая реализация (есть список словарей числовой дельты от ревизии до ревизии). Я не уверен, как превратить это в общую форму. Может быть, загрузите целочисленную версию и добавьте массив значений?

вся помощь оценена.

Ответы [ 2 ]

2 голосов
/ 16 апреля 2010

Роскошным решением будет использование B + Trees с копированием при записи. Я использовал вариант деревьев B + для реализации моего типа данных blist (который можно использовать для очень эффективного создания ревизий списков , в точности аналогичных вашей проблеме).

Общая идея - хранить данные в сбалансированном дереве. Когда вы создаете новую ревизию, вы копируете только корневой узел. Если вам нужно изменить узел, совместно используемый со старой версией, вы копируете узел и вместо этого изменяете копию. Таким образом, старое дерево по-прежнему полностью не повреждено, но вам нужна только память для изменений (технически, O (k * log n), где k - количество изменений, а n - общее количество элементов).

Однако реализовать его нетривиально.

2 голосов
/ 16 апреля 2010

Имеется только один словарь, сопоставляющий ключ с списком (revision_number, actual_value) кортежей. Текущее значение the_dict[akey][-1][1]. Откат просто включает извлечение соответствующих записей из конца каждого списка.

Обновление: примеры отката

key1 -> [(10, 'v1-10'), (20, 'v1-20')]

Сценарий 1: текущая версия 30, откат до 25: ничего не происходит

Сценарий 2: текущие 30, назад к 15: всплыть последняя запись

Сценарий 3: текущий 30, назад к 5: вывести обе записи

Обновление 2: более быстрый откат (с компромиссами)

Я думаю, что ваше беспокойство по поводу высовывания каждого списка лучше выражается как «необходимо изучить каждый список, чтобы выяснить, нужно ли ему выскочить». Благодаря более изящной структуре данных (больше памяти, больше времени для поддержки модных битов в операциях добавления и обновления) вы можете сократить время отката.

Добавьте массив (проиндексированный по номеру ревизии), значения которого являются списками значений словаря, которые были изменены в этой ревизии. 

# Original rollback code:
for rlist in the_dict.itervalues():
    if not rlist: continue
    while rlist[-1][0] > target_revno:
        rlist.pop()

# New rollback code
for revno in xrange(current_revno, target_revno, -1):
    for rlist in delta_index[revno]:
        assert rlist[-1][0] == revno
        del rlist[-1] # faster than rlist.pop()    
del delta_index[target_revno+1:]

Обновление 3: полный код для более необычного метода 

import collections

class RevDict(collections.MutableMapping):

    def __init__(self):
        self.current_revno = 0
        self.dict = {}
        self.delta_index = [[]]

    def __setitem__(self, key, value):
        if key in self.dict:
            rlist = self.dict[key]
            last_revno = rlist[-1][0]
            rtup = (self.current_revno, value)
            if last_revno == self.current_revno:
                rlist[-1] = rtup
                # delta_index already has an entry for this rlist
            else:
                rlist.append(rtup)
                self.delta_index[self.current_revno].append(rlist)
        else:
            rlist = [(self.current_revno, value)]
            self.dict[key] = rlist
            self.delta_index[self.current_revno].append(rlist)

    def __getitem__(self, key):
        if not key in self.dict:
            raise KeyError(key)
        return self.dict[key][-1][1]

    def new_revision(self):
        self.current_revno += 1
        self.delta_index.append([])

    def roll_back(self, target_revno):
        assert 0 <= target_revno < self.current_revno
        for revno in xrange(self.current_revno, target_revno, -1):
            for rlist in self.delta_index[revno]:
                assert rlist[-1][0] == revno
                del rlist[-1]
        del self.delta_index[target_revno+1:]
        self.current_revno = target_revno

    def __delitem__(self, key):
        raise TypeError("RevDict doesn't do del")

    def keys(self):
        return self.dict.keys()

    def __contains__(self, key):
        return key in self.dict

    def iteritems(self):
        for key, rlist in self.dict.iteritems():
            yield key, rlist[-1][1]

    def __len__(self):
        return len(self.dict)

    def __iter__(self):
        return self.dict.iterkeys()
...