1. 首頁 > 生活百科 >

aj 是什么，面試官給我挖坑：a「i」「j」 和 a「j」「i」 有什么區別？

什么 生活百科

本文以一個簡單的程序開頭——數組賦值：
int LEN = 10000;
int[][] arr = new int[LEN][LEN];
for (int i = 0; i < LEN; i++) {
for (int j = 0; j < LEN; j++) {
arr[i][j] = 1;
【aj 是什么，面試官給我挖坑：a「i」「j」 和 a「j」「i」 有什么區別？】 }
}
示例中雖然采用了Java，但是熟悉其他編程語言的同學可以自行腦補成自己熟悉的語言，如C/C++、Go、Python之類的，這里的知識點不限制在語言層級 。
我們在使用這種for循環的時候，是否會習慣性地使用arr[i][j]的這種寫法? 其實很多開源代碼、技術書籍示例中都是如此 。你是否還考慮過還有如下這種寫法，即將 arr[i][j] 替換成 arr[j][i] ：
int LEN = 10000;
int[][] arr = new int[LEN][LEN];
for (int i = 0; i < LEN; i++) {
for (int j = 0; j < LEN; j++) {
arr[j][i] = 1;
}
}
兩段代碼功能完全一樣，究竟有何區別？兩者性能會有數十倍或者數百倍之差 。
有些同學看到這里，直接祭出IDE，運行試了一下，發現第一段代碼的性能最優，所以很快地得出了a[i][j]最優的結論 。不過也會有同學會運行出第二段代碼性能更優的結果，即a[j][i]最優 。這到底是怎么回事呢？
從語言本身看，這個問題的要點在于語言怎樣實現矩陣 arr[M][N] 的存放 。有兩種最基本的存放方式：一種是第1下標優先存放；另一種是第2下標優先存放 。也就是一般所說的行優先（Row-major）和列優先（Column-major） 。
舉個例子，對于下面的數組：
可以有兩種存儲方式：左為列優先，右為行優先 。
行優先存儲，顧名思義，就是一行的數據存放在一起，然后逐行存放 。列優先存儲，就是每一列的數據是存儲在一起的，一列一列地存放在內存中 。這兩種存儲方法，對于編寫遍歷二維矩陣的循環語句，還是有一定影響的 。比如，如果是按行優先存儲的，那么在遍歷時，一行一行的讀取數據，肯定比一列一列地讀取整個數組，要方便許多（前者連續訪問內存，有利于CPU高速緩存，后者不聯系訪問內存，會引起頻繁更新高速緩存） 。
行優先（Row-major）或者列優先（Column-major）沒有好壞，但其直接涉及到對內存中數據的最佳存儲訪問方式 。因為在內存使用上，程序訪問的內存地址之間連續性越好，程序的訪問效率就越高；相應地，程序訪問的內存地址之間連續性越差 。所以，我們應該盡量在行優先機制的編譯器，比如C/C++、Objective-C（for C-style arrays）、Pascal等等上，采用行優先的數據存儲方式；在列優先機制的編譯器，比如Fortune、Matlab、R等等上，采用列優先的數據存儲方式 。但這種思想滲透到編程中之后，代碼的質量就會提高一個檔次 。
這里沒有提到市場占有率很高的Java語言，那么它們屬于行優先還是列優先呢？
答案：兩者都不是 。
密集數組存儲的一個典型替代方案是使用伊利夫向量（Iliffe vector），它通常將元素存儲在連續的同一行中(如同Row-major順序)，但不存儲行本身 。
什么是Iliffe向量？在計算機編程中，Iliffe向量是一種用于實現多維數組的數據結構 。n維數組的Iliffe向量(其中n≥2)由指向(n - 1)維數組的指針的向量(或1維數組)組成 。它們通常用于避免在對數組元素執行地址計算時執行昂貴的乘法操作 。它們還可用于實現交錯數組，如三角形數組、三角形矩陣和其他各種不規則形狀的數組 。數據結構以John K. Iliffe命名 。
它們的缺點包括需要多個鏈接指針來訪問一個元素，以及需要額外的工作來確定n維數組中的下一行，以允許優化編譯器預取它 。在CPU明顯快于主存的系統中，這兩個問題都是延遲的來源 。
在Java、Python(多維列表)、Ruby、Visual Basic . net、Perl、PHP、Javascript、Objective-C(當使用NSArray時，不是一個Row-magor C-Style的數組)、Swift和Atlas Autocode等語言中的多維數組被實現為Iliffe向量 。利用Iliffe向量實現OLAP產品全息的稀疏多維陣列 。
回到開頭，如果使用Java語言運行文中開頭的2段代碼，哪個更叫高效呢？請在留言區留下你的答案和思考 。

aj 是什么，面試官給我挖坑：a「i」「j」 和 a「j」「i」 有什么區別？

文章插圖
原文鏈接：***/u013256816/java/article/details/105525284

    推薦閱讀