python - 为什么 len() 这么慢？

Question

我在 ipython 中运行以下代码 session :

# This call is slow, but that is expected. (It loads 3 GB of data.)
In [3]: arc, arc_sub, upls, go = foo_mod.ready_set()

# This call is also slow, as `upls` is huge.
In [4]: upls = list(upls)

# This call is slow in meatspace, but `%timeit` doesn't notice!
In [5]: %timeit -n1 -r1 len(upls)
1 loops, best of 1: 954 ns per loop

%timeit正直躺在这里。有或没有 %timeit ，该命令实际运行需要 10 秒以上。然而，这只是第一次；随后调用 len很快。

甚至time.time()唱着相似的曲调:

In [5]: import time

In [6]: s = time.time(); len_ = len(upls); e = time.time()

In [7]: e - s
Out[7]: 7.104873657226562e-05

但在现实世界中花了秒 In [6]真正完成。我似乎无法捕捉到实际时间花在了哪里!

这个列表没有什么特别之处，除了它很大:它是一个真实的 list ;它持有 ~25 亿 bson.ObjectId对象。 (在 list() 调用之前，它是一个 set 对象；那个 调用也很慢，但这是有道理的；list(<set instance>) 是 O(n)，我的套装很大。)

编辑重新GC

如果我运行 gc.set_debug(gc.DEBUG_STATS)就在 ready_set 之前，这本身就是一个缓慢的调用，我看到了大量的 GC 周期。这是意料之中的。 gen3 成长:

gc: objects in each generation: 702 701 3289802
gc: done, 0.0000s elapsed.
gc: collecting generation 0...
gc: objects in each generation: 702 1402 3289802
gc: done, 0.0000s elapsed.
gc: collecting generation 0...
gc: objects in each generation: 702 2103 3289802

不幸的是，控制台输出使这个运行时间慢得令人难以置信。如果我改为延迟 gc.set_debug直到 ready_set 之后才打电话，我没有看到任何 GC 周期，但是gc.get_count()声称世代很小:

In [6]: gc.get_count()
Out[6]: (43, 1, 193)

In [7]: len(upls)
Out[7]: 125636395

(但是为什么/如何 get_count 比列表中的对象少？；它们绝对都是独一无二的，因为它们刚刚经历了 set ……)涉及 gc 的事实在代码中使 len快速让我相信我已经停下来收集世界了。

(版本，以防万一:

Python 2.7.6 (default, Mar 22 2014, 22:59:56)
IPython 3.2.0 -- An enhanced Interactive Python.

)

Answer 1

我会将对您问题的评论总结为答案。

正如每个人所说(并且您指出)，Python 的list 对象知道它的大小并且它returns just the stored number :

static Py_ssize_t
list_length(PyListObject *a)
{
    return Py_SIZE(a);
}

哪里 Py_SIZE is defined :

Py_SIZE(o)

This macro is used to access the ob_size member of a Python object. It expands to: (((PyVarObject*)(o))->ob_size)

所以我可以断定它不应该做任何计算。唯一怀疑的是您试图转换为列表的对象。但是如果你发誓它真的是 list，没有任何假对象通过一些惰性计算来模拟它的方法 - 它不是。

所以我假设所有 timeit 方法都显示调用 len 函数所花费的准确时间。

唯一浪费时间的过程是.. 垃圾收集器。在测量结束时，它发现没有人使用如此大的数据并开始释放内存。当然，这需要几秒钟。