Почему моя рекурсия приводит к самоссылке на диктатные ценности? - PullRequest
Новая
       4

Почему моя рекурсия приводит к самоссылке на диктатные ценности?

0 голосов
/ 28 января 2020

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

def get_all_allocation_proposals(budget, options, upstream_element=dict()):
    # accepts:
    #   budget to be allocated
    #   list of options
    # returns:
    #   a list of allocation proposals

    # filter options for affordable options and sort by cost benefit ratio
    options = [x for x in options if x['cost'] <= budget]
    options = sorted(options, key=lambda x: (
        x['benefit_cost_ratio'], x['benefit']), reverse=True)

    if (len(options) > 0):
        # select the best options
        best_bc_ratio = options[0]['benefit_cost_ratio']
        best_options = [
            x for x in options if x['benefit_cost_ratio'] == best_bc_ratio]
        upstream_element['downstream_elements'] = []

        for current_element in best_options:

            downstream_options = remove_conflicting_options(
                current_element, options)
            downstream_budget = budget - current_element['cost']
            current_element['donstream_budget'] = downstream_budget

            downstream_elements = get_all_allocation_proposals(downstream_budget,
                                                               downstream_options,
                                                               current_element)
            if downstream_elements is not None:
                current_element['downstream_elements'] = downstream_elements

            upstream_element['downstream_elements'].append(current_element)

        return upstream_element
    else:
        return None

В приведенном выше коде при добавлении элементов создаются собственные ссылки на значения dict. Почему это так и как я могу избежать этого? Все, что я хочу сделать, это передать все нижестоящие элементы первому стеку вызовов. Есть ли что-то в корне неправильное в моем шаблоне рекурсии?

1 Ответ

1 голос
/ 28 января 2020

Я думаю, что проблема, вероятно, в том, что вы передаете изменяемые объекты в ваш рекурсивный вызов. В частности, downstream_options и current_element являются диктовками, и когда вы изменяете их в рамках данной рекурсии функции, вы также изменяете их на уровне выше, что в данном случае, кажется, оставляет вас при попытке присвоить значение в диктовке само по себе (или какая-то такая невозможность, мне не совсем удалось проследить логику c).

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

from copy import deepcopy

...

downstream_elements = get_all_allocation_proposals(downstream_budget,
                                                   deepcopy(downstream_options),
                                                   deepcopy(current_element))

Кроме того, как указано в комментариях, вы должны избегать использования изменяемого аргумента по умолчанию, то есть upstream_element=dict(). Это может привести к очень запутанному поведению, если вы на самом деле используете значение по умолчанию (которого вы не видите в своем коде)

...