Python中高效地向列表添加元素

Question

我正在遍历一个包含超过三百万个元素的列表，并给它们分配整数值。为了组织起来，我创建了一个字典，其键是整数，值是具有该得分的项的列表。事先，我不知道会有多少项具有某个得分，因此我使用+运算符将其附加到列表中，如下所示：

for e in xs:
   myDict[val(e)] = myDict.get(val,[]) + [e]

我的问题是：

1. 有没有更简洁的方法来做这个？
2. +操作的时间复杂度是多少？它是否会创建一个全新的列表，将原始列表中的元素复制并添加到其中？
3. 如果我要向集合中添加一个元素怎么办？

- user217285

---

这样做就相当于使用“Shlemiel 画家算法”创建一个全新的列表，将原始列表中的元素复制并添加进去。 - Peter Mortensen

Answer 1

使用 append：

for e in xs:
   myDict.setdefault(val(e), []).append(e)

这样可以避免每次构建新列表。操作list1+list2需要在每次迭代中构建一个新列表，因此需要分配内存。append更有效率，因为列表在末尾预先分配了内存。例如，从空列表开始使用append构建一个包含1000万个条目的列表需要超过100次内存分配。

字典的setdefault方法返回相应的值（如果键存在）。如果键不在字典中，则返回默认值。在这种情况下，默认值是一个列表。由于列表的可变性，我们可以在第一次迭代时向空列表添加内容，并在每个后续迭代中向部分填充的列表添加内容。

使用setdefault()的替代方法是collections.defaultdict。进行一些分析以找出哪种方法更快。

- Mike Müller

---

谢谢。那么，setdefault方法是否返回键的值的引用呢？否则，添加操作将不会有任何作用。 - user217285

是的。如果键存在，则返回它，否则将键设置为第二个参数，然后返回该参数。 - ShadowRanger

Answer 2

是的，可以使用 collections.defaultdict 进行追加和使用：

from collections import defaultdict

d = defaultdict(list)
for e in xs:
   d[val(e)].append(e)

追加是一个0(1)的操作，而你的方法是线性的0(n+k)，因为你每次都创建了一个新列表。

如果你需要添加多个项目，你应该使用extend来扩展你的列表。

需要注意的一点是，my_list += some_list等同于mylist.extend(some_list)，但它与my_list = my_list + some_list非常不同。前者将添加到原始列表中，而后者正在执行你的代码所做的操作，即连接两个列表以创建一个全新的列表。

extend或+=的复杂度是0(k)，其中k是some_list的长度。

wiki.python列出了Python中常见操作的复杂度。

- Padraic Cunningham

---

在 += 和 extend 之间绝对没有任何区别吗？也就是说，我可以通过 += [e] 和 .extend([e]) 进行操作，甚至在纳秒级别上也看不到任何差异吗？ - user217285

两者执行相同的任务，但可能存在纳秒级别的差异。我想“extend”操作可能会稍微快一些。 - Padraic Cunningham