第三章 ArrayList
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
本章一舉兩得：我展示了上一個(gè)練習(xí)的解法，并展示了一種使用攤銷分析來劃分算法的方法。
3.1 劃分MyArrayList的方法
對于許多方法，我們不能通過測試代碼來確定增長級別。例如，這里是MyArrayList的get的實(shí)現(xiàn)：
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return array[index];
}
get中的每個(gè)東西都是常數(shù)時(shí)間的。所以get是常數(shù)時(shí)間，沒問題。
現(xiàn)在我們已經(jīng)劃分了get，我們可以使用它來劃分set。這是我們以前的練習(xí)中的set：
public E set(int index, E element) {
E old = get(index);
array[index] = element;
return old;
}
該解決方案的一個(gè)有些機(jī)智的部分是，它不會顯式檢查數(shù)組的邊界；它利用get，如果索引無效則引發(fā)異常。
set中的一切，包括get的調(diào)用都是常數(shù)時(shí)間，所以set也是常數(shù)時(shí)間。
接下來我們來看一些線性的方法。例如，以下是我的實(shí)現(xiàn)indexOf：
public int indexOf(Object target) {
for (int i = 0; i<size; i++) {
if (equals(target, array[i])) {
return i;
}
}
return -1;
}
每次在循環(huán)中，indexOf調(diào)用equals，所以我們首先要?jiǎng)澐?code>equals。這里就是：
private boolean equals(Object target, Object element) {
if (target == null) {
return element == null;
} else {
return target.equals(element);
}
}
此方法調(diào)用target.equals；這個(gè)方法的運(yùn)行時(shí)間可能取決于target或element的大小，但它不依賴于該數(shù)組的大小，所以出于分析indexOf的目的,我們認(rèn)為這是常數(shù)時(shí)間。
回到之前的indexOf，循環(huán)中的一切都是常數(shù)時(shí)間，所以我們必須考慮的下一個(gè)問題是：循環(huán)執(zhí)行多少次？
如果我們幸運(yùn)，我們可能會立即找到目標(biāo)對象，并在測試一個(gè)元素后返回。如果我們不幸，我們可能需要測試所有的元素。平均來說，我們預(yù)計(jì)測試一半的元素，所以這種方法被認(rèn)為是線性的（除了在不太可能的情況下，我們知道目標(biāo)元素在數(shù)組的開頭）。
remove的分析也類似。這里是我的時(shí)間。
public E remove(int index) {
E element = get(index);
for (int i=index; i<size-1; i++) {
array[i] = array[i+1];
}
size--;
return element;
}
它使用get，這是常數(shù)時(shí)間，然后從index開始遍歷數(shù)組。如果我們刪除列表末尾的元素，循環(huán)永遠(yuǎn)不會運(yùn)行，這個(gè)方法是常數(shù)時(shí)間。如果我們刪除第一個(gè)元素，我們遍歷所有剩下的元素，它們是線性的。因此，這種方法同樣被認(rèn)為是線性的（除了在特殊情況下，我們知道元素在末尾，或到末尾距離恒定）。
3.2 add的劃分
這里是add的一個(gè)版本，接受下標(biāo)和元素作為參數(shù)：
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// add the element to get the resizing
add(element);
// shift the other elements
for (int i=size-1; i>index; i--) {
array[i] = array[i-1];
}
// put the new one in the right place
array[index] = element;
}
這個(gè)雙參數(shù)的版本，叫做add(int, E)，它使用了單參數(shù)的版本，稱為add(E)，它將新的元素放在最后。然后它將其他元素向右移動，并將新元素放在正確的位置。
在我們可以劃分雙參數(shù)add之前，我們必須劃分單參數(shù)add：
public boolean add(E element) {
if (size >= array.length) {
// make a bigger array and copy over the elements
E[] bigger = (E[]) new Object[array.length * 2];
System.arraycopy(array, 0, bigger, 0, array.length);
array = bigger;
}
array[size] = element;
size++;
return true;
}
單參數(shù)版本很難分析。如果數(shù)組中存在未使用的空間，那么它是常數(shù)時(shí)間，但如果我們必須調(diào)整數(shù)組的大小，它是線性的，因?yàn)?code>System.arraycopy所需的時(shí)間與數(shù)組的大小成正比。
那么add是常數(shù)還是線性時(shí)間的？我們可以通過考慮一系列n個(gè)添加中，每次添加的平均操作次數(shù)，來分類此方法。為了簡單起見，假設(shè)我們以一個(gè)有2個(gè)元素的空間的數(shù)組開始。
- 我們第一次調(diào)用
add時(shí)，它會在數(shù)組中找到未使用的空間，所以它存儲1個(gè)元素。 - 第二次，它在數(shù)組中找到未使用的空間，所以它存儲
1個(gè)元素。 - 第三次，我們必須調(diào)整數(shù)組的大小，復(fù)制
2個(gè)元素，并存儲1個(gè)元素。現(xiàn)在數(shù)組的大小是4。 - 第四次存儲
1個(gè)元素。 - 第五次調(diào)整數(shù)組的大小，復(fù)制
4個(gè)元素，并存儲1個(gè)元素?，F(xiàn)在數(shù)組的大小是8。 - 接下來的
3個(gè)添加儲存3個(gè)元素。 - 下一個(gè)添加復(fù)制
8個(gè)并存儲1個(gè)?，F(xiàn)在的大小是16。 - 接下來的
7個(gè)添加復(fù)制了7個(gè)元素。
以此類推，總結(jié)一下：
-
4次添加之后，我們儲存了4個(gè)元素，并復(fù)制了兩個(gè)。 -
8次添加之后，我們儲存了8個(gè)元素，并復(fù)制了6個(gè)。 -
16次添加之后，我們儲存了16個(gè)元素，并復(fù)制了14個(gè)。
現(xiàn)在你應(yīng)該看到了規(guī)律：要執(zhí)行n次添加，我們必須存儲n個(gè)元素并復(fù)制n-2個(gè)。所以操作總數(shù)為n + n - 2，為2 * n - 2。
為了得到每個(gè)添加的平均操作次數(shù)，我們將總和除以n；結(jié)果是2 - 2 / n。隨著n變大，第二項(xiàng)2 / n變小。參考我們只關(guān)心n的最大指數(shù)的原則，我們可以認(rèn)為add是常數(shù)時(shí)間的。
有時(shí)線性的算法平均可能是常數(shù)時(shí)間，這似乎是奇怪的。關(guān)鍵是我們每次調(diào)整大小時(shí)都加倍了數(shù)組的長度。這限制了每個(gè)元素被復(fù)制的次數(shù)。否則 - 如果我們向數(shù)組的長度添加一個(gè)固定的數(shù)量，而不是乘以一個(gè)固定的數(shù)量 - 分析就不起作用。
這種劃分算法的方式，通過計(jì)算一系列調(diào)用中的平均時(shí)間，稱為攤銷分析。你可以在 http://thinkdast.com/amort 上閱讀更多信息。重要的想法是，復(fù)制數(shù)組的額外成本是通過一系列調(diào)用展開或“攤銷”的。
現(xiàn)在，如果add(E)是常數(shù)時(shí)間，那么add(int, E)呢？調(diào)用add(E)后，它遍歷數(shù)組的一部分并移動元素。這個(gè)循環(huán)是線性的，除了在列表末尾添加的特殊情況中。因此， add(int, E)是線性的。
3.3 問題規(guī)模
最后一個(gè)例子中，我們將考慮removeAll，這里是MyArrayList中的實(shí)現(xiàn)：
public boolean removeAll(Collection<?> collection) {
boolean flag = true;
for (Object obj: collection) {
flag &= remove(obj);
}
return flag;
}
每次循環(huán)中，removeAll都調(diào)用remove，這是線性的。所以認(rèn)為removeAll是二次的很誘人。但事實(shí)并非如此。
在這種方法中，循環(huán)對于每個(gè)collection中的元素運(yùn)行一次。如果collection包含m個(gè)元素，并且我們從包含n個(gè)元素的列表中刪除，則此方法是O(nm)的。如果collection的大小可以認(rèn)為是常數(shù)，removeAll相對于n是線性的。但是，如果集合的大小與n成正比，removeAll則是平方的。例如，如果collection總是包含100個(gè)或更少的元素， removeAll則是線性的。但是，如果collection通常包含的列表中的 1% 元素，removeAll則是平方的。
當(dāng)我們談?wù)搯栴}規(guī)模時(shí)，我們必須小心我們正在討論哪個(gè)大小。這個(gè)例子演示了算法分析的陷阱：對循環(huán)計(jì)數(shù)的誘人捷徑。如果有一個(gè)循環(huán)，算法往往是 線性的。如果有兩個(gè)循環(huán)（一個(gè)嵌套在另一個(gè)內(nèi)），則該算法通常是平方的。不過要小心！你必須考慮每個(gè)循環(huán)運(yùn)行多少次。如果所有循環(huán)的迭代次數(shù)與n成正比，你可以僅僅對循環(huán)進(jìn)行計(jì)數(shù)之后離開。但是，如在這個(gè)例子中，迭代次數(shù)并不總是與n成正比，所以你必須考慮更多。
3.4 鏈接數(shù)據(jù)結(jié)構(gòu)
對于下一個(gè)練習(xí)，我提供了List接口的部分實(shí)現(xiàn)，使用鏈表來存儲元素。如果你不熟悉鏈表，你可以閱讀 http://thinkdast.com/linkedlist ，但本部分會提供簡要介紹。
如果數(shù)據(jù)結(jié)構(gòu)由對象（通常稱為“節(jié)點(diǎn)”）組成，其中包含其他節(jié)點(diǎn)的引用，則它是“鏈接”的。在鏈表 中，每個(gè)節(jié)點(diǎn)包含列表中下一個(gè)節(jié)點(diǎn)的引用。其他鏈接結(jié)構(gòu)包括樹和圖，其中節(jié)點(diǎn)可以包含多個(gè)其他節(jié)點(diǎn)的引用。
這是一個(gè)簡單節(jié)點(diǎn)的類定義：
public class ListNode {
public Object data;
public ListNode next;
public ListNode() {
this.data = null;
this.next = null;
}
public ListNode(Object data) {
this.data = data;
this.next = null;
}
public ListNode(Object data, ListNode next) {
this.data = data;
this.next = next;
}
public String toString() {
return "ListNode(" + data.toString() + ")";
}
}
該ListNode對象具有兩個(gè)實(shí)例變量：data是某種類型的Object的引用，并且next是列表中下一個(gè)節(jié)點(diǎn)的引用。在列表中的最后一個(gè)節(jié)點(diǎn)中，按照慣例，next是null。
ListNode提供了幾個(gè)構(gòu)造函數(shù)，可以讓你為data和next提供值，或?qū)⑺鼈兂跏蓟癁槟J(rèn)值，null。
你可以將每個(gè)ListNode看作具有單個(gè)元素的列表，但更通常，列表可以包含任意數(shù)量的節(jié)點(diǎn)。有幾種方法可以制作新的列表。一個(gè)簡單的選項(xiàng)是，創(chuàng)建一組ListNode對象，如下所示：
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
之后將其鏈接到一起，像這樣：
node1.next = node2;
node2.next = node3;
node3.next = null;
或者，你可以創(chuàng)建一個(gè)節(jié)點(diǎn)并將其鏈接在一起。例如，如果要在列表開頭添加一個(gè)新節(jié)點(diǎn)，可以這樣做：
ListNode node0 = new ListNode(0, node1);
圖 3.1 鏈表的對象圖
圖 3.1 是一個(gè)對象圖，展示了這些變量及其引用的對象。在對象圖中，變量的名稱出現(xiàn)在框內(nèi)，箭頭顯示它們所引用的內(nèi)容。對象及其類型（如ListNode和Integer）出現(xiàn)在框外面。
3.5 練習(xí) 3
這本書的倉庫中，你會找到你需要用于這個(gè)練習(xí)的源代碼：
-
MyLinkedList.java包含List接口的部分實(shí)現(xiàn)，使用鏈表存儲元素。 -
MyLinkedListTest.java包含用于MyLinkedList的 JUnit 測試。
運(yùn)行ant MyArrayList來運(yùn)行MyArrayList.java，其中包含幾個(gè)簡單的測試。
然后可以運(yùn)行ant MyArrayListTest來運(yùn)行 JUnit 測試。其中幾個(gè)應(yīng)該失敗。如果你檢查源代碼，你會發(fā)現(xiàn)三條 TODO 注釋，表示你應(yīng)該填充的方法。
在開始之前，讓我們來看看一些代碼。以下是MyLinkedList的實(shí)例變量和構(gòu)造函數(shù)：
public class MyLinkedList<E> implements List<E> {
private int size; // keeps track of the number of elements
private Node head; // reference to the first node
public MyLinkedList() {
head = null;
size = 0;
}
}
如注釋所示，size跟蹤MyLinkedList有多少元素；head是列表中第一個(gè)Node的引用，或者如果列表為空則為null。
存儲元素?cái)?shù)量不是必需的，并且一般來說，保留冗余信息是有風(fēng)險(xiǎn)的，因?yàn)槿绻麤]有正確更新，就有機(jī)會產(chǎn)生錯(cuò)誤。它還需要一點(diǎn)點(diǎn)額外的空間。
但是如果我們顯式存儲size，我們可以實(shí)現(xiàn)常數(shù)時(shí)間的size方法；否則，我們必須遍歷列表并對元素進(jìn)行計(jì)數(shù)，這需要線性時(shí)間。
因?yàn)槲覀冿@式存儲size明確地存儲，每次添加或刪除一個(gè)元素時(shí)，我們都要更新它，這樣一來，這些方法就會減慢，但是它不會改變它們的增長級別，所以很值得。
構(gòu)造函數(shù)將head設(shè)為null，表示空列表，并將size設(shè)為0。
這個(gè)類使用類型參數(shù)E作為元素的類型。如果你不熟悉類型參數(shù)，可能需要閱讀本教程：http://thinkdast.com/types。
類型參數(shù)也出現(xiàn)在Node的定義中，嵌套在MyLinkedList里面：
private class Node {
public E data;
public Node next;
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
除了這個(gè)，Node類似于上面的ListNode。
最后，這是我的add的實(shí)現(xiàn)：
public boolean add(E element) {
if (head == null) {
head = new Node(element);
} else {
Node node = head;
// loop until the last node
for ( ; node.next != null; node = node.next) {}
node.next = new Node(element);
}
size++;
return true;
}
此示例演示了你需要的兩種解決方案：
對于許多方法，作為特殊情況，我們必須處理列表的第一個(gè)元素。在這個(gè)例子中，如果我們向列表添加列表第一個(gè)元素，我們必須修改head。否則，我們遍歷列表，找到末尾，并添加新節(jié)點(diǎn)。
此方法展示了，如何使用for循環(huán)遍歷列表中的節(jié)點(diǎn)。在你的解決方案中，你可能會在此循環(huán)中寫出幾個(gè)變體。注意，我們必須在循環(huán)之前聲明node，以便我們可以在循環(huán)之后訪問它。
現(xiàn)在輪到你了。填充indexOf的主體。像往常一樣，你應(yīng)該閱讀文檔，位于 http://thinkdast.com/listindof，所以你知道應(yīng)該做什么。特別要注意它應(yīng)該如何處理null。
與上一個(gè)練習(xí)一樣，我提供了一個(gè)輔助方法equals，它將數(shù)組中的一個(gè)元素與目標(biāo)值進(jìn)行比較，并檢查它們是否相等，并正確處理null。這個(gè)方法是私有的，因?yàn)樗谶@個(gè)類中使用，但它不是List接口的一部分。
完成后，再次運(yùn)行測試；testIndexOf，以及依賴于它的其他測試現(xiàn)在應(yīng)該通過。
接下來，你應(yīng)該填充雙參數(shù)版本的add，它使用索引并將新值存儲在給定索引處。再次閱讀 http://thinkdast.com/listadd 上的文檔，編寫一個(gè)實(shí)現(xiàn)，并運(yùn)行測試進(jìn)行確認(rèn)。
最后一個(gè)：填寫remove的主體。文檔在這里：http://thinkdast.com/listrem。當(dāng)你完成它時(shí)，所有的測試都應(yīng)該通過。
一旦你的實(shí)現(xiàn)能夠工作，將它與倉庫solution目錄中的版本比較。
3.6 垃圾回收的注解
在MyArrayList以前的練習(xí)中，如果需要，數(shù)字會增長，但它不會縮小。該數(shù)組從不收集垃圾，并且在列表本身被銷毀之前，元素不會收集垃圾。
鏈表實(shí)現(xiàn)的一個(gè)優(yōu)點(diǎn)是，當(dāng)元素被刪除時(shí)它會縮小，并且未使用的節(jié)點(diǎn)可以立即被垃圾回收。
這是我的實(shí)現(xiàn)的clear方法：
public void clear() {
head = null;
size = 0;
}
當(dāng)我們將head設(shè)為null時(shí)，我們刪除第一個(gè)Node的引用。如果沒有其他Node的引用（不應(yīng)該有），它將被垃圾收集。這個(gè)時(shí)候，第二個(gè)Node引用被刪除，所以它也被垃圾收集。此過程一直持續(xù)到所有節(jié)點(diǎn)都被收集。
那么我們應(yīng)該如何劃分clear？該方法本身包含兩個(gè)常數(shù)時(shí)間的操作，所以它看起來像是常數(shù)時(shí)間。但是當(dāng)你調(diào)用它時(shí)，你將使垃圾收集器做一些工作，它與元素?cái)?shù)成正比。所以也許我們應(yīng)該將其認(rèn)為是線性的！
這是一個(gè)有時(shí)被稱為性能 bug 的例子：一個(gè)程序做了正確的事情，在這種意義上它是正確的，但它不屬于我們預(yù)期的增長級別。在像 Java 這樣的語言中，它在背后做了大量工作的，例如垃圾收集，這種 bug 可能很難找到。
