字典是用python3.6+排序的吗?

  • 问题:
  • 字典在python3.6中(至少在CPython实现下)进行排序,这与以前的版本不同。这看起来是一个实质性的改变,但它只是documentation. 它被描述为一个CPython实现细节而不是一个语言特性,但也意味着这在将来可能成为标准

    在保持元素顺序的同时,新字典实现的性能如何比旧的更好?在

    以下是文档中的文本:

    dict()现在使用“紧凑”表示pioneered by PyPy. 与Python3.5相比,新dict()的内存使用量减少了20%到25%。PEP 468(在函数中保持**kwargs的顺序。)就是通过这个实现的。这种新实现的订单保持方面被视为一个实施细节,不应依赖(这可能在未来发生变化,但是,在修改语言规范,为所有当前和未来的Python实现指定保序语义之前,我们希望这个新的dict实现能在几个版本中使用;这也有助于保持与该语言旧版本的向后兼容性,其中随机迭代顺序仍然有效,e、 g.python3.5)。(作者:INADA Naokihttps://bugs.python.org/issue27350“rel=”noreferrer“>第27350期。想法最初由Raymond Hettinger提出

    2017年12月更新:dicts保留插入顺序为guaranteed对于Python 3.7

  • 答案:
  • 字典是用python3.6+排序的吗?

    它们是按插入顺序排列的。对于python3.6,对于Python的CPython实现,字典记住插入项的顺序。这在Python3.6中被认为是一个实现细节;如果您希望插入顺序在Python的其他实现中得到保证(以及其他有序行为[1]),则需要使用OrderedDict

    从python3.7开始,这不再是一个实现细节,而是一个语言特性。From a python-dev message by GvR公司名称:

    就这样吧。”“Dict保持插入顺序”是规则。谢谢!在

    这就意味着你可以依赖它。其他Python实现如果希望成为python3.7的一致实现,也必须提供插入顺序字典

    Python3.6字典实现在保持元素顺序的同时,如何比旧的字典实现更好地执行[2]

    本质上,通过保持两个数组。在

    第一个数组,dk_entries,保留条目(类型为PyDictKeyEntry),按插入顺序排列。保持顺序是通过这是一个只附加的数组来实现的,其中总是在末尾插入新的项(插入顺序)

    第二次,dk_indices,保存dk_entries数组的索引(即,指示对应项在dk_entries中的位置的值)。这个数组充当哈希表。当对一个键进行哈希运算时,它将导致存储在dk_index中的一个索引,并通过索引dk_entries来获取相应的项。因为只保留索引,此数组的类型取决于字典的总体大小(从typeint81字节)到int32/int644/8字节)在32/64位构建时)

    在以前的实现中,必须分配一个pydictkeytentry和sizedk_size的稀疏数组;不幸的是,由于该数组不允许超过2/3*dk_size满,因此也会产生大量空空间for performance reasons. (而空白的仍然PyDictKeyEntry大小!)。在

    现在不是这样,因为只存储所需的条目(已插入的条目),并保留intX_t类型的稀疏数组(取决于dict大小)2/3*dk_sizes full。空白空间从typepydictkeytentry更改为intX\u t。在

    因此,显然,创建pydictkeytentry类型的稀疏数组比存储ints的稀疏数组需要更多的内存

    你可以看到完整的对话on Python-Dev关于这个功能,如果有兴趣,这是一个很好的阅读

    In the original proposal made by Raymond Hettinger,可以看到所使用的数据结构的可视化,它抓住了想法的要旨

    例如,字典:

    d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

    当前存储为[keyhash,key,value]:

    entries = [['--', '--', '--'],
    [-8522787127447073495, 'barry', 'green'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [-9092791511155847987, 'timmy', 'red'],
    ['--', '--', '--'],
    [-6480567542315338377, 'guido', 'blue']]

    相反,数据的组织方式如下:

    indices =  [None, 1, None, None, None, 0, None, 2]
    entries = [[-9092791511155847987, 'timmy', 'red'],
    [-8522787127447073495, 'barry', 'green'],
    [-6480567542315338377, 'guido', 'blue']]

    正如你现在可以看到的,在最初的提案中,为了减少碰撞和加快查找速度,很多空间基本上是空的。使用新方法,您可以通过将稀疏性移动到索引中真正需要的位置来减少所需的内存

    key-lookups, for example)而在其他情况下(想到迭代和调整大小),性能应该得到提升。