PythonにおけるListとTupleの違い

日頃お世話になっているAIお師匠様に「ListとTupleはなぜ分かれているのか教えてくれ」と突然言われました。AIお師匠様には全く頭があがらないのですが、「僕はPythonは15年やってますからね」とPython歴だけはマウンティングしていましたので、こういう質問もスラスラと答えられないと格好がつきません。しかし間違えると怖いので調べつつまとめてみました。

機能的な違い

ListとTupleの違いについて書かれているドキュメントは他にも山ほどあってそれを繰り返すことになりますがTupleはImmutable(変更不可)で、ListはMutable(変更可)というのが一番大きい違いです。

>>> lst = [1,2,3]
>>> lst[1] = 999
>>> tpl = (1,2,3)
>>> tpl[1] = 999
Traceback (most recent call last):
  File “<stdin>”, line 1, in <module>
TypeError: ‘tuple’ object does not support item assignment

これによる大きな差は、Immutableだと例えばdictのkeyに使えるということがあります。

>>> d = {}
>>> d[tpl] = 'hoge'
>>> d{(1, 2, 3): 'hoge'}
>>> d[lst] = 'moge'
Traceback (most recent call last):
  File “<stdin>”, line 1, in <module>
TypeError: unhashable type: 'list'

dictのkeyとして扱えるかどうかは、 hash() をサポートしているかどうかによります。

>>> hash(tpl)
2528502973977326415
>>> hash(lst)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> tpl.__hash__()
2528502973977326415
>>> lst.__hash__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable

Immutableでないと (hash() をサポートしていないと)、同様にsetの要素としても扱えません。

>>> set((tpl,))
{(1, 2, 3)}
>>> set((lst,))
Traceback (most recent call last):
  File “<stdin>”, line 1, in <module>
TypeError: unhashable type: ‘list’

概念的な違い

Python公式FAQにWhy are there separate tuple and list data types? — Design and History FAQ — Python 3.7.2 documentationという記事がありました。

Lists and tuples, while similar in many respects, are generally used in fundamentally different ways. Tuples can be thought of as being similar to Pascal records or C structs; they’re small collections of related data which may be of different types which are operated on as a group. For example, a Cartesian coordinate is appropriately represented as a tuple of two or three numbers.

Lists, on the other hand, are more like arrays in other languages. They tend to hold a varying number of objects all of which have the same type and which are operated on one-by-one. For example, os.listdir(‘.’) returns a list of strings representing the files in the current directory. Functions which operate on this output would generally not break if you added another file or two to the directory.

Tuples are immutable, meaning that once a tuple has been created, you can’t replace any of its elements with a new value. Lists are mutable, meaning that you can always change a list’s elements. Only immutable elements can be used as dictionary keys, and hence only tuples and not lists can be used as keys.

日本語訳（Google Translateの精度すごい…）

リストとタプルは、多くの点で似ていますが、一般的には根本的に異なる方法で使用されます。タプルはPascalのレコードやCの構造体に似ていると考えることができます。それらは、グループとして処理されるさまざまなタイプの関連データの小さな集まりです。たとえば、直交座標は、2つまたは3つの数のタプルとして適切に表現されます。

一方、リストは他の言語の配列に似ています。それらはすべて同じタイプを持ち、1つずつ操作されるさまざまな数のオブジェクトを保持する傾向があります。たとえば、os.listdir（ ‘。’）は現在のディレクトリ内のファイルを表す文字列のリストを返します。ディレクトリに他のファイルを追加しても、この出力を処理する関数は通常壊れません。

タプルは不変です。つまり、タプルが作成されると、その要素を新しい値に置き換えることはできません。リストは変更可能です。つまり、リストの要素はいつでも変更できます。不変の要素のみが辞書のキーとして使用できるため、リストとしてではなくタプルのみがキーとして使用できます。

つまり、TupleとListでは入るものの質が違う、と言い換えても良いかもしれません。
Tupleは「複数の値を一つにまとめる（値は異種の場合もある）」ためにある。その意味で他言語でのstructと似ています。
他方、Listは「同種の値を一つにまとめる」ために使われます。（自分の経験上、様々なデータが雑多に入る配列を用いてなにかするコードを書いたことはないです。）

これはPythonのType Hinting(Pythonにおける静的型チェック機能)にもあらわれていて、ListのType hintは List[int] のように、中に入る型をひとつだけ指定しますが、Tupleの場合は Tuple[int,str]のように中に入る型をその数だけ指定するように使います。

( Tuple[int, …] という形で ”intがany個はいるTuple” を定義することもできます。これは例えば set((1, 2, 3, 4, 5, 6))のようににiteratableを受け取る関数に対してTupleを使うことが多々あるためだと思われます。）

実装上の違い

実用上、概念上の違いをみてきました。では実装はどうなっているでしょうか？

Tupleの実装: cpython/tupleobject.h at 54ba556c6c7d8fd5504dc142c2e773890c55a774 · python/cpython · GitHub

typedef struct {
    PyObject_VAR_HEAD
    /* ob_item contains space for 'ob_size' elements.
       Items must normally not be NULL, except during construction when
       the tuple is not yet visible outside the function that builds it. */
    PyObject *ob_item[1];
} PyTupleObject;

Listの実装: cpython/listobject.h at master · python/cpython · GitHub

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */

    PyObject **ob_item;
    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */

    Py_ssize_t allocated;
} PyListObject;

PyObject はPythonの変数の内部表現です。全てのPythonの変数はPyObjectとして表されます。先頭に PyObject_VAR_HEAD を持つものがPyObjectとして扱うことができます。Cでオブジェクト指向的なことをしているのですね。PyObjectの実際の型(intなのかdictなのか)は、このPyObject_VAR_HEADに入っています。逆に言うと、これ以外のデータが変数固有のデータということになります。

その前提で2つを見比べると、 ob_itemの持ち方が違うのがわかります。
Tupleについては sizeof(PyObject_VAR_HEAD)+sizeof(PyObject *) * [要素数]でアロケートされたPyObjectの中に要素のPyObjectのリファレンスをいれているのに対し、 Listはリストの配列のポインタを持つ形になっています。これは、Listを可変長として扱えるようにするためです。Listの長さが変わる度に、List自体(=PyObject)のポインタも変わってしまうと困るためですね。

2つのコードを見ていくと、たとえば要素数を増やす処理を行う場合の効率が違うことがわかります。
Tupleにはそもそも固定長なので要素数を増やせません。`(1, 2) + (3, 4)`は、新しくサイズが4のTupleを返します。
Listにappendしたときに、サイズが足りない場合は自動的に伸長させます(
cpython/listobject.c at master · python/cpython · GitHub。) この際、要求より多めにアサインすることによって、何度もメモリ割り当てがおこらないようにしています。
（”何度もメモリ割り当てがおこらないように”、という意味では、使わなくなったTupleも再利用するような実装になっているが、その話は割愛)

どれぐらい効率が違うか実験してみましょう。

>>> import timeit
>>> tpl_test = '''t = ()\nfor x in range(10000): t += (x,)'''
>>> timeit.timeit(tpl_test, number=100)
10.803446996000275
>>> lst_test = '''l = []\nfor x in range(10000): l.append(x)'''
>>> timeit.timeit(lst_test, number=100)
0.0802035459992112

かなり違いますね。びっくりしました。

3つの方向からListとTupleの違いをみていきました。コードを書いていくときには「こいつは可変長な入れ物なのか？ それとも値なのか？」という点を気にしながら使い分けて行けばよいかと思います。