为什么python不包含有序的dict(默认情况下)？

Question

Python有一些很好的结构来建模数据.这里有一些 :

              +-------------------+-----------------------------------+
              | indexed by int    | no-indexed by int                 |
+-------------+-------------------+-----------------------------------+
| no-indexed  | [1, 2, 3]         | {1, 2, 3}                         |
| by key      | or                | or                                |
|             | [x+1 in range(3)] | {x+1 in range(3)}                 |
+-------------+-------------------+-----------------------------------+
| indexed     |                   | {'a': 97, 'c': 99, 'b': 98}       |
| by key      |                   | or                                |
|             |                   | {chr(x):x for x in range(97,100)} |
+-------------+-------------------+-----------------------------------+

为什么python默认不包含由key + int索引的结构(如PHP数组)？我知道有一个模拟这个对象的库(http://docs.python.org/3/library/collections.html#ordereddict-objects).但这里是从文档中获取的"orderedDict"的表示:

OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

拥有一个逻辑上应该写的本机类型不是更好吗:

['a': 97, 'b': 98, 'c': 99]

与orderedDict理解相同的逻辑:

[chr(x):x for x in range(97,100)]

在python设计中填充像这样的表格单元格是否有意义？这有什么特别的原因尚未实施吗？

Answer 1

Python的字典被实现为哈希表.这些本质上是无序的数据结构.虽然可以添加额外的逻辑来跟踪顺序(如collections.OrderedDict在Python 2.7和3.1+中所做的那样),但是涉及到一个非平凡的开销.

例如,文档建议在Python 2.4-2.6中使用的配方collections需要两倍多的工作才能完成许多基本字典操作(例如添加和删除值).这是因为它必须维护一个双向链表以用于有序迭代,并且它需要一个额外的字典来帮助维护列表.虽然其操作仍为O(1),但常数项更大.

由于Python dict在任何地方都使用实例(例如,对于所有变量查找),因此它们需要非常快或者每个程序的每个部分都会受到影响.由于不经常需要有序迭代,因此在一般情况下避免它所需的开销是有意义的.如果您需要有序字典,请使用标准库中的字典(或者它建议的配方,如果您使用的是早期版本的Python).