【ITニュース解説】What Python Lists Really Are

Pythonを学び始めた誰もが一度はリストを使ったことがあるだろう。myList = [1, 2, 3, 4]のように簡単に数字を並べたり、myList.append(5)で要素を追加したり、myList[0]で最初の要素にアクセスしたりできる。非常に直感的で便利なリストだが、一体その裏側ではどのような仕組みで動いているのだろうか。特に、C言語のような静的な配列しか持たないプログラミング言語とは異なり、なぜPythonのリストは自動的にサイズを調整できるのだろうか。この疑問に答えるためには、Pythonの根幹部分、つまりそのソースコードを覗き見る必要がある。

私たちが普段python3とコマンドを打って実行しているPythonのプログラムは、最も普及している実装であるCPythonだ。このCPythonは、ほとんどC言語で書かれている。つまり、Pythonでリストを作成したり、append()メソッドを呼び出したりするたびに、裏側ではCPythonが特定のC言語の関数を実行しているのだ。リストがどのように機能するかを本当に理解するためには、このリストを定義しているC言語のコードを見る必要がある。

驚くべきことに、オブジェクト指向言語として有名なPythonが、本来クラスやオブジェクトという概念を直接持たないC言語の上に構築されているという事実がある。これは一体どういうことだろうか。オブジェクト指向プログラミングの基本的な要素は、C言語における「構造体（struct）」（データをまとめる）、「ポインタ」（他のデータへの参照を作る）、「関数ポインタ」（メソッドを表す）、「間接参照」（実行時にどの関数を呼び出すかを決定する）といった仕組みを組み合わせることで実現されている。これらの要素を巧みに使うことで、CPythonはデータとメソッドを一つにまとめる「カプセル化」、ある型が別の型の特徴を借りる「継承」、そしてオブジェクトがその型に応じて異なる振る舞いをする「ポリモーフィズム」といったオブジェクト指向の主要な機能をサポートしている。

Pythonにおけるすべてのオブジェクトの根源は「PyObject」という構造体である。他のすべてのオブジェクト構造体は、このPyObjectを内部に含んでいるため、あらゆるPythonオブジェクトの絶対的な基盤となっている。このPyObjectは主に二つの属性を持つ。一つは「ob_refcnt」で、これはオブジェクトへの参照数を数える整数カウンタだ。Pythonの主要なメモリ管理システムの一部であり、このカウントがゼロになると、そのオブジェクトは不要と判断され、メモリが解放される。もう一つは「ob_type」で、これはPyTypeObjectという別の重要な構造体へのポインタだ。これはオブジェクトの「IDカード」のようなもので、「私は整数です」とか「私はリストです」といった情報をCPythonに伝える。このPyTypeObjectは、その型が持つすべてのメソッド（C言語の関数）を格納する大きなルックアップテーブルのようなものだ。例えば、len(my_list)と呼び出すとき、CPythonはmy_listのob_typeを見て、リストの長さを計算するための正しいC言語関数を見つけ出して実行する。これにより、len()はリストだけでなく、タプルや辞書など、さまざまな型に対して機能する。

数字の7のように固定サイズのオブジェクトもあるが、リストや文字列のように可変数の要素を格納できるコンテナもある。これらの可変サイズのコンテナの共通基盤が「PyVarObject」という構造体だ。この構造体は、PyObject_HEADというマクロを通じてPyObjectの属性（ob_refcntとob_type）を「継承」し、さらに「ob_size」という新しいフィールドを追加する。ob_sizeは、コンテナ内に現在いくつのアイテムが存在するかを示す整数カウンタだ。この値は事前に計算されているため、len()を呼び出すと、リストやタプルのサイズがどれだけ大きくても、要素を数える必要がなく瞬時に（O(1)の時間で）結果が返される。

そして、ついにPythonリストの秘密にたどり着く。内部的に、動的で柔軟なPythonのリストは、基本的に「静的なC言語の配列」なのだ。PyListObjectという構造体がその正体であり、PyObject_VAR_HEADマクロを通じてPyVarObjectのフィールド（ob_refcnt、ob_type、ob_size）を継承し、さらにリスト固有の二つのフィールドを追加する。一つは「ob_item」で、これはPyObject **型、つまりPythonオブジェクトへのポインタの配列へのポインタだ。これは、リスト内のすべての実際のPythonオブジェクトのメモリアドレスを保持する、連続したC言語の配列へのメモリアドレスを指している。my_list[500]のように要素にアクセスする際、これが連続したメモリブロックであるため、単純な計算で目的のメモリアドレスに到達でき、アイテムへのアクセスが非常に高速なO(1)操作となる。もう一つは「allocated」で、これはob_sizeの補助的な整数カウンタだ。これはob_itemC配列がメモリ内に確保しているスロットの総数を追跡する。allocatedはob_sizeよりも大きくなることがあり、この余分な、未使用のスロットがappend()呼び出しに備えて待機しているため、リストが「動的」に見える鍵となっている。

リストの作成は、my_list = []のような簡単なコマンドで「PyList_New」というC言語関数を呼び出すことから始まる。この関数には「フリーリスト」というパフォーマンス最適化の仕組みがあり、最近削除されたリストオブジェクトを「リサイクルビン」として保持し、新しいリストを作成する前に再利用できるオブジェクトを探す。これにより、OSに新しいメモリを要求するコストを削減する。また、空のリストを作成した場合、メインのC配列（ob_item）さえも確保せず、ポインタをNULLに設定することでメモリを節約する「空リスト最適化」も行われる。初期状態ではob_sizeとallocatedは同じ値に設定される。

リストの最も単純な操作である、my_list[i]のようにインデックスでアイテムにアクセスする際は、「PyList_GetItem」というC言語関数が処理する。この関数はまずインデックスiが有効な範囲内にあるか（ob_sizeを超えていないか）をチェックし、問題がなければ、opをPyListObjectにキャストし、ob_itemC配列の指定されたインデックスiに直接アクセスしてポインタを取得する。この操作がO(1)（定数時間）である理由は、これがポインタ演算として知られる直接的なメモリ計算だからだ。コンピュータは開始アドレス + (インデックス * ポインタのサイズ)という数式で任意のアイテムの正確なメモリアドレスを計算でき、リストのサイズに関わらず同じ時間でデータに直接ジャンプする。

リストが魔法のように成長する秘密は、「list_resize」関数にある。これはPythonから直接呼び出すメソッドではなく、append()やinsert()のようなメソッドがリストの容量を変更する必要があるときに内部的に呼び出す関数だ。list_resizeには二つのパスがある。一つは「高速パス」で、allocatedに十分な余裕がある場合、ob_sizeだけを更新してO(1)で処理を終える。もう一つは「低速パス」で、容量が不足している場合、より大きな新しいC配列の容量を計算し、PyMem_Realloc関数を使ってOSに新しい大きなメモリチャンクを要求し、古い配列のアイテムポインタを新しい配列にコピーする。このコピー処理はO(n)のコストがかかる。最後に、リストの内部的なob_itemポインタとallocatedカウンタを新しい大きなC配列に合わせて更新する。Pythonは、新しい容量を現在の容量に比例して増やす（約1/8を追加する）「幾何学的成長」の式を使用する。これにより、コストの高いO(n)のコピーがリストが大きくなるにつれて発生する頻度が減少し、多くの追加操作にわたってコストが分散され、平均的なコストはO(1)になる。

my_list.append(item)メソッドは、「list_append」というC言語関数から始まる。これはまず_PyList_AppendTakeRefというヘルパー関数を呼び出す。この関数は、allocatedに空きスロットがあるかどうかをチェックする（高速パス）。もしあれば、新しいアイテムを空きスロットに配置し、ob_sizeを1増やしてO(1)で成功する。空きがなければ、list_resize関数を呼び出して容量を拡張する（低速パス）。このように、append()は常に可能な限り安価なO(1)操作を最初に試みるように設計されており、ほとんどの場合非常に効率的だ。

リストの先頭や途中にアイテムを挿入するmy_list.insert(index, item)メソッドは、「ins1」というC言語関数によって処理される。appendがリストの末尾に空きスペースを追加するのに対し、insertはリストの途中にスペースを作る必要があるため、処理が遅くなる。まずlist_resizeを呼び出して、要素を追加するためのスロットを一つ確保する。その後、指定されたwhere（挿入位置）以降のすべての要素を一つずつ右にずらし、whereの位置に空きを作る。このメモリのシャッフルはforループで行われるため、移動する要素の数に比例して時間がかかり、O(n)の操作となる。

要素の削除（del my_list[index]）は、「list_ass_slice」という関数（またはその簡略版のdelete_one_item）によって行われる。これは「ギャップを埋める」という逆の問題を解決する。削除対象のアイテムの参照カウントが減らされた後、リストから削除された要素によってできたギャップを埋めるため、C標準ライブラリのmemmove関数が使用される。memmoveは、メモリブロック全体を一つの場所から別の場所に物理的に移動させる、高度に最適化されたC言語の関数だ。これは、削除されたアイテムの右側にあるすべてのアイテムを一つ左にスライドさせることで、ギャップを閉じる。このmemmoveによる物理的な要素の移動が必要なため、削除操作もO(n)のコストがかかる。その後、list_resizeを呼び出してob_sizeを1減らす。

これらの深層を理解することで、Pythonのリストが動的であるという表面的な振る舞いの裏には、C言語の静的な配列という現実が存在することが明らかになる。my_list[99999]のような高速なアクセスは、C配列がメモリのアドレスを単純な計算で見つける生の力によるものだ。しかし、my_list.insert(0, 'x')が非常に遅く感じられるのは、同じC配列が、先頭にスペースを作るために、すべての要素を一つずつ物理的にシャッフルする、その力技を目にしているからだ。最終的に、Pythonのリストは、巧妙なトレードオフの上に構築された美しいエンジニアリングの結晶である。末尾への追加が中間への挿入よりも頻繁に行われるという前提に基づき、オーバーアロケーション戦略によってそのケースを最適化しているのだ。