2

我正在编写一些涉及这样的 Python 代码

values = {}
for element in iterable:
    values.setdefault(element.name, []).append(element)

因为我之前可以对输入进行排序，所以我也这样实现了

values = {}

cur_name = None
cur_list = None

for element in iterable:
    if element.name != cur_name:
        values[cur_name] = cur_list
        cur_name = element.name
        cur_list = []
    cur_list.append(element)
if cur_list:
    values[cur_name] = cur_list
del values[None]

这里输入已经按 排序element.name。

第二种方法比第一种方法快得多，而且它使用的内存也更少。

这是什么原因？

还是我在第二种方法中犯了某种错误？

4

3 回答 3

4

每次循环时，您的原始代码都会创建一个列表，然后大部分都会被丢弃。它还进行多个字典查找（查找方法setdefault是字典查找，然后方法本身进行字典查找以查看对象是否已设置，如果未设置，则执行另一个以存储值）。.name并且.append()也是字典查找，但它们仍然存在于修改后的代码中。

for element in iterable:
    values.setdefault(element.name, []).append(element)

修改后的代码仅在名称更改时查找字典，因此它从每个循环中删除了两个字典查找和一个方法调用。这就是为什么它更快。

至于内存使用，当列表增长时，有时可能需要复制数据，但如果内存块可以扩展，则可以避免这种情况。我的猜测是，创建所有这些未使用的临时列表可能会使内存更加碎片化并强制执行更多副本。换句话说，Python 实际上并没有使用更多内存，但它可能分配了更多但未使用的内存。

当您觉得需要setdefault考虑使用时collections.defaultdict。除非需要，否则可以避免创建列表：

from collections import defaultdict
values = defaultdict(list)
for element in iterable:
    values[element.name].append(element)

这可能仍然比您的第二个代码慢，因为它没有利用您对名称全部分组的知识，但对于一般情况，它比setdefault.

另一种方法是使用itertools.groupby. 像这样的东西：

from itertools import groupby
from operator import attrgetter
values = { name: list(elements) for name,elements in
    groupby(elements, attrgetter('name')) }

That takes advantage of the ordering and simplifies everything down to a single dictionary comprehension.

于 2012-08-16T08:10:25.470 回答
2

我可以想到第二种方法更快的几个原因。

values.setdefault(element.name, []).append(element)

在这里，您正在为每个创建一个空列表element，即使您永远不会使用它。您还setdefault为每个元素调用该方法，这相当于一次哈希表查找和一次可能的哈希表写入，加上调用该方法本身的成本，这在 python 中并非微不足道。最后，正如其他人在我发布此答案后指出的那样，您正在setdefault为 each 查找一次属性element，即使它总是引用相同的方法。

在第二个示例中，您避免了所有这些低效率。您只是根据需要创建尽可能多的列表，并且您无需调用任何方法即可完成所有操作，除了 required list.append，还散布着少量的字典分配。您实际上还用简单的比较 ( element.name != cur_name) 替换了哈希表查找，这是另一个改进。

我希望您也能获得缓存的好处，因为在将项目添加到列表时不会到处乱跳（这会导致大量缓存未命中），而是一次处理一个列表。这样，相关内存可能位于非常靠近 CPU 的缓存层中，因此处理速度更快。不应低估这种影响——从 RAM 中获取数据比从 L1 缓存中读取数据慢两个数量级（或约 100 倍）。

当然排序会增加一点时间，但是 python 拥有世界上最好和最优化的排序算法之一，全部用 C 编码，所以它不会超过上面列出的好处。

我不知道为什么第二种解决方案的内存效率更高。正如 Jiri 指出的那样，它可能是不必要的列表，但我的理解是这些应该由垃圾收集器立即收集，所以它应该只会增加少量的内存使用——单个空列表的大小。也许是因为垃圾收集器比我想象的要懒惰。

于 2012-08-16T07:51:00.960 回答
1

您的第一个版本有两个效率低下的部分：

  1. 在循环中调用和取消引用values.setdefault。您可以values_setdefault = values.setdefault在循环之前进行评估，它可以加快速度。

  2. 正如其他答案所建议的那样，为列表中的每个元素创建新的空列表非常慢且内存效率低下。我不知道如何避免它并立即使用 setdefault 。

于 2012-08-16T08:07:30.403 回答