同一份邏輯，不同人的實(shí)現(xiàn)的代碼性能會出現(xiàn)數(shù)量級的差異； 同一份代碼，你可能微調(diào)幾個(gè)字符或者某行代碼的順序，就會有數(shù)倍的性能提升；同一份代碼，也可能在不同處理器上運(yùn)行也會有幾倍的性能差異；十倍程序員不是只存在于傳說中，可能在我們的周圍也比比皆是。十倍體現(xiàn)在程序員的方法面面，而代碼性能卻是其中最直觀的一面。
“如何寫出高性能代碼”系列源自我在組內(nèi)做的一次分享，本系列將以我個(gè)人之前的經(jīng)驗(yàn)為基礎(chǔ)，嘗試幫助大家寫出更高性能的代碼 。原ppt分享的面有寬也比較淺薄，所以這里將原ppt拆分成5個(gè)獨(dú)立的部分，分別成文，也作為對原ppt的擴(kuò)展和補(bǔ)充，本文是第一篇——善用算法和數(shù)據(jù)結(jié)構(gòu)。
荀子-勸學(xué)中說道：君子生非異也，善假于物也。其大意是君子的資質(zhì)跟一般人沒什么不同，只是善于借助外物罷了。 對于程序猿而已，我們在日常編碼過程中，可能最常用的就是數(shù)據(jù)結(jié)構(gòu)。現(xiàn)代各語言的開發(fā)庫里基本上都封裝好了各類的數(shù)據(jù)結(jié)構(gòu)，我們基本不需要自己去實(shí)現(xiàn)。但錯(cuò)誤地使用數(shù)據(jù)結(jié)構(gòu)可能導(dǎo)致代碼性能出現(xiàn)大幅的下降。
這里我舉三個(gè)Java中因未考慮到底層實(shí)現(xiàn)導(dǎo)致性能損耗的示例。
上面這段代碼本身功能上沒有任何問題，但Java中ArrayList在添加過程中在容量不足時(shí)會觸發(fā)擴(kuò)容，擴(kuò)容的過程會額外消耗CPU資源。但我在上述代碼中指定了ArrayList的初始化容量為100后，用JMH壓測發(fā)現(xiàn)有了33%的性能提升。
在Java中，很多容器都有動(dòng)態(tài)擴(kuò)容的特性，而擴(kuò)容的過程涉及到內(nèi)存的拷貝，很消耗性能。 所以建議如果能預(yù)知到數(shù)據(jù)量大小，在容器初始化的時(shí)候給定一個(gè)初始容量。這點(diǎn)在現(xiàn)在很多公司的編碼規(guī)范中也明確提出了，如下圖來自阿里巴巴Java開發(fā)手冊。
再來看一個(gè)錯(cuò)誤使用LinkedList導(dǎo)致的性能問題。
// jdk LinkedList中的get(int index）
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
// 這里會從前到后遍歷鏈表
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
LinkedList并不受動(dòng)態(tài)擴(kuò)容的影響，但是它的底層實(shí)現(xiàn)是用的鏈表，而鏈表最大的問題在于不支持隨機(jī)遍歷，所以LinkedList中g(shù)et(int index)的底層實(shí)現(xiàn)是用了遍歷，時(shí)間復(fù)雜度是O(n)，而ArrayList的底層實(shí)現(xiàn)是數(shù)組，它的get時(shí)間復(fù)雜度是O(1)。在上述代碼中我將LinkedList改成ArrayList后壓測確實(shí)也得到了十倍以上的性能提升。
在Java中，Set和List都提供了contains()方法，其作用就是校驗(yàn)?zāi)硞€(gè)在是否存在于這個(gè)集合中，但其contains實(shí)現(xiàn)方法完全不一樣。在HashSet中，contains直接是從hash表中查找，其時(shí)間復(fù)雜度只有O(1)。而在ArrayList和LinkedList中，都是需要遍歷一次全量數(shù)據(jù)才能得出結(jié)果，時(shí)間復(fù)雜度是O(n)，代碼這里就不再贅述，具體可以自行查閱。
在我實(shí)際測試是，Set和List的contains性能差異確實(shí)也非常明顯。我用JMH測試發(fā)現(xiàn)，當(dāng)有100個(gè)元素時(shí)，HashSet.contains的性能是ArrayList的10倍，是LinkedList的20倍，當(dāng)數(shù)據(jù)量更大時(shí)，這個(gè)差異會更明顯。
以上3個(gè)錯(cuò)誤的示例其實(shí)在我們?nèi)粘４a中經(jīng)常會遇到，或許你現(xiàn)在去翻閱下項(xiàng)目代碼，很容易就能找到List和Set使用不當(dāng)之處。 也許你會反駁，JDK中這些Api的性能都極高，而且這部分也只是業(yè)務(wù)邏輯中非常非常小的一部分，錯(cuò)誤得使用可能只會導(dǎo)致整體百分之一甚至千分之一的差異，但是不積跬步無以至千里，不積小流無以成江河。
下圖是各種常用數(shù)據(jù)結(jié)構(gòu)各種操作的時(shí)間、空間復(fù)雜度供大家查閱：
算法和數(shù)據(jù)結(jié)構(gòu)是一個(gè)程序員的根基，雖然日常我們很少自己去實(shí)現(xiàn)某種具體的算法或數(shù)據(jù)結(jié)構(gòu)，但我們卻無時(shí)無刻不在使用各種已被封裝好的算法或數(shù)據(jù)結(jié)構(gòu)，我們應(yīng)當(dāng)做到對各種算法和數(shù)據(jù)結(jié)構(gòu)爛熟于心，包括其時(shí)間復(fù)雜度、空間復(fù)雜度、適用范圍。
