はじめに
Pythonには配列というデータ構造としてリスト(List)とタプル(Tuple)があります。
どちらもPython初心者の段階からよく触れることになるものかと思いますが、私のようななんとなく使っている人種は「どのような状況でどちらを使えばよいか？」また「その理由の根拠を示せるか？」と言われると困ってしまいます。
今回は上記の問いについて考えていきます。
※本記事は以下の書籍を参考にしています。
リストとタプルの共通点
リストとタプルの違いを見ていく前にまずは共通点を見ていきます。
- どちらも配列というデータ構造である
- 生成するにはシステムメモリの領域を必要なだけ連続するバケットで確保する
- 特定の要素(例えば10番目とか)へのアクセスは$O(1)$で行える
配列のメモリ配置のイメージは以下のようになります。
連続した領域が確保されているので、1番目の要素は0x04に、3番目の要素は0x06を見に行けばよいことがわかるので、$O(1)$で要素へのアクセスができます。
<参考>リストの要素へのアクセスが O(1) であることの確認
以下の検証から要素数の違う2つのリスト、異なるインデックスに対しても要素へのアクセス時間は変わらないと言えることが確認できます。
%%timeit l = list(range(10))
l[5]
# 30.1 ns ± 0.753 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
%%timeit l = list(range(10_000_000))
l[100_000]
# 29.5 ns ± 0.543 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
リストとタプルの違いを一言で！
リストとタプルの違いを一言でまとめると、
- リスト：動的な配列、値や要素数の変更が可能
- タプル：静的な配列、値や要素数は固定で変更できない
です。
このくらいの認識はリストとタプルを学び始めた際に耳にすることも多いかと思います。これだけ認識しておけば困ることはない可能性もありますが以下で少し深堀してみます。
リストとタプルの使い分け例
| データ | リスト or タプル | 理由 |
|---|---|---|
| 素数の最初の20個 | タプル | データが変化しないから |
| プログラミング言語の名前 | リスト | データが増える可能性があるから |
| ある人の年齢、体重、身長 | リスト | 値が変わる可能性があるから |
| あるビリヤードゲームの結果 | タプル | 一度出た結果は変化しないから |
| 連続するビリヤードゲームの結果 | リスト | ゲームの数が増える可能性があるから(個々の結果はタプルで良い) |
他にも例はいくらでも考えられますが、使い分けは先述した違いにある「要素が変わる可能性があるか？」を基準にすれば実情は問題ないかと思います。
リストの動作
リストは動的な配列であるため、以下のように要素の変更・追加等が行えます。
numbers = [5, 8, 1, 3, 2, 6]
print(numbers)
# [5, 8, 1, 3, 2, 6]
# 要素の変更
numbers[2] = 2 * numbers[0]
print(numbers)
# [5, 8, 10, 3, 2, 6]
# 要素の追加
print(len(numbers))
# 6
numbers.append(42)
print(numbers)
# [5, 8, 10, 3, 2, 6, 42]
print(len(numbers))
# 7
動的な配列にはサイズを増やすresize操作があるため、このような操作が可能となっている。
resize操作
resize操作とは、
- サイズ$N$のリストが渡された際に本来の要素数$N$個に対して、後から要素が追加されることを見込んで$N$よりも大きい$M$個の領域を確保する
- M個確保した領域に渡されたサイズ$N$の要素をコピーする
というような操作です。
リストの余剰領域の確保
リストはresize操作によって余剰領域を確保すると先述しました。
余剰領域の確保サイズについての思想は以下のようなもののようです。
- 要素を1つ追加するなら、今後も多数の要素を追加すると考えられる
- その場合は、余剰領域を大きく余裕をもって確保すれば再確保する回数を減らせる
- それによりメモリのコピー回数も減らせる
- ※メモリのコピーはコストが大きく、サイズが大きくなるほどそれは顕著である
領域を大きく確保しすぎるとムダになるが、コピー等のコストを考えると大きく確保しておきたいのでバランスが大切ということになります。
そこで、Python3.7では以下のようにバランスを取って余剰領域を確保しているようです(他versionは未確認)
グラフの見方は
「8000個の要素を持つリストをappendで作成した際に、約8600個の領域が確保される → 600個の余剰領域を確保している」
というようになっています。
また、追加後の要素数$N$と確保領域数$M$の関係は以下のようになっています。
$$M = N + (N >> 3) + (3 \space if \space N < 9 \space else \space 6)$$
| N | 0 | 1-4 | 5-8 | 9-16 | 17-25 | 26-35 | 36-46 | $\cdots$ | 991-1120 |
|---|---|---|---|---|---|---|---|---|---|
| M | 0 | 4 | 8 | 16 | 25 | 35 | 46 | $\cdots$ | 1120 |
動作としては現在の余剰領域がなくなった状態で、追加される際に式をもとに確保領域数を再計算して確保 → 現要素のcopyを行うようです。
以下のコードの動作を可視化すると図のようになります。
l = [1, 2]
for i in range(3, 6):
l.append(i)
確保される余剰領域はかなり小さい領域と言えますが、積み重なることもあります。
appendでの構築は内包表記での構築よりメモリ使用量が大きく、時間も遅くなる例を示します。
%load_ext memory_profiler
%memit [i*i for i in range(100_000)]
# peak memory: 99.10 MiB, increment: 0.83 MiB
%%memit
l = []
for i in range(100_000):
l.append(i * 2)
# peak memory: 98.58 MiB, increment: 3.64 MiB
incrementを見るとappendを使用した方がメモリ使用量が大きいことがわかります。
%timeit [i*i for i in range(100_000)]
# 7.67 ms ± 993 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit
l = []
for i in range(100_000):
l.append(i * 2)
# 12.9 ms ± 1.27 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
実行時間もappendを使用した方が遅いとわかります。
タプルの動作
タプルはリストと異なり、一度作られると要素やサイズを変更することはできません。
t = (1, 2, 3, 4)
t[0] = 5
# TypeError: 'tuple' object does not support item assignment
サイズの変更はできないが、2つのタプルを連結して新しいタプルを作ることは可能
t1 = (0, 1, 2)
t2 = (3, 4, 5, 6)
print(t1 + t2)
# (0, 1, 2, 3, 4, 5, 6)
タプルの結合はリストの結合に似ているが、余剰領域は確保しない。(結合後もタプルなので自然)
リストのappendはresize操作が発生しない場合は$O(1)$だが、タプルの結合は$O(n)$です。タプルの結合は新しい領域を必ず確保し、確保した領域に結合前のすべての要素をコピーする必要があるからということです。
しかし、タプルでは余剰領域を確保しないので変更のない静的なデータはタプルで扱うのが望ましいです。
また、タプルは以下の利点があるそうです。
Pythonには使用されなくなった変数はメモリを開放するガベージコレクションという機能があるが、サイズが1~20の小さなタプルは使われなくなってもすぐには解放されず最大20000個までは将来の再利用のために保持されるそうです。
これにより、再度タプルが必要になった際に保持しておいたメモリを使用すればよくメモリ確保のためにOSを呼び出さなくてよくなります。
このことはPythonが余分なメモリを保持することになりますが、リストよりも高速にタプルが生成されることの恩恵は大きくタプルの良い特徴の一つだとのことです。
%timeit l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 72 ns ± 1.94 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
%timeit l = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
# 13.2 ns ± 0.136 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
実際にタプルの方が生成速度が速いことが確認できます。
まとめ
基本的には「要素が変わる可能性があるか？」を基準にリストとタプルを使い分ければ実情としては問題なさそう。
- 変更の可能性があるデータ → リスト
- 変更の可能性がないデータ → タプル
リストはappend時に必要に応じて行うresize操作の中身や、小さいタプルはメモリが解放されずに使いまわされることなど知らなかったこともあり勉強になりました。