第四章 LinkedList

原文：Chapter 4 LinkedList

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

這一章展示了上一個練習的解法，并繼續(xù)討論算法分析豹悬。

4.1 MyLinkedList方法的劃分

我的indexOf實現(xiàn)在下面蒋情。在閱讀說明之前颖医，請閱讀它，看看你是否可以確定其增長級別原杂。

public int indexOf(Object target) {
    Node node = head;
    for (int i=0; i<size; i++) {
        if (equals(target, node.data)) {
            return i;
        }
        node = node.next;
    }
    return -1;
}

最初node為head的副本拾给，所以他們都指向相同的Node盒发。循環(huán)變量i從0計數(shù)到size-1。每次在循環(huán)中玛迄，我們都用equals來看看我們是否找到了目標由境。如果是這樣，我們立即返回i蓖议。否則我們移動到列表中的下一個Node虏杰。

通常我們會檢查以確保下一個Node不是null，但在這里勒虾，它是安全的纺阔，因為當我們到達列表的末尾時循環(huán)結束（假設與列表中size與實際節(jié)點數(shù)量一致）。

如果我們走完了循環(huán)而沒有找到目標修然，我們返回-1州弟。

那么這種方法的增長級別是什么钧栖？

• 每次在循環(huán)中，我們調(diào)用了equals婆翔，這是一個常數(shù)時間（它可能取決于target或data大小拯杠，但不取決于列表的大小）啃奴。循環(huán)中的其他操作也是常數(shù)時間潭陪。
• 循環(huán)可能運行n次，因為在更糟的情況下最蕾，我們可能必須遍歷整個列表依溯。

所以這個方法的運行時間與列表的長度成正比。

接下來瘟则，這里是我的雙參數(shù)add方法的實現(xiàn)黎炉。同樣，你應該嘗試對其進行劃分醋拧，然后再閱讀說明慷嗜。

public void add(int index, E element) {
    if (index == 0) {
        head = new Node(element, head);
    } else {
        Node node = getNode(index-1);
        node.next = new Node(element, node.next);
    }
    size++;
}

如果index==0，我們在開始添加新的Node丹壕，所以我們把它當作特殊情況庆械。否則，我們必須遍歷列表來查找index-1處的元素菌赖。我們使用輔助方法getNode：

private Node getNode(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    Node node = head;
    for (int i=0; i<index; i++) {
        node = node.next;
    }
    return node;
}

getNode檢查index是否超出范圍缭乘；如果是這樣，它會拋出異常琉用。否則堕绩，它遍歷列表并返回所請求的節(jié)點。

我們回到add邑时，一旦我們找到合適的Node奴紧，我創(chuàng)建新的Node，并把它插到node和node.next之間刁愿。你可能會發(fā)現(xiàn)绰寞，繪制此操作的圖表有助于確保你了解此操作。

那么铣口，add的增長級別什么呢滤钱？

• getNode類似indexOf，出于同樣的原因也是線性的脑题。
• 在add中件缸，getNode前后的一切都是常數(shù)時間。

所以放在一起叔遂，add是線性的他炊。

最后争剿，我們來看看remove：

public E remove(int index) {
    E element = get(index);
    if (index == 0) {
        head = head.next;
    } else {
        Node node = getNode(index-1);
        node.next = node.next.next;
    }
    size--;
    return element;
}

remove使用了get查找和存儲index處的元素。然后它刪除包含它的Node痊末。

如果index==0蚕苇，我們再次處理這個特殊情況。否則我們找到節(jié)點index-1并進行修改凿叠，來跳過node.next并直接鏈接到node.next.next涩笤。這有效地從列表中刪除node.next，它可以被垃圾回收盒件。

最后蹬碧，我們減少size并返回我們在開始時檢索的元素。

那么炒刁，remove的增長級別是什么呢恩沽？remove中的一切是常數(shù)時間，除了get和getNode翔始，它們是線性的罗心。因此，remove是線性的绽昏。

當人們看到兩個線性操作時协屡，他們有時會認為結果是平方的俏脊，但是只有一個操作嵌套在另一個操作中才適用全谤。如果你在一個操作之后調(diào)用另一個，運行時間會相加爷贫。如果它們都是O(n)的认然，則總和也是O(n)的。

4.2 MyArrayList和MyLinkedList的對比

下表總結了MyArrayList和MyLinkedList之間的差異漫萄，其中1表示O(1)或常數(shù)時間卷员，和n表示O(n)或線性。

• MyArrayList的優(yōu)勢操作是腾务，插入末尾毕骡，移除末尾，獲取和設置岩瘦。
• MyLinkedList的優(yōu)勢操作是未巫，插入開頭，以及移動開頭启昧。

對于其他操作叙凡，這兩個實現(xiàn)方式的增長級別相同。

哪個實現(xiàn)更好密末？這取決于你最有可能使用哪些操作握爷。這就是為什么 Java 提供了多個實現(xiàn)跛璧，因為它取決于你。

4.3 性能分析

對于下一個練習新啼，我提供了一個Profiler類追城，它包含代碼，使用一系列問題規(guī)模運行方法燥撞，測量運行時間和繪制結果漓柑。

你將使用Profiler，為 Java 的實現(xiàn)ArrayList和LinkedList叨吮，劃分add方法的性能辆布。

以下是一個示例，展示了如何使用分析器：

public static void profileArrayListAddEnd() {
    Timeable timeable = new Timeable() {
        List<String> list;

        public void setup(int n) {
            list = new ArrayList<String>();
        }

        public void timeMe(int n) {
            for (int i=0; i<n; i++) {
                list.add("a string");
            }
        }
    };

    String title = "ArrayList add end";
    Profiler profiler = new Profiler(title, timeable);

    int startN = 4000;
    int endMillis = 1000;
    XYSeries series = profiler.timingLoop(startN, endMillis);
    profiler.plotResults(series);
}

此方法測量在ArrayList上運行add所需的時間茶鉴，它向末尾添加新元素锋玲。我將解釋代碼，然后展示結果涵叮。

為了使用Profiler惭蹂，我們需要創(chuàng)建一個Timeable，它提供兩個方法：setup和timeMe割粮。setup方法執(zhí)行在啟動計時之前所需的任何工作盾碗；這里它會創(chuàng)建一個空列表。然后timeMe執(zhí)行我們試圖測量的任何操作舀瓢；這里它將n個元素添加到列表中廷雅。

創(chuàng)建timeable的代碼是一個匿名類，用于定義Timeable接口的新實現(xiàn)京髓，并同時創(chuàng)建新類的實例航缀。如果你不熟悉匿名類，你可以閱讀這里：http://thinkdast.com/anonclass堰怨。

但是下一次練習不需要太多的知識芥玉；即使你不喜歡匿名類，也可以復制和修改示例代碼备图。

下一步是創(chuàng)建Profiler對象灿巧，傳遞Timeable對象和標題作為參數(shù)。

Profiler提供了timingLoop揽涮，它使用存儲為實例變量的Timeable抠藕。它多次調(diào)用Timeable對象上的timeMe方法，使用一系列的n值绞吁。timingLoop接受兩個參數(shù)：

• startN是n的值幢痘，計時循環(huán)應該從它開始。
• endMillis是以毫秒為單位的閾值家破。隨著 timingLoop增加問題規(guī)模颜说，運行時間增加购岗；當運行時間超過此閾值時，timingLoop停止门粪。

當你運行實驗時喊积，你可能需要調(diào)整這些參數(shù)。如果startN太低玄妈，運行時間可能太短乾吻，無法準確測量。如果endMillis太低拟蜻，你可能無法獲得足夠的數(shù)據(jù)绎签，來查看問題規(guī)模和運行時間之間的明確關系。

這段代碼位于ProfileListAdd.java酝锅，你將在下一個練習中運行它诡必。當我運行它時，我得到這個輸出：

4000, 3
8000, 0
16000, 1
32000, 2
64000, 3
128000, 6
256000, 18
512000, 30
1024000, 88
2048000, 185
4096000, 242
8192000, 544
16384000, 1325

第一列是問題規(guī)模搔扁，n爸舒；第二列是以毫秒為單位的運行時間。前幾個測量非常嘈雜稿蹲；最好將startN設置在64000左右扭勉。

timingLoop的結果是包含此數(shù)據(jù)的XYSeries。如果你將這個序列傳給plotResults苛聘，它會產(chǎn)生一個如圖 4.1 所示的圖形涂炎。

圖 4.1 分析結果：將n個元素添加到ArrayList末尾的運行時間與問題規(guī)模。

下一節(jié)解釋了如何解釋它焰盗。

4.4 解釋結果

基于我們對ArrayList工作方式的理解璧尸，我們期望咒林，在添加元素到最后時熬拒，add方法需要常數(shù)時間。所以添加n個元素的總時間應該是線性的垫竞。

為了測試這個理論澎粟，我們可以繪制總運行時間和問題規(guī)模，我們應該看到一條直線欢瞪，至少對于大到足以準確測量的問題規(guī)模活烙。在數(shù)學上，我們可以為這條直線編寫一個函數(shù)：

runtime = a + b * n 

其中a是線的截距遣鼓，b是斜率啸盏。

另一方面，如果add是線性的骑祟，則n次添加的總時間將是平方回懦。如果我們繪制運行時間與問題規(guī)模气笙，我們預計會看到拋物線∏釉危或者在數(shù)學上潜圃，像：

runtime = a + b * n + c * n ** 2 

有了完美的數(shù)據(jù)，我們可能能夠分辨直線和拋物線之間的區(qū)別舟茶，但如果測量結果很嘈雜谭期，可能很難辨別。解釋嘈雜的測量值的更好方法是吧凉，在重對數(shù)刻度上繪制的運行時間和問題規(guī)模隧出。

為什么？我們假設運行時間與n ** k成正比阀捅，但是我們不知道指數(shù)k是什么鸳劳。我們可以將關系寫成這樣：

runtime = a + b * n + … + c * n ** k 

對于n的較大值，最大指數(shù)項是最重要的也搓，因此：

runtime ≈ c * n ** k 

其中≈意思是“大致相等”∩屠現(xiàn)在，如果我們對這個方程的兩邊取對數(shù)：

log(runtime) ≈ log(c) + k * log(n) 

這個方程式意味著傍妒，如果我們在重對數(shù)合度上繪制運行時間與n幔摸，我們預計看到一條直線，截距為log(c)颤练，斜率為k既忆。我們不太在意截距，但斜率表示增長級別：如果k = 1嗦玖，算法是線性的患雇；如果k = 2，則為平方的宇挫。

看上一節(jié)中的數(shù)字苛吱，你可以通過眼睛來估計斜率。但是當你調(diào)用plotResults它時器瘪，會計算數(shù)據(jù)的最小二乘擬合并打印估計的斜率翠储。在這個例子中：

Estimated slope = 1.06194352346708

它接近1；并且這表明n次添加的總時間是線性的橡疼，所以每個添加是常數(shù)時間援所，像預期的那樣。

其中重要的一點：如果你在圖形看到這樣的直線欣除，這并不意味著該算法是線性的住拭。如果對于任何指數(shù)k，運行時間與n ** k成正比，我們預計看到斜率為k的直線滔岳。如果斜率接近1瘟檩，則表明算法是線性的。如果接近2澈蟆，它可能是平方的墨辛。

4.5 練習 4

在本書的倉庫中，你將找到此練習所需的源文件：

• Profiler.java包含上述Profiler類的實現(xiàn)趴俘。你會使用這個類睹簇，但你不必知道它如何工作。但可以隨時閱讀源碼寥闪。
• ProfileListAdd.java包含此練習的起始代碼太惠，包括上面的示例，它測量了ArrayList.add疲憋。你將修改此文件來測量其他一些方法凿渊。

此外，在code目錄中缚柳，你將找到 Ant 構建文件build.xml埃脏。

運行ant ProfileListAdd來運行ProfileListAdd.java。你應該得到類似圖 4.1 的結果秋忙，但是你可能需要調(diào)整startN或endMillis彩掐。估計的斜率應該接近1，表明執(zhí)行n個添加操作的所需時間與n成正比灰追；也就是說堵幽，它是O(n)的。

在ProfileListAdd.java中弹澎，你會發(fā)現(xiàn)一個空的方法profileArrayListAddBeginning朴下。用測試ArrayList.add的代碼填充這個方法的主體，總是把新元素放在開頭苦蒿。如果你以profileArrayListAddEnd的副本開始殴胧，你只需要進行一些更改。在main中添加一行來調(diào)用這個方法刽肠。

再次運行ant ProfileListAdd并解釋結果溃肪。基于我們對ArrayList工作方式的理解音五，我們期望，每個添加操作是線性的羔沙，所以n次添加的總時間應該是平方的躺涝。如果是這樣，在重對數(shù)刻度中，直線的估計斜率應該接近2坚嗜。是嗎夯膀？

現(xiàn)在我們來將其與LinkedList比較。當我們把新元素放在開頭苍蔬，填充profileLinkedListAddBeginning并使用它劃分LinkedList.add诱建。你期望什么性能？結果是否符合你的期望碟绑？

最后俺猿，填充profileLinkedListAddEnd的主體，使用它來劃分LinkedList.add格仲。你期望什么性能押袍？結果是否符合你的期望？

我將在下一章中展示結果并回答這些問題凯肋。