ハイパフォーマンスPython

3章リストとタプル

本章を読めば以下の問いに答えられるようになる

• リストとタプルの長所は？
• リストとタプルの探索の計算オーダーは？
• その計算オーダーの理由は？
• リストとタプルの違いは？
• リストに追加するときの動作は？
• リストとタプルを使うのが適当なときは？

効率的なプログラムを書くときにもっとも重要なことは、使用するデータ構造の特徴を理解することです。最適化プログラミングとは、データにどんな質問をするのかを理解し、その質問に高速に答えられるデータ構造を採用することと言っても過言ではありません。本章では、リストとタプルが高速に答えることができる質問の種類と、その使用法を説明します。

リストとタプルは配列というデータ構造のクラスに属します。配列とは、なんらかの固有な順番で並んだ単純な一連のデータです。順序が事前にわかっていることが重要です。配列上のデータが特定の位置にあることがわかっていれば、O(1)のオーダーで探索することができるからです。さらに、配列はさまざまな方法で実装することができます。このことがリストとタプルを明確に区別するポイントになります。すなわち、リストは動的な配列であり、タプルは静的な配列である、ということです。

もう少し噛み砕いて説明します。コンピュータのシステムメモリは番号のついたバケットが並んでいて、それぞれに数字を入れることができる、とみなすことができます。数字は、メモリ上のデータへの参照となって、整数、浮動小数点数、文字列などの任意のデータ型の変数を表します†1。

[†1] 64ビットコンピュータでは、12KBのメモリで725個のバケット、52GBのメモリで3,250,000,000個のバケットになります。

配列（リストまたはタプル）を生成すると、まずシステムメモリの領域を確保し、各要素が実際のデータへのポインタになります。このときOSのカーネルを呼び出して、 ...