Data Collections
AP Computer Science A Topic 4 13:32 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Take one photo on your phone.
用手机拍一张照片。
To the computer it is not a picture at all — it is a grid of numbers, one for every pixel, about twelve million of them.
对计算机来说，它根本不是一幅图像—— 而是一格一格的数字，每个像素一个，大约有一千二百万个。
Now try to store that with the tools we have used so far.
现在试着用我们目前学过的工具去存它。
One variable holds one value, so you would need twelve million names.
一个变量只装一个值， 那你就需要一千二百万个名字。
Nobody can write that.
没有人写得出来。
We need a different idea: one name that holds many values.
我们需要一个新想法：用一个名字装下许多值。
This is Unit Four: data collections.
这是第四单元：数据集合。
Arrays, ArrayLists and grids — how to hold many values under one name, how to walk through them, and the searching and sorting algorithms the exam will ask you to trace.
数组、动态数组和网格—— 怎样用一个名字装下许多值，怎样逐个遍历它们， 以及考试会要求你手动追踪的查找与排序算法。
Let's begin.
让我们开始吧。
Think of a filing cabinet.
想象一个文件柜。
One drawer holds many folders under one label.
一个抽屉在同一个标签下装着许多文件夹。
A data structure does the same job for a program: it organises a collection so you can store, find, and process items efficiently.
数据结构对程序做同样的事： 它组织一组数据，让你能高效地存放、查找和处理。
A single variable holds one value, but real problems need many related values — a class roster, every pixel, a run of sensor readings.
一个变量只装一个值， 但真实问题需要许多相关的值——一份班级名册、每一个像素、一串传感器读数。
This course uses three tools for that: the array, the ArrayList, and the two-dimensional array.
本课程为此提供三种工具：数组、动态数组，以及二维数组。
Everything that follows is how those three work.
后面讲的就是这三者怎么用。
First, a warning that carries marks.
首先是一个能拿分的提醒。
When the data is about people, collecting it is a choice with privacy consequences.
当数据关乎人的时候，收集它就是一个有后果的选择。
Take only what you actually need.
只拿你真正需要的。
Ask permission — that is consent.
征求许可——这就是同意。
Guard anything that identifies a person.
保护一切能识别个人身份的信息。
And watch for bias: if your data does not represent everyone fairly, your program will not treat everyone fairly either.
还要警惕偏见：如果你的数据没有公平地代表每一个人， 你的程序也不会公平地对待每一个人。
On this exam you argue that in words, not in code.
在这场考试里，你要用文字论证这一点，而不是写代码。
Behind racks like these sit names, addresses, and phone numbers — personally identifiable information, or P-I-I.
像这样的机柜后面，装着姓名、地址和电话——也就是能识别个人身份的信息。
Guard it.
要保护它。
A breach can expose home addresses and enable surveillance, so weigh both benefits and harms before you collect.
一次泄露可能暴露家庭住址，也可能助长监控，所以在收集之前要权衡好处与危害。
When you reuse code or data, respect intellectual property and licensing — you do not own every file you can download.
当你复用代码或数据时，要尊重知识产权和许可——你能下载的文件并不都归你所有。
On free-response ethics questions, name a concrete harm and give a specific reason.
在伦理类的自由作答题里，要说出一个具体危害，并给出具体理由。
A vague claim that something could be bad earns nothing.
只说「可能会不好」这种空话，一分也拿不到。
So, the first collection: the array.
那么，第一种集合：数组。
An array holds a fixed number of values, all of the same type, in order, under one name.
数组用一个名字，按顺序装下固定个数、类型相同的值。
You build one two ways: ask for a size, and every slot starts at zero; or list the values yourself.
建立数组有两种方式：给出一个大小，每个格子都从零开始；或者自己把值列出来。
To reach a single value, write the name and the position in square brackets.
要取出其中一个值，就写名字加上方括号里的位置。
Positions start at zero, so the last one is the length minus one.
位置从零开始， 所以最后一个是长度减一。
Go outside that, and the program crashes.
超出这个范围，程序就会崩溃。
To use a collection you traverse it — visit every element in turn. Two loops do this.
要使用一个集合，你就得遍历它——依次访问每一个元素。
The counting loop gives you the position, so you can change what is stored there.
有两种循环可以做到。 计数循环给你位置，所以你可以修改存在那里的值。
The enhanced for / for-each loop hands you each value directly. It is shorter and safer, but you cannot change the array through it.
增强 for 循环直接把每个值交给你，写起来更短也更安全，但你没法通过它修改数组。
Almost every array question is one of these loops carrying a running result: start a total at zero, then add, or compare, or count, one element at a time.
几乎每一道数组题都是这两种循环之一，加上一个不断更新的结果： 把总和从零开始，然后一个元素一个元素地累加、比较或计数。
Master a short list of patterns on a line of values like this.
在这样的一排数值上，要掌握一组短模式。
To sum, start a total at zero and add each element.
求和时，把总和从零开始，再逐个加上每个元素。
For the average, divide that total by the length — cast to double if you need a fraction.
求平均值时，用总和除以长度——如果需要小数，就转换成双精度类型。
To find the maximum, keep a best-so-far and replace it whenever you see something larger.
找最大值时，保留一个目前最好的，一旦看到更大的就替换。
Count by testing a condition and adding one.
计数时，先判断条件，再加一。
Duplicates need nested loops or a second pass.
查重复需要嵌套循环或再走一遍。
To reverse, swap the ends and walk inward.
反转时，两端对调并向中间走。
To shift, move each element one slot and leave a blank at the other end.
平移时，把每个元素移一格，另一端留下空位。
Every one is a traversal with a running result — the skill the multiple-choice questions keep reusing.
每一种都是带有不断更新结果的遍历——选择题反复考的就是这个本领。
Real data usually lives in a file.
真实的数据通常放在文件里。
To read one you need two things.
要读一个文件，你需要两样东西。
First, import the input-output library, because File lives there.
第一，导入输入输出库，因为 File 在那里面。
Second, warn Java that opening might fail — the file may not exist — by adding throws to the method header.
第二，提醒 Java 打开文件可能会失败——文件也许并不存在—— 办法是在方法头上加 throws。
Then a Scanner reads it, and you always test before you read: ask has-next-line before you take the next line.
然后用 Scanner 来读，而且读之前一定要先问： 先问还有没有下一行，再去取下一行。
Ask for a number when the next word is text, and the program throws an input mismatch.
如果下一个词是文字你却要一个数字， 程序就会抛出输入不匹配异常。
An array cannot grow.
数组不能变大。
Fix its size, and that is its size forever.
大小一旦定好，就永远是那么大。
An ArrayList stretches as you add and shrinks as you remove.
ArrayList 则是添加时伸长、删除时缩短。
But watch what is really inside: an ordinary array.
但看看它里面究竟是什么：一个普通数组。
When it fills, Java builds a bigger one and copies everything across.
当它装满时，Java 会造一个更大的，把所有东西复制过去。
An ArrayList stores objects, never plain numbers, so an int is wrapped as an Integer.
ArrayList 存的是对象，绝不是普通的数字，所以 int 会变成 Integer。
Java does that for you — autoboxing — and reading it back is unboxing.
Java 会替你完成这件事，这叫自动装箱。
The toolbox is small: add, get, set, remove, and size.
它的工具箱很小： add、get、set、remove 和 size。
Now two traps that cost marks every year.
下面是每年都在丢分的两个陷阱。
Size is a method, with brackets, while an array's length is a field, without them.
size 是方法，要带括号；而数组的 length 是字段，不带括号。
And removing inside a counting loop shifts everything after it to the left, so loop backwards or you will skip an element.
还有，在计数循环里删除元素，会让后面的一切向左移动， 所以要倒着循环，否则你会跳过一个元素。
One more trap that fails free-response code every year.
还有一个每年都让自由作答代码失分的陷阱。
Never remove inside a for-each loop on an ArrayList.
绝不要在动态数组的增强循环里删除。
Changing the size while that loop walks throws a Concurrent Modification Exception and the program dies.
当那种循环正在走时改变大小，会抛出并发修改异常，程序就崩溃。
The same algorithms as arrays still apply — max, min, count, sum — plus insertion and deletion that arrays cannot do easily.
数组上的算法在这里同样适用——最大、最小、计数、求和——再加上数组不好做的插入与删除。
A classic skill is to remove every match of a condition: loop the index backwards, call remove at the current spot, and keep going.
一项经典本领是删掉所有符合条件的元素：从后往前用下标循环， 在当前位置调用删除，然后继续。
Going forward without care skips the element that just slid into place.
若正向乱删，刚滑过来的那个元素就会被跳过。
Some data is a table, not a line: a seating plan, a chess board, an image.
有些数据是一张表，而不是一条线：座位表、棋盘、一幅图像。
For that we use a two-dimensional array — which is really an array of arrays.
对付这种数据，我们用二维数组——它其实就是数组的数组。
You give two sizes, rows first and then columns.
你要给两个大小，先行后列。
To reach one cell you give two positions, again row first, then column.
要取到某一个格子，也要给两个位置，同样先行后列。
The number of rows is the length of the whole thing, and the number of columns is the length of its first row.
行数就是整个数组的长度，列数就是它第一行的长度。
To visit every cell you need two loops, one inside the other.
要访问每一个格子，你需要两层循环，一层套在另一层里面。
The outer loop picks a row; the inner one runs along that row, column by column.
外层循环选一行，内层循环沿着这一行一列一列地走。
That order — all of row zero, then all of row one — is called row-major order, and it is the order the exam expects you to follow.
这个顺序——先走完第零行，再走完第一行——叫做行主序， 也正是考试要求你遵循的顺序。
On a grid like this, the same running-result idea returns with nested loops.
在这样的网格上，同样的「不断更新结果」思路会带着嵌套循环回来。
To sum one row, fix that row and walk its columns.
要求和某一行，就固定那一行，沿着列走。
To sum one column, fix the column and walk the rows.
要求和某一列，就固定那一列，沿着行走。
To find the maximum in the whole grid, keep a best-so-far and visit every cell.
要找整张网格的最大值，保留一个目前最好的，并访问每一个格子。
Count matching cells the same way.
统计符合条件的格子也一样。
A diagonal is special: the cells where the row index equals the column index.
对角线很特别：行下标等于列下标的那些格子。
Sum those, or walk the other diagonal with a matching formula.
把它们加起来，或者用对应公式走另一条对角线。
Each task is still a nested traversal carrying one running answer.
每一项任务仍然是带着一个不断更新答案的嵌套遍历。
First, the honest search.
先说最老实的查找。
Linear search checks each element in turn from the start, until it finds the target or runs out of values.
线性搜索从开头起依次检查每一个元素， 直到找到目标，或者把值都看完。
It works on any list — sorted or not.
它对任何列表都有效——有序的或无序的都行。
The cost is the problem: on a million items it can take a million comparisons.
代价是问题：在一百万个元素上，可能要做一百万次比较。
When the exam asks for a method that works even if the data is messy, this is the one you write.
当考试要求一个即使数据杂乱也能工作的方法时，你就写它。
That is one way to search.
那是查找的一种办法。
The other is far faster, and it buys that speed with a condition: the data must already be sorted.
另一种要快得多，而它用一个条件换来这份速度： 数据必须已经排好序。
Binary search looks at the middle value first.
二分搜索先看中间那个值。
If the target is smaller, the entire upper half disappears in one step — without spending a single comparison inside it.
如果目标更小，整个上半部分就在一步之内消失—— 而且不必在它里面花掉哪怕一次比较。
Then it repeats on what is left.
然后对剩下的部分重复。
Every step halves the range, so a million items are down to one in about twenty comparisons instead of a million.
每一步都把范围减半，所以一百万个元素大约二十次比较就见分晓，而不是一百万次。
This picture is the exam skill in one frame.
这张图把考试要点收进一帧。
Low and high mark the live range.
低界与高界标出还活着的范围。
Mid is their average, truncated.
中点是它们的平均值，再取整。
Compare the middle value to the target, then either return that index or throw away half the range.
把中间的值与目标比较， 然后要么返回那个下标，要么扔掉一半范围。
Binary search requires sorted data — if the list is not ordered, the discarded half might still hide the answer.
二分搜索要求数据已排序—— 如果列表没有顺序，被丢掉的那一半里可能还藏着答案。
The number of steps grows like log base two of n, so even a huge array needs only a few dozen comparisons.
步数大约按二的对数增长，所以即使数组很大，也只需几十次比较。
Let's trace one.
我们来追踪一次。
Search for forty in this sorted array of seven values.
在这个有七个值的有序数组里查找四十。
Low starts at zero and high at six, so the middle is three.
low 从零开始，high 是六，所以中间是三。
Twenty-three is smaller than forty, so low becomes four.
二十三比四十小，于是 low 变成四。
Now the middle is five.
现在中间是五。
Forty-two is bigger, so high becomes four.
四十二更大，于是 high 变成四。
The middle is four.
中间是四。
Thirty-one is smaller, so low becomes five.
三十一更小，于是 low 变成五。
Now low has passed high, the loop stops, and forty is not present — simply not there.
现在 low 越过了 high，循环结束， 四十根本不在里面。
Three comparisons — even to prove it is missing.
只用了三次比较——连不存在都证明出来了。
To put a small array in order, two simple methods — and this is the first of them.
要把一个小数组排好序，有两种简单的方法——这是其中的第一种。
Insertion sort grows a sorted front, sliding each new value back to where it belongs, which is exactly what you are watching now.
插入排序让前面的有序部分不断变长，把每个新值往回滑到它该在的位置， 你现在看到的正是它。
The other is selection sort, which repeatedly finds the smallest value left and swaps it into place.
另一种是选择排序， 它不断找出剩下的最小值，把它交换到位。
Both take about n squared steps, so doubling the data quadruples the work — which is why neither is used on large arrays, and why both are small enough to trace by hand.
两种都大约需要 n 的平方步，所以数据翻倍，工作量就变成四倍—— 这正是它们不用于大数组的原因，也正是两种都小到可以手工追踪的原因。
Here is insertion sort written pass by pass.
这里是一趟一趟写出的插入排序。
The left side is already sorted.
左边已经有序。
The next key slides left until every value behind it is smaller or equal.
下一个关键值向左滑，直到它后面的每个值都更小或相等。
That shifting is the heart of the algorithm — not a single swap like selection, but a walk back through the sorted front.
那种平移才是算法的核心——不是选择排序那样一次交换，而是沿着有序前端往回走。
On nearly ordered data it is quick; on reverse-ordered data it still does about n squared moves.
在接近有序的数据上它很快；在完全逆序的数据上，它仍大约要做平方级的移动。
When a question shows a half-sorted array, name which sort it is by how the front grows.
当题目给出一个半排好的数组时，就看前端怎样变长，来判断它是哪一种排序。
Selection sort is the other one.
选择排序就是另一种。
It finds the smallest remaining value in the unsorted tail and swaps it into the next front slot, again and again — one swap per pass, where insertion sort shifted a whole run.
它在还没排好的尾部找出剩下的最小值， 再把它交换到下一个前端位置，一遍又一遍——每趟只交换一次， 而插入排序要平移一整段。
After the first pass, the smallest value sits at index zero.
第一趟之后，最小值坐在下标零。
After the second pass, the two smallest values sit in order at the front.
第二趟之后，两个最小的值按顺序坐在最前面。
Write the whole array after each pass — that is what the free-response trace asks for.
每一趟之后都要把整个数组写出来——自由作答的追踪题要的就是这个。
It costs about n squared steps whatever the data looks like: unlike insertion sort, a nearly sorted array saves it nothing, because it still scans the entire tail to find each minimum.
不论数据长什么样，它都大约需要平方级的步数： 和插入排序不同，数组接近有序也省不了它一点力气， 因为它仍然要把整条尾部扫一遍才能找到每个最小值。
Some problems solve themselves.
有些问题会自己解决自己。
Recursion is a method that calls itself on a smaller input, and it needs exactly two parts: a base case that stops, and a recursive case that moves toward it.
递归就是一个方法在更小的输入上调用它自己， 它必须有两个部分：一个能停下来的基本情况，以及一个朝基本情况靠近的递归情况。
Forget the base case, and the calls never end — the stack fills and the program dies.
忘了基本情况，调用就永远停不下来——栈被填满，程序就崩溃。
And here is what students miss: recursion and iteration are interchangeable — loops can do exactly the same jobs.
下面是学生常常忽略的一点：递归和循环能做的事情完全一样。
This method and this loop return the same answer.
这个方法和这个循环返回同一个答案。
The choice is about clarity, not capability.
选哪个是清晰度的问题，不是能力的问题。
Write each call above the value it returns, and watch.
把每一次调用写在它返回值的上面，然后看。
Factorial of four cannot answer yet, so it calls three.
四的阶乘还答不上来，于是它调用三。
Three calls two. Two calls one — the base case — so it answers straight back.
三调用二，二调用一——这是基本情况—— 所以它直接给出答案。
Then the answers unwind outward: two times one is two, three times two is six, four times six is twenty-four.
接着答案一层层往外回： 二乘一是二，三乘二是六，四乘六是二十四。
Recursion also gives us a fast sort.
递归还给了我们一种快速排序方法。
Merge sort splits the array in half, sorts each half by calling itself, then merges the two sorted halves back into one.
归并排序把数组对半分开， 通过调用自己把每一半排好，再把两个有序的一半合并成一个。
That is about n log n work — on a thousand items, roughly a hundred times faster than the simple sorts.
这大约是 n 乘以 log n 的工作量——在一千个元素上， 比那些简单排序快大约一百倍。
This diagram is the whole algorithm.
这张图就是整个算法。
Split down until every piece is a single element — a single element is already sorted.
一直对半分，直到每一段只有一个元素——单个元素已经有序。
Then merge neighbouring sorted runs: always take the smaller of the two front values, and write it into a new list.
然后合并相邻的有序段：总是取两端前端中更小的那个，写进新列表。
The tree of splits costs log n levels, and each level does about n work, so the total is about n log n.
分裂的树大约有对数层，每一层大约做线性工作，所以总量大约是线性对数级。
Binary search can also be written recursively — search the correct half — but merge sort is the recursive algorithm the exam pairs with that n-log-n cost.
二分搜索也可以写成递归——在正确的那一半里继续找—— 但归并排序才是考试把它与线性对数代价放在一起的递归算法。
Three habits for this unit.
这一单元有三个习惯。
First, know which size word to use: length with no brackets for an array, size with brackets for an ArrayList, and an index out of bounds crash if you go past the end of either.
第一，知道该用哪个"大小"： 数组用 length，不带括号；ArrayList 用 size，要带括号； 任何一个越界，都会得到下标越界的崩溃。
Second, when you remove from an ArrayList inside a loop, go backwards.
第二，在循环里从 ArrayList 删除元素时，要倒着走。
Third, the ethics questions are written, not coded — name a real harm, like a data breach or bias from unrepresentative data, and give a specific reason.
第三，伦理题是要写文字的，不是写代码—— 说出一个真实的危害，比如数据泄露，或者因数据不具代表性而产生的偏见， 并给出具体的理由。
A vague answer earns nothing.
含糊的答案一分也拿不到。