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

はじめに

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

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

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

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

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

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

用語の整理

先に、解説で使用する用語をざっくり整理します。

• コレクション(Collection)型 : 様々なデータ構造の総称です。代表的なものとして、リストやタプルなどはSequence型、辞書はMapping型、setはset(集合)型にそれぞれ分類されます。
• ミュータブル(Mutable) : idを変えずに値を変更可能なオブジェクトを指します。リストや辞書はミュータブルです。
• イミュータブル(Immutable) : 固定の値を持つオブジェクトを指します。数字や文字列、タプルなどはイミュータブルです。値を変更するには、別の新しい（idが異なる）オブジェクトを生成する必要があります。
• ハッシュ可能(Hashable) : 「固定のハッシュ値を持ち、他のオブジェクトと比較可能」なオブジェクトをハッシュ可能と言います。辞書のキーや集合の要素はハッシュ可能である必要があります。Python のイミュータブルな組み込みオブジェクトは、ほとんどがハッシュ可能です。

各コレクションの解説

以降はフローチャートで紹介した各コレクションについて、

• リストとは何が同じで、何が違うのか
• どのように使うのが効果的か

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

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

$ python -V
Python 3.9.2

$ cat /etc/debian_version
11.8

array

arrayは数値（整数、浮動小数点数）専用のシーケンス型です。公式ドキュメントでは以下のように紹介されています。

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

現状は文字列（'u'）も扱えますが、Python3.3から非推奨、4.0で削除予定です。よって本記事では数値のみを解説します。

arrayは、リストとほぼ同じ操作ができます。arrayの第一引数にはデータ型を示す一文字を指定します。

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やpydanticでも可能ですが、arrayなら標準ライブラリだけで対応できる点が強みです。

# "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の方が省メモリです。

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で事足りることも多いでしょう。

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

【まとめ】listの代わりにarrayを使用すると、以下メリットが得られます。

• シーケンスのデータ型を実行時に制限・担保できる
• メモリ消費量を削減できる

tuple

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

tupleはイミュータブルなシーケンス型であり、tupleの要素がイミュータブルであれば、リストのように値を後から変更・追加・削除することはできません。最後の例は一見すると追加できたかのように見えますが、追加要素を含む新しいtupleオブジェクトが変数tに上書きされたものであり、元のオブジェクトとはid値が異なります。

# タプルを作成し、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が適しています。

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で値をコピーしたつもりが、実際は同じオブジェクトを参照していた」という勘違いが原因です。

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を使えば意図しない更新操作を例外でキャッチでき、上記のようなバグの早期発見とリファクタリングにつなげやすくなります。

x = (1, 2, 3)
y = double(x)  # TypeError: 'tuple' object does not support item assignment

namedtuple

tupleの要素数が多かったり異種データをまとめて扱いたい場合は、namedtuple(名前付きタプル)がおすすめです。namedtupleはtupleの拡張版で、インデックスに加えて属性アクセスも可能になります。

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

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

【まとめ】listの代わりにtupleやnamedtupleを用いると、以下メリットが得られます。

• ハッシュ可能なtupleを辞書のキーに使用できる
• （要素がイミュータブルの場合）想定しない変更処理が実行時エラーとなり、バグを発見しやすくなる
• namedtupleを使えばプログラムが読みやすくなり、保守性を向上できる

set

リストが使われているプログラムを調べると、

• 全要素のイテレーションのみに利用しており、要素の順番は意識していない
• 要素の重複を想定していない（もしくは、重複を除去するコードが実装されている）

というケースが以外と多くあります。そんな時はsetの出番です。

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

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

# 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→リスト」の順に変換するだけで重複を除去できるので便利です。

duplicate = [5, 2, 2, 9, 1, 0, 9, 5]
unique = list(set(duplicate))
unique  # {0, 1, 2, 5, 9}

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

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

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型に重複はあり得るか？」という疑問の余地が無いからです。このように、適切なデータ型を用いることでデータの特性や制約を的確に伝えることができ、プログラムの可読性が向上します。

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

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

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と同様に、「意図しない変更」を抑止することに使用できます。

# 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が必ず必要になります。

{{2, 4, 8}, {1, 3, 7}}  # TypeError: unhashable type: 'set'
{frozenset([2, 4, 8]), frozenset([1, 3, 7])} # OK

【まとめ】listの代わりにsetやfrozensetを用いることで、以下メリットが得られます。

• 「要素に重複がなく、要素の順序は任意である」ことが自明となり、プログラムの可読性が向上する
• 要素検索が高速になる

deque（両端キュー）

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

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

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は要素の出し入れが先頭・末尾に集中する操作に適しています。以下はシンプルなラウンドロビンスケジューリングの実装例です。

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後の要素数が最大長を超える場合、挿入方向の反対側から自動的に削除されます。

# 最大長が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なら最大長を指定するだけで、最小限のコードとメモリ使用量で実装できます。

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を使えば、ヒープアルゴリズムにより要素の追加や最小値の取り出しが最適化になります。

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

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

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

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

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

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

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

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

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

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]

【まとめ】listの代わりにdequeやheapqを用いると、以下メリットが得られます。

• dequeでは、両端からの挿入や取り出しを$O(1)$で実行できまる
• heapqでは、要素の挿入や最小値の取り出しを$O(logN)$で実行できる

終わりに

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

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

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