为什么从元组列表中创建python dict比从kwargs慢3倍

问题描述 投票:9回答:3

有几种方法可以在python中构造字典,例如:

keyvals = [('foo', 1), ('bar', 'bar'), ('baz', 100)]

dict(keyvals)

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

dict(**dkwargs)

当你对这些基准进行测

In [0]: %timeit dict(keyvals)
667 ns ± 38 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [1]: %timeit dict(**dkwargs)
225 ns ± 7.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

你看到第一种方法比第二种方法快3倍。为什么是这样?

python python-3.x performance benchmarking python-internals
3个回答
14
投票

dict(**kwargs)传入一个现成的字典,因此Python可以复制已经存在的内部结构。

另一方面,元组列表需要迭代,验证,散列并将结果插入到一个新的空表中。那不是那么快。

Python字典作为hash table实现,并随着时间的推移随着密钥的增加而动态增长;它们从小开始,随着需要的出现,构造了一个新的,更大的哈希表,数据(键,值和哈希)被复制。这在Python代码中都是不可见的,但调整大小需要时间。但是当你使用dict(**kwargs)(或dict(other_dict) CPython(你用来测试的默认Python实现)时可以采用一种快捷方式:从一个足够大的哈希表开始。你不能用一系列元组做同样的技巧,因为如果序列中没有重复的键,你无法预先知道。

有关更多详细信息,请参阅dict类型的C源代码,特别是dict_update_common implementation(从dict_init()调用);这会调用PyDict_MergeFromSeq2()作为元组序列的情况,或者在传入关键字参数时调用PyDict_Merge()

PyDict_MergeFromSeq2() function迭代序列,测试每个结果以确保有两个元素,然后基本上在字典上调用.__setitem__(key, value)。这可能需要在某些时候调整字典的大小!

PyDict_Merge()函数(通过dict_merge())专门检测是否传入了常规字典,然后executes a fast path调整内部结构的大小一次,然后直接使用insertdict()调用从原始字典中复制散列和结构(遵循override == 1路径,如override当目标字典为空时,已设置为1dict(**kwargs)总是这样。只调整一次并直接使用内部数据要快得多,而且需要完成的工作要少得多!

所有这些都是CPython特有的实现细节。其他Python实现(如Jython,IronPython和PyPy)可以自行决定dict类型的内部如何工作,并将为相同的操作显示不同的性能差异。


3
投票

Short answer (TL;DR)

这是因为在第一次测试中,dict的CPython实现将从列表中创建一个新的dict,但第二次只复制字典。复制比解析列表花费的时间更少。

Additional info

考虑以下代码:

import dis
dis.dis("dict([('foo', 1), ('bar', 'bar'), ('baz', 100)])", depth=10)
print("------------")
dis.dis("dict({'foo': 1, 'bar': 'bar', 'baz': 100})", depth=10)

哪里

dis模块通过反汇编支持CPython字节码的分析。

这让我们看到了执行的字节码操作。输出显示

  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (('foo', 1))
              4 LOAD_CONST               1 (('bar', 'bar'))
              6 LOAD_CONST               2 (('baz', 100))
              8 BUILD_LIST               3
             10 CALL_FUNCTION            1
             12 RETURN_VALUE
------------
  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (1)
              4 LOAD_CONST               1 ('bar')
              6 LOAD_CONST               2 (100)
              8 LOAD_CONST               3 (('foo', 'bar', 'baz'))
             10 BUILD_CONST_KEY_MAP      3
             12 CALL_FUNCTION            1
             14 RETURN_VALUE

从输出中您可以看到:

  1. 两个调用都需要加载要调用的dict名称。
  2. 之后,第一个方法将列表加载到内存(BUILD_LIST),而第二个方法构建一个字典(BUILD_CONST_KEY_MAP)(参见here
  3. 出于这个原因,当调用dict函数时(CALL_FUNCTION步骤(参见here)),在第二种情况下需要更短的时间,因为字典已经创建,所以它只是复制而不必迭代列表创建哈希表。

注意:使用字节码你无法确定CALL_FUNCTION是否这样做,因为它的实现是用C语言编写的,只有通过阅读它才能真正知道(参见Martijn Pieters的答案,准确解释这部分是如何工作的)。但是,它有助于查看字典对象是如何在dict()之外创建的(逐步,在示例中不是语法上),而对于列表,情况并非如此。

Edit

要说清楚,当你说

有几种方法可以在python中构建字典

通过这样做:

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

您正在创建一个字典,在这个意义上,解释器将表达式转换为存储在内存中的字典对象,并使变量dkwargs指向它。但是,通过执行:dict(**kwargs)或者如果您更喜欢dict(kwargs),您实际上并不是在创建一个字典,而只是复制一个已经存在的对象(强调复制很重要):

>>> dict(dkwargs) is dkwargs
False

dict(kwargs)强迫Python创建一个新对象;但是,这并不意味着它必须重新构建对象。实际上,该操作是无用的,因为在实践中它们是相同的对象(尽管不是同一个对象)。

>>> id(dkwargs)
2787648914560
>>> new_dict = dict(dkwargs)
>>> id(new_dict)
2787652299584
>>> new_dict == dkwargs
True
>>> id(dkwargs) is id(new_dict)
False

id:

返回对象的“标识”。这是一个整数,在它的生命周期内保证对于该对象是唯一且恒定的[...]

CPython实现细节:这是内存中对象的地址。

当然,除非您想要专门复制对象以便修改对象,因此编辑不会链接到其他引用。


0
投票

dkwargs已经是一本字典了,所以你基本上都要复制它。这就是它快得多的原因。

© www.soinside.com 2019 - 2024. All rights reserved.