首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 数据库 > Access >

RandomAccess接口的应用

2013-03-06 
RandomAccess接口的使用引子:RandomAccess在类Collections的shuffle()方法中的使用:(jdk源码如下)Java代码

RandomAccess接口的使用

引子:
RandomAccess在类Collections的shuffle()方法中的使用:(jdk源码如下)Java代码  RandomAccess接口的应用
  1. <span style="font-size: small;">/** 
  2.      * Randomly permute the specified list using the specified source of 
  3.      * randomness.  All permutations occur with equal likelihood 
  4.      * assuming that the source of randomness is fair.<p> 
  5.      * 
  6.      * This implementation traverses the list backwards, from the last element 
  7.      * up to the second, repeatedly swapping a randomly selected element into 
  8.      * the "current position".  Elements are randomly selected from the 
  9.      * portion of the list that runs from the first element to the current 
  10.      * position, inclusive.<p> 
  11.      * 
  12.      * This method runs in linear time.  If the specified list does not 
  13.      * implement the {@link RandomAccess} interface and is large, this 
  14.      * implementation dumps the specified list into an array before shuffling 
  15.      * it, and dumps the shuffled array back into the list.  This avoids the 
  16.      * quadratic behavior that would result from shuffling a "sequential 
  17.      * access" list in place. 
  18.      * 
  19.      * @param  list the list to be shuffled. 
  20.      * @param  rnd the source of randomness to use to shuffle the list. 
  21.      * @throws UnsupportedOperationException if the specified list or its 
  22.      *         list-iterator does not support the <tt>set</tt> operation. 
  23.      */  
  24.   
  25.   
  26. public static void shuffle(List<?> list, Random rnd) {  
  27.         int size = list.size();  
  28.         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {//注意这一句中的instanceof  
  29.             for (int i=size; i>1; i--)  
  30.                 swap(list, i-1, rnd.nextInt(i));  
  31.         } else {  
  32.             Object arr[] = list.toArray();  
  33.   
  34.             // Shuffle array  
  35.             for (int i=size; i>1; i--)  
  36.                 swap(arr, i-1, rnd.nextInt(i));  
  37.   
  38.             // Dump array back into list  
  39.             ListIterator it = list.listIterator();  
  40.             for (int i=0; i<arr.length; i++) {  
  41.                 it.next();  
  42.                 it.set(arr[i]);  
  43.             }  
  44.         }  
  45.     }</span>  

 由以上的jdk源码可见,在对实现list接口的对象进行洗牌,打乱时,区分了该类是否是RandomAccess的实例,这样做有什么意义呢?请继续向下看:


介绍: 

在jdk文档中对RandomAccess接口的定义如下:

public interface RandomAccess

List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。


将操作随机访问列表的最佳算法(如 ArrayList )应用到连续访问列表(如 LinkedList )时,可产生二次项的行为。如果将某个算法应用到连续访问列表,那么在应用可能提供较差性能的算法前,鼓励使用一般的列表算法检查给定列表是否为此接口的一个 instanceof ,如果需要保证可接受的性能,还可以更改其行为。

现在已经认识到,随机和连续访问之间的区别通常是模糊的。例如,如果列表很大时,某些 List 实现提供渐进的线性访问时间,但实际上是固定的访问时间。这样的 List 实现通常应该实现此接口。


强调:

JDK中推荐的是对List集合尽量要实现RandomAccess接口

如果集合类是RandomAccess的实现,则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历,在效率上要差一些。反过来,如果List是Sequence List,则最好用迭代器来进行迭代。


JDK中说的很清楚,在对List特别是Huge size的List的遍历算法中,要尽量来判断是属于RandomAccess(如ArrayList)还是Sequence List (如LinkedList),因为适合RandomAccess List的遍历算法,用在Sequence List上就差别很大,常用的作法就是:
    要作一个判断:
    if (list instance of RandomAccess) {
        for(int m = 0; m < list.size(); m++){}
    }else{
        Iterator iter = list.iterator();
        while(iter.hasNext()){}
    }


验证:

Java代码  RandomAccess接口的应用
  1. <span style="font-size: small;">/* 
  2.  * To change this template, choose Tools | Templates 
  3.  * and open the template in the editor. 
  4.  */  
  5. package testrandomaccess;  
  6.   
  7. import java.util.ArrayList;  
  8. import java.util.Iterator;  
  9. import java.util.LinkedList;  
  10. import java.util.List;  
  11. import java.util.RandomAccess;  
  12.   
  13. /** 
  14.  * 
  15.  * @author bolong 
  16.  */  
  17. public class TestRandomAccess {  
  18. // 初始化列表  
  19.   
  20.     public static void initList(List list, int n) {  
  21.         for (int i = 0; i < n; i++) {  
  22.             list.add(i);  
  23.         }  
  24.     }  
  25. //使用循环进行对列表的迭代  
  26.   
  27.     public static void traverseWithLoop(List list) {  
  28.         long starttime = 0;  
  29.         long endtime = 0;  
  30.         starttime = System.currentTimeMillis();  
  31.         for (int count = 0; count <= 1000; count++) {  
  32.             for (int i = 0; i < list.size(); i++) {  
  33.                 list.get(i);  
  34.             }  
  35.         }  
  36.         endtime = System.currentTimeMillis();  
  37.         System.out.println("使用loop迭代一共花了" + (endtime - starttime) + "ms时间");  
  38.   
  39.     }  
  40. //使用迭代器对列表进行迭代  
  41.   
  42.     public static void traverseWithIterator(List list) {  
  43.         long starttime = 0;  
  44.         long endtime = 0;  
  45.         starttime = System.currentTimeMillis();  
  46.         for (int count = 0; count <= 1000; count++) {  
  47.             for (Iterator itr = list.iterator(); itr.hasNext();) {  
  48.                 itr.next();  
  49.             }  
  50.         }  
  51.         endtime = System.currentTimeMillis();  
  52.         System.out.println("使用Iterator迭代一共花了" + (endtime - starttime) + "ms时间");  
  53.     }  
  54.   
  55.     public static void traverse(List list) {  
  56.   
  57.         long starttime = 0;  
  58.         long endtime = 0;  
  59.         if (list instanceof RandomAccess) {  
  60.             System.out.println("该list实现了RandomAccess接口");  
  61.             starttime = System.currentTimeMillis();  
  62.             for (int count = 0; count <= 1000; count++) {  
  63.                 for (int i = 0; i < list.size(); i++) {  
  64.                     list.get(i);  
  65.                 }  
  66.             }  
  67.             endtime = System.currentTimeMillis();  
  68.             System.out.println("迭代一共花了" + (endtime - starttime) + "ms时间");  
  69.         } else {  
  70.             System.out.println("该list未实现RandomAccess接口");  
  71.             starttime = System.currentTimeMillis();  
  72.             for (int count = 0; count <= 1000; count++) {  
  73.                 for (Iterator itr = list.iterator(); itr.hasNext();) {  
  74.                     itr.next();  
  75.                 }  
  76.             }  
  77.             endtime = System.currentTimeMillis();  
  78.             System.out.println("迭代一共花了" + (endtime - starttime) + "ms时间");  
  79.         }  
  80.     }  
  81.   
  82.     public static void main(String[] args) {  
  83.         ArrayList arraylist = new ArrayList();  
  84.         LinkedList linkedlist = new LinkedList();  
  85.         initList(arraylist, 1000);  
  86.         initList(linkedlist, 1000);  
  87.         traverse(arraylist);  
  88.         traverse(linkedlist);  
  89.         traverseWithIterator(arraylist);  
  90.         traverseWithLoop(arraylist);  
  91.         traverseWithIterator(linkedlist);  
  92.         traverseWithLoop(linkedlist);  
  93.     }  
  94. }  
  95. </span>  

 运行程序输出的结果为:


该list实现了RandomAccess接口
迭代一共花了47ms时间
该list未实现RandomAccess接口
迭代一共花了15ms时间
使用Iterator迭代一共花了79ms时间
使用loop迭代一共花了46ms时间
使用Iterator迭代一共花了47ms时间
使用loop迭代一共花了797ms时间


结论:

根据程序输出的结果的确证明了,arraylist等实现了RandomAccessj接口的类在进行迭代时使用loop效率更高,而linkedList那些未实现该接口的类在进行迭代时使用Iterator进行迭代效率更高.

热点排行