Существует ли стандартный алгоритм или библиотека для представления дельт данных?

У меня есть словарь Python с довольно сложной структурой — несколько слоев вложенных значений, некоторые из которых являются словарями, а некоторые — списками. Я хочу представить изменения данных в компактном виде, который можно легко применить.

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

Но со списками все становится намного сложнее. Похоже, мне нужно придумать какую-то собственную схему адресации, которая должна учитывать множество случаев — вы не можете просто наивно использовать индексы списка в качестве ключей, потому что вам нужно поддерживать, например. удаление элемента 5 одновременно с вставкой между элементами 2 и 3.

Кроме того, если списки не ограничены тем, что они являются листьями, сложно указывать изменения элементов, содержащихся в списке, одновременно изменяя элементы этого списка.

Есть ли библиотека Python, которая стандартизирует что-то подобное? Или стандартный алгоритм/подход, который относительно разумен для реализации?

для справки, вот функция, которая реализует то, что я ищу для данных только для dict:

def update(d, u):
    for k, v in u.items():
        if v == 'del':
            del d[k]
        elif isinstance(v, collections.abc.Mapping):
            d[k] = update(d.get(k, {}), v)
        else:
            d[k] = v
    return d

>>> d = {1: 2, 3: {4: 5, 6: 7}}
>>> delta = {3: {4: 'del', 6: 8}, 9: 10}
>>> update(d, delta)
{1: 2, 3: {6: 8}, 9: 10}

Я не думаю, что вставка - это проблема с индексами списка. Выполните все манипуляции со списком, используя старые индексы. Только после того, как все манипуляции проделаны, индексы меняются.

Stef 17.05.2022 10:23

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

Personman 17.05.2022 10:33

Я имел в виду, что с точки зрения пользователя индексы имеют смысл. Конечно, с точки зрения реализации вы должны быть очень осторожны.

Stef 17.05.2022 10:46
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
3
31
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

С точки зрения пользователя, я не думаю, что списковые индексы представляют собой такую ​​большую проблему, как вы говорите. Индексы изменятся только после выполнения всех манипуляций. Используйте старые индексы при работе со списком.

С точки зрения реализации нам нужно быть очень осторожными при манипулировании индексами списка. Что мы можем сделать, так это поддерживать «дельту индекса i» во время итерации, и вместо изменения l[k] мы изменяем l[k+i].

Здесь я буду использовать словарь для дельты со списком индексов в качестве ключа и этими тремя возможными значениями:

  • 'del' удалить элемент по этому индексу;
  • ('insert', v) чтобы вставить значение v непосредственно перед этим индексом; и
  • v, чтобы изменить значение на v в этом индексе.

Обратите внимание, что 'del' и v являются взаимоисключающими, но 'insert' может быть кумулятивным: можно вставить более одного элемента в один и тот же индекс, а также можно вставить элементы непосредственно перед индексом и удалить или изменить элемент в этом индексе. Итак, мы хотим, чтобы наша дельта dict могла сопоставлять ключ с более чем одним обновлением; т. е. для сопоставления ключа со списком.

from operator import itemgetter

def update(d, u):
    if isinstance(d, dict):
        return update_dict(d, u)
    elif isinstance(d, list):
        return update_list(d, u)

def update_dict(d, u):
    for k, v in u.items():
        if v == 'del':
            del d[k]
        elif isinstance(v, dict):
            d[k] = update(d.get(k, {}), v)
        else:
            d[k] = v
    return d

def update_list(d, u):
    i = 0
    for k, v in sorted(u.items(), key=itemgetter(0)):
        if isinstance(v, list):
            for x in v:
                i = update_list_once(d, i, k, x)
        else:
            i = update_list_once(d, i, k, v)
    return d

def update_list_once(d, i, k, v):
    if v == 'del':
        del d[k+i]
        i -= 1
    elif isinstance(v, tuple) and len(v) == 2 and v[0] == 'insert':
        d.insert(k+i, v[1])
        i += 1
    else:
        if isinstance(v, dict):
            d[k + i] = update(d[k+i], v)
        else:
            d[k+i] = v
    return i

Тестирование:

d = {1: 2, 3: {4: [0, 1, 2, 3, 4, 5], 6: 7}}
delta = {3: {4: {0: 'fizzbuzz', 3: 'fizz', 4: [('insert', 3.5), 4.001], 5: 'buzz'}, 6: 8}, 9: 10}
d = update(d, delta)
print(d)
# {1: 2, 3: {4: ['fizzbuzz', 1, 2, 'fizz', 3.5, 4.001, 'buzz'], 6: 8}, 9: 10}

Это действительно солидное начало, и сначала я подумал, что вы прибили его, но мои опасения были в некоторой степени оправданы: поскольку вы используете старые индексы списка, нет возможности изменить элемент в позиции n, а также вставить элемент перед ним. . когда вы выполняете вставку, элемент в этой позиции становится невидимым, потому что вы не можете снова использовать этот ключ. (например, пытаясь создать список ['шипение', 1, 2, 'шипение', 3.5, 7, 'жужжание'], вы ничего не можете поместить в дельту, чтобы указать, что 7.)

Personman 17.05.2022 10:55

@Personman Ооооооооо, ты прав

Stef 17.05.2022 11:00

@Personman Нам нужен «мультидикт». То есть, dict, который может иметь более одного значения для каждого ключа. Мы бы хотели что-то вроде {4: [('insert', 3.5), 7]}

Stef 17.05.2022 11:00

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

Personman 17.05.2022 11:02

@Personman я редактировал. Теперь это должно работать.

Stef 17.05.2022 11:07

Это было бы хорошим вариантом использования more_itertools.always_iterable.

Stef 17.05.2022 11:10

@Personman Обратите внимание, что большинство функций в библиотеке python следуют этому соглашению: либо функция изменяет свой ввод на месте и возвращает None, либо не изменяет свой ввод и возвращает что-то. Например, list.sort изменяет свой ввод и возвращает None, а sorted не изменяет свой ввод, а возвращает новый список. Функция update выше представляет собой смесь двух, что не очень хорошо.

Stef 17.05.2022 12:13

Другие вопросы по теме