第五章 雙鏈表
譯者:飛龍
協(xié)議:CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
本章回顧了上一個練習的結(jié)果,并介紹了List
接口的另一個實現(xiàn)乘凸,即雙鏈表何暇。
5.1 性能分析結(jié)果
在之前的練習中,我們使用了Profiler.java
浦译,運行ArrayList
和LinkedList
的各種操作,它們具有一系列的問題規(guī)模溯职。我們將運行時間與問題規(guī)模繪制在重對數(shù)比例尺上精盅,并估計所得曲線的斜率,它表示運行時間和問題規(guī)模之間的關系的主要指數(shù)谜酒。
例如叹俏,當我們使用add
方法將元素添加到ArrayList
的末尾,我們發(fā)現(xiàn)僻族,執(zhí)行n
次添加的總時間正比于n
粘驰。也就是說,估計的斜率接近1
述么。我們得出結(jié)論蝌数,執(zhí)行n
次添加是 O(n)
的,所以平均來說度秘,單個添加的時間是常數(shù)時間顶伞,或者O(1)
,基于算法分析,這是我們的預期唆貌。
這個練習要求你填充profileArrayListAddBeginning
的主體滑潘,它測試了,在ArrayList
頭部添加一個新的元素的性能锨咙。根據(jù)我們的分析语卤,我們預計每個添加都是線性的,因為它必須將其他元素向右移動酪刀;所以我們預計粹舵,n
次添加是平方復雜度。
這是一個解決方案蓖宦,你可以在倉庫的solution
目錄中找到它齐婴。
public static void profileArrayListAddBeginning() {
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(0, "a string");
}
}
};
int startN = 4000;
int endMillis = 10000;
runProfiler("ArrayList add beginning", timeable, startN, endMillis);
}
這個方法幾乎和profileArrayListAddEnd
相同。唯一的區(qū)別在于timeMe
稠茂,它使用add
的雙參數(shù)版本柠偶,將新元素置于下標0
處。同樣睬关,我們增加了endMillis
诱担,來獲取一個額外的數(shù)據(jù)點。
以下是時間結(jié)果(左側(cè)是問題規(guī)模电爹,右側(cè)是運行時間蔫仙,單位為毫秒):
4000, 14
8000, 35
16000, 150
32000, 604
64000, 2518
128000, 11555
圖 5.1 展示了運行時間和問題規(guī)模的圖形。
圖 5.1:分析結(jié)果:在ArrayList
開頭添加n
個元素的運行時間和問題規(guī)模
請記住丐箩,該圖上的直線并不意味著該算法是線性的摇邦。相反,如果對于任何指數(shù)k
屎勘,運行時間與n ** k
成正比施籍,我們預計會看到斜率為k
的直線。在這種情況下概漱,我們預計丑慎,n
次添加的總時間與n ** 2
成正比,所以我們預計會有一條斜率為2
的直線瓤摧。實際上竿裂,估計的斜率是1.992
,非常接近照弥∧逡欤恐怕假數(shù)據(jù)才能做得這么好。
5.2 分析LinkedList
方法的性能
在以前的練習中这揣,你還分析了悔常,在LinkedList
頭部添加新元素的性能敢会。根據(jù)我們的分析,我們預計每個add
都要花時間这嚣,因為在一個鏈表中,我們不必轉(zhuǎn)移現(xiàn)有元素塞俱;我們可以在頭部添加一個新節(jié)點姐帚。所以我們預計n
次添加的總時間是線性的。
這是一個解決方案:
public static void profileLinkedListAddBeginning() {
Timeable timeable = new Timeable() {
List<String> list;
public void setup(int n) {
list = new LinkedList<String>();
}
public void timeMe(int n) {
for (int i=0; i<n; i++) {
list.add(0, "a string");
}
}
};
int startN = 128000;
int endMillis = 2000;
runProfiler("LinkedList add beginning", timeable, startN, endMillis);
}
我們只做了一些修改障涯,將ArrayList
替換為LinkedList
并調(diào)整startN
和endMillis
罐旗,來獲得良好的數(shù)據(jù)范圍。測量結(jié)果比上一批數(shù)據(jù)更加嘈雜唯蝶;結(jié)果如下:
128000, 16
256000, 19
512000, 28
1024000, 77
2048000, 330
4096000, 892
8192000, 1047
16384000, 4755
圖 5.2 展示了這些結(jié)果的圖形九秀。
圖 5.2:分析結(jié)果:在LinkedList
開頭添加n
個元素的運行時間和問題規(guī)模
并不是一條很直的線,斜率也不是正好是1
粘我,最小二乘擬合的斜率是1.23
鼓蜒。但是結(jié)果表示,n
次添加的總時間至少近似于O(n)
征字,所以每次添加都是常數(shù)時間都弹。
5.3 LinkedList
的尾部添加
在開頭添加元素是一種操作,我們期望LinkedList
的速度快于ArrayList
匙姜。但是為了在末尾添加元素畅厢,我們預計LinkedList
會變慢。在我的實現(xiàn)中氮昧,我們必須遍歷整個列表來添加一個元素到最后框杜,它是線性的。所以我們預計n
次添加的總時間是二次的袖肥。
但是不是這樣咪辱。以下是代碼:
public static void profileLinkedListAddEnd() {
Timeable timeable = new Timeable() {
List<String> list;
public void setup(int n) {
list = new LinkedList<String>();
}
public void timeMe(int n) {
for (int i=0; i<n; i++) {
list.add("a string");
}
}
};
int startN = 64000;
int endMillis = 1000;
runProfiler("LinkedList add end", timeable, startN, endMillis);
}
這里是結(jié)果:
64000, 9
128000, 9
256000, 21
512000, 24
1024000, 78
2048000, 235
4096000, 851
8192000, 950
16384000, 6160
圖 5.3 展示了這些結(jié)果的圖形。
圖 5.2:分析結(jié)果:在LinkedList
末尾添加n
個元素的運行時間和問題規(guī)模
同樣昭伸,測量值很嘈雜梧乘,線不完全是直的,但估計的斜率為1.19
庐杨,接近于在頭部添加元素选调,而并不非常接近2
,這是我們根據(jù)分析的預期灵份。事實上仁堪,它接近1
,這表明在尾部添加元素是常數(shù)元素填渠。這是怎么回事弦聂?
5.4 雙鏈表
我的鏈表實現(xiàn)MyLinkedList
鸟辅,使用單鏈表;也就是說莺葫,每個元素都包含下一個元素的鏈接匪凉,并且MyArrayList
對象本身具有第一個節(jié)點的鏈接。
但是捺檬,如果你閱讀LinkedList
的文檔再层,網(wǎng)址為 http://thinkdast.com/linked,它說:
List
和Deque
接口的雙鏈表實現(xiàn)堡纬。[...] 所有的操作都能像雙向列表那樣執(zhí)行聂受。索引該列表中的操作將從頭或者尾遍歷列表,使用更接近指定索引的那個烤镐。
如果你不熟悉雙鏈表蛋济,你可以在 http://thinkdast.com/doublelist 上閱讀更多相關信息,但簡稱為:
- 每個節(jié)點包含下一個節(jié)點的鏈接和上一個節(jié)點的鏈接炮叶。
-
LinkedList
對象包含指向列表的第一個和最后一個元素的鏈接碗旅。
所以我們可以從列表的任意一端開始,并以任意方向遍歷它悴灵。因此扛芽,我們可以在常數(shù)時間內(nèi),在列表的頭部和末尾添加和刪除元素积瞒!
下表總結(jié)了ArrayList
川尖,MyLinkedList
(單鏈表)和LinkedList
(雙鏈表)的預期性能:
MyArrayList |
MyLinkedList |
LinkedList |
|
---|---|---|---|
add (尾部) |
1 | n | 1 |
add (頭部) |
n | 1 | 1 |
add (一般) |
n | n | n |
get /set
|
1 | n | n |
indexOf / lastIndexOf
|
n | n | n |
isEmpty /size
|
1 | 1 | 1 |
remove (尾部) |
1 | n | 1 |
remove (頭部) |
n | 1 | 1 |
remove (一般) |
n | n | n |
5.5 結(jié)構的選擇
對于頭部插入和刪除,雙鏈表的實現(xiàn)優(yōu)于ArrayList
茫孔。對于尾部插入和刪除叮喳,都是一樣好。所以缰贝,ArrayList
唯一優(yōu)勢是get
和set
馍悟,鏈表中它需要線性時間,即使是雙鏈表剩晴。
如果你知道锣咒,你的應用程序的運行時間取決于get
和set
元素的所需時間,則ArrayList
可能是更好的選擇赞弥。如果運行時間取決于在開頭或者末尾附加添加和刪除元素毅整,LinkedList
可能會更好。
但請記住绽左,這些建議是基于大型問題的增長級別悼嫉。還有其他因素要考慮:
- 如果這些操作不占用你應用的大部分運行時間 - 也就是說,如果你的應用程序花費大部分時間來執(zhí)行其他操作 - 那么你對
List
實現(xiàn)的選擇并不重要拼窥。 - 如果你正在處理的列表不是很大戏蔑,你可能無法獲得期望的性能蹋凝。對于小型問題,二次算法可能比線性算法更快总棵,或者線性可能比常數(shù)時間更快鳍寂。而對于小型問題,差異可能并不重要情龄。
- 另外伐割,別忘了空間。到目前為止刃唤,我們專注于運行時間,但不同的實現(xiàn)需要不同的空間白群。在
ArrayList
中尚胞,這些元素并排存儲在單個內(nèi)存塊中,所以浪費的空間很少帜慢,并且計算機硬件通常在連續(xù)的塊上更快笼裳。在鏈表中,每個元素需要一個節(jié)點粱玲,帶有一個或兩個鏈接躬柬。鏈接占用空間(有時甚至超過數(shù)據(jù)!)抽减,并且節(jié)點分散在內(nèi)存中允青,硬件效率可能不高。
總而言之卵沉,算法分析為數(shù)據(jù)結(jié)構的選擇提供了一些指南颠锉,但只有:
- 你的應用的運行時間很重要,
- 你的應用的運行時間取決于你選擇的數(shù)據(jù)結(jié)構史汗,以及琼掠,
- 問題的規(guī)模足夠大,增長級別實際上預測了哪個數(shù)據(jù)結(jié)構更好停撞。
作為一名軟件工程師瓷蛙,在較長的職業(yè)生涯中,你幾乎不必考慮這種情況戈毒。