配列 — Project Hematite

少しでもコードを書いたことがあれば、配列を使ったことがあるはずだ。配列はコンピューティングにおける最も基本的なデータ構造 — あまりにも単純なため、ハードウェアがそれに合わせて設計されたほどだ。より洗練された構造を探求する前に、配列がなぜそのように動くのかをきちんと理解しておく価値がある。

配列とは何か

配列（array）は、同じ型の要素を固定数だけ、順序を持って連続するメモリ（contiguous memory）に格納するコレクションだ — 要素は隙間なく、ひとつずつ隣り合わせに並ぶ。

すべての配列は 2 つの性質で定義される：

要素型（element type） — すべての要素は同じ型でなければならず、各要素は同じバイト数を占める。
長さ（length） — 要素数。基本的な形では配列の有効期間中は固定だ（可変長の変種については後述する）。

「連続するメモリ」という言葉が鍵だ。要素が隙間なく詰まっているため、配列は非連続な構造には持てない性質を得る：O(1) のインデックスアクセス — 最初の要素でも 100 万番目でも、任意の要素に到達するのに一定の時間しかかからない。

インデックスアクセスが O(1) な理由

メモリレイアウトでは、RAM が各バイトに固有のアドレス（address）を持つ長いバイト列だということを学んだ。配列が作られると、ランタイムはそのために連続したアドレスのブロックを予約する。

すべての要素が同じ型なので、すべての要素は同じバイト数を占める。そのサイズを $s$ と呼ぼう。最初の要素がベースアドレス（base address） $b$ に存在するなら、要素 $i$ は次のアドレスにある：

\text{address}(i) = b + i \times s

これは定数時間の算術だ。CPU は配列の全長に関係なく、1 命令でこれを計算する。検索もポインタをたどることもなく — 掛け算と足し算だけだ。

5 要素の i32 配列（各 i32 は 4 バイト）の具体例を示す：

インデックス: 0         1         2         3         4
            ┌─────────┬─────────┬─────────┬─────────┬─────────┐
値:         │   10    │   20    │   30    │   40    │   50    │
            └─────────┴─────────┴─────────┴─────────┴─────────┘
アドレス:   1000      1004      1008      1012      1016

インデックス 3 の要素へのアクセス： $1000 + 3 \times 4 = 1012$ 。完了。

Zig の固定長配列

Zig で固定長配列型を書く構文は [N]T だ。N はコンパイル時の長さ、T は要素型だ。

const std = @import("std");

pub fn main() void {
    const nums: [5]i32 = .{ 10, 20, 30, 40, 50 };

    std.debug.print("element 0: {}\n", .{nums[0]}); // 10
    std.debug.print("element 3: {}\n", .{nums[3]}); // 40
    std.debug.print("length:    {}\n", .{nums.len}); // 5
    std.debug.print("size:      {} bytes\n", .{@sizeOf([5]i32)}); // 20
}

nums.len は N に等しいコンパイル時定数だ。@sizeOf([5]i32) は 20 — 5 要素 × 4 バイト、隙間なしで、アドレス計算式の通りだ。

配列への書き込み

要素を変更するには、配列を var で宣言する必要がある：

var scores: [3]u32 = .{ 0, 0, 0 };
scores[0] = 95;
scores[1] = 87;
scores[2] = 76;

境界チェック

Zig は Debug ビルドと ReleaseSafe ビルドで、すべてのインデックスアクセスを配列の長さと照合する。5 要素の配列（有効なインデックスは 0 〜 4）で nums[5] にアクセスすると、壊れたメモリを暗黙に読む代わりにランタイムパニック（runtime panic）が発生する：

const nums: [5]i32 = .{ 10, 20, 30, 40, 50 };
_ = nums[5]; // runtime panic: index out of bounds

これは整数オーバーフローで見たのと同じ安全モデルだ：Debug ビルドがミスを声高に知らせてくれるので、開発中に発見できる。

配列の反復処理

Zig の for ループは、要素だけ、インデックスだけ、または両方を同時に走査できる：

const std = @import("std");

pub fn main() void {
    const words: [3][]const u8 = .{ "alpha", "beta", "gamma" };

    // 要素だけ
    for (words) |w| {
        std.debug.print("{}\n", .{w});
    }

    // インデックスと要素を同時に
    for (words, 0..) |w, i| {
        std.debug.print("[{}] {}\n", .{ i, w });
    }
}

スライス：実行時に柔軟なビュー

固定長配列はその長さが型に焼き込まれている — [5]i32 と [10]i32 は異なる型であり、互換なく使えない。これは、任意の長さの配列を扱う関数が必要なときや、長さが実行時にしか分からないときに不便になる。

スライス（slice）（[]T）はこの問題を解決する。スライスは軽量なペアだ：

最初の要素へのポインタ（pointer）
usize として格納された長さ（length）

長さは型レベルの定数ではなく実行時の値なので、1 つのスライス型がサイズを問わず同じ要素型の配列すべてをカバーできる。

const std = @import("std");

fn sum(s: []const i32) i32 {
    var total: i32 = 0;
    for (s) |v| total += v;
    return total;
}

pub fn main() void {
    const a: [3]i32 = .{ 1, 2, 3 };
    const b: [5]i32 = .{ 10, 20, 30, 40, 50 };

    std.debug.print("{}\n", .{sum(&a)}); // 6
    std.debug.print("{}\n", .{sum(&b)}); // 150
}

&a は [3]i32 配列を []const i32 スライスに変換する。関数 sum は具体的な配列型を見ず、ポインタと長さだけを受け取る。[]const i32 の []const は、そのスライスでは元の要素を変更できないことを意味する。変更可能なスライスには []i32 を使う。

start..end の範囲構文を使うと、配列の一部だけをカバーするスライスも作れる：

const arr: [6]i32 = .{ 0, 1, 2, 3, 4, 5 };
const mid = arr[2..5]; // インデックス 2, 3, 4 をカバーするスライス → 値 2, 3, 4

スライスの境界も、安全ビルドでは実行時にチェックされる。

ヒープに確保する配列

スタック上の固定長配列にはメモリレイアウトで学んだ制約がある：長さはコンパイル時に分かっていなければならず、非常に大きな配列はスタックをオーバーフローさせる。

長さがユーザー入力やファイル、ネットワーク応答から来る場合、あるいは配列がスタックに収まらない場合は、ヒープに確保する。allocator.alloc(T, n) は n 要素分を予約し、そのヒープメモリを所有する ![]T スライスを返す：

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const n: usize = 8; // 実行時にユーザー入力などから来てもよい
    const buf = try allocator.alloc(i32, n);
    defer allocator.free(buf);

    for (buf, 0..) |*elem, i| {
        elem.* = @intCast(i * i); // 二乗で埋める: 0, 1, 4, 9, …
    }

    for (buf) |v| {
        std.debug.print("{} ", .{v});
    }
    // 0 1 4 9 16 25 36 49
}

返されたスライス buf は他の []i32 とまったく同じように振る舞う — インデックスアクセス、境界チェック、反復処理はすべて同様に動く。唯一の違いは、使い終わったら allocator.free(buf) を呼ぶ必要があることだ。直後の行で defer とペアにするのが標準的な書き方だ。

主要操作の時間計算量

操作	時間	理由
インデックス $i$ の要素の読み書き	$O(1)$	アドレス算術： $b + i \times s$
値の検索（未ソート）	$O(n)$	最悪の場合、全要素を確認する必要がある
末尾への挿入（空きがある場合）	$O(1)$	次のスロットへ 1 回書き込むだけ
位置 $i$ への挿入（右シフト）	$O(n)$	最大 $n - i$ 要素を 1 スロット移動する必要がある
位置 $i$ の削除（左シフト）	$O(n)$	最大 $n - i$ 要素を 1 スロット移動する必要がある

$O(1)$ の読み書きは配列の最大の強みだ。中間での $O(n)$ の挿入・削除が主な弱点だ。任意の位置での挿入・削除が多いワークロードには、連結リストなど別の構造のほうが適している場合がある。

まとめ

配列は同じ型の要素を連続するメモリに格納する — 要素間に隙間はない。
任意の要素に $\text{address}(i) = b + i \times s$ （ $b$ はベースアドレス、 $s$ は要素のバイトサイズ）の計算式で O(1) に到達できる。
Zig では [N]T が固定長配列型で、N と要素型 T の両方がコンパイル時定数だ。要素へのアクセスは arr[i]、反復処理は for で行う。
範囲外アクセスは Debug ビルドと ReleaseSafe ビルドで実行時にパニックを引き起こす。
スライス（[]T）はポインタと実行時の長さのペアで、1 つの型がサイズを問わず任意の配列をカバーできる。&arr で配列をスライスに変換し、arr[start..end] で部分範囲を取り出せる。
配列の長さがコンパイル時に不明だったり、データがスタックに収まらない場合は、allocator.alloc(T, n) でヒープに確保し、allocator.free(slice) で解放する。
読み書きは O(1)。中間への挿入・削除は要素をずらす必要があるため O(n) だ。