我指的是来自collections模块的 OrderedDict,它是一个有序的字典. 如果它具有可订购的附加功能,我意识到这可能通常不是必要的,但即便如此,是否有任何缺点？它慢了吗？它缺少任何功能吗
如果它具有可订购的附加功能,我意识到这可能通常不是必要的,但即便如此,是否有任何缺点？它慢了吗？它缺少任何功能吗？我没有看到任何遗漏的方法.
简而言之,为什么我不应该总是使用它而不是普通的字典呢？
OrderedDict是dict的子类,需要更多内存来跟踪添加键的顺序.这不是微不足道的.该实现在封面下添加了第二个dict,以及所有键的双重链接列表(这是记住订单的部分),以及一堆弱反射代理.它的速度并不慢很多,但至少使用普通字典使内存翻倍.但如果合适,请使用它！这就是为什么它在那里:-)
这个怎么运作
基本字典只是一个普通的字典映射键值 – 它根本不是“有序”的.当< key,value>添加了对,密钥将附加到列表中.列表是记住订单的部分.
但如果这是一个Python列表,删除一个密钥将花费O(n)时间两次：O(n)时间在列表中找到密钥,O(n)时间从列表中删除密钥.
所以这是一个双向链表.这使得删除键常量(O(1))时间.但是我们仍然需要找到属于密钥的双向链表节点.为了使该操作也是O(1)时间,第二个 – 隐藏 – 字典将键映射到双向链表中的节点.
所以添加一个新的< key,value> pair需要将对添加到基本字典,创建一个新的双向链表节点来保存密钥,将新节点附加到双向链表,并将密钥映射到隐藏字典中的新节点.工作量的两倍多,但总体上还是O(1)(预期的情况)时间.
类似地,删除当前存在的密钥也是工作量的两倍多但O(1)整体预期时间：使用隐藏的字典找到密钥的双向链表节点,从列表中删除该节点,然后删除密钥从这两个词.
等等.效率很高.