民國114年 高考三級 統計 資料處理
第2題
編譯器（compiler）將二維陣列資料映射到線性記憶體空間，一般採Row- major 或Column-major 兩種不同儲存順序。 何謂Row-major…
題目
編譯器（compiler）將二維陣列資料映射到線性記憶體空間，一般採Row- major 或Column-major 兩種不同儲存順序。 何謂Row-major 儲存順序與Column-major 儲存順序？（8 分） 試問程式碼應如何撰寫，對整個巨大型二維陣列之資料讀取，才能獲得 較高的讀取時間效率？（6 分）並請給予一程式片段範例做說明。（6 分）
參考解答（AI 生成，非官方）
- （一）Row-major（列優先）是先存第 0 列所有元素，再存第 1 列；若 A 為 M×N、以 0 起始、元素大小 w、基底位址 B，則 A[i][j] 位址為 B+(i×N+j)×w。Column-major（行優先）是先存第 0 行所有元素，再存第 1 行，位址為 B+(j×M+i)×w。C/C++、Java 採列優先；Fortran、MATLAB 採行優先。兩者差別在於哪一個索引先連續變動。
- （二）巨大型陣列之效率取決於 spatial locality（空間局部性）。CPU 一次載入一整條 cache line（快取線），若存取順序與記憶體排列一致，後續元素多半已在快取，可減少 cache miss、TLB miss 與記憶體頻寬浪費；跳躍式存取則可能每讀一元素就發生一次快取置換。故應依儲存順序走訪：列優先語言外層跑列、內層跑行；行優先語言外層跑行、內層跑列。
- （三）以 C 列優先為例：int sum=0; for(i=0;i<M;i++) for(j=0;j<N;j++) sum+=A[i][j]; 內層 j 連續存取同一列，效率最佳。若改成 for(j=0;j<N;j++) for(i=0;i<M;i++) sum+=A[i][j]; 每次跨列，對大陣列會不斷 cache miss。若使用 Fortran 行優先，則應寫 do j=1,N; do i=1,M; sum=sum+A(i,j); end do; end do。編譯器雖可能自動迴圈交換，但含指標別名或動態記憶體時不可依賴。
- （四）若單列或單行仍大於快取，可再用 loop tiling/blocking（迴圈分塊），切成 B×B 小塊，使每塊在快取中重複使用；矩陣乘法、轉置特別有效。另須注意資料對齊、prefetch、編譯器優化與多執行緒 false sharing。惟本題核心是「讀取順序與 layout 一致」；若函式庫可指定 order（如 NumPy 的 C order/F order），應配合設定或先轉置。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。