はじめに

こんにちは！今回は、Pythonのcollectionsモジュールに含まれる高度なコレクション型であるdeque、Counter、OrderedDictについて、それぞれの特徴と活用法を詳しく解説します。

1. deque（デック）

deque（発音は「デック」）は、両端キュー（double-ended queue）を実現するためのコレクション型です。リストと似ていますが、両端での要素の追加と削除が非常に高速です。

1.1 基本的な使い方

from collections import deque

d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])

# 右端に追加
d.append(6)
print(d)  # deque([1, 2, 3, 4, 5, 6])

# 左端に追加
d.appendleft(0)
print(d)  # deque([0, 1, 2, 3, 4, 5, 6])

# 右端から削除
right = d.pop()
print(right)  # 6
print(d)  # deque([0, 1, 2, 3, 4, 5])

# 左端から削除
left = d.popleft()
print(left)  # 0
print(d)  # deque([1, 2, 3, 4, 5])

1.2 高度な使用例

1.2.1 循環バッファとしての使用

dequeは最大長を指定でき、これを超えると反対側の要素が自動的に削除されます。これは、最新のN個の要素だけを保持したい場合に便利です。

from collections import deque

recent_items = deque(maxlen=3)
for i in range(5):
    recent_items.append(i)
    print(recent_items)

# 出力:
# deque([0], maxlen=3)
# deque([0, 1], maxlen=3)
# deque([0, 1, 2], maxlen=3)
# deque([1, 2, 3], maxlen=3)
# deque([2, 3, 4], maxlen=3)

1.2.2 dequeの回転

dequeはrotateメソッドを使って要素を循環させることができます。

d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)  # deque([4, 5, 1, 2, 3])

d.rotate(-1)
print(d)  # deque([5, 1, 2, 3, 4])

1.3 パフォーマンス比較

dequeとlistの両端での操作のパフォーマンスを比較してみましょう。

import timeit

def test_list_append(n):
    lst = []
    for i in range(n):
        lst.append(i)

def test_deque_append(n):
    d = deque()
    for i in range(n):
        d.append(i)

def test_list_appendleft(n):
    lst = []
    for i in range(n):
        lst.insert(0, i)

def test_deque_appendleft(n):
    d = deque()
    for i in range(n):
        d.appendleft(i)

n = 100000
print(f"List append:      {timeit.timeit(lambda: test_list_append(n), number=1):.6f}")
print(f"Deque append:     {timeit.timeit(lambda: test_deque_append(n), number=1):.6f}")
print(f"List appendleft:  {timeit.timeit(lambda: test_list_appendleft(n), number=1):.6f}")
print(f"Deque appendleft: {timeit.timeit(lambda: test_deque_appendleft(n), number=1):.6f}")

出力例:

List append:      0.005123
Deque append:     0.005678
List appendleft:  0.789012
Deque appendleft: 0.006789

dequeは両端での操作が非常に高速であることがわかります。特に、先頭への挿入操作はlistと比べて劇的に速いです。

2. Counter

Counterは、要素の出現回数を数えるための辞書のサブクラスです。

2.1 基本的な使い方

from collections import Counter

# リストから作成
c = Counter(['a', 'b', 'c', 'a', 'b', 'b'])
print(c)  # Counter({'b': 3, 'a': 2, 'c': 1})

# 文字列から作成
word = "mississippi"
c = Counter(word)
print(c)  # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

# 最も一般的な要素
print(c.most_common(2))  # [('i', 4), ('s', 4)]

2.2 高度な使用例

2.2.1 数学的な集合演算

Counterオブジェクトは加算、減算、交差（AND）、合併（OR）などの演算をサポートしています。

c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)

print(c1 + c2)  # Counter({'a': 4, 'b': 3})
print(c1 - c2)  # Counter({'a': 2})
print(c1 & c2)  # Counter({'a': 1, 'b': 1})
print(c1 | c2)  # Counter({'a': 3, 'b': 2})

2.2.2 要素のカウントの更新

c = Counter(a=3, b=1)
c.update(['a', 'a', 'c'])
print(c)  # Counter({'a': 5, 'b': 1, 'c': 1})

c.subtract(['a', 'b'])
print(c)  # Counter({'a': 4, 'c': 1, 'b': 0})

2.3 実践的な使用例：単語頻度の分析

import re
from collections import Counter

def word_frequency(text):
    words = re.findall(r'\w+', text.lower())
    return Counter(words).most_common()

text = """
Python is a programming language that lets you work quickly and integrate systems more effectively. 
Python is powerful... and fast; plays well with others; runs everywhere; is friendly & easy to learn; is Open.
"""

print(word_frequency(text))

出力:

[('is', 3), ('python', 2), ('and', 2), ('a', 1), ('programming', 1), ('language', 1), ('that', 1), ('lets', 1), ('you', 1), ('work', 1), ('quickly', 1), ('integrate', 1), ('systems', 1), ('more', 1), ('effectively', 1), ('powerful', 1), ('fast', 1), ('plays', 1), ('well', 1), ('with', 1), ('others', 1), ('runs', 1), ('everywhere', 1), ('friendly', 1), ('easy', 1), ('to', 1), ('learn', 1), ('open', 1)]

3. OrderedDict

OrderedDictは、要素の挿入順序を記憶する辞書のサブクラスです。Python 3.7以降の通常のdictも順序を保持しますが、OrderedDictには追加の機能があります。

3.1 基本的な使い方

from collections import OrderedDict

od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3

print(od)  # OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# キーの移動
od.move_to_end('b')
print(od)  # OrderedDict([('a', 1), ('c', 3), ('b', 2)])

od.move_to_end('b', last=False)
print(od)  # OrderedDict([('b', 2), ('a', 1), ('c', 3)])

3.2 高度な使用例

3.2.1 LRU (Least Recently Used) キャッシュの実装

OrderedDictを使用して、簡単なLRUキャッシュを実装できます。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

# 使用例
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))       # 1
cache.put(3, 3)           # 2が削除される
print(cache.get(2))       # -1 (not found)
cache.put(4, 4)           # 1が削除される
print(cache.get(1))       # -1 (not found)
print(cache.get(3))       # 3
print(cache.get(4))       # 4

3.2.2 順序を考慮した辞書の比較

OrderedDictは、順序も考慮して等価性を判断します。

od1 = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od2 = OrderedDict([('a', 1), ('c', 3), ('b', 2)])

print(od1 == od2)  # False

d1 = dict([('a', 1), ('b', 2), ('c', 3)])
d2 = dict([('a', 1), ('c', 3), ('b', 2)])

print(d1 == d2)  # True

3.3 パフォーマンスの考慮

OrderedDictは、通常のdictよりもメモリを多く使用します。また、頻繁に要素の順序を変更する操作は、パフォーマンスに影響を与える可能性があります。大量のデータを扱う場合や、順序が重要でない場合は、通常のdictを使用することをお勧めします。

まとめ

dequeは、両端でのデータの追加と削除が高速な双方向キューです。循環バッファの実装や、両端での頻繁な操作が必要な場合に適しています。
Counterは、要素の出現回数を効率的に数えるためのツールです。データの頻度分析や、多数の要素を扱う集合演算に便利です。
OrderedDictは、要素の挿入順序を保持する辞書です。LRUキャッシュの実装や、順序が重要なデータの管理に適しています。

これらの高度なコレクション型を適切に使用することで、より効率的で読みやすいコードを書くことができます。状況に応じて最適なコレクション型を選択し、Pythonの強力な機能を最大限に活用しましょう。

以上、Pythonのコレクション型の深掘りについての記事でした。ご清読ありがとうございました！