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
描述