Java/陣列之道
陣列
array type!array
陣列是一組值，其中每個值都由一個索引標識。您可以建立一個 int、double 或任何其他型別的陣列，但陣列中的所有值必須具有相同的型別。
從語法上講，陣列型別看起來像其他 Java 型別，但後面跟著 []。例如，int[] 是“整數陣列”型別，而 double[] 是“雙精度浮點數陣列”型別。
您可以在通常的方式中宣告具有這些型別的變數
逐字
int[] count; double[] values;
逐字
在您初始化這些變數之前，它們被設定為 null。要建立陣列本身，請使用 new 命令。
逐字
count = new int[4]; values = new double[size];
逐字
第一個賦值使 count 指向一個包含 4 個整數的陣列；第二個賦值使 values 指向一個包含 double 值的陣列。values 中元素的數量取決於 size。您可以使用任何整數表示式作為陣列大小。
null state diagram
下圖顯示瞭如何在狀態圖中表示陣列
figure=figs/array.eps
方框內部的較大數字是陣列的元素。方框外部的較小數字是用來標識每個方框的索引。當您分配一個新陣列時，元素被初始化為零。
element array!element
要將值儲存在陣列中，請使用 [] 運算子。例如 count[0] 指的是陣列的“第零”個元素，count[1] 指的是“第一個”元素。您可以在表示式中的任何位置使用 [] 運算子
逐字
count[0] = 7; count[1] = count[0] * 2; count[2]++; count[3] -= 60;
逐字
所有這些都是合法的賦值語句。以下是這段程式碼片段的效果
figure=figs/array2.eps
到目前為止，您應該已經注意到這個陣列的四個元素從 0 到 3 編號，這意味著沒有索引為 4 的元素。這應該聽起來很熟悉，因為我們在 String 索引中也看到了同樣的事情。然而，超出陣列範圍是一個常見的錯誤，這將導致 ArrayOutOfBoundsException。與所有異常一樣，您會收到一條錯誤訊息，程式也會退出。
exception!ArrayOutOfBounds run-time error index expression
您可以使用任何表示式作為索引，只要它具有 int 型別。最常見的索引陣列的方法之一是使用迴圈變數。例如
逐字
int i = 0;
while (i < 4)
System.out.println (count[i]);
i++;
逐字
這是一個標準的 while 迴圈，它從 0 計數到 4，當迴圈變數 i 等於 4 時，條件失敗，迴圈終止。因此，迴圈體僅在 i 等於 0、1、2 和 3 時執行。
loop loop variable variable!loop
每次迴圈時，我們都使用 i 作為陣列的索引，列印第 i 個元素。這種型別的陣列遍歷非常常見。陣列和迴圈就像豌豆和一杯美酒。
fava beans Chianti
array!copying
當您複製一個數組變數時，請記住您複製的是對陣列的引用。例如
逐字
double[] a = new double [3]; double[] b = a;
逐字
這段程式碼建立了一個包含三個 double 值的陣列，並使兩個不同的變數指向它。這種情況是別名的一種形式。
figure=figs/array3.eps
任何對任一陣列的更改都將反映在另一個數組中。這通常不是您想要的行為；相反，您應該透過分配一個新陣列並將每個元素從一個數組複製到另一個數組來製作陣列的副本。
逐字
double[] b = new double [3];
int i = 0;
while (i < 4)
b[i] = a[i];
i++;
逐字
我們迄今為止編寫的迴圈具有一些共同的元素。它們都從初始化一個變數開始；它們有一個測試（或條件），該測試（或條件）依賴於該變數；在迴圈內部，它們對該變數做了一些操作，例如遞增它。
loop!for for statement!for
這種型別的迴圈非常常見，因此有一個名為 for 的備用迴圈語句，它更簡潔地表達了它。一般語法如下所示
逐字
for (INITIALIZER; CONDITION; INCREMENTOR)
BODY
逐字
此語句與以下語句完全等效
逐字
INITIALIZER;
while (CONDITION)
BODY
INCREMENTOR
逐字
除了它更簡潔，而且由於它將所有與迴圈相關的語句放在一個地方，因此它更容易閱讀。例如
逐字
for (int i = 0; i < 4; i++)
System.out.println (count[i]);
逐字
與以下語句等效
逐字
int i = 0;
while (i < 4)
System.out.println (count[i]);
i++;
逐字
作為練習，編寫一個 for 迴圈來複制陣列的元素。
object!compared to array array!compared to object
在很多方面，陣列的行為類似於物件
itemize
當您宣告一個數組變數時，您會獲得對陣列的引用。
您必須使用 new 命令來建立陣列本身。
當您將陣列作為引數傳遞時，您傳遞的是一個引用，這意味著被呼叫的方法可以更改陣列的內容。
itemize
我們已經看過的一些物件，比如 Rectangle，類似於陣列，因為它們是命名的值集合。這就提出了一個問題，“包含 4 個整數的陣列與 Rectangle 物件有什麼區別？”
collection
如果您回到本章開頭對“陣列”的定義，您會發現一個區別，即陣列的元素由索引標識，而物件的元素（例項變數）具有名稱（如 x、width 等）。
陣列和物件之間的另一個區別是陣列的所有元素都必須具有相同的型別。雖然對於 Rectangle 也是如此，但我們已經看到了其他具有不同型別例項變數的物件（例如 Time）。
length!array array!length
實際上，陣列確實有一個名為 length 的例項變數。毫不奇怪，它包含陣列的長度（元素數量）。最好使用此值作為迴圈的上限，而不是一個常量值。這樣，如果陣列的大小發生變化，您不必遍歷程式更改所有迴圈；它們將對任何大小的陣列正常工作。
逐字
for (int i = 0; i < a.length; i++)
b[i] = a[i];
逐字
迴圈體最後一次執行時，i 等於 a.length - 1，這是最後一個元素的索引。當 i 等於 a.length 時，條件失敗，迴圈體不會執行，這是件好事，因為它會導致異常。這段程式碼假設陣列 b 至少包含與 a 相同數量的元素。
作為練習，編寫一個名為 cloneArray 的方法，該方法將一個整數陣列作為引數，建立一個與它大小相同的陣列，將元素從第一個陣列複製到新陣列，然後返回對新陣列的引用。
隨機 偽隨機
random number deterministic nondeterministic
大多數計算機程式每次執行時都會做同樣的事情，因此它們被稱為確定性程式。通常，確定性是一件好事，因為我們希望相同的計算產生相同的結果。然而，對於某些應用程式，我們希望計算機不可預測。遊戲是一個明顯的例子，但還有很多其他例子。
使程式真正變得非確定性並非易事，但有一些方法可以使它看起來至少是非確定性的。其中一種方法是生成隨機數並使用它們來確定程式的結果。Java 提供了一個內建方法，它可以生成偽隨機數，它們在數學意義上並不真正隨機，但對於我們的目的來說已經足夠了。
檢視 Math 類中 random 方法的文件。返回值是 0.0 到 1.0 之間的 double 值。每次呼叫 random 時，您都會得到一個不同的隨機生成數。要檢視示例，請執行此迴圈
逐字
for (int i = 0; i < 10; i++)
double x = Math.random ();
System.out.println (x);
逐字
要生成 0.0 到高上限（如 high）之間的隨機 double 值，您可以將 x 乘以 high。您將如何生成 low 到 high 之間的隨機數？您將如何生成隨機整數？
statistics distribution mean
random 生成的數字應該均勻分佈。如果您學過統計學，您就知道這意味著什麼。除其他事項外，這意味著如果我們將可能值的範圍劃分為大小相等的“桶”，並計算隨機值落在每個桶中的次數，那麼每個桶最終都應該獲得相同次數的命中。
在接下來的幾節中，我們將編寫程式來生成隨機數序列，並檢查此屬性是否成立。
第一步是生成大量隨機值並將它們儲存在陣列中。當然，我所說的“大量”是指 8 個。從一個易於管理的數字開始始終是個好主意，這有助於除錯，之後再逐漸增加。
以下方法接受一個引數，即陣列的大小。它分配一個新的雙精度陣列，用隨機值填充它，並返回對新陣列的引用。
逐字
public static double[] randomArray (int n)
double[] a = new double[n];
for (int i = 0; i<a.length; i++)
a[i] = Math.random ();
return a;
逐字
返回值型別是 double[]，這意味著該方法返回一個雙精度陣列。為了測試該方法，最好有一個方法可以列印陣列的內容。
逐字
public static void printArray (double[] a)
for (int i = 0; i<a.length; i++)
System.out.println (a[i]);
逐字
以下程式碼生成一個數組並列印它。
逐字
int numValues = 8; double[] array = randomArray (numValues); printArray (array);
逐字
在我的機器上，輸出結果是
verbatim 0.7344558779885422 0.6224282219647016 0.09591424515329172 0.2992298398883563 0.7736458103088713 0.7069110192991597 0.7042440765950522 0.977839532249852 verbatim
看起來相當隨機。你的結果可能有所不同。
如果這些數字確實是隨機的，我們預計其中一半大於 0.5，一半小於 0.5。實際上，有六個大於 0.5，因此略高。
如果我們將範圍劃分為四個區間 - 從 0.0 到 0.25，0.25 到 0.5，0.5 到 0.75 以及 0.75 到 1.0 - 我們預計每個區間內有 2 個值。實際上，我們得到的是 1、1、4、2。同樣，並不完全是我們預期的結果。
這些結果是否意味著這些值並非真正隨機？很難說。由於值很少，我們得到完全符合預期的結果的可能性很小。但是隨著值的增加，結果應該更易於預測。
為了驗證這一理論，我們將編寫一些程式，將範圍劃分為區間並計算每個區間內的值數量。
計數
[edit | edit source]traverse!array array!traverse looping and counting counter
解決這類問題的良好方法是考慮易於編寫且可能證明有用的簡單方法。然後，你可以將它們組合成一個解決方案。當然，事先並不知道哪些方法可能有用，但隨著你積累經驗，你將對這個問題有更好的理解。
此外，並不是總是很明顯哪些東西容易編寫，但一個好的方法是尋找符合你以前見過的模式的子問題。
回到 loopcount 部分，我們查看了一個遍歷字串並計算給定字母出現的次數的迴圈。你可以將該程式視為“遍歷並計數”模式的一個示例。該模式的元素包括：
itemize
可以遍歷的一組或容器，例如陣列或字串。
可以應用於容器中每個元素的測試。
一個計數器，用於跟蹤透過測試的元素數量。
itemize
在本例中，我想到了一種名為 inBucket 的方法，用於計算陣列中落在給定區間內的元素數量。引數是陣列以及兩個指定區間上下限的雙精度數。
逐字
public static int inBucket (double[] a, double low, double high)
int count = 0;
for (int i=0; i<a.length; i++)
if (a[i] >= low && a[i] < high) count++;
return count;
逐字
我沒有特別注意等於 low 或 high 的值是否落在區間內，但你可以從程式碼中看到 low 在內，high 在外。這應該可以防止我多次計算任何元素。
現在，要將範圍劃分為兩部分，我們可以編寫
逐字
int low = inBucket (a, 0.0, 0.5); int high = inBucket (a, 0.5, 1.0);
逐字
要將其劃分為四部分
逐字
int bucket1 = inBucket (a, 0.0, 0.25); int bucket2 = inBucket (a, 0.25, 0.5); int bucket3 = inBucket (a, 0.5, 0.75); int bucket4 = inBucket (a, 0.75, 1.0);
逐字
你可能想嘗試使用更大的 numValues 執行此程式。隨著 numValues 的增加，每個區間內的數字是否趨於平穩？
多個區間
[edit | edit source]bucket histogram
當然，隨著區間數量的增加，我們不想不得不重寫程式，尤其是在程式碼變得越來越大且重複的情況下。每當你發現自己做某件事超過幾次，你應該尋找自動執行它的方法。
假設我們想要 8 個區間。每個區間的寬度將是範圍的八分之一，即 0.125。要計算每個區間內的值數量，我們需要能夠自動生成每個區間的邊界，並且需要有某個地方來儲存 8 個計數。
我們可以使用迴圈解決第一個問題
逐字
int numBuckets = 8; double bucketWidth = 1.0 / numBuckets;
for (int i = 0; i < numBuckets; i++)
double low = i * bucketWidth;
double high = low + bucketWidth;
System.out.println (low + " to " + high);
逐字
此程式碼使用迴圈變數 i 乘以區間寬度，以找到每個區間的下限。此迴圈的輸出結果是
verbatim 0.0 to 0.125 0.125 to 0.25 0.25 to 0.375 0.375 to 0.5 0.5 to 0.625 0.625 to 0.75 0.75 to 0.875 0.875 to 1.0 verbatim
你可以確認每個區間寬度相同，它們沒有重疊，並且它們覆蓋了從 0.0 到 1.0 的整個範圍。
現在我們只需要一種方法來儲存 8 個整數，最好能夠使用索引訪問每個整數。“陣列！”馬上你就會想到。
我們想要的是一個包含 8 個整數的陣列，我們可以在迴圈外分配它；然後，在迴圈內，我們將呼叫 inBucket 並存儲結果
逐字
int numBuckets = 8; int[] buckets = new int [8]; double bucketWidth = 1.0 / numBuckets;
for (int i = 0; i<numBuckets; i++)
double low = i * bucketWidth;
double high = low + bucketWidth;
//System.out.println (low + " to " + high);
buckets[i] = inBucket (a, low, high);
逐字
這裡棘手的地方是我將迴圈變數用作 buckets 陣列的索引，以及用它來計算每個區間的範圍。
此程式碼有效。我將值的數量增加到 1000，並將範圍劃分為 8 個區間。輸出結果是
verbatim 129 109 142 118 131 124 121 126 verbatim
這非常接近每個區間內的 125。至少，它足夠接近，讓我相信隨機數生成器正在正常工作。
單遍解決方案
[edit | edit source]雖然此程式碼有效，但它並非儘可能高效。每次呼叫 inBucket 時，它都會遍歷整個陣列。隨著區間數量的增加，遍歷次數會很多。
更好的做法是單遍遍歷陣列，對於每個值，計算它落在哪個區間內。然後我們可以增加相應的計數器。
在上一部分中，我們獲取了一個索引 i，並將其乘以 bucketWidth 以找到給定區間的下限。現在我們想要獲取一個範圍在 0.0 到 1.0 之內的值，並找到它所落在的區間的索引。
由於這個問題是上一個問題的逆問題，我們可能會猜到我們應該除以 bucketwidth 而不是乘以它。這個猜想是正確的。
請記住，由於 bucketWidth = 1.0 / numBuckets，因此除以 bucketWidth 等同於乘以 numBuckets。如果我們取一個範圍在 0.0 到 1.0 之內的數字，並將其乘以 numBuckets，我們得到一個範圍在 0.0 到 numBuckets 之內的數字。如果我們將該數字四捨五入到下一個較小的整數，我們恰好得到我們想要的東西 - 對應區間的索引。
逐字
int numBuckets = 8; int[] buckets = new int [8];
for (int i = 0; i < numValues; i++)
int index = (int) (a[i] * numBuckets);
buckets[index]++;
逐字
這裡我使用型別轉換將值向下舍入到下一個整數，並同時將其轉換為 int 型別。
這種計算有可能產生超出範圍（負數或大於 a.length-1）的索引嗎？如果有，你會如何修復它？
histogram
像 buckets 這樣的陣列，它包含每個範圍內的值數量的計數，被稱為直方圖。作為練習，編寫一個名為 histogram 的方法，該方法接受一個數組和區間數量作為引數，並返回具有給定區間數量的直方圖。
詞彙表
[edit | edit source]描述
[陣列：] 一個命名的值集合，其中所有值具有相同的型別，並且每個值都由一個索引標識。
[集合：] 任何包含一組項或元素的資料結構。
[元素：] 陣列中的一個值。[] 運算子選擇陣列的元素。
[索引：] 用於指示陣列元素的整數變數或值。
[確定性：] 一個每次呼叫時執行相同操作的程式。
[偽隨機：] 一系列看似隨機的數字，但實際上是確定性計算的產物。
[直方圖：] 一個整數陣列，其中每個整數都計算落在特定範圍內的值數量。
array collection element index deterministic pseudorandom
描述