Python レシピ更新 ハッシュの要素を挿入した順に取り出す

『118:ハッシュの要素を挿入した順に取り出す』を 「PEP 372 で順序つき辞書提案中」という内容から、「標準モジュール collections に OrderedDict があるよ」という内容に更新！

collections.OrderedDict 、その実装

collections.OrderedDict の実装は「順序の保持に双方向循環リストを用いる」というものだった。すべてのメソッドの計算量が通常の dict と同じオーダーとなっている*1とのこと。

なので「順序の保持に Python 組み込みの list*2 を用いる」実装のものとは特性が異なる操作があったりする。たとえば OrderedDict だと値のセット(__setitem__)は O(1)。 http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py だと既存のキーがすでに存在しないかどうか線形探索するので O(n) 。代わりにインデックスアクセスは OrderedDict には用意されていなくて、無理に行えば O(n) （コード例は以下）。 odict だと byindex メソッドで O(1) 。

OrderedDict に無理やりインデックスアクセスする例1

>>> from collections import OrderedDict
>>> a = OrderedDict()
>>> a['x'] = 'X'
>>> a['y'] = 'Y'
>>> keys = list(a)
>>> keys[0]
'x'
>>> a[_]
'X'

OrderedDict に無理やりインデックスアクセスする例2

メモリ消費量および先頭に近いほうの値を取り出す際の速度が「例1」のものより有利ではあるものの、負の値のインデックスをつかうことはできない。

>>> from collections import OrderedDict
>>> from itertools import islice
>>> def nth(iterable, n, default=None):
...     return next(islice(iterable, n, None), default)
...
>>> a = OrderedDict()
>>> a['x'] = 'X'
>>> a['y'] = 'Y'
>>> nth(a, 0)
'x'
>>> a[_]
'X'
>>>
>>> nth(a, -1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in nth
ValueError: Indices for islice() must be None or an integer: 0 <= x <= maxint.

*1:原文：「Big-O running times for all methods are the same as for regular dictionaries.」

*2:CPython の list は PyObject へのポインタを保持する配列。 PyListObject 構造体は PyObject **ob_item; Py_ssize_t allocated; というメンバを持っていて、そのコメントには Vector of pointers to list elements. list[0] is ob_item[0], etc. とか ob_item contains space for 'allocated' elements. The number currently in use is ob_size. とある。