为什么len(<a list object>)这么慢？

Question

我在ipython会话中运行以下代码:

# 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; 它拥有~~亿个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对象知道它的大小，并且它只返回存储的数字：

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

Py_SIZE 定义在哪里：

Py_SIZE(o)

该宏用于访问Python对象的ob_size成员。它扩展到： (((PyVarObject*)(o))->ob_size)

所以我可以得出结论它不应该做任何计算。唯一可疑的是您尝试转换为列表的对象。但如果你发誓它真的list没有任何假对象通过一些惰性计算来模拟其方法 - 事实并非如此。

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

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