考鏈接:
http://www.trinea.cn/android/arraylist-linkedlist-loop-performance/
https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html#jls-14.14.2
foreach也稱為增強(qiáng)for循環(huán),是java5新特性,可用于遍歷數(shù)組或?qū)崿F(xiàn)了Iterable接口的集合容器。
假設(shè)已有數(shù)據(jù):
List<Integer> list;
(1) foreach循環(huán):
for (Integer j : list) {
// use j
}
(2) 下標(biāo)遞增(遞減)循環(huán):
int size=list.size();
for (int j=0; j < size; j++) {
list.get(j);
}
(3) 迭代器循環(huán)迭代:
for (Iterator<Integer> iterator=list.iterator(); iterator.hasNext();) {
iterator.next();
}
經(jīng)測(cè)試通過上述三種方式分別迭代ArrayList和LinkedList時(shí)所消耗的時(shí)間如下:
compare loop performance of ArrayList
-----------------------------------------------------------------------
list size | 10,000 | 100,000 | 1,000,000 | 10,000,000
-----------------------------------------------------------------------
for each | 1 ms | 3 ms | 14 ms | 152 ms
-----------------------------------------------------------------------
for iterator | 0 ms | 1 ms | 12 ms | 114 ms
-----------------------------------------------------------------------
for size=list.size() | 0 ms | 0 ms | 6 ms | 62 ms
-----------------------------------------------------------------------
compare loop performance of LinkedList
-----------------------------------------------------------------------
list size | 100 | 1,000 | 10,000 | 100,000
-----------------------------------------------------------------------
for each | 0 ms | 1 ms | 1 ms | 2 ms
-----------------------------------------------------------------------
for iterator | 0 ms | 0 ms | 0 ms | 2 ms
-----------------------------------------------------------------------
for size=list.size() | 0 ms | 0 ms | 67 ms | 8216 ms
ArrayList:
當(dāng)size < 100萬時(shí),三種方式性能差別不大;
當(dāng)size >=100萬時(shí),for > iterator >=foreach.
LinkedList:
當(dāng)size小于1萬時(shí),三種方式性能差別不大;
當(dāng)size>=1萬時(shí), iterator >=foreach > for.
由于foreach底層也是通過iterator來迭代,因此foreach的性能與iterator接近。
是什么影響了這三種遍歷方式的性能呢?
主要原因是List的底層數(shù)據(jù)結(jié)構(gòu)和從List容器中獲取元素的算法。
我們知道ArrayList的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組,LinkedList是鏈表。
這三種遍歷方式從List中獲取元素的算法分別為:
1) foreach循環(huán)和iterator迭代器:
都是調(diào)用iterator.next(),查看ArrayList對(duì)于iterator中next方法的實(shí)現(xiàn)可知其最終是通過數(shù)組下標(biāo)獲取元素。如下圖:
ArrayList迭代之next
查看LinkedList對(duì)于iterator中next方法的實(shí)現(xiàn)可知其最終是調(diào)用了父類AbstractList中iterator的實(shí)現(xiàn),然后調(diào)用了get(index),而LinkedList的get方法是通過遍歷鏈表來獲取元素的。如下圖:
2) for循環(huán):調(diào)用get(index).
綜上,這三種遍歷方式從容器中獲取元素的方式如下圖:
可見遍歷ArrayList時(shí)最終都是直接通過數(shù)組下標(biāo)定位元素的,這應(yīng)該是當(dāng)ArrayList的容量在100萬以內(nèi)時(shí),其遍歷時(shí)間在20ms以內(nèi)的根本原因。
遍歷LinkedList時(shí)最終都是查詢鏈表。但為什么iterator方式遍歷LinkedList的速度是for的數(shù)千倍呢?因?yàn)閕terator利用了游標(biāo),而后者是調(diào)用了get(index)方法將鏈表從頭到尾或從尾到頭查了一遍。
最后我們來看一下為什么諸如《Effective-Java》都推薦使用foreach:
1) 性能較優(yōu):
分析上文性能測(cè)試結(jié)果發(fā)現(xiàn),通過foreach遍歷ArrayList時(shí)當(dāng)size < 100萬時(shí),時(shí)間在20ms以內(nèi),并不比for循環(huán)差多少。遍歷size在百萬以上的超大ArrayList的時(shí)其性能明顯低于for循環(huán)遍歷方式。
通過foreach遍歷LinkedList時(shí),無論size大小,其性能始終接近于最優(yōu)的iterator遍歷方式。
2) 書寫簡(jiǎn)潔。
3) 不必關(guān)心元素下標(biāo),可避免數(shù)組下標(biāo)越界。
最后別忘了點(diǎn)波關(guān)注哦!
JavaScript作為Web前端開發(fā)的基石,其強(qiáng)大的功能和靈活性不僅體現(xiàn)在網(wǎng)頁的動(dòng)態(tài)交互上,更在于其處理數(shù)據(jù)的能力。數(shù)組遍歷是JavaScript中最常見的操作之一,尤其在算法題的求解過程中,它扮演著至關(guān)重要的角色。本文將深入探討JavaScript中數(shù)組遍歷的多種方法,通過具體的算法題示例,幫助讀者掌握高效解決問題的技巧。
在JavaScript中,數(shù)組遍歷可以通過多種方式進(jìn)行,每種方法都有其特點(diǎn)和適用場(chǎng)景:
const numbers=[1, 2, 3, 4, 5];
// 使用for循環(huán)遍歷
for (let i=0; i < numbers.length; i++) {
console.log(numbers[i]);
}
// 使用forEach遍歷
numbers.forEach(number=> console.log(number));
// 使用map創(chuàng)建新數(shù)組
const doubled=numbers.map(number=> number * 2);
console.log(doubled); // 輸出: [2, 4, 6, 8, 10]
數(shù)組遍歷方法本質(zhì)上是通過迭代數(shù)組中的每一個(gè)元素來執(zhí)行特定的邏輯操作。不同的方法提供不同的操作能力,如map用于變換,filter用于篩選,而reduce用于聚合。
假設(shè)我們有一道算法題,要求找出數(shù)組中所有偶數(shù),并返回它們的平方和。
function sumOfSquaresEvenNumbers(numbers) {
return numbers
.filter(number=> number % 2===0) // 篩選偶數(shù)
.map(number=> number * number) // 平方
.reduce((acc, curr)=> acc + curr, 0); // 求和
}
const result=sumOfSquaresEvenNumbers([1, 2, 3, 4, 5, 6]);
console.log(result); // 輸出: 56
function optimizedSumOfSquaresEvenNumbers(numbers) {
let sum=0;
for (let number of numbers) {
if (number % 2===0) {
sum +=number * number;
}
}
return sum;
}
const optimizedResult=optimizedSumOfSquaresEvenNumbers([1, 2, 3, 4, 5, 6]);
console.log(optimizedResult); // 輸出: 56
數(shù)組遍歷不僅是JavaScript編程的基礎(chǔ),也是解決復(fù)雜算法問題的利器。通過本文的探討,我們不僅學(xué)習(xí)了多種數(shù)組遍歷的方法,還掌握了如何在實(shí)際問題中選擇合適的遍歷策略,以提高代碼的效率和可讀性。未來,隨著JavaScript語言的不斷發(fā)展,新的數(shù)組方法和迭代器模式將進(jìn)一步豐富我們的編程工具箱,為開發(fā)者提供更加高效和靈活的解決方案。掌握數(shù)組遍歷的技巧,意味著在算法題的求解中擁有了更多的選擇和自信,這也是前端開發(fā)者邁向更高層次的關(guān)鍵一步。
*請(qǐng)認(rèn)真填寫需求信息,我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。