配列とは？

1週間の気温を表示する天気アプリには、7つの数値が必要です。monday、tuesday のように7つの別々の変数を使うこともできますが、それではループで順にたどれず、8日目を加えるには新しいコードを書くことになります。配列なら、7つの数値すべてを temperatures という1つの名前の下に、0から6までの番号付きの枠に入れておけます。

配列のしくみ

配列は要素を1つのメモリ領域に隣り合わせで並べ、どの要素も同じバイト数を使います。この並び方のおかげで、コンピュータは1回の計算でどの要素でも見つけられます。

address of element i = start address + i × element size

32ビット整数（1つ4バイト）の配列が、メモリアドレス1000から始まるとしましょう。要素0は1000、要素1は1004、要素2は1008、要素3は1012にあります。要素3に届くのも、要素3,000,000に届くのも同じ1ステップです。そのため、インデックスによる配列の読み取りは定数時間と呼ばれ、O(1)と書かれます。

Pythonの array モジュールは生の数値をこの方法で保存するので、計算を確かめられます。

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

この式は、ほとんどの言語が0から数える理由も説明しています。インデックスはオフセット、つまり先頭からいくつの要素を飛ばすかです。最初の要素は先頭から0個分の位置にあるのでインデックスは0で、長さnの配列の最後の要素のインデックスはn − 1です。Lua、MATLAB、R、Fortranなど、1から始まる言語もわずかにあります。

Pythonで配列を使う

Pythonのコードの多くは、組み込みの list を配列として使います。角かっこで作り、インデックスで要素を読んだり変えたりし、len() で長さを調べます。

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

負のインデックスは末尾から数えるので、temperatures[-1] は最後の要素です。この書き方はPython独自のもので、CやJavaには負のインデックスはありません。

配列の操作にかかるコスト

連続した並び方は、ある操作を速くし、別の操作を遅くします。コストは要素数nとともに増えます。

先頭への挿入が遅いのは、場所を空けるためにすべての要素を1つずつずらす必要があるからです。ソートされていない配列を探すには、要素を順番に調べる線形探索をすることになります。ソート済みの配列なら、1ステップごとに残りの範囲を半分にする二分探索が使えます。

配列をループでたどる

配列とループは一緒に使うものです。ループは各要素を順に訪れ、これを反復と呼びます。同じ数行で、要素が5個の配列も500万個の配列も扱えます。

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

ほかの言語の配列

Cの配列は、宣言したときに決めた固定の大きさを持ち、1つの型の生の値を保持します。sizeof はその大きさをバイト単位で返します。

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Javaの配列も長さが固定で、新しい要素は数値なら0のような既定値から始まります。伸びるJavaの配列が必要なときは ArrayList を使います。

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

JavaScriptの配列は自由に伸び縮みし、[1, "two", true] のように型を混ぜることもできます。

Pythonの list、Javaの ArrayList、C++の std::vector のように伸びる配列は、動的配列と呼ばれます。末尾に余分な領域を確保しておき、それを使い切ると、より大きな領域を確保してすべての要素をコピーし、続きを行います。コピーはたまにしか起こらないので、末尾への追加は平均すると速いままです。

配列はほかの配列を持つこともできます。grid[row][col] は2次元配列の1つのマスを読み取ります。ゲーム盤、スプレッドシート、画像に使われる並び方です。メモリ上でどう並ぶかはCの多次元配列ガイドで説明しています。

よくある間違い

1つずれる。 要素が3つの配列のインデックスは0、1、2なので、インデックス3は末尾を越えています。Pythonはエラーで止まります。

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Javaは ArrayIndexOutOfBoundsException を投げ、JavaScriptは黙って undefined を返します。Cは一切チェックしません。末尾を越えた読み取りは未定義動作で、でたらめな値が返ったり、セグメンテーション違反でプログラムがクラッシュしたりします。

代入でコピーする。 Python、Java、JavaScriptでは、b = a は配列をコピーしません。2つの名前が同じ配列を指すので、b を変えると a も変わります。本当のコピーには、Pythonでは a.copy()、JavaScriptでは [...a] を使います。理由は変数のページで説明しています。

次に読むもの

配列はループでたどってこそ役に立つので、次は反復とは何かを読み、上の要素の大きさの単位についてはバイトとは何かを読んでください。Pythonのリストガイドではスライス、ソート、リストのメソッドを扱っています。連結リストの可視化では、速いインデックスアクセスと引き換えに速い挿入を得るデータ構造を見られます。