# 8.3. `collections` --- 高性能なコンテナ・データ型

バージョン 2.4 で追加.

Source code: Lib/collections.py and Lib/_abcoll.py

このモジュールは、汎用の Python 組み込みコンテナ `dict`, `list`, `set`, および `tuple` に代わる、特殊なコンテナデータ型を実装しています。

`namedtuple()` | 名前付きフィールドを持つタプルのサブクラスを作成するファクトリ関数 | バージョン 2.6 で追加.
`deque` | 両端における append や pop を高速に行えるリスト風のコンテナ | バージョン 2.4 で追加.
`Counter` | ハッシュ可能なオブジェクトを数え上げる辞書のサブクラス | バージョン 2.7 で追加.
`OrderedDict` | 項目が追加された順序を記憶する辞書のサブクラス | バージョン 2.7 で追加.
`defaultdict` | ファクトリ関数を呼び出して存在しない値を供給する辞書のサブクラス | バージョン 2.5 で追加.

コンテナ型の作成に加えて、 collections モジュールは幾つかの ABC (abstract base classes = 抽象基底クラス) を提供しています。 ABC はクラスが特定のインタフェース持っているかどうか、たとえばハッシュ可能であるかやマッピングであるかを判定するのに利用します。

## 8.3.1. `Counter` オブジェクト

便利で迅速な検数をサポートするカウンタツールが提供されています。例えば:

    >>> # Tally occurrences of words in a list
    >>> cnt = Counter()
    >>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
    ...     cnt[word] += 1
    >>> cnt
    Counter({'blue': 3, 'red': 2, 'green': 1})

    >>> # Find the ten most common words in Hamlet
    >>> import re
    >>> words = re.findall(r'\w+', open('hamlet.txt').read().lower())
    >>> Counter(words).most_common(10)
    [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631),
     ('you', 554),  ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]

class `collections.``Counter`([iterable-or-mapping])

  `Counter` はハッシュ可能なオブジェクトをカウントする `dict` のサブクラスです。これは、要素を辞書のキーとして保存し、そのカウントを辞書の値として保存する、順序付けされていないコレクションです。カウントは、0 や負のカウントを含む整数値をとれます。 `Counter` クラスは、他の言語のバッグや多重集合のようなものです。

  要素は、 iterable から数え上げられたり、他の mapping (やカウンタ) から初期化されます:

      >>> c = Counter()                           # a new, empty counter
      >>> c = Counter('gallahad')                 # a new counter from an iterable
      >>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
      >>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args

  カウンタオブジェクトは辞書のインタフェースを持ちますが、存在しない要素に対して `KeyError` を送出する代わりに 0 を返すという違いがあります:

      >>> c = Counter(['eggs', 'ham'])
      >>> c['bacon']                              # count of a missing element is zero
      0

  カウントを 0 に設定しても、要素はカウンタから取り除かれません。完全に取り除くには、 `del` を使ってください:

      >>> c['sausage'] = 0                        # counter entry with a zero count
      >>> del c['sausage']                        # del actually removes the entry

  バージョン 2.7 で追加.

  カウンタオブジェクトは、すべての辞書に利用できるものに加え、 3 つのメソッドをサポートしています:

  `elements`()

    それぞれの要素を、そのカウント分の回数だけ繰り返すイテレータを返します。要素は任意の順序で返されます。ある要素のカウントが 1 未満なら、 `elements()` はそれを無視します。

        >>> c = Counter(a=4, b=2, c=0, d=-2)
        >>> list(c.elements())
        ['a', 'a', 'a', 'a', 'b', 'b']

  `most_common`([n])

    最も多い n 要素を、カウントが多いものから少ないものまで順に並べたリストを返します。 n が省略されるか `None` であれば、 `most_common()` はカウンタの すべての 要素を返します。等しいカウントの要素は任意に並べられます:

        >>> Counter('abracadabra').most_common(3)
        [('a', 5), ('r', 2), ('b', 2)]

  `subtract`([iterable-or-mapping])

    要素から iterable の要素または mapping の要素が引かれます。 `dict.update()` に似ていますが、カウントを置き換えるのではなく引きます。入力も出力も、 0 や負になりえます。

        >>> c = Counter(a=4, b=2, c=0, d=-2)
        >>> d = Counter(a=1, b=2, c=3, d=4)
        >>> c.subtract(d)
        >>> c
        Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

  普通の辞書のメソッドは、以下の 2 つのメソッドがカウンタに対して異なる振る舞いをするのを除き、 `Counter` オブジェクトにも利用できます。

  `fromkeys`(iterable)

    このクラスメソッドは `Counter` オブジェクトには実装されていません。

  `update`([iterable-or-mapping])

    要素が iterable からカウントされるか、別の mapping (やカウンタ) が追加されます。 `dict.update()` に似ていますが、カウントを置き換えるのではなく追加します。また、 iterable には `(key, value)` 対のシーケンスではなく、要素のシーケンスが求められます。

`Counter` オブジェクトを使ったよくあるパターン:

    sum(c.values())                 # total of all counts
    c.clear()                       # reset all counts
    list(c)                         # list unique elements
    set(c)                          # convert to a set
    dict(c)                         # convert to a regular dictionary
    c.items()                       # convert to a list of (elem, cnt) pairs
    Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
    c.most_common()[:-n-1:-1]       # n least common elements
    c += Counter()                  # remove zero and negative counts

`Counter` オブジェクトを組み合わせて多重集合 (1 以上のカウントをもつカウンタ) を作るために、いくつかの数学演算が提供されています。足し算と引き算は、対応する要素を足したり引いたりすることによってカウンタを組み合わせます。共通部分と合併集合は、対応するカウントの最大値と最小値を返します。それぞれの演算はカウントに符号がついた入力を受け付けますが、カウントが 0 以下である結果は出力から除かれます。

    >>> c = Counter(a=3, b=1)
    >>> d = Counter(a=1, b=2)
    >>> c + d                       # add two counters together:  c[x] + d[x]
    Counter({'a': 4, 'b': 3})
    >>> c - d                       # subtract (keeping only positive counts)
    Counter({'a': 2})
    >>> c & d                       # intersection:  min(c[x], d[x])
    Counter({'a': 1, 'b': 1})
    >>> c | d                       # union:  max(c[x], d[x])
    Counter({'a': 3, 'b': 2})

注釈

カウンタはもともと、推移するカウントを正の整数で表すために設計されました。しかし、他の型や負の値を必要とするユースケースを不必要に排除することがないように配慮されています。このようなユースケースの助けになるように、この節で最低限の範囲と型の制限について記述します。

- `Counter` クラス自体は辞書のサブクラスで、キーと値に制限はありません。値はカウントを表す数であることを意図していますが、値フィールドに任意のものを保存 できます 。
- `most_common()` メソッドが要求するのは、値が順序付け可能なことだけです。
- `c[key] += 1` のようなインプレース演算では、値の型に必要なのは足し算と引き算ができることだけです。よって分数、浮動小数点数、小数も使え、負の値がサポートされています。これと同じことが、負や 0 の値を入力と出力に許す `update()` と `subtract()` メソッドにも言えます。
- 多重集合メソッドは正の値を扱うユースケースに対してのみ設計されています。入力は負や 0 に出来ますが、正の値の出力のみが生成されます。型の制限はありませんが、値の型は足し算、引き算、比較をサポートしている必要があります。
- `elements()` メソッドは整数のカウントを要求します。これは 0 と負のカウントを無視します。

参考

- Python 2.5 向けの Counter class と、それより前の Python 2.4 向けの Bag recipe 。

- Smalltalk の Bag class 。

- Wikipedia の Multisets の項目。

- C++ multisets の例を交えたチュートリアル。

- 数学的な多重集合の演算とそのユースケースは、 Knuth, Donald. The Art of Computer Programming Volume II, Section 4.6.3, Exercise 19 を参照してください。

- 与えられた要素の集まりから与えられた大きさの別個の多重集合をすべて数え上げるには、 `itertools.combinations_with_replacement()` を参照してください。

  > map(Counter, combinations_with_replacement('ABC', 2)) --> AA AB AC BB BC CC

## 8.3.2. `deque` オブジェクト

class `collections.``deque`([iterable[, maxlen]])

  iterable で与えられるデータから、新しい deque オブジェクトを (`append()` をつかって) 左から右に初期化して返します。 iterable が指定されない場合、新しい deque オブジェクトは空になります。

  Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ `O(1)` のパフォーマンスで実行できます。

  `list` オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような `pop(0)` や `insert(0, v)` などの操作ではメモリ移動のために `O(n)` のコストを必要とします。

  バージョン 2.4 で追加.

  maxlen が指定され無かったり `None``* だった場合、 deque は任意のサイズまで大きくなります。 そうでない場合、 deque のサイズは指定された最大長に制限されます。 長さが制限された deque がいっぱいになると、新しい要素を追加するときに追加した要素数分だけ追加したのと反対側から要素が捨てられます。 長さが制限された deque は Unix における ``tail` フィルタと似た機能を提供します。 トランザクションの tracking や最近使った要素だけを残したいデータプール (pool of data) などにも便利です。

  バージョン 2.6 で変更: maxlen パラメータを追加しました。

  Deque オブジェクトは以下のようなメソッドをサポートしています:

  `append`(x)

    x を deque の右側につけ加えます。

  `appendleft`(x)

    x を deque の左側につけ加えます。

  `clear`()

    deque からすべての要素を削除し、長さを 0 にします。

  `count`(x)

    x に等しい deque の要素を数え上げます。

    バージョン 2.7 で追加.

  `extend`(iterable)

    イテレータ化可能な引数 iterable から得られる要素を deque の右側に追加し拡張します。

  `extendleft`(iterable)

    イテレータ化可能な引数 iterable から得られる要素を deque の左側に追加し拡張します。注意: 左から追加した結果は、イテレータ引数の順序とは逆になります。

  `pop`()

    deque の右側から要素をひとつ削除し、その要素を返します。要素がひとつも存在しない場合は `IndexError` を発生させます。

  `popleft`()

    deque の左側から要素をひとつ削除し、その要素を返します。要素がひとつも存在しない場合は `IndexError` を発生させます。

  `remove`(value)

    value の最初に現れるものを削除します。要素が見付からないない場合は `ValueError` を送出します。

    バージョン 2.5 で追加.

  `reverse`()

    deque の要素をインプレースに逆転し、 `None` を返します。

    バージョン 2.7 で追加.

  `rotate`(n=1)

    deque の要素を全体で n ステップだけ右にローテートします。n が負の値の場合は、左にローテートします。

    When the deque is not empty, rotating one step to the right is equivalent to `d.appendleft(d.pop())`, and rotating one step to the left is equivalent to `d.append(d.popleft())`.

  deque オブジェクトは読み取り専用属性も 1 つ提供しています:

  `maxlen`

    deque の最大長で、制限されていなければ `None` です。

    バージョン 2.7 で追加.

上記の操作のほかにも、deque は次のような操作をサポートしています: イテレータ化、pickle、 `len(d)`, `reversed(d)`, `copy.copy(d)`, `copy.deepcopy(d)`, `in` 演算子による包含検査、そして `d[-1]` などの添え字による参照。両端についてインデックスアクセスは O(1) ですが、中央部分については O(n) の遅さです。高速なランダムアクセスが必要ならリストを使ってください。

例:

    >>> from collections import deque
    >>> d = deque('ghi')                 # make a new deque with three items
    >>> for elem in d:                   # iterate over the deque's elements
    ...     print elem.upper()
    G
    H
    I

    >>> d.append('j')                    # add a new entry to the right side
    >>> d.appendleft('f')                # add a new entry to the left side
    >>> d                                # show the representation of the deque
    deque(['f', 'g', 'h', 'i', 'j'])

    >>> d.pop()                          # return and remove the rightmost item
    'j'
    >>> d.popleft()                      # return and remove the leftmost item
    'f'
    >>> list(d)                          # list the contents of the deque
    ['g', 'h', 'i']
    >>> d[0]                             # peek at leftmost item
    'g'
    >>> d[-1]                            # peek at rightmost item
    'i'

    >>> list(reversed(d))                # list the contents of a deque in reverse
    ['i', 'h', 'g']
    >>> 'h' in d                         # search the deque
    True
    >>> d.extend('jkl')                  # add multiple elements at once
    >>> d
    deque(['g', 'h', 'i', 'j', 'k', 'l'])
    >>> d.rotate(1)                      # right rotation
    >>> d
    deque(['l', 'g', 'h', 'i', 'j', 'k'])
    >>> d.rotate(-1)                     # left rotation
    >>> d
    deque(['g', 'h', 'i', 'j', 'k', 'l'])

    >>> deque(reversed(d))               # make a new deque in reverse order
    deque(['l', 'k', 'j', 'i', 'h', 'g'])
    >>> d.clear()                        # empty the deque
    >>> d.pop()                          # cannot pop from an empty deque
    Traceback (most recent call last):
      File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
    IndexError: pop from an empty deque

    >>> d.extendleft('abc')              # extendleft() reverses the input order
    >>> d
    deque(['c', 'b', 'a'])

### 8.3.2.1. `deque` のレシピ

この節では deque をつかったさまざまなアプローチを紹介します。

長さが制限された deque は Unix における `tail` フィルタに相当する機能を提供します:

    def tail(filename, n=10):
        'Return the last n lines of a file'
        return deque(open(filename), n)

別のアプローチとして deque を右に append して左に pop して使うことで追加した要素を維持するのに使えます:

    def moving_average(iterable, n=3):
        # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
        # http://en.wikipedia.org/wiki/Moving_average
        it = iter(iterable)
        d = deque(itertools.islice(it, n-1))
        d.appendleft(0)
        s = sum(d)
        for elem in it:
            s += elem - d.popleft()
            d.append(elem)
            yield s / float(n)

`rotate()` メソッドのおかげで、 `deque` の一部を切り出したり削除したりできることになります。たとえば `del d[n]` の純粋な Python 実装では pop したい要素まで `rotate()` します

    def delete_nth(d, n):
        d.rotate(-n)
        d.popleft()
        d.rotate(n)

`deque` の切り出しを実装するのにも、同様のアプローチを使います。まず対象となる要素を `rotate()` によって deque の左端までもってきてから、 `popleft()` をつかって古い要素を消します。そして、 `extend()` で新しい要素を追加したのち、逆のローテートでもとに戻せばよいのです。このアプローチをやや変えたものとして、Forth スタイルのスタック操作、つまり `dup`, `drop`, `swap`, `over`, `pick`, `rot`, および `roll` を実装するのも簡単です。

## 8.3.3. `defaultdict` オブジェクト

class `collections.``defaultdict`([default_factory[, ...]])

  新しいディクショナリ状のオブジェクトを返します。 `defaultdict` は組込みの `dict` のサブクラスです。メソッドをオーバーライドし、書き込み可能なインスタンス変数を1つ追加している以外は `dict` クラスと同じです。同じ部分については以下では省略されています。

  1つめの引数は `default_factory` 属性の初期値です。デフォルトは `None` です。残りの引数はキーワード引数もふくめ、 `dict` のコンストラクタにあたえられた場合と同様に扱われます。

  バージョン 2.5 で追加.

  `defaultdict` オブジェクトは標準の `dict` に加えて、以下のメソッドを実装しています:

  `__missing__`(key)

    もし `default_factory` 属性が `None` であれば、このメソッドは `KeyError` 例外を、 key を引数として発生させます。

    もし `default_factory` 属性が `None` でなければ、このメソッドは `default_factory` を引数なしで呼び出し、あたえられた key に対応するデフォルト値を作ります。そしてこの値を key に対応する値を辞書に登録して返ります。

    もし `default_factory` の呼出が例外を発生させた場合には、変更せずそのまま例外を投げます。

    このメソッドは `dict` クラスの `__getitem__()` メソッドで、キーが存在しなかった場合によびだされます。値を返すか例外を発生させるのどちらにしても、 `__getitem__()` からもそのまま値が返るか例外が発生します。

    なお、 `__missing__()` は `__getitem__()` 以外のいかなる演算に対しても呼び出され ません 。よって `get()` は、普通の辞書と同様に、 `default_factory` を使うのではなくデフォルトとして `None` を返します。

  `defaultdict` オブジェクトは以下のインスタンス変数をサポートしています:

  `default_factory`

    この属性は `__missing__()` メソッドによって使われます。これは存在すればコンストラクタの第1引数によって初期化され、そうでなければ `None` になります。

### 8.3.3.1. `defaultdict` の使用例

`list` を `default_factory` とすることで、キー=値ペアのシーケンスをリストの辞書へ簡単にグループ化できます。:

    >>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
    >>> d = defaultdict(list)
    >>> for k, v in s:
    ...     d[k].append(v)
    ...
    >>> d.items()
    [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

それぞれのキーが最初に登場したとき、マッピングにはまだ存在しません。そのためエントリは `default_factory` 関数が返す空の `list` を使って自動的に作成されます。 `list.append()` 操作は新しいリストに紐付けられます。キーが再度出現下場合には、通常の参照動作が行われます(そのキーに対応するリストが返ります)。そして `list.append()` 操作で別の値をリストに追加します。このテクニックは `dict.setdefault()` を使った等価なものよりシンプルで速いです:

    >>> d = {}
    >>> for k, v in s:
    ...     d.setdefault(k, []).append(v)
    ...
    >>> d.items()
    [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

`default_factory` を `int` にすると、 `defaultdict` を(他の言語の bag や multisetのように)要素の数え上げに便利に使うことができます:

    >>> s = 'mississippi'
    >>> d = defaultdict(int)
    >>> for k in s:
    ...     d[k] += 1
    ...
    >>> d.items()
    [('i', 4), ('p', 2), ('s', 4), ('m', 1)]

最初に文字が出現したときは、マッピングが存在しないので `default_factory` 関数が `int()` を呼んでデフォルトのカウント0を生成します。インクリメント操作が各文字を数え上げます。

常に0を返す `int()` は特殊な関数でした。定数を生成するより速くて柔軟な方法は、 0に限らず何でも定数を生成する `itertools.repeat()` を使うことです。

    >>> def constant_factory(value):
    ...     return itertools.repeat(value).next
    >>> d = defaultdict(constant_factory('<missing>'))
    >>> d.update(name='John', action='ran')
    >>> '%(name)s %(action)s to %(object)s' % d
    'John ran to <missing>'

`default_factory` を `set` に設定することで、 `defaultdict` をセットの辞書を作るために利用することができます:

    >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
    >>> d = defaultdict(set)
    >>> for k, v in s:
    ...     d[k].add(v)
    ...
    >>> d.items()
    [('blue', set([2, 4])), ('red', set([1, 3]))]

## 8.3.4. `namedtuple()` 名前付きフィールドを持つタプルのファクトリ関数

名前付きタプルはタプルの中の場所に意味を割り当てて、より読みやすく自己解説的なコードを書けるようにします。通常のタプルが利用されていた場所で利用でき、場所に対するインデックスの代わりに名前を使ってフィールドにアクセスできます。

`collections.``namedtuple`(typename, field_names[, verbose=False][, rename=False])

  typename という名前の tuple の新しいサブクラスを返します。新しいサブクラスは、 tuple に似ているけれどもインデックスやイテレータだけでなく属性名によるアクセスもできるオブジェクトを作るのに使います。このサブクラスのインスタンスは、わかりやすい docstring (型名と属性名が入っています) や、 tuple の内容を `name=value` という形のリストで返す使いやすい `__repr__()` も持っています。

  field_names は `['x', 'y']` のような文字列のシーケンスです。 field_names には、代わりに各属性名を空白文字 (whitespace) および/またはカンマ (,) で区切った文字列を渡すこともできます。例えば、 `'x y'` や `'x, y'` です。

  アンダースコア (_) で始まる名前を除いて、 Python の正しい識別子 (identifier) ならなんでも属性名として使うことができます。正しい識別子とはアルファベット(letters), 数字(digits), アンダースコア(_) を含みますが、数字やアンダースコアで始まる名前や、 class, for, return, global, pass, print, raise などといった `keyword` は使えません。

  rename が真なら、不適切なフィールド名は自動的に位置引数に置き換えられます。例えば `['abc', 'def', 'ghi', 'abc']` は、予約語 `def` と重複しているフィールド名 `abc` が除去され、 `['abc', '_1', 'ghi', '_3']` に変換されます。

  verbose が真なら、クラスを作る直前にクラス定義が表示されます。

  名前付きタプルのインスタンスはインスタンスごとの辞書を持たないので、軽量で、普通のタプル以上のメモリを使用しません。

  バージョン 2.6 で追加.

  バージョン 2.7 で変更: rename のサポートを追加しました。

例:

    >>> Point = namedtuple('Point', ['x', 'y'], verbose=True)
    class Point(tuple):
        'Point(x, y)'

        __slots__ = ()

        _fields = ('x', 'y')

        def __new__(_cls, x, y):
            'Create new instance of Point(x, y)'
            return _tuple.__new__(_cls, (x, y))

        @classmethod
        def _make(cls, iterable, new=tuple.__new__, len=len):
            'Make a new Point object from a sequence or iterable'
            result = new(cls, iterable)
            if len(result) != 2:
                raise TypeError('Expected 2 arguments, got %d' % len(result))
            return result

        def __repr__(self):
            'Return a nicely formatted representation string'
            return 'Point(x=%r, y=%r)' % self

        def _asdict(self):
            'Return a new OrderedDict which maps field names to their values'
            return OrderedDict(zip(self._fields, self))

        def _replace(_self, **kwds):
            'Return a new Point object replacing specified fields with new values'
            result = _self._make(map(kwds.pop, ('x', 'y'), _self))
            if kwds:
                raise ValueError('Got unexpected field names: %r' % kwds.keys())
            return result

        def __getnewargs__(self):
            'Return self as a plain tuple.  Used by copy and pickle.'
            return tuple(self)

        __dict__ = _property(_asdict)

        def __getstate__(self):
            'Exclude the OrderedDict from pickling'
            pass

        x = _property(_itemgetter(0), doc='Alias for field number 0')

        y = _property(_itemgetter(1), doc='Alias for field number 1')

    >>> p = Point(11, y=22)     # instantiate with positional or keyword arguments
    >>> p[0] + p[1]             # indexable like the plain tuple (11, 22)
    33
    >>> x, y = p                # unpack like a regular tuple
    >>> x, y
    (11, 22)
    >>> p.x + p.y               # fields also accessible by name
    33
    >>> p                       # readable __repr__ with a name=value style
    Point(x=11, y=22)

名前付きタプルは `csv` や `sqlite3` モジュールが返すタプルのフィールドに名前を付けるときにとても便利です:

    EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade')

    import csv
    for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))):
        print emp.name, emp.title

    import sqlite3
    conn = sqlite3.connect('/companydata')
    cursor = conn.cursor()
    cursor.execute('SELECT name, age, title, department, paygrade FROM employees')
    for emp in map(EmployeeRecord._make, cursor.fetchall()):
        print emp.name, emp.title

タプルから継承したメソッドに加えて、名前付きタプルは3つの追加メソッドと一つの属性をサポートしています。フィールド名との衝突を避けるためにメソッド名と属性名はアンダースコアで始まります。

classmethod `somenamedtuple.``_make`(iterable)

  既存の sequence や Iterable から新しいインスタンスを作るクラスメソッド.

      >>> t = [11, 22]
      >>> Point._make(t)
      Point(x=11, y=22)

`somenamedtuple.``_asdict`()

  フィールド名を対応する値にマッピングする新しい順序付き辞書 (`OrderedDict`) を返します:

      >>> p = Point(x=11, y=22)
      >>> p._asdict()
      OrderedDict([('x', 11), ('y', 22)])

  バージョン 2.7 で変更: 通常の `dict` の代わりに `OrderedDict` を返すようになりました。

`somenamedtuple.``_replace`(**kwargs)

  指定されたフィールドを新しい値で置き換えた、新しい名前付きタプルを作って返します:

      >>> p = Point(x=11, y=22)
      >>> p._replace(x=33)
      Point(x=33, y=22)

      >>> for partnum, record in inventory.items():
      ...     inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now())

`somenamedtuple.``_fields`

  フィールド名をリストにしたタプル. 内省 (introspection) したり、既存の名前付きタプルをもとに新しい名前つきタプルを作成する時に便利です。

      >>> p._fields            # view the field names
      ('x', 'y')

      >>> Color = namedtuple('Color', 'red green blue')
      >>> Pixel = namedtuple('Pixel', Point._fields + Color._fields)
      >>> Pixel(11, 22, 128, 255, 0)
      Pixel(x=11, y=22, red=128, green=255, blue=0)

文字列に格納された名前を使って名前つきタプルから値を取得するには `getattr()` 関数を使います:

    >>> getattr(p, 'x')
    11

辞書を名前付きタプルに変換するには、 `**` 演算子 (double-star-operator, 引数リストのアンパック で説明しています) を使います。:

    >>> d = {'x': 11, 'y': 22}
    >>> Point(**d)
    Point(x=11, y=22)

名前付きタプルは通常の Python クラスなので、継承して機能を追加したり変更するのは容易です。次の例では計算済みフィールドと固定幅の print format を追加しています:

    >>> class Point(namedtuple('Point', 'x y')):
    ...     __slots__ = ()
    ...     @property
    ...     def hypot(self):
    ...         return (self.x ** 2 + self.y ** 2) ** 0.5
    ...     def __str__(self):
    ...         return 'Point: x=%6.3f  y=%6.3f  hypot=%6.3f' % (self.x, self.y, self.hypot)
    ...
    >>> for p in Point(3, 4), Point(14, 5/7.):
    ...     print p
    Point: x= 3.000  y= 4.000  hypot= 5.000
    Point: x=14.000  y= 0.714  hypot=14.018

このサブクラスは `__slots__` に空のタプルをセットしています。これにより、インスタンス辞書の作成を抑制してメモリ使用量を低く保つのに役立ちます。

サブクラス化は新しいフィールドを追加するのには適していません。代わりに、新しい名前付きタプルを `_fields` 属性を元に作成してください:

    >>> Point3D = namedtuple('Point3D', Point._fields + ('z',))

`_replace()` でプロトタイプのインスタンスをカスタマイズする方法で、デフォルト値を実現できます:

    >>> Account = namedtuple('Account', 'owner balance transaction_count')
    >>> default_account = Account('<owner name>', 0.0, 0)
    >>> johns_account = default_account._replace(owner='John')

列挙型定数は名前付きタプルでも実装できますが、クラス定義を利用した方がシンプルで効率的です:

    >>> Status = namedtuple('Status', 'open pending closed')._make(range(3))
    >>> Status.open, Status.pending, Status.closed
    (0, 1, 2)
    >>> class Status:
    ...     open, pending, closed = range(3)

参考

Python 2.4 向けの Named tuple recipe 。

## 8.3.5. `OrderedDict` オブジェクト

順序付き辞書 (ordered dictionary) は、ちょうど普通の辞書と同じようなものですが、項目が挿入された順序を記憶します。順序付き辞書に渡ってイテレートするとき、項目はそのキーが最初に追加された順序で返されます。

class `collections.``OrderedDict`([items])

  通常の `dict` メソッドをサポートする、辞書のサブクラスのインスタンスを返します。 OrderedDict は、キーが最初に追加された順序を記憶します。新しい項目が既存の項目を上書きしても、元の挿入位置は変わらないままです。項目を削除して再挿入するとそれが最後に移動します。

  バージョン 2.7 で追加.

`OrderedDict.``popitem`(last=True)

  順序付き辞書の `popitem()` メソッドは、(key, value) 対を返して消去します。この対は last が真なら後入先出で、偽なら先入先出で返されます。

通常のマッピングのメソッドに加え、順序付き辞書は `reversed()` による逆順の反復もサポートしています。

`OrderedDict` 間の等価判定は順序が影響し、 `list(od1.items())==list(od2.items())` のように実装されます。 `OrderedDict` オブジェクトと他のマッピング (`Mapping`) オブジェクトの等価判定は、順序に影響されず、通常の辞書と同様です。これによって、 `OrderedDict` オブジェクトは通常の辞書が使われるところならどこでも使用できます。

`OrderedDict` コンストラクタと `update()` メソッドは、どちらもキーワード引数を受け付けますが、その順序は失われます。これは、Python の関数呼び出しの意味づけにおいて、キーワード引数は順序付けされていない辞書を用いて渡されるからです。

参考

Python 2.4 以降で動作する、 Equivalent OrderedDict recipe 。

### 8.3.5.1. `OrderedDict` の例とレシピ

順序付き辞書は挿入順序を記憶するので、ソートと組み合わせて使うことで、ソートされた辞書を作れます:

    >>> # regular unsorted dictionary
    >>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}

    >>> # dictionary sorted by key
    >>> OrderedDict(sorted(d.items(), key=lambda t: t[0]))
    OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])

    >>> # dictionary sorted by value
    >>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
    OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

    >>> # dictionary sorted by length of the key string
    >>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
    OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

この新しい順序付き辞書は、項目が削除されてもソートされた順序を保持します。しかし、キーが追加されるとき、そのキーは最後に追加され、ソートは保持されません。

キーが 最後に 挿入された順序を記憶するような、順序付き辞書の変種を作るのも簡単です。新しい項目が既存の項目を上書きしたら、元の挿入位置は最後に移動します:

    class LastUpdatedOrderedDict(OrderedDict):
        'Store items in the order the keys were last added'

        def __setitem__(self, key, value):
            if key in self:
                del self[key]
            OrderedDict.__setitem__(self, key, value)

順序付き辞書と `Counter` クラスを組み合わせると、要素が最初に現れた順を記憶するカウンタができます:

    class OrderedCounter(Counter, OrderedDict):
         'Counter that remembers the order elements are first encountered'

         def __repr__(self):
             return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

         def __reduce__(self):
             return self.__class__, (OrderedDict(self),)

## 8.3.6. コレクション抽象基底クラス

collections モジュールは以下の ABC (抽象基底クラス) を提供します:

ABC | 継承しているクラス | 抽象メソッド | mixin メソッド
--- | --- | --- | ---
`Container` |  | `__contains__` |
`Hashable` |  | `__hash__` |
`Iterable` |  | `__iter__` |
`Iterator` | `Iterable` | `next` | `__iter__`
`Sized` |  | `__len__` |
`Callable` |  | `__call__` |
`Sequence` | `Sized`, `Iterable`, `Container` | `__getitem__`, `__len__` | `__contains__`, `__iter__`, `__reversed__`, `index`, `count`
`MutableSequence` | `Sequence` | `__getitem__`, `__setitem__`, `__delitem__`, `__len__`, `insert` | `Sequence` から継承したメソッドと、 `append`, `reverse`, `extend`, `pop`, `remove`, `__iadd__`
`Set` | `Sized`, `Iterable`, `Container` | `__contains__`, `__iter__`, `__len__` | `__le__`, `__lt__`, `__eq__`, `__ne__`, `__gt__`, `__ge__`, `__and__`, `__or__`, `__sub__`, `__xor__`, `isdisjoint`
`MutableSet` | `Set` | `__contains__`, `__iter__`, `__len__`, `add`, `discard` | `Set` から継承したメソッドと、 `clear`, `pop`, `remove`, `__ior__`, `__iand__`, `__ixor__`, `__isub__`
`Mapping` | `Sized`, `Iterable`, `Container` | `__getitem__`, `__iter__`, `__len__` | `__contains__`, `keys`, `items`, `values`, `get`, `__eq__`, `__ne__`
`MutableMapping` | `Mapping` | `__getitem__`, `__setitem__`, `__delitem__`, `__iter__`, `__len__` | `Mapping` から継承したメソッドと、 `pop`, `popitem`, `clear`, `update`, `setdefault`
`MappingView` | `Sized` |  | `__len__`
`ItemsView` | `MappingView`, `Set` |  | `__contains__`, `__iter__`
`KeysView` | `MappingView`, `Set` |  | `__contains__`, `__iter__`
`ValuesView` | `MappingView` |  | `__contains__`, `__iter__`

class `collections.``Container`
class `collections.``Hashable`
class `collections.``Sized`
class `collections.``Callable`

  それぞれメソッド `__contains__()`, `__hash__()`, `__len__()`, `__call__()` を提供するクラスの ABC です。

class `collections.``Iterable`

  `__iter__()` メソッドを提供するクラスの ABC です。 iterable の定義も参照してください。

class `collections.``Iterator`

  `__iter__()` メソッドと `next()` メソッドを提供するクラスの ABC です。 iterator の定義も参照してください。

class `collections.``Sequence`
class `collections.``MutableSequence`

  読み出し専用でミュータブルな シーケンス の ABC です。

class `collections.``Set`
class `collections.``MutableSet`

  読み出し専用でミュータブルな集合の ABC です。

class `collections.``Mapping`
class `collections.``MutableMapping`

  読み出し専用でミュータブルな マッピング の ABC です。

class `collections.``MappingView`
class `collections.``ItemsView`
class `collections.``KeysView`
class `collections.``ValuesView`

  マッピング、要素、キー、値の ビュー の ABC です。

これらの ABC はクラスやインスタンスが特定の機能を提供しているかどうかを調べるのに使えます。例えば:

    size = None
    if isinstance(myvar, collections.Sized):
        size = len(myvar)

幾つかの ABC はコンテナ型 API を提供するクラスを開発するのを助ける mixin 型としても使えます。例えば、 `Set` API を提供するクラスを作る場合、3つの基本になる抽象メソッド `__contains__()`, `__iter__()`, `__len__()` だけが必要です。 ABC が残りの `__and__()` や `isdisjoint()` といったメソッドを提供します:

    class ListBasedSet(collections.Set):
         ''' Alternate set implementation favoring space over speed
             and not requiring the set elements to be hashable. '''
         def __init__(self, iterable):
             self.elements = lst = []
             for value in iterable:
                 if value not in lst:
                     lst.append(value)

         def __iter__(self):
             return iter(self.elements)

         def __contains__(self, value):
             return value in self.elements

         def __len__(self):
             return len(self.elements)

    s1 = ListBasedSet('abcdef')
    s2 = ListBasedSet('defghi')
    overlap = s1 & s2            # The __and__() method is supported automatically

`Set` と `MutableSet` を mixin 型として利用するときの注意点:

1. 幾つかの set の操作は新しい set を作るので、デフォルトの mixin メソッドは iterable から新しいインスタンスを作成する方法を必要とします。クラスのコンストラクタは `ClassName(iterable)` の形のシグネチャを持つと仮定されます。内部の `_from_iterable()` というクラスメソッドが `cls(iterable)` を呼び出して新しい set を作る部分でこの仮定が使われています。コンストラクタのシグネチャが異なるクラスで `Set` を使う場合は、 iterable 引数から新しいインスタンスを生成するように `_from_iterable()` をオーバーライドする必要があります。
2. (たぶん意味はそのままに速度を向上する目的で)比較をオーバーライドする場合、 `__le__()` と `__ge__()` だけを再定義すれば、その他の演算は自動的に追随します。
3. `Set` mixin型は set のハッシュ値を計算する `_hash()` メソッドを提供しますが、すべての set が hashable や immutable とは限らないので、 `__hash__()` は提供しません。 mixin を使ってハッシュ可能な set を作る場合は、 `Set` と `Hashable` の両方を継承して、 `__hash__ = Set._hash` と定義してください。

参考

- `MutableSet` を使った例として OrderedSet recipe。
- ABCs についての詳細は、 `abc` モジュールと PEP 3119 を参照してください。