时间戳

首页 > 解决方案 > 为什么我的递归会导致自引用 dict 值？

python - 为什么我的递归会导致自引用 dict 值？

问题描述

我的目标是编写一个函数，通过根据收益/成本比比较选项并将它们存储在嵌套字典列表中，从而在选项之间拆分预算。当具有相同收益/成本比的多个选项可用时，每个选项都应单独进行（作为下游元素，而下游元素又可能具有多个下游元素）并反映为其上游字典的字典列表。对于可能出现的选项数量没有限制。

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 值。为什么会这样，我该如何避免呢？我要做的就是将所有下游元素传递给第一个调用堆栈。我的递归模式是否存在根本缺陷？

标签： pythonrecursion

解决方案

我认为问题可能是因为您将可变对象传递到递归调用中。具体来说downstream_options，current_element是 dicts，当你在函数的给定递归中修改它们时，你也在上面的级别修改它们，在这种情况下，这似乎让你试图在 dict 中为自身分配一个值（或者一些这样的不可能，我还没有完全遵循逻辑）。

一个快速的解决方案可能是（我不确定这是否会破坏你的逻辑）在每次递归时制作这些字典的副本：

from copy import deepcopy

...

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

此外，如评论中所述，您应该避免使用可变的默认参数，即upstream_element=dict(). 如果您实际使用默认值（您的代码中没有出现），这可能会产生一些非常令人困惑的行为

推荐阅读