Java JDK7源码-java.util.RandomAccess

源码

1
package java.util;
2
3
public interface RandomAccess {
4
}

综述

本接口是Java集合框架中的一员,是被List所使用的标记接口,实现该接口表明List支持快速(通常是指常数时间)随机访问。

本接口的主要目的为在随机或顺序访问list时允许通用算法修改其行为以提供更好的性能。

当把基于随机访问list(例如ArrayList)的最佳算法用于顺序访问list(例如LinkedList)时,算法在用时上会呈平方阶增长。因此在设计list访问的通用算法时,最好先看一下传入的list是否实现了本接口,若未实现本接口,则说明传入list天然不支持随机访问,在设计算法时必须特殊考虑以保证访问的性能在可接受的范围内。

随机访问与顺序访问的界限通常是模糊的。例如,一些List在长度巨大时的访问时间复杂度接近于线性阶,但是在实际使用中,长度一般时的时间复杂度为常数阶。这样的List通常也会实现本接口。

一般来说,当某个list执行循环1的效率高于循环2时,即认为应该实现本接口。

循环1:

1
for (int i=0, n=list.size(); i < n; i++)
2
    list.get(i);

循环2:

1
for (Iterator i=list.iterator(); i.hasNext(); )
2
    i.next();

换句话说,在欲迭代一个list之前,最好先判断其是否已实现了本接口。然后采取不同的调用方法:

1
if (list instance of RandomAccess) {
2
    for (int i = 0; i < list.size(); i++){
3
        // TODO
4
    }
5
} else {
6
    Iterator iterator = list.iterator();
7
    while (iterator.hasNext()) {
8
        // TODO
9
    }
10
}

以下类是对性能的测试:

1
import java.util.ArrayList;
2
import java.util.Iterator;
3
import java.util.LinkedList;
4
import java.util.List;
5
6
import org.junit.Test;
7
8
public class TestRandomAccess {
9
10
    private final static int LIST_SIZE = 1000;
11
12
    private final static int TEST_COUNT = 1000; 
13
14
    @Test
15
    public void testRandomAccess() {
16
      List<Integer> arraylist = new ArrayList<Integer>();
17
      for (int i = 0; i < TestRandomAccess.LIST_SIZE; i++)  arraylist.add(i);
18
      List<Integer> linkedList = new LinkedList<Integer>();
19
      for (int i = 0; i < TestRandomAccess.LIST_SIZE; i++)  linkedList.add(i);
20
21
      System.out.println("size=" + TestRandomAccess.LIST_SIZE + ",test count=" + TestRandomAccess.TEST_COUNT + "\n");
22
      System.out.println("ArrayList for time=" + this.forTime(arraylist));
23
      System.out.println("ArrayList iterator time=" + this.iteratorTime(arraylist));
24
      System.out.println("LinkedList for time=" + this.forTime(linkedList));
25
      System.out.println("LinkedList iterator time=" + this.iteratorTime(linkedList));
26
    }
27
28
    private long forTime(List<Integer> list) {
29
        long beginTime = System.currentTimeMillis();
30
        for (int count = 0; count < TestRandomAccess.TEST_COUNT; count++) {
31
            for (int i = 0; i < list.size(); i++) list.get(i);
32
        }
33
        return System.currentTimeMillis() - beginTime;
34
    }
35
36
    private long iteratorTime(List<Integer> list) {
37
        long beginTime = System.currentTimeMillis();
38
        for (int count = 0; count < TestRandomAccess.TEST_COUNT; count++) {
39
            Iterator<Integer> iterator = list.iterator();
40
            while (iterator.hasNext()) iterator.next();
41
        }
42
        return System.currentTimeMillis() - beginTime;
43
    }
44
}

运行结果为:

1
size=1000,test count=1000
2
3
ArrayList for time=7
4
ArrayList iterator time=12
5
LinkedList for time=466
6
LinkedList iterator time=15