配列とインデックス
配列は順序付きの列を番号付きスロットに置き、ゼロ始まりのインデックスで読みます。長さ n の配列で有効な非負インデックスは 0 から n - 1 です。range(len(values)) はそれらを訪れ、n には対応するスロットがありません。
インデックスは定規の座標に似ています。スロット 0 の変位は 0、スロット 1 は 1 です。位置を示す座標であって、移動経路ではありません。配列は目的の場所を直接計算し、先頭から右へ走査しません。
配列とインデックスの仕組み
values = [12, 7, 25] では、インデックス 0、1、2 にそれぞれ 12、7、25 があります。インデックスが扱うのは位置で、値の大小ではありません。
非負インデックス i の境界条件は 0 <= i < len(values) です。長さ 3 のスロット番号は 0、1、2 なので、上界は厳密な不等号になります。長さはスロットの個数であり、末尾のインデックスではありません。
range(len(values)) はこの範囲を走査します。range(3) は 0、1、2 を生成して止まり、i = 3 を代入せず、ループ内で values[3] を試しません。
配列型の表現では、一回の添字アクセスは O(1) です。開始位置、インデックス、参照スロット一つの幅から目的の位置を計算します。全走査は n 回の読み取りが必要なので O(n) です。
Python で values[3] を評価すると IndexError が発生します。None を返したり空のセルを補ったりはしません。print の引数に使った場合も、print を呼ぶ前に例外が発生します。
ステップごとの解説
既定では values = [12, 7, 25] と probe = 3 を使います。
- 1 行目で
range(len(values))を準備します。長さは 3、候補は 0、1、2 です。 i = 0を生成し、2 行目でvalues[0]の 12 を読み、0 12を表示します。i = 1を生成し、values[1]の 7 を読み、1 7を表示します。i = 2を生成し、values[2]の 25 を読み、2 25を表示します。- イテレーターが尽きます。
iは 2 のままで、3 は代入されません。四回目の読み取りをせずにループを出ます。 - 3 行目で
0 <= 3 < 3を調べ、偽になります。 values[3]の評価でIndexErrorが発生します。引数の評価が止まるため、print("probe", ...)は実行されません。
画面は二つの出来事を分けます。まず range(3) が 3 の前で止まる境界を示し、次に同じ場所への実アクセスで赤くなります。アドレスの表示 base + 3 × one slot は、一回の計算で境界へ到達することを示します。0、1、2 を順に調べる動きではありません。
添字アクセスが O(1) である理由
| 操作 | 時間 | 追加領域 | 理由 |
|---|---|---|---|
values[i] の読み取り | O(1) | O(1) | インデックスから一つの位置を計算する |
全 n スロットの走査 | O(n) | O(1) | 各スロットを一回ずつ読む |
0 <= i < n の確認 | O(1) | O(1) | 二つの境界と比較する |
O(1) は固定幅の参照スロットを持つ配列型の表現を仮定します。連結リストは先頭から位置 i までリンクをたどるため O(i) で、同じ直接計算は使えません。
境界ケース
- 空の配列。 長さは 0 で、
range(0)は何も生成しません。非負の探査位置はすべて範囲外です。 - 先頭。 空でなければ 0 は有効で、開始位置からの変位はゼロです。
- 末尾。
n > 0なら最後の非負インデックスはn - 1です。 - 末尾の先。
nは最初の無効な非負インデックスで、Python はIndexErrorを発生させます。 - Python の負のインデックス。
-1は末尾、-nは先頭を表します。他言語が同じ規則を持つとは限らないため、主図は非負の範囲を扱います。
よくある間違い
- 走査条件を
i <= len(values)にする。等号が範囲外のnを許してしまいます。 - 長さを最後のインデックスと考える。空でない場合は一を引きます。
- 範囲外なら
Noneが返ると思う。Python は外側の呼び出しより先に例外を発生させます。 - O(1) のアクセスを先頭からの移動と想像する。目的のスロットを直接計算します。
nに空の箱を描く。そこにセルは存在しないため、境界として示します。
このレッスンでの簡略化
セルは Python リストの論理スロットで、メモリダンプではありません。リストはオブジェクト参照を連続して置きますが、整数オブジェクト自体は隣接するとは限りません。バイトアドレス、予備容量、拡張、オブジェクトヘッダー、インタープリター内部は省き、負のインデックスも主図では扱いません。他言語はトラップ、別の例外、不安全なアクセスなどを使うことがあり、IndexError は Python 固有の挙動です。