### ナビゲーション

- 索引
- モジュール |
- 次へ |
- 前へ |
- Python v2.6.2 documentation »
- Python 標準ライブラリ »
- 9. データ型 »

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

バージョン 2.4 で追加.

このモジュールでは高性能なコンテナ・データ型を実装しています。現在のところ、 `deque` と `defaultdict` という２つのデータ型と、 `namedtuple()` というデータ型ファクトリ関数があります。

バージョン 2.5 で変更: `defaultdict` の追加.

バージョン 2.6 で変更: `namedtuple()` の追加.

このモジュールが提供する特殊なコンテナは、 Python の汎用的なコンテナ、 `dict`, `list`, `set`, `tuple` の代わりに なります。

ここで提供されるコンテナと別に、オプションとして `bsddb` モジュールが in-memory もしくは file を使った、文字列をキーとする順序付き辞書を、 `bsddb.btopen()` メソッドで提供しています。

コンテナ型に加えて、 collections モジュールは幾つかの ABC (abstract base classes = 抽象基本型) を提供しています。 ABC はクラスが特定のインタフェース(例えばhashable や mapping)を 持っているかどうかをテストするのに利用します。

バージョン 2.6 で変更: Added abstract base classes.

## 9.3.1. ABCs - abstract base classes

collections モジュールは以下の ABC を提供します。

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

これらの 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):
         ''' 速度よりもメモリ使用量を重視して、 hashable も提供しない
             set の別の実装 '''
         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            # __and__() は ABC により自動的に提供される

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

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

参考

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

## 9.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 にします。

  `extend`(iterable)

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

  `extendleft`(iterable)

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

  `pop`()

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

  `popleft`()

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

  `remove`(value)

    最初に現れる value を削除します。要素がみつからないない場合は `ValueError` を発生させます。

    バージョン 2.5 で追加.

  `rotate`(n)

    deque の要素を全体で n ステップだけ右にローテートします。 n が負の値の場合は、左にローテートします。Deque を ひとつ右にローテートすることは `d.appendleft(d.pop())` と同じです。

上記の操作のほかにも、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')                 # 3つの要素からなる新しい deque をつくる。
    >>> for elem in d:                   # deque の要素をひとつずつたどる。
    ...     print elem.upper()
    G
    H
    I

    >>> d.append('j')                    # 新しい要素を右側につけたす。
    >>> d.appendleft('f')                # 新しい要素を左側につけたす。
    >>> d                                # deque の表現形式。
    deque(['f', 'g', 'h', 'i', 'j'])

    >>> d.pop()                          # いちばん右側の要素を削除し返す。
    'j'
    >>> d.popleft()                      # いちばん左側の要素を削除し返す。
    'f'
    >>> list(d)                          # deque の内容をリストにする。
    ['g', 'h', 'i']
    >>> d[0]                             # いちばん左側の要素をのぞく。
    'g'
    >>> d[-1]                            # いちばん右側の要素をのぞく。
    'i'

    >>> list(reversed(d))                # deque の内容を逆順でリストにする。
    ['i', 'h', 'g']
    >>> 'h' in d                         # deque を検索。
    True
    >>> d.extend('jkl')                  # 複数の要素を一度に追加する。
    >>> d
    deque(['g', 'h', 'i', 'j', 'k', 'l'])
    >>> d.rotate(1)                      # 右ローテート
    >>> d
    deque(['l', 'g', 'h', 'i', 'j', 'k'])
    >>> d.rotate(-1)                     # 左ローテート
    >>> d
    deque(['g', 'h', 'i', 'j', 'k', 'l'])

    >>> deque(reversed(d))               # 新しい deque を逆順でつくる。
    deque(['l', 'k', 'j', 'i', 'h', 'g'])
    >>> d.clear()                        # deque を空にする。
    >>> d.pop()                          # 空の deque からは pop できない。
    Traceback (most recent call last):
      File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
    IndexError: pop from an empty deque

    >>> d.extendleft('abc')              # extendleft() は入力を逆順にする。
    >>> d
    deque(['c', 'b', 'a'])

## 9.3.3. `deque` のレシピ

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

`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` を実装するのも簡単です。

複数パスのデータ・リダクションアルゴリズムは、 `popleft()` を複数回呼んで要素をとりだし、リダクション用の関数を適用してから `append()` で deque に戻してやることにより、簡潔かつ効率的に表現することができます。

たとえば入れ子状になったリストでバランスされた二進木をつくりたい場合、 2つの隣接するノードをひとつのリストにグループ化することになります:

    >>> def maketree(iterable):
    ...     d = deque(iterable)
    ...     while len(d) > 1:
    ...         pair = [d.popleft(), d.popleft()]
    ...         d.append(pair)
    ...     return list(d)
    ...
    >>> print maketree('abcdefgh')
    [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]

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

    def tail(filename, n=10):
        'ファイルの最後の n 行を返す.'
        return deque(open(filename), n)

## 9.3.4. `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__()` からもそのまま値が返るか例外が発生します。

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

  `default_factory`

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

### 9.3.4.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]))]

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

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

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

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

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

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

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

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

  バージョン 2.6 で追加.

Example:

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

            __slots__ = ()

            _fields = ('x', 'y')

            def __new__(cls, 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 'Point(x=%r, y=%r)' % self

            def _asdict(t):
                'Return a new dict which maps field names to their values'
                return {'x': t[0], 'y': t[1]}

            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 tuple(self)

            x = property(itemgetter(0))
            y = property(itemgetter(1))

    >>> p = Point(11, y=22)     # 順序による引数やキーワード引数を使ってインスタンス化
    >>> p[0] + p[1]             # 通常の tuple (11, 22) と同じようにインデックスアクセス
    33
    >>> x, y = p                # 通常の tuple と同じようにアンパック
    >>> x, y
    (11, 22)
    >>> p.x + p.y               # 名前でフィールドにアクセス
    33
    >>> p                       # name=value スタイルの読みやすい __repr__
    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つの追加メソッドと 一つの属性をサポートしています。フィールド名との衝突を避けるために メソッド名と属性名はアンダースコアで始まります。

`somenamedtuple.``_make`(iterable)

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

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

`somenamedtuple.``_asdict`()

  フィールド名とその値をもとに新しい辞書(dict)を作って返します:

      >>> p._asdict()
      {'x': 11, 'y': 22}

`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)

参考

Named tuple recipe は Python 2.4 で使えます。

### ナビゲーション

- 索引
- モジュール |
- 次へ |
- 前へ |
- Python v2.6.2 documentation »
- Python 標準ライブラリ »
- 9. データ型 »