Learning Objectives
- 說明陣列的元素在記憶體裡連續存放，並用「起點＋索引×元素大小」算出任何元素的位址
- 說明為什麼用索引讀取是 O(1)，以及元素大小如何影響相鄰元素的位址差
- 算出二維陣列在列優先與行優先兩種排列下，m[r][c] 是第幾格、位址是多少
- 說明 Java 的二維陣列與 Python 的串列在記憶體裡和 C／C++ 有什麼不同
- 在有容量上限的陣列裡插入與刪除，數出要搬移幾個元素
陣列為什麼能直接跳到第 i 格
上一課反覆用到一件事：陣列「可以直接跳到第 i 格」，所以二分搜尋每次都能馬上看中間那一個。這一課要看清楚它為什麼做得到。
先想像電腦的記憶體：一長條很多很多格的空間，每一格是一個位元組（byte，8 個位元），每一格都有一個編號，叫做位址（address）。
一個 int 通常占 4 個位元組，也就是連續的 4 格；一個 double 占 8 格。
陣列（array）的規則只有兩條：
- 所有元素的型別相同，所以每個元素占的位元組數一樣
- 元素一個緊接一個存放，中間沒有空隙（連續配置）
有了這兩條，第 i 個元素的位址可以直接算出來：
a[i] 的位址 = 起點 + i × 元素大小
不管 i 是 3 還是 300 萬，都只是一次乘法和一次加法，所以用索引讀取或修改是 O(1)，這叫做隨機存取（random access）。 「索引從 0 開始」也是從這個公式來的：a[0] 就在起點，偏移是 0。
元素大小決定相鄰兩格差幾個位元組
int 陣列相鄰兩格差 4 個位元組，double 陣列差 8 個位元組。切換到 C++ 看看：C++ 的版本不是用公式算，而是真的取兩個元素的位址相減（&a[i] 是 a[i] 的位址），量出來的數字和公式完全一樣；右邊的記憶體圖也畫出了 a 和 d 的真實位址。Java 不讓程式看到記憶體位址，Python 的串列存的是物件的參考（下面會說明），所以這兩種寫法用公式示範。
元素大小與 sizeof
元素大小由型別決定。常見的大小如下：
| 型別 | C／C++（常見的 64 位元系統） | Java（語言規格固定） |
|---|---|---|
char |
1 | 2（Java 的 char 是 UTF-16） |
short |
2 | 2 |
int |
4 | 4 |
long long／long |
8 | 8 |
double |
8 | 8 |
| 指標／參考 | 8 | 依 JVM 而定 |
C／C++ 用 sizeof(int) 查大小，sizeof(a) 是整個陣列的位元組數，所以常見 sizeof(a) / sizeof(a[0]) 這種算元素個數的寫法。
C／C++ 標準只規定了最小範圍，實際大小依平台而定；Java 的基本型別大小則由語言規格固定。
Python 的串列比較特別：串列底下的陣列存的不是數字本身，而是指向物件的參考。每個參考大小相同，所以「起點＋索引×大小」的公式照樣成立，用索引讀取仍是 O(1)；
但參考指向的物件散落在記憶體各處。需要真正緊密排列的數字陣列時，用標準函式庫的 array 模組或第三方套件 NumPy。
二維陣列：表格要攤平成一排
記憶體只有一條，二維的表格要先攤平成一排才能存。有兩種攤法：
- 列優先（row-major）：先放第 0 列的全部元素，再放第 1 列……同一列的元素連在一起
- 行優先（column-major）：先放第 0 行的全部元素，再放第 1 行……同一行的元素連在一起
一個 rows 列、cols 行的表格，m[r][c] 排在第幾格：
| 排列 | m[r][c] 是第幾格 | 位址 |
|---|---|---|
| 列優先 | r × cols + c（前面有 r 整列，每列 cols 個） |
起點 ＋ (r × cols ＋ c) × 元素大小 |
| 行優先 | c × rows + r（前面有 c 整行，每行 rows 個） |
起點 ＋ (c × rows ＋ r) × 元素大小 |
C 與 C++ 的二維陣列、NumPy 的預設都是列優先；Fortran、MATLAB、R 用行優先。 下面的程式把同一個 2 × 3 的表格用兩種方式攤平，看每個元素被放到哪一格。
同一個表格，兩種攤平方式
外層迴圈一列一列走，內層一格一格走。列優先的指標每次往右一格，一列走完剛好接到下一列；行優先的指標每次跳 rows = 2 格，第 0 列填的是偶數格，第 1 列填的是奇數格。最後一行印出 m[1][2] 在兩種排列裡各是第幾格。
Java 與 Python 的「二維陣列」
不是每種語言的二維陣列都攤平成一整排：
| 語言 | m[r][c] 在記憶體裡 |
|---|---|
C／C++ int m[3][4] |
12 個 int 連續存放，列優先 |
Java int[][] m = new int[3][4] |
陣列的陣列：外層是存 3 個參考的陣列，每個參考指向一個獨立的 int[4]。同一列連續，但列和列之間不一定相鄰；各列的長度甚至可以不同（不規則陣列，jagged array） |
Python [[0] * 4 for _ in range(3)] |
串列的串列：外層串列存 3 個參考，每個指向一個內層串列，內層再存元素的參考 |
所以 Java 讀 m[r][c] 要先讀外層的 m[r] 拿到那一列，再在那一列裡用 c 算位址；C／C++ 則直接用 r × cols + c 一次算出來。
切換到 Java 版的上一個範例，可以看到 m 是一個指向兩個列陣列的物件。
Python 還有一個常見的陷阱：[[0] * 4] * 3 會讓外層的 3 個參考都指向同一個內層串列，改 m[0][0] 時三列一起變。建立二維串列要用 [[0] * 4 for _ in range(3)]。
走訪的順序會影響速度
處理器讀記憶體時，不是一次只拿一個位元組，而是把附近一整塊（常見是 64 個位元組，叫做一條快取線，cache line）一起搬進快取（cache）。 接下來讀到同一塊裡的資料就很快；讀到另一塊，就得再去比較慢的主記憶體拿。
列優先存放的表格：
- 一列一列走訪，每次讀的位置和上一次相鄰，同一塊快取線裡的資料都用上了
- 一行一行走訪，每次跳過一整列（cols 個元素），表格很大時，幾乎每讀一個元素都要換一塊
兩種走訪做的運算次數完全一樣，都是 O(rows × cols)，但實際速度可能差好幾倍。下面的程式記下兩種走訪依序讀到的位置。
一列一列走與一行一行走
前半段一列一列走，▲ 每次往右一格，從頭走到尾；後半段一行一行走，▲ 每次往右跳 4 格，走到底再折回前面。輸出的兩行就是兩種走訪讀到的位置順序。
想一想：位址與排列
一個 int 陣列（每個元素 4 個位元組）從位址 2000 開始，a[7] 的位址是多少？
int m[3][5] 從位址 1000 開始，每個 int 4 個位元組。m[2][1] 在列優先與行優先時的位址分別是？
用索引讀取陣列的第 i 個元素是 O(1)，最主要的原因是？
在陣列裡插入與刪除：大小與容量
陣列一建立，格子數就固定了，這叫做容量（capacity）。實際放了幾個元素另外用一個整數記錄，叫做大小（size）。 不變條件是：a[0] 到 a[size - 1] 是有效的元素，size 不超過容量；size 以後的格子放什麼都不算。
在索引 k 插入 x：
- 檢查：size 已經等於容量（滿了），或 k 不在 0～size 之間，就不能插入
- 從最後一個元素開始，把 a[size - 1]、a[size - 2]……a[k] 各往右挪一格（從前面開始挪會把還沒挪的值蓋掉）
- 把 x 放進 a[k]，size 加 1
要挪 size - k 個元素。刪除 a[k] 則反過來，從 k 開始把右邊的元素往左補，要挪 size - 1 - k 個。 所以在最前面插入或刪除是 O(n)，在最後面是 O(1)。
演算法軌第 03 課數過「在最前面插入」的搬移次數；這裡把它寫成有大小、容量檢查的函式，在中間插入，也示範不合法的位置。
有容量上限的插入與刪除
容量 7 的陣列放了 5 個元素。在索引 2 插入 15 時，33、26、19 依序往右挪；刪除索引 0 時，右邊 5 個元素往左補，最後一格的舊值還在，但已經落在 size 之外（虛線）。最後在索引 9 插入，9 大於 size，不合法，什麼都不改。
想一想：搬移與走訪
這段程式會印出什麼？
a = [2, 4, 6, 8, 10, 0, 0]
size = 5
moves = 0
for j in range(size, 1, -1):
a[j] = a[j - 1]
moves += 1
a[1] = 3
print(moves, a[3], a[5])
C++ 有一個很大的 int m[2000][2000]。要把所有元素加總，下列哪一種寫法通常比較快？
Java 的 int[][] m = new int[3][4]; 在記憶體裡是什麼樣子？
實作：一次刪除所有指定的值
要從陣列刪除所有等於 x 的元素，如果每找到一個就呼叫一次「刪除 a[k]」，每次都要把右邊整段往左挪，最壞是 O(n²)。更好的做法是用兩個索引：r 由左往右讀每個元素，w 指向下一個要寫入的位置；a[r] 不等於 x 就寫到 a[w]、w 加 1。掃完一遍，w 就是新的大小，只要 O(n)。請完成 remove_all，回傳新的大小。
重點整理
- 記憶體以位元組為單位編號；陣列的元素型別相同、連續存放
a[i]的位址＝起點＋i×元素大小，一次乘法、一次加法，所以用索引讀取是 O(1)- 元素大小由型別決定：C／C++ 用
sizeof查；Python 串列存的是參考，參考大小相同，公式照樣成立 - 二維陣列要攤平：列優先第
r×cols+c格（C／C++、NumPy 預設），行優先第c×rows+r格（Fortran、MATLAB、R） - Java 的二維陣列是陣列的陣列，Python 是串列的串列，列與列之間不一定相鄰
- 依存放順序走訪（列優先就一列一列走）能善用快取
- 陣列有容量與大小；在索引 k 插入要挪 size - k 個、刪除要挪 size - 1 - k 個，最壞 O(n)
下一課：動態陣列。容量滿了怎麼辦？Python 的串列、C++ 的 vector、Java 的 ArrayList 都能一直加元素，下一課親手做一個，並算出「平均每次 append 要幾步」。