数据集合

收集数据的程序提出隐私(privacy)和同意(consent)的问题。只收集需要的、保护它,并对它的使用诚实。数据能携带偏见(bias),若它不公平地代表每个人,导致不公平的结果——一个随着存储信息而来的责任。

一个单一的变量持有一个值;真实的问题需要存储许多相关的值——一个班级名册、像素、传感器读数。一个数据结构(data structure)组织一个搜集,以便我们能高效地存储、找到和处理项。AP 课程用三个:数组(array)、ArrayList,和 2D 数组。

一个数组(array)是一个固定大小的、有序的相同类型值的搜集。索引从 0 到 length - 1:

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

访问 0..length-1 之外的一个索引抛出一个 ArrayIndexOutOfBoundsException。

用一个 for 循环(给出索引)或一个增强 for / for-each(enhanced for / for-each)循环(给出每个值,只读)遍历(traverse)一个数组:

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

掌握这些模式:计算一个和或平均、找最大/最小、计数满足一个条件的项、检查一个重复,和反转或移位元素。每一个都是一个带连续结果的遍历:

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

File 和 IOException 在 java.io 里,所以一个读文件的程序需要 import java.io.*;。打开一个文件可能失败(它也许不存在),Java 强制你处理这一点——最简单的方式是在方法头上加 throws IOException。然后一个 Scanner 逐行读文件,用 hasNext... 在读之前测试:

import java.io.*;
...
public static void readFile() throws IOException {
    Scanner f = new Scanner(new File("data.txt"));
    while (f.hasNextLine()) {
        String line = f.nextLine();
    }
}

用 nextInt()、nextDouble() 或 nextBoolean() 读有类型的记号时,如果下一个记号是错误的类型,会抛出一个 InputMismatchException——例如当文件里下一个东西是单词 cat 时调用 nextInt()。

一个 ArrayList 存储对象,不是基本类型,所以一个基本类型被包装在一个对象里:Integer 包装 int,Double 包装 double。Java 用自动装箱(autoboxing)(int 到 Integer)和拆箱(unboxing)(再回去)自动做这个,所以你能写 list.add(5) 和 int x = list.get(0)。

一个 ArrayList(动态数组)在你添加或移除项时增长和收缩。用 <> 里的元素类型声明它:

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

用一个索引循环或一个 for-each 循环遍历,就像数组(用 size() 和 get(i)):

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

考试技能: 当在一个索引循环里移除项时,要么向后循环,要么在一次移除之后不递增 i ——否则移除会把元素向左移动而你跳过一个。而且绝不要在用一个 for-each 循环遍历一个 ArrayList 时添加或移除元素:在循环中途改变它的大小会抛出一个 ConcurrentModificationException,所以每当你必须移除时用一个索引循环(向后,如上)。

与数组相同的算法——最大/最小、计数、求和——加上数组不能轻易做的插入和删除。一个常见的任务是移除所有匹配一个条件的元素,小心地处理索引移位。

一个 2D 数组(2D array)是一个网格(行和列)——一个数组的数组:

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

用嵌套循环(nested loops)访问每个单元格——外层遍历行、内层遍历列(行主序(row-major order)):

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

典型的网格任务:求一行或一列的和、找网格里的最大值、计数匹配的单元格,或求一条对角线的和(r == c 的地方)。每一个都是一个带连续结果的嵌套遍历。

• 线性搜索(linear search)依次检查每个元素——在任何列表上起作用,取最多 $n$ 步。
• 二分搜索(binary search)只在一个排序的列表上起作用:检查中间、然后丢弃不能包含目标的那一半,重复。它取约 $\log_2 n$ 步——在大数据上快得多。

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

考试技能: 二分搜索需要排序的数据;知道它做多少次比较以及 lo、hi、mid 如何更新。

Worked example. 在排序的数组 {3, 9, 14, 23, 31, 42, 55}(索引 0–6)里搜索 target = 40。开始 lo=0, hi=6:

• mid = (0+6)/2 = 3,a[3]=23 < 40,所以 lo = 4;
• mid = (4+6)/2 = 5,a[5]=42 > 40,所以 hi = 4;
• mid = (4+4)/2 = 4,a[4]=31 < 40,所以 lo = 5;
• 现在 lo (5) > hi (4),所以循环结束——40 不存在。

每一步把范围减半,所以即使这次未命中也只取三次比较。

• 选择排序(selection sort)反复找到最小的剩余元素并把它交换到位。
• 插入排序(insertion sort)增长一个排序的前部,把每个新元素插入到它所属的地方。

两者都简单,平均取约 $n^2$ 步——对小数组还行。能够跟踪每一趟之后的数组。

递归(recursion)是一个在一个更小的输入上调用它自己的方法。它需要一个停止调用的基本情况(base case),和一个朝基本情况移动的递归情况(recursive case):

public static int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

没有一个可达的基本情况,递归从不停止(一个栈溢出)。

递归和迭代是可以互换的。任何递归解法都能用一个循环(迭代方式)改写,而任何循环也都能用递归改写 —— 它们解决的是同一类问题。上面的 factorial 与一个迭代版本效果完全相同:

public static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;   // same answer, no self-call
    return result;
}

所以这个选择关乎清晰度,而非能力:对于具有自相似结构的问题(树、归并排序),递归读起来很自然;而迭代则避免了每一步都压入一个调用帧的内存开销。考试可能会要求你把其中一种转换成另一种。

递归驱动高效的算法。二分搜索能被递归地写(搜索正确的那一半)。归并排序(merge sort)把数组分成一半、递归地排序每一半,然后归并两个排序的一半——取约 $n\log_2 n$ 步,在大数据上比选择或插入排序快得多。

Worked example. 跟踪 factorial(4)。每个调用推迟给一个更小的:factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1)。factorial(1) 命中基本情况并返回 1,所以调用向内展开:2 * 1 = 2,然后 3 * 2 = 6,然后 4 * 6 = 24。把每个调用写在它返回值的上方是跟踪递归的可靠方式。

考试技能: 通过写出每个调用和它的返回值来跟踪一个递归方法,并知道归并排序的效率($n\log n$)击败 $n^2$ 的简单排序。

• 权衡收集数据的好处和害处——这个单元通过简短的书面论证考查,不是代码。
• 保护个人身份信息(PII)(personally identifiable information)并在上下文里解释隐私和安全风险。
• 命名真实的害处:数据泄露、监视,和来自不具代表性数据的算法偏见。
• 当你重用代码或数据时尊重知识产权和许可。
• 给出一个具体的、有理由的答案——一个模糊的"它可能是坏的"不赢得分数。