java.util.RandomAccess
用法
Random Access List(隨機(jī)訪問(wèn)列表)如 ArrayList 要實(shí)現(xiàn)此接口，Sequence Access List(順序訪問(wèn)列表)如 LinkedList 不要實(shí)現(xiàn)削彬。
因?yàn)閮烧叩母咝П闅v算法不同
通常做法，遍歷前先判斷：
if (list instance of RandomAccess) {
for(int m = 0; m < list.size(); m++){}
}else{
Iterator iter = list.iterator();
while(iter.hasNext()){}
}
隨機(jī)訪問(wèn)列表使用循環(huán)遍歷里覆，順序訪問(wèn)列表使用迭代器遍歷二汛。
JDK 定義
List 實(shí)現(xiàn)使用的標(biāo)記接口祖凫，用來(lái)表明支持快速(通常是固定時(shí)間)隨機(jī)訪問(wèn)。這個(gè)接口的主要目的是允許一般的算法更改它們的行為酸些，從而在隨機(jī)或連續(xù)訪問(wèn)列表時(shí)提供更好的性能取募。
將操作隨機(jī)訪問(wèn)列表(比如 ArrayList)的最好的算法應(yīng)用到順序訪問(wèn)列表(比如 LinkedList)時(shí)琐谤，會(huì)產(chǎn)生二次項(xiàng)行為。鼓勵(lì)一般的列表算法檢查給定的列表是否 instanceof 這個(gè)接口玩敏，防止在順序訪問(wèn)列表時(shí)使用較差的算法斗忌，如果需要保證可接受的性能時(shí)可以更改算法。
公認(rèn)的是隨機(jī)和順序訪問(wèn)的區(qū)別通常是模糊的旺聚。例如织阳，當(dāng)一些 List 實(shí)現(xiàn)很大時(shí)會(huì)提供漸進(jìn)的線性訪問(wèn)時(shí)間，但實(shí)際是固定的訪問(wèn)時(shí)間翻屈。這樣的 List 實(shí)現(xiàn)通常應(yīng)該實(shí)現(xiàn)此接口陈哑。通常來(lái)說(shuō)，一個(gè) List 的實(shí)現(xiàn)類(lèi)應(yīng)該實(shí)現(xiàn)這個(gè)接口如果
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
比
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
快
驗(yàn)證事例
package com.ld.practice.arraylist;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.RandomAccess;
/**
* 測(cè)試Random Access List(隨機(jī)訪問(wèn)列表)如 ArrayList 和 Sequence Access List(順序訪問(wèn)列表)如 LinkedList </br>
* 不同遍歷算法的效率</br>
* 結(jié)論：前者用循環(huán)伸眶，后者用迭代器
*/
@SuppressWarnings({"rawtypes", "unchecked"})
public class ListLoopTest {
/**
* 初始化 list，添加n個(gè)元素
*
* @param list
* @return
*/
public static <T> List initList(List list, int n) {
for (int i = 0; i < n; i++)
list.add(i);
return list;
}
/**
* 遍歷 list刽宪，判斷是否實(shí)現(xiàn) RandomAccess 接口來(lái)使用不同的遍歷方法
*
* @param list
*/
public static void accessList(List list) {
long startTime = System.currentTimeMillis();
if (list instanceof RandomAccess) {
System.out.println("實(shí)現(xiàn)了 RandomAccess 接口...");
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
} else {
System.out.println("沒(méi)實(shí)現(xiàn) RandomAccess 接口...");
for (Iterator iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
}
long endTime = System.currentTimeMillis();
System.out.println("遍歷時(shí)間：" + (endTime - startTime));
}
/**
* loop 遍歷 list
*/
public static void accessListByLoop(List list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("loop遍歷時(shí)間：" + (endTime - startTime));
}
/**
* 迭代器遍歷
*/
public static void accessListByIterator(List list) {
long startTime = System.currentTimeMillis();
for (Iterator iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
long endTime = System.currentTimeMillis();
System.out.println("Iterator遍歷時(shí)間：" + (endTime - startTime));
}
public static void main(String[] args) {
ArrayList<Integer> aList = (ArrayList<Integer>) initList(new ArrayList<>(), 2000000);
LinkedList<Integer> lList = (LinkedList<Integer>) initList(new LinkedList<>(), 50000);
accessList(aList);
accessList(lList);
System.out.println("ArrayList");
accessListByLoop(aList);
accessListByIterator(aList);
System.out.println("LinkedList");
accessListByLoop(lList);
accessListByIterator(lList);
}
}
實(shí)現(xiàn)了 RandomAccess 接口...
遍歷時(shí)間：8
沒(méi)實(shí)現(xiàn) RandomAccess 接口...
遍歷時(shí)間：2
ArrayList
loop遍歷時(shí)間：5
Iterator遍歷時(shí)間：8
LinkedList
loop遍歷時(shí)間：1532
Iterator遍歷時(shí)間：1
