ChatGPT解决这个技术问题 Extra ChatGPT

为什么 [] 比 list() 快?

我最近比较了 []list() 的处理速度,并惊讶地发现 [] 的运行速度比 list()三倍。我对 {}dict() 进行了相同的测试,结果几乎相同:[]{} 都花费了大约 0.128 秒 / 百万个周期,而 list()dict() 大约花费了 0.428 秒 / 百万个周期每个循环。

为什么是这样?执行 []{}(可能还有 ()'')立即传回一些空股票文字的副本,而它们的明确命名的对应物(list()dict()tuple()str()) 完全创建一个对象,不管它们是否真的有元素?

我不知道这两种方法有何不同,但我很想知道。我在文档或 SO 上找不到答案,而且搜索空括号的问题比我预期的要严重。

我通过调用 timeit.timeit("[]")timeit.timeit("list()") 以及 timeit.timeit("{}")timeit.timeit("dict()") 来分别比较列表和字典来获得计时结果。我正在运行 Python 2.7.9。

我最近发现了将 if Trueif 1 的性能进行比较的“Why is if True slower than if 1?”,并且似乎触及了类似的文字与全局场景;也许它也值得考虑。

注意:()'' 是特殊的,因为它们不仅是空的,而且是不可变的,因此,将它们设为单例很容易;他们甚至不构造新对象,只为空的 tuple/str 加载单例。从技术上讲,这是一个实现细节,但我很难想象他们为什么出于性能原因不会缓存空的 tuple/str。所以你关于 []{} 传回股票文字的直觉是错误的,但它确实适用于 ()''

B
Boris Verkhovskiy

因为 []{}文字语法。 Python 可以创建字节码来创建列表或字典对象:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list()dict() 是独立的对象。需要解析它们的名称,必须涉及堆栈以推送参数,必须存储框架以供以后检索,并且必须进行调用。这一切都需要更多时间。

对于空的情况,这意味着您至少有一个 LOAD_NAME(它必须搜索全局命名空间以及 builtins module),然后是一个 CALL_FUNCTION,它必须保留当前帧:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

您可以使用 timeit 单独为名称查找计时:

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

时间差异可能是字典哈希冲突。从调用这些对象的时间中减去这些时间,并将结果与使用文字的时间进行比较:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

因此,每 1000 万次调用,必须调用该对象需要额外的 1.00 - 0.31 - 0.30 == 0.39 秒。

您可以通过将全局名称别名为本地名称来避免全局查找成本(使用 timeit 设置,您绑定到名称的所有内容都是本地名称):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

但是您永远无法克服CALL_FUNCTION的成本。


D
Dan D.

list() 需要全局查找和函数调用,但 [] 编译为单个指令。看:

Python 2.7.3
>>> import dis
>>> dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        

T
Torxed

因为 list 是将字符串转换为列表对象的 function,而 [] 用于立即创建列表。试试这个(可能对你更有意义):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

尽管

y = ["wham bam"]
>>> y
["wham bam"]

为您提供包含您放入其中的任何内容的实际列表。


这并没有直接解决这个问题。问题是为什么 []list() 快,而不是为什么 ['wham bam']list('wham bam') 快。
@JeremyVisser 这对我来说意义不大,因为 []/list()['wham']/list('wham') 完全相同,因为它们具有相同的变量差异,就像 1000/10 在数学中与 100/1 相同。理论上你可以去掉 wham bam 并且事实仍然是一样的,list() 试图通过调用函数名来转换某些东西,而 [] 将直接转换变量。函数调用是不同的,是的,这只是问题的逻辑概述,例如公司的网络图也是解决方案/问题的逻辑。随心所欲地投票。
@JeremyVisser 相反,它表明他们对内容做了不同的操作。
D
Dimitris Fasarakis Hilliard

这里的答案很好,切中要害,完全涵盖了这个问题。对于那些感兴趣的人,我将从字节码中进一步降低。我正在使用 CPython 的最新存储库;旧版本在这方面的行为相似,但可能会有细微的变化。

以下是其中每个的执行细分,BUILD_LIST 用于 []CALL_FUNCTION 用于 list()

BUILD_LIST 指令:

你应该只看到恐怖:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

我知道,非常令人费解。这很简单:

使用 PyList_New 创建一个新列表(这主要为新列表对象分配内存), oparg 指示堆栈上的参数数量。开门见山。

检查 if (list==NULL) 没有出错。

使用 PyList_SET_ITEM (宏)添加位于堆栈上的任何参数(在我们的示例中不执行)。

难怪它很快!它是为创建新列表而定制的,仅此而已:-)

CALL_FUNCTION 指令:

这是您查看代码处理 CALL_FUNCTION 时首先看到的内容:

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

看起来很无害,对吧?好吧,不,不幸的是,call_function 不是一个会立即调用函数的直截了当的人,它不能。相反,它从堆栈中抓取对象,抓取堆栈的所有参数,然后根据对象的类型进行切换;是不是:

PyCFunction_Type?不,它是列表,列表不是 PyCFunction 类型

PyMethodType?不,见前文。

PyFunctionType?不,见前面。

我们调用 list 类型,传递给 call_function 的参数是 PyList_Type。 CPython 现在必须调用一个通用函数来处理任何名为 _PyObject_FastCallKeywords 的可调用对象,还有更多的函数调用。

此函数再次对某些函数类型进行一些检查(我不明白为什么),然后在为 kwargs if required 创建一个 dict 之后,继续调用 _PyObject_FastCallDict

_PyObject_FastCallDict 终于把我们带到了某个地方!在对我们传入的 type 执行更多检查后,它 grabs the tp_call slot from the type 会抓取 type.tp_call。然后它继续使用 _PyStack_AsTuple 传入的参数创建一个元组,最后是 a call can finally be made

type.__call__ 匹配的 tp_call 接管并最终创建列表对象。它调用对应于 PyType_GenericNew 的列表 __new__ 并使用 PyType_GenericAlloc 为其分配内存:这实际上是它最终赶上 PyList_New 的部分。所有前面的都是以通用方式处理对象所必需的。

最后,type_call 调用 list.__init__ 并使用任何可用参数初始化列表,然后我们继续原路返回。 :-)

最后,请记住 LOAD_NAME,这是另一个在这里做出贡献的人。

很容易看出,在处理我们的输入时,Python 通常必须跳过一些环节才能真正找到合适的 C 函数来完成这项工作。它不能立即调用它,因为它是动态的,有人可能会掩盖 list 很多人都会这样做)并且必须采取另一条路径。

这就是 list() 损失很大的地方:探索 Python 需要做的是找出它到底应该做什么。

另一方面,字面语法只意味着一件事。它无法更改,并且始终以预先确定的方式运行。

脚注:从一个版本到另一个版本,所有函数名称都可能发生变化。这一点仍然存在,并且很可能在任何未来的版本中都存在,它是动态查找使事情变慢。


我无法用语言来形容我有多喜欢这个解释,但我会尽力而为。它简明扼要,深入探讨了主题,并有一个很好的总结,可以在所有内容上打上一个漂亮的蝴蝶结。谢谢!
R
Russia Must Remove Putin

为什么 [] 比 list() 快?

最大的原因是 Python 将 list() 视为用户定义的函数,这意味着您可以通过将其他内容别名为 list 来拦截它并执行不同的操作(例如使用您自己的子类列表或可能是双端队列)。

它立即使用 [] 创建一个内置列表的新实例。

我的解释旨在让您对此有直觉。

解释

[] 通常称为文字语法。

在语法中,这被称为“列表显示”。 From the docs

列表显示是用方括号括起来的可能为空的一系列表达式: list_display ::= "[" [starred_list | comprehension] "]" 列表显示产生一个新的列表对象,其内容由表达式列表或推导式指定。当提供以逗号分隔的表达式列表时,它的元素从左到右进行计算,并按该顺序放置到列表对象中。当提供推导时,列表由推导产生的元素构成。

简而言之,这意味着创建了一个 list 类型的内置对象。

没有办法规避这一点——这意味着 Python 可以尽可能快地做到这一点。

另一方面,可以通过使用内置列表构造函数创建内置 list 来拦截 list()

例如,假设我们希望我们的列表被嘈杂地创建:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

然后,我们可以在模块级别的全局范围内截取名称 list,然后当我们创建 list 时,我们实际上创建了子类型列表:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

同样,我们可以将其从全局命名空间中移除

del list

并将其放在内置命名空间中:

import builtins
builtins.list = List

现在:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

并注意列表显示无条件地创建一个列表:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

我们可能只是暂时这样做,所以让我们撤消我们的更改 - 首先从内置函数中删除新的 List 对象:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

哦,不,我们失去了原来的踪迹。

不用担心,我们仍然可以得到 list - 它是列表文字的类型:

>>> builtins.list = type([])
>>> list()
[]

所以...

为什么 [] 比 list() 快?

正如我们所看到的——我们可以覆盖 list——但我们不能拦截文字类型的创建。当我们使用 list 时,我们必须进行查找以查看是否存在任何内容。

然后我们必须调用我们查找的任何可调用对象。从语法:

调用调用带有可能为空的一系列参数的可调用对象(例如,函数): call ::= primary "(" [argument_list [","] | comprehension] ")"

我们可以看到它对任何名称都做同样的事情,而不仅仅是列表:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

对于 [],在 Python 字节码级别没有函数调用:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

它只是直接构建列表,而无需在字节码级别进行任何查找或调用。

结论

我们已经证明 list 可以通过使用范围规则的用户代码被截获,并且 list() 会查找可调用对象然后调用它。

[] 是列表显示或文字,因此避免了名称查找和函数调用。


+1 指出您可以劫持 list 并且 python 编译器无法确定它是否真的会返回一个空列表。