删除list-of-list中的共享引用？

Question

好的,让我用一个简单的例子来解释这个问题:

l = [[0]]*3       # makes the array [[0], [0], [0]]
l[0][0] = 42      # l becomes [[42], [42], [42]]
from copy import deepcopy
m = deepcopy(l)   # m becomes [[42], [42], [42]]
m[0][0] = 2       # m becomes [[2], [2], [2]]

这是一个基本的共享参考问题.除了通常情况,当发生这样的问题时,deepcopy我们的朋友.目前,我这样做是为了解决我的deepcopy背叛问题:

l = [[0]]*3       # makes the array [[0], [0], [0]]
import JSON
m = JSON.loads(JSON.dumps(l)) # m becomes [[0], [0], [0]] with no self references

我正在寻找一种效率较低且不那么愚蠢的处理自共享引用的方法.

当然我不会故意制作这样的数组,但是我需要处理有人给我的代码一个的情况.在大型阵列上运行我的"解决方案"很慢,而且我有很多级别的嵌套数组,我不能为这些野兽制作这么大的字符串.

Answer 1

这是一种适用于列表,dicts和不可变值的任意组合的方法.

def very_deep_copy(obj):
    if isinstance(obj, list):
        return [very_deep_copy(item) for item in obj]
    elif isinstance(obj, dict):
        return {k: very_deep_copy(v) for k,v in obj.items()}
    else:
        return obj

l = [[0]]*3 
m = very_deep_copy(l)
m[0][0] = 2
print(m)

结果:

[[2], [0], [0]]

Answer 2

我要挑战一个假设,正确的做法是复制共享对象.你这么说

当然我不会故意制作这样的数组,但是我需要处理有人给我的代码一个的情况.

但如果有人通过意外的对象共享传递给你一个输入,他们的代码有一个错误.如果您的代码注意到该错误,您的代码应该通过抛出异常来告诉他们,以帮助他们修复错误.

大多数代码只是假设输入没有任何不需要的对象共享.如果你想要检测它,手动遍历可能是你最好的选择,特别是因为你的输入应该是JSON可序列化的:

def detect_duplicate_references(data):
    _detect_duplicate_references(data, set())

def _detect_duplicate_references(data, memo):
    if isinstance(data, (dict, list)):
        if id(data) in memo:
            raise ValueError(f'multiple references to object {data} detected in input')
        memo.add(id(data))
    if isinstance(data, list):
        for obj in data:
            _detect_duplicate_references(obj, memo)
    if isinstance(data, dict):
        for obj in data.values():
            _detect_duplicate_references(obj, memo)