list - 有效地将元素添加到python中的列表

Question

我正在遍历超过 300 万个项目的列表，并为它们分配整数值。为了组织，我制作了一个字典，其键是整数，值是具有该分数的项目列表。先验地，我不知道有多少项目会有一定的分数，所以我使用 + 运算符追加到列表中，如下所示:

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

我的问题是:

1. 是否有更简洁的方法来执行此操作？
2. + 操作的时间复杂度是多少？它是创建一个全新的列表，从原始列表中复制元素，然后添加它们吗？
3. 如果我向集合中添加一个元素会怎样？

Answer 1

使用append:

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

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

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

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