如何复制一个列表字典？

Question

我该如何复制一个列表字典，它的复杂度是多少？我想要复制的字典类似于这样：

myDict = { 'k1': ['a', 'b', 'c'], 
           'k2': ['d', 'e', 'f'], 
           'k3': ['g', 'h', 'i'] }

- Sajad Rastegar

---

from copy import deepcopy：从复制模块中导入深度复制函数。 - l4mpi

那么...你为什么需要这样做呢？如果你担心它的复杂性，那就意味着你有一个性能问题，也许答案是找出一种不需要复制的设计？ - abarnert

@abarnert 是的，我只是想改变<a href='http://stackoverflow.com/questions/14106736/is-this-algorithm-good-for-finding-the-longest-common-subsequence'>我的旧算法</a>，将所有索引映射到字母而不是使用ystr.find(cl, start)来使用字典在O(1)中查找字母。但现在我发现它并不高效。 - Sajad Rastegar

为什么需要深度复制地图？（另外，我们都假设你需要在这里进行深度复制，但是...你需要吗？如果你只想要地图的浅层副本，那么显然可以更快地完成。（基本上，它应该只复制哈希表并增加所有键和值的引用计数。） - abarnert

@abarnert 我可以在哪里发布我的修改后的代码？ - Sajad Rastegar

如果您只想将内容发布给其他人审查，http://pastebin.com 是一个好的选择。如果您想要编辑并查看完整的版本历史记录，则http://gist.github.com 更适合您。 - abarnert

Answer 1

from copy import deepcopy
myCopy = deepcopy(myDict)

deepcopy 总是 唯一的方法。

- Volatility

---

几乎总是这样的方式 ;) - Jakob Bowyer

Answer 2

最简单的复制任何复杂数据结构的方法是 copy.deepcopy。 （如果您想自己处理它，请参见源代码以了解所涉及的内容。）

复杂度显然应该为O（NM），其中N是字典条目数，M是列表条目的平均数。但让我们来看看它：

假设您有一个带有N个键/值对的字典，每个值都是具有平均M个元素的列表。

如果列表是简单值，则需要分配1个哈希表，并进行2N + 1个简单复制和可能的N个哈希。字符串是不可变的，并且它们的长度都为1，如果它们不是，Python会在大型字符串中缓存哈希值。因此，我们总共有O（N）个操作。

但是这些list不是简单的值。您需要分配一个新的列表并复制M个元素。这需要O（M）时间。由于有N个，所以是O（NM）。

因此，总时间为O（N + NM）= O（NM）。

鉴于您拥有NM个对象并明确想要复制所有这些对象，实际上没有办法可以超越它。

当然，通过剥离deepcopy的无关部分并将任何剩余的紧密循环移植到Cython或C中，可以想象您可以获得一个数量级的改进。

- abarnert

---

自从这个答案被接受，并且只回答了问题的后半部分，我编辑了它以包括第一部分（在我之前已经由Volatility给出）。 - abarnert

在使用Volatility之前，l4mpi的评论帮助了我，因此我接受了你的答案。 - Sajad Rastegar

Answer 3

你可以使用内置的字典方法 copy() 来复制一个字典：

示例：

a = {'s':[1,2,3], 'f':[5,4,2]}
b = a.copy()

如果你改变了a，b不会改变。

而且复杂度接近于O(1)，因为字典使用哈希表来存储数据，访问其数据接近于O(1)，对于列表，访问数据和内存处理是恒定时间，所以接近于O(1)。

- Ramin Omrani

---

mydict是一个列表的字典，所以如果我使用复制，当我更改列表时它会改变我的原始列表。 - Sajad Rastegar

关于列表，你应该使用list[:]先复制它们，然后在副本上操作，以避免改变原始列表。但是对于字典，我已经在Python 2.7.3上尝试过了，它可以工作。 - Ramin Omrani

我会认为复杂度仍然是O(N)。 - tzelleke

我也在Python 2.7.3上尝试过，但它不起作用。你能测试一下这段代码吗？seq = [1,5,9]，d = {'a':seq，'b':[2,6,8]}，td = d.copy()，td['a'].append(52)，print d，输出是什么？ - Sajad Rastegar

在你即将进行的测试中，是的，你应该先导入copy，然后使用td = copy.deepcopy(d)而不是.copy()。deepcopy的复杂度是O(N)，因为它会递归地复制对象。 - Ramin Omrani

是的，我已经看到答案后面了，但“نوش دارو پس از مرگ سهراب”没有意义。 - Sajad Rastegar