Pythonでリストを多用しがちな新人に贈りたい、array/tuple/set/queueの魅力と使い分けフローチャート

# はじめに
みずほリサーチ＆テクノロジーズの @fujine です。

Pythonのリストってとても便利ですよね。可変長で任意のオブジェクトを保存できるため、**シーケンシャルなデータなら何でもリストで実装したくなる**気持ち、分かります。

でもちょっと待ってください！**リスト以外にも便利なコレクション型がある**こと、ご存知でしょうか？コレクション型を適切に使い分けることで、

- プログラムの意図を（ドキュメントに頼らなくても）読み手に的確に伝えられる
- パフォーマンスが向上する

などの効果が期待できます。

そこで本記事では、Pythonの組み込み型や標準ライブラリを対象に、**リストと似たコレクション型をどのように使い分けるか？の案をフローチャート化**しました。それぞれの特徴や使い方を、次章にて解説していきます。

```plantuml
@startuml
!pragma useVerticalIf on

start
if (要素を特定の条件（先頭から、\n優先度順など）で取り出したい？) then (yes)
  #application:**deque, heapq**;
(No) elseif (要素は重複せず、順序性も不要？) then (yes)
  #application:**set, frozenset**;
(No) elseif (要素は変更しない\n（させたくない）？) then (yes)
  #application:**tuple, namedtuple**;
(No) elseif (要素は全て数字型？) then (yes)
  #application:**array**;
else (No)
  #application:**list**;
endif
stop
@enduml
```

# 用語の整理
先に、解説で使用する用語をざっくり整理します。
- **[コレクション(Collection)型](https://docs.python.org/ja/3/library/collections.abc.html)** : 様々なデータ構造の総称です。代表的なものとして、リストやタプルなどは[Sequence型](https://docs.python.org/ja/3/glossary.html#term-sequence)、辞書は[Mapping型](https://docs.python.org/ja/3/glossary.html#term-mapping)、`set`は[set(集合)型](https://docs.python.org/ja/3/library/stdtypes.html#set-types-set-frozenset)にそれぞれ分類されます。
- **[ミュータブル(Mutable)](https://docs.python.org/ja/3/glossary.html#term-mutable)** : [id](https://docs.python.org/ja/3/library/functions.html#id)を変えずに値を変更可能なオブジェクトを指します。リストや辞書はミュータブルです。
- **[イミュータブル(Immutable)](https://docs.python.org/ja/3/glossary.html#term-immutable)** : 固定の値を持つオブジェクトを指します。数字や文字列、タプルなどはイミュータブルです。値を変更するには、別の新しい（idが異なる）オブジェクトを生成する必要があります。
- **[ハッシュ可能(Hashable)](https://docs.python.org/ja/3/glossary.html#term-hashable)** : 「固定のハッシュ値を持ち、他のオブジェクトと比較可能」なオブジェクトをハッシュ可能と言います。辞書のキーや集合の要素はハッシュ可能である必要があります。Python のイミュータブルな組み込みオブジェクトは、ほとんどがハッシュ可能です。

# 各コレクションの解説
以降はフローチャートで紹介した各コレクションについて、
- リストとは何が同じで、何が違うのか
- どのように使うのが効果的か 

を順次解説していきます。

実行環境は4vCPU/16GBメモリ、PythonとOSのバージョンは以下の通りです。
```sh
$ python -V
Python 3.9.2

$ cat /etc/debian_version
11.8
```

## array
[array](https://docs.python.org/ja/3/library/array.html)は数値（整数、浮動小数点数）専用のシーケンス型です。公式ドキュメントでは以下のように紹介されています。

> このモジュールでは、基本的な値 (文字、整数、浮動小数点数) のアレイ (array、配列) をコンパクトに表現できるオブジェクト型を定義しています。アレイはシーケンス (sequence) 型であり、中に入れるオブジェクトの型に制限があることを除けば、リストとまったく同じように振る舞います。
> （「[array --- 効率のよい数値アレイ](https://docs.python.org/ja/3/library/array.html)」より抜粋）

:::note warn
現状は文字列（`'u'`）も扱えますが、[Python3.3から非推奨、4.0で削除予定](https://docs.python.org/ja/3/library/array.html)です。よって本記事では数値のみを解説します。
:::

`array`は、リストとほぼ同じ操作ができます。`array`の第一引数には[データ型を示す一文字](https://docs.python.org/ja/3/library/array.html)を指定します。
```python
from array import array

# 8bit符号付き整数のarrayを作成
a = array("b", [0])

# 要素を1つ追加
a.append(1)
a  # array('b', [0, 1])

# 要素を複数追加
a.extend([2, 3])
a  # array('b', [0, 1, 2, 3])

# 要素を検索し、インデックスを取得
a.index(1)  # 1 

# スライス
a[1:-1]  # array('b', [1, 2])
```
`array`の優れた点の１つ目は、**データの型や値に厳密**なことです。以下のように、範囲外のデータや異なるデータ型はエラーとなります（`1.0`も`1`にキャストされません）。**「シーケンスのデータ型が保証されている」ことは、ロバストな業務アプリケーションの構築・保守においてとても重要です**。型チェックは[mypy](https://mypy.readthedocs.io/en/stable/index.html)や[pydantic](https://docs.pydantic.dev/latest/)でも可能ですが、`array`なら標準ライブラリだけで対応できる点が強みです。

```python
# "b"(8bit符号付き整数)の値の範囲は-128〜127
a = array("b")

a.append(127)   # OK
a.append(128)   # OverflowError: signed char is greater than maximum
a.append(-129)  # OverflowError: signed char is less than minimum
a.append(1.0)   # TypeError: integer argument expected, got float
a.append("1")   # TypeError: an integer is required (got type str)
```

もう一つの利点として、**ビット数を小さくすることでメモリ消費量を削減**できます。一例として、0〜255の値を持つ100万件のシーケンスを`list`と`array`でそれぞれ作成し、メモリ消費量を比較してみます。

結果は以下の通り、適切なビット数を指定した`array`の方が省メモリです。
```python
import sys

N = 10**6
list_ = [i % 255 for i in range(N)]
# "B"は8bit符号なし整数
array_ = array("B", (i % 255 for i in range(N)))

sys.getsizeof(list_)   # 8448728
sys.getsizeof(array_)  # 1000064
```

浮動小数点数の場合は、`d(64bit)`と`f(32bit)`の2種類から選択できます。**f(32bit)を使用すればメモリ使用量が半分で済みます**ので、高い精度を必要としない場面なら32bitで事足りることも多いでしょう。
```python
f64 = array("d", list_)  # 64bit浮動小数点数
f32 = array("f", list_)  # 32bit浮動小数点数

# メモリ使用量を比較
sys.getsizeof(f64)  # 8000064
sys.getsizeof(f32)  # 4000064

# 精度を比較
array("d", [0.1])  # array('d', [0.1])
array("f", [0.1])  # array('f', [0.10000000149011612])
```

:::note info
【まとめ】`list`の代わりに`array`を使用すると、以下メリットが得られます。
- シーケンスのデータ型を実行時に制限・担保できる
- メモリ消費量を削減できる
:::

## tuple
「シーケンス型の値は後から変更しない（もしくは、意図しない変更をガードしたい）」という用途なら、`tuple`(タプル)が適しています。

`tuple`は[イミュータブルなシーケンス型](https://docs.python.org/ja/3/reference/datamodel.html#immutable-sequences)であり、`tuple`の要素がイミュータブルであれば、リストのように**値を後から変更・追加・削除することはできません**。最後の例は一見すると追加できたかのように見えますが、追加要素を含む新しい`tuple`オブジェクトが変数`t`に上書きされたものであり、元のオブジェクトとはid値が異なります。
```python
# タプルを作成し、id値を取得
t = (True, 2, 3.14, "4")
t_id = id(t)

# タプル要素の変更、追加、削除はエラー
t[0] = False  # TypeError: 'tuple' object does not support item assignment
del t[-1]     # TypeError: 'tuple' object doesn't support item deletion
t.append(5)   # AttributeError: 'tuple' object has no attribute 'append'

t += (5, 6)
t              # (True, 2, 3.14, '4', 5, 6)
id(t) == t_id  # False
```

`tuple`の要素が全てハッシュ可能であれば`tuple`自体もハッシュ可能なため、**辞書のキーにすることも可能**です。通常、辞書のキーには文字列を使いますが、複数の値の組合せをキーとしたい場合には`tuple`が適しています。
```python
t1 = (7, 5)
hash(t1)   # 7267574591690527098

# タプルを辞書のキーに指定
d = {t1: 35}
d  #  {(7, 5): 35}

# ミュータブルオブジェクトを含むタプルはハッシュ可能ではない
t2 = (6, [7])
hash(t2)  # TypeError: unhashable type: 'list'
```

`tuple`を用いると、リストで起こりうる **「意図しない変更」に気付きやすくなります**。

以下に簡単な例を作成しました（敢えてPythonicではない実装にしています）。関数の実行前後で`x`の値が変わってしまっているのにお気付きでしょうか？これは「`y = x`で値をコピーしたつもりが、実際は同じオブジェクトを参照していた」という勘違いが原因です。

```python
def double(x):
    """シーケンスの要素を2倍して返す"""
    y = x
    for i in range(len(y)):
        y[i] *= 2
    return y


x = [1, 2, 3]
y = double(x)

y   # [2, 4, 6]
x   # [2, 4, 6]
```

`tuple`を使えば意図しない更新操作を例外でキャッチでき、上記のようなバグの早期発見とリファクタリングにつなげやすくなります。
```python
x = (1, 2, 3)
y = double(x)  # TypeError: 'tuple' object does not support item assignment
```

## namedtuple
`tuple`の要素数が多かったり異種データをまとめて扱いたい場合は、**[namedtuple](https://docs.python.org/ja/3/library/collections.html#collections.namedtuple)(名前付きタプル)がおすすめ**です。`namedtuple`は`tuple`の拡張版で、インデックスに加えて**属性アクセスも可能**になります。

2次元座標を表現する`Point`オブジェクトを`namedtuple`で表現すると以下になります。`x`・`y`属性で要素にアクセスできる他、`defaults`で初期値を設定できる、`repr()`の出力結果が`Point(x=..., y=...)`と分かりやすい等、`tuple`には無い様々なメリットが得られます。

```python
from collections import namedtuple

# 属性x, y(デフォルト値は0)を持つPointオブジェクトを作成
Point = namedtuple("Point", ("x", "y"), defaults=(0, 0))

# Pointインスタンスを様々な方法で作成
Point()            # Point(x=0, y=0)
Point(1, 2)        # Point(x=1, y=2)
Point(y=4, x=3)    # Point(x=3, y=4)
Point(*[5, 6])     # Point(x=5, y=6)
Point(**{"x": 7})  # Point(x=7, y=0)

# インデックスと属性によるアクセス
point = Point(1, 2)
point[0]  # 1
point.y   # 2
```

:::note info
【まとめ】`list`の代わりに`tuple`や`namedtuple`を用いると、以下メリットが得られます。
- ハッシュ可能な`tuple`を辞書のキーに使用できる
- （要素がイミュータブルの場合）想定しない変更処理が実行時エラーとなり、バグを発見しやすくなる
- `namedtuple`を使えばプログラムが読みやすくなり、保守性を向上できる
:::

## set
リストが使われているプログラムを調べると、
- 全要素のイテレーションのみに利用しており、要素の順番は意識していない
- 要素の重複を想定していない（もしくは、重複を除去するコードが実装されている）

というケースが以外と多くあります。そんな時は[set](https://docs.python.org/ja/3/library/stdtypes.html#set-types-set-frozenset)の出番です。

> set オブジェクトは、固有の hashable オブジェクトの順序なしコレクションです。通常の用途には、帰属テスト、シーケンスからの重複除去、積集合、和集合、差集合、対称差 (排他的論理和) のような数学的演算の計算が含まれます。
> （中略）
> コレクションには順序がないので、集合は挿入の順序や要素の位置を記録しません。従って、集合はインデクシング、スライシング、その他のシーケンス的な振舞いをサポートしません。
> [set（集合）型 --- set, frozenset](https://docs.python.org/ja/3/library/stdtypes.html#set-types-set-frozenset)より抜粋

`set`のイメージとしては、「キーのみを持つ（値を持たない）辞書」が近しいかと思います。以下コードのように、要素の追加や削除、集合演算、イテレーションをサポートしています。

```python
# setを作成、重複する要素は除去される
s = {1, 2, 2}
s  # {1, 2}

# 要素を追加
s.add(3)
s  # {1, 2, 3}

# 要素を削除（なければKeyError）
s.remove(2)
s  # {1, 3}

# 要素があれば削除
s.discard(4)
s  # {1, 3}

# 他のsetと結合（和集合）
s |= {5, 0}
s  # {0, 1, 3, 5}

# イテレーション（順序は不定）
[i for i in s]  # [0, 1, 3, 5]
```

`set`のよくある使い方は、 **「リストから重複する要素を除外する」** でしょう。「リスト→`set`→リスト」の順に変換するだけで重複を除去できるので便利です。
```python
duplicate = [5, 2, 2, 9, 1, 0, 9, 5]
unique = list(set(duplicate))
unique  # {0, 1, 2, 5, 9}
```

可読性の観点でもメリットがあります。リストの代わりに`set`を使うことで、 **「要素に重複がなく、要素の順序は任意である」ことが自明** になります。

事例として、ログデータからエラーの件数を集計する関数を考えてみましょう。この関数は実装通り、ERRORログの件数を正しくカウントしています。

```python
def count_error(logs):
    """ログレベルがERRORの件数をカウントする"""
    count = 0
    for log in logs:
        time, level, message = log
        if "Error" == level:
            count += 1
    return count


logs = [
    ("2024-01-01T00:00:00", "INFO", "Information message."),
    ("2024-01-01T01:05:07", "WARNING", "Warning message."),
    ("2024-01-01T01:23:45", "ERROR", "Error message."),
    ("2024-01-01T01:23:45", "ERROR", "Error message."),
]

count_error(logs)  # 2
```
ここで、外部サービスの仕様により「ログレコードは稀に重複することがある」と仮定しましょう（`logs`変数にも2件の重複があります）。さて、 **この関数はログの重複を想定しているのでしょうか？** コードにもドキュメントにも記載がない場合、**この実装が想定通りなのか、それともバグ（実装不足）なのかは判断できません** 。このような曖昧さは、テストやリファクタリングで苦労するポイントです。

本来の関数仕様が「重複を除いてカウントする」であれば、`logs`をリストの代わりに`set`にするだけで、**上記の曖昧さは即座に解消します**。「`set`型に重複はあり得るか？」という疑問の余地が無いからです。このように、**適切なデータ型を用いることでデータの特性や制約を的確に伝える**ことができ、プログラムの可読性が向上します。

```python
logs = set(logs)
count_error(logs)  # 1
```

他のメリットとして、`set`は**要素の検索が$O(1)$であり、リストの検索（$O(n)$）よりも圧倒的に高速**です。100万件のデータから要素を検索する以下コードでは **`set`の方が1500倍以上高速** なように、要素数が多く検索回数が多いケースほど`set`が適していると言えます。

```python
from timeit import timeit

time_set = timeit(stmt="N in x", number=1,
                  setup="N = 10**6; x = {i for i in range(1, N + 1)}")
time_list = timeit(stmt="N in x", number=1,
                   setup="N = 10**6; x = [i for i in range(1, N + 1)]")

int(time_list / time_set)  # 1579
```

## frozenset
`set`はミュータブルであり、ハッシュ可能ではありません。イミュータブルな`set`を扱いたい場合は`frozenset`を使用します。`tuple`と同様に、「意図しない変更」を抑止することに使用できます。

```python
# frozensetはハッシュ可能
fs = frozenset([1, 2, 2, 3])
fs_id = id(fs)
hash(fs)   # -3779889356588604112

# 要素の追加や削除はエラー
fs.add(4)     # AttributeError: 'frozenset' object has no attribute 'add'
fs.remove(2)  # AttributeError: 'frozenset' object has no attribute 'remove'

# 集合演算の結果は直接更新されず、
# 新たなfrozensetオブジェクトに代入される
fs |= {5, 4}
fs               # frozenset({1, 2, 3, 4, 5})
fs_id == id(fs)  # False
```

`frozenset`はハッシュ可能なため、「集合の集合」を表現できます。これは`set`だけでは実現できず、`frozenset`が必ず必要になります。
```python
{{2, 4, 8}, {1, 3, 7}}  # TypeError: unhashable type: 'set'
{frozenset([2, 4, 8]), frozenset([1, 3, 7])} # OK
```

:::note info
【まとめ】`list`の代わりに`set`や`frozenset`を用いることで、以下メリットが得られます。
- 「要素に重複がなく、要素の順序は任意である」ことが自明となり、プログラムの可読性が向上する
- 要素検索が高速になる
:::

## deque（両端キュー）
リストは要素の挿入(`insert`)や取り出し(`pop`)が簡単なため、スタックやキューとして使うこともできます。しかし、**先頭要素の挿入や取り出しの計算コストは$O(n)$と非効率**であり、要素数が多いほど性能上のボトルネックになりがちです。

スタックやキューのように先頭・末尾要素を頻繁に出し入れしたい場合は、専用の[deque](https://docs.python.org/ja/3/library/collections.html#collections.deque)（デック）を使いましょう。`deque`の操作は基本的にリストと同じで、**先頭や末尾の挿入や削除が$O(1)$で実行**されるように最適化されています。

```python
from collections import deque

# dequeインスタンスを作成
d = deque([1, 2, 3])
d  # deque([1, 2, 3])

# 末尾に4、先頭に0を追加
d.append(4)
d.appendleft(0)
d  # deque([0, 1, 2, 3, 4])

# 先頭を取得して削除
d.popleft()
d  # deque([1, 2, 3, 4])
```

`deque`は要素の出し入れが先頭・末尾に集中する操作に適しています。以下はシンプルなラウンドロビンスケジューリングの実装例です。
```python
def roundrobin(tasks):
    """ラウンドロビンスケジューリング（タスクの所要時間は整数、クォンタムは1）"""
    remain_tasks = tasks[:]
    log = []

    while remain_tasks:
        task_name, need_time = remain_tasks.pop()
        need_time -= 1
        log.append(f"{task_name}")

        if need_time > 0:
            remain_tasks.insert(0, (task_name, need_time))

    return log 


# 各タスクを(タスク名、所要時間)のタプルで作成
tasks = [("task1", 2), ("task2", 1), ("task3", 3)]
# タスクを実行し、ログを取得
logs = roundrobin(tasks)
logs  # ['task3', 'task2', 'task1', 'task3', 'task1', 'task3']
```

リストには無い`deque`の特徴として、**最大長を指定可能**な点にあります。`append`や`extend`後の要素数が最大長を超える場合、挿入方向の反対側から自動的に削除されます。

```python
# 最大長が5のdequeを作成
d = deque(range(5), maxlen=5)
d  # deque([0, 1, 2, 3, 4], maxlen=5)

# 末尾に挿入すると、先頭から削除される
d.append(6)
d  # deque([1, 2, 3, 4, 6], maxlen=5)

# 先頭に挿入すると、末尾から削除される
d.appendleft(-1)
d  # deque([-1, 1, 2, 3, 4], maxlen=5)
```

この機能は、**外部ファイルやジェネレータから末尾N件を取得する**のに便利です。同じ処理をリストで実装しようとすると、データ全体をリストに保存してからスライスする必要があり、メモリ使用量が大きくなってしまいます（もっと賢い方法もありますが、コードが複雑化しがちです）。`deque`なら最大長を指定するだけで、最小限のコードとメモリ使用量で実装できます。

```python
def generate_many():
    """大量のデータを生成する"""
    for i in range(10**6):
        yield i

# ジェネレータの出力結果から最後の5件を取得
d = deque(generate_many(), maxlen=5)
d  # deque([999995, 999996, 999997, 999998, 999999], maxlen=5)
```

## heapq（優先度付きキュー）
リストを事前にソートし、昇順や降順（もしくは任意の関数の実行結果順）でイテレーション処理したいシーンも多いでしょう。その際、「イテレーションの途中で要素が追加される」という条件があったとしたらどうでしょう？`sort()`の計算量は$O(NlogN)$のため、追加の度に毎回ソートし直すのは計算コストが結構かかりそうですね。

[heapq](https://docs.python.org/ja/3/library/heapq.html)を使えば、**ヒープアルゴリズムにより要素の追加や最小値の取り出しが最適化**になります。

> ヒープとは、全ての親ノードの値が、その全ての子の値以下であるようなバイナリツリーです。この実装は、全ての k に対して、ゼロから要素を数えていった際に、heap[k] <= heap[2*k+1] かつ heap[k] <= heap[2*k+2] となる配列を使っています。比較のために、存在しない要素は無限大として扱われます。ヒープの興味深い性質は、最小の要素が常にルート、つまり heap[0] になることです。
> （[heapq --- ヒープキューアルゴリズム](https://docs.python.org/ja/3/library/heapq.html) より抜粋）

ヒープの作成には、空のリストを指定するか、既存のリストを`heapify()`で変換します。リスト`h`に対して`heappush`で追加し、`heappop`で小さい順に取り出します。`heappush`と`heappop`の計算量はどちらも$O(logN)$で、リストの$O(N)$よりも高速です。

```python
from heapq import heapify, heappop, heappush

# 既存のリストをヒープに変換
h = [6, 5, 4]
heapify(h)

# hの各要素はヒープアルゴリズムに基づいて配置され、
# h[0]が必ず最小値となる
h[0] == min(h)  # True

# heappushでデータを追加
for i in (1, 3, 2):
    heappush(h, i)

# データ追加後も、h[0]は必ず最小値
h[0] == min(h)  # True

# heappopで、リストの要素を最小値から順に取得
while h:
    print(heappop(h))  # 1, 2, 3 ,4 ,5 ,6
```

:::note warn
- pythonの`heapq`は最小ヒープです。
- `heapq`のメソッドは、リストをインプレース操作します。
:::

`heapq`の要素にはタプルを使用できます。タプルの第1要素に比較可能なオブジェクト（数字や文字列など）を指定することで、**オブジェクトが直接比較できない場合でもヒープを利用可能**です。

```python
# タスクを、(期限までの日数, タスク内容)のタプルで定義
tasks = [
    (3, "普通だから3日以内で十分だよ"),
    (7, "急ぎじゃないから1週間で！"),
    (1, "緊急なんで今日中に頼む！")
]

# ヒープに変換
heapq.heapify(tasks)
# どのタスクから実行する？
while tasks:
    print(heappop(tasks))

# (1, '緊急なんで今日中に頼む！')
# (3, '普通だから3日以内で十分だよ')
# (7, '急ぎじゃないから1週間で！')
```

`heapq`の`nsmallest`や`nlargest`を使用すると、シーケンスやジェネレータから**N個の最小値・最大値を効率的に取得**できます。

```python
from heapq import nlargest, nsmallest

def generate_many():
    """大量のデータを生成する"""
    for i in range(10**6):
        yield i

# 最小値と最大値をそれぞれ5件取得
nsmallest(5, generate_many())  # [0, 1, 2, 3, 4]
nlargest(5, generate_many())   # [999999, 999998, 999997, 999996, 999995]
```

:::note info
【まとめ】`list`の代わりに`deque`や`heapq`を用いると、以下メリットが得られます。
- `deque`では、両端からの挿入や取り出しを$O(1)$で実行できまる
- `heapq`では、要素の挿入や最小値の取り出しを$O(logN)$で実行できる
:::

# 終わりに
本記事では、Pythonの組み込み型や標準ライブラリを対象に、リスト以外のコレクション型の魅力や使い分けを紹介させていただきました。

適切なコレクション型を使用することで可読性・保守性やパフォーマンスの向上が期待できますので、これを機に「リスト以外のも使ってみようかな」と思っていただけたら幸いです。

なお、記事内では計算量についても触れましたが、要素数が少ない場合ならリストでも十分速いケースもありますし、数値計算なら`Numpy`などの専用ライブラリを用いた方が更に高速です。ご自身のデータで実際に計測し、どれが最適かを試してみて下さい。