Хобрук: Ваш путь к мастерству в программировании

Python: изменение значений в древовидной структуре словаря

У меня есть древовидная структура в Python, где каждый узел представляет собой список [dict,int]. Диктант указывает на детей. Листья представляют собой простые целые числа, без списков для экономии памяти. Теперь я хочу масштабировать целочисленное значение в каждом узле с постоянным коэффициентом. Я написал следующую рекурсивную функцию, которая принимает корневой узел и множитель:

def scale(node,factor):
    if type(node) != list:
        node *= factor;
    else:
        node[1] *= factor;
        for key in node[0]:
            scale(node[0][key],factor);

У меня сложилось впечатление, что узлы выхода не изменились из-за некоторых из этих проблем со ссылками/разыменованиями Python. Это правда?

python dictionary reference dereference tree
08.08.2014

  • Вы проверили это, чтобы узнать? Почему бы не найти доказательства, подтверждающие ваше впечатление? 08.08.2014
  • У меня есть ограничение нормализации, согласно которому сумма всех целых чисел дочернего узла является целым числом родительского узла. Это ограничение выполняется до, но не после масштабирования. Если я правильно посчитал, то должно получиться в обоих случаях. И проблема, похоже, не возникает на более высоких уровнях дерева. 08.08.2014
  • Добавьте несколько операторов print в обе ветви оператора if. Когда вы запускаете программу, которая покажет вам, что происходит. 08.08.2014
  • Не могли бы вы предоставить минимальный пример, включая данные, чтобы другие могли воспроизвести проблему? 08.08.2014

Ответы:


1

Это утверждение не делает то, что вы думаете:

node *= factor

Это только умножает локальную переменную node, это не изменит значение dict, которое вы изначально передали. Ints неизменяемы, поэтому нет способа передать его в функцию и заставить функцию изменить его на месте.

В этой статье подробно описано, как имена и значения работают в Python: Факты и мифы об именах и значениях в Python.

Кстати: лучший способ проверить тип (если необходимо):

if not isinstance(node, list):
08.08.2014

2

Этот фрагмент объясняет, почему конечные узлы (типа int) не обновляются:

def f(x):
    print "got x", x
    x *= 10
    print "set x to", x

>>> n = 123
>>> f(n)
got x 123
set x to 1230
>>> n
123

>>> l=[1]
>>> f(l)
got x [1]
set x to [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
>>> l
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Таким образом, вы можете видеть, что n не изменяется, потому что в функции f(x) обновляется только локальная переменная x. Однако список l обновляется, поскольку он может быть изменен.

Любой простой способ исправить это — обернуть листовые узлы в list (или другой изменяемый тип) и сохранить (и обновить) значение листа. Тогда вы можете написать scale() вот так:

def scale(node,factor):
    if len(node) == 1:   # leaf node is a list containing a single int
        node[0] *= factor;
    else:
        node[1] *= factor;
        for key in node[0]:
            scale(node[0][key],factor)
08.08.2014

3

Поскольку я не собираюсь менять свою структуру данных, мне пришлось сделать следующее (на мой взгляд, это один из тех случаев, когда Python отстой):

def scale(node,factor):
    for key in node[0]:
        if type(node[0][key]) != list:
            node[0][key] *= factor;
        else:
            node[0][key][1] *= factor;
            scale(node[0][key],factor);

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

08.08.2014
Новые материалы
Управление состоянием в микрофронтендах
Стратегии бесперебойного сотрудничества Микро-фронтенды — это быстро растущая тенденция в сфере фронтенда, гарантирующая, что удовольствие не ограничивается исключительно бэкэнд-системами..
Декларативное и функциональное программирование в стиле LINQ с использованием JavaScript с использованием каррирования и генератора ...
LINQ - одна из лучших функций C #, которая обеспечивает элегантный способ написания кода декларативного и функционального стиля, который легко читать и понимать. Благодаря таким функциям ES6,..
Структуры данных в C ++ - Часть 1
Реализация общих структур данных в C ++ C ++ - это расширение языка программирования C, которое поддерживает создание классов, поэтому оно известно как C с классами . Он используется для..
Как я опубликовал свое первое приложение в App Store в 13 лет
Как все началось Все началось три года назад летом после моего четвертого класса в начальной школе. Для меня, четвертого класса, лето кажется бесконечным, пока оно не закончится, и мой отец..
Что в лицо
Очерк о возвращении физиогномики и о том, почему мы должны это приветствовать. История начинается со странной науки. Р. Тора Бьорнсдоттир, Николас О. Рул. Видимость социального класса по..
Почему шаблоны проектирования и почему нет?
Сложность — мать всех проблем в программировании. Программное обеспечение должно быть разработано с точки зрения того, кто его поддерживает, а не того, кто его пишет, потому что программное..
Создание дизайна обуви с помощью машинного обучения
Обувь. Что подождать? Я думал, что речь пойдет о машинном обучении! Ну это так. Если бы вы пошли на Amazon, сколько обуви вы бы нашли? Наверное, много, не так ли? Но много ли в них..