注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

民主与科学

独立之人格,自由之思想

 
 
 

日志

 
 

随机访问RandomAccess  

2010-08-12 12:29:53|  分类: JAVA集合容器 |  标签: |举报 |字号 订阅

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

在对List特别的遍历算法中,要尽量来判断是属于 RandomAccess(如ArrayList)还是SequenceAccess(如LinkedList),
因为适合RandomAccess List的遍历算法,用在SequenceAccess List上就差别很大,
即对于实现了RandomAccess接口的类实例而言,此循环
 for (int i=0, i<list.size(); i++)
   list.get(i);

运行速度要快于以下循环:
for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();

实现了RandomAccess接口的有:
 ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector
通过下面的代码,大家可以加深理解。
package com.bokee.lzqdiy;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.RandomAccess;
public class Test{
    
public static void travel(List list)
    {
       
 if (list instanceof RandomAccess)
        {
            System.out.println("实现了RandomAccess接口,不使用迭代器!");
           
 for(int i=0;i<list.size();i++)
            {
                System.out.println(list.get(i));
            }
        }
        
else
        {
            System.out.println("没实现RandomAccess接口,使用迭代器!");
            for (Iterator iter = list.iterator(); iter.hasNext();)
            {
                System.out.println((String) iter.next());
            }
        }
    }
    public static void main(String[] args)
    {
        List list=new ArrayList();
        list.add("a");
        list.add("b");
        travel(list);
        list=new LinkedList(); 
        list.add("c");
        list.add("d");
        travel(list);
    }
}
补充:(2007年4月23日)
下面的程序用来测试ArrayList和LinkedList遍历方式的不同对性能(执行时间)的影响。
package net.blogjava.lzqdiy;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.RandomAccess;
public class TestDifferent
{
    public static void main(String[] args)
    {
        if (args.length == 0)
        {
            System.err.println("请输入元素的个数和遍历次数!");
            return;
        }
        int number = Integer.parseInt(args[0]);// 集合中元素的个数
        int count = Integer.parseInt(args[1]);// 遍历集合中元素的次数
        List list = new ArrayList();
        addObject(list, number);//向集合中添加number个元素
        System.out.println("遍历ArrayList");
        travelwithoutIterator(list, count);//不用迭代器遍历
        travelwithIterator(list, count);//用迭代器遍历
        list = new LinkedList();
        addObject(list, number);//向集合中添加number个元素
        System.out.println("遍历LinkedList");
        travelwithoutIterator(list, count);//不用迭代器遍历
        travelwithIterator(list, count);//用迭代器遍历
    }
    public static void addObject(List list, int n)
    {
        for (int m = 1; m <= n; m++)
        {
            list.add("" + m);
        }
    }
    public static void travelwithoutIterator(List list, int count)
    {
        long startTime;
        long endTime;
        startTime = System.currentTimeMillis();
        for (int a = 1; a <= count; a++)
        {
            for (int i = 0; i < list.size(); i++)
            {
                list.get(i);
            }
        }
        endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println("不使用迭代器的间隔时间:" + interval);
    }
    public static void travelwithIterator(List list, int count)
    {
        long startTime;
        long endTime;
        startTime = System.currentTimeMillis();
        for (int a = 1; a <= count; a++)
        {
            for (Iterator iter = list.iterator(); iter.hasNext();)
            {
                iter.next();
            }
        }
        endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println("使用迭代器的间隔时间:" + interval);
    }
    public static void travel(List list, int count)
    {
        long startTime;
        long endTime;
        if (list instanceof RandomAccess)
        {
            System.out.println("实现了RandomAccess接口,不使用迭代器!");
            startTime = System.currentTimeMillis();
            for (int a = 1; a <= count; a++)
            {
                for (int i = 0; i < list.size(); i++)
                {
                    list.get(i);
                }
            }
            endTime = System.currentTimeMillis();
            long interval = endTime - startTime;
            System.out.println("间隔时间:" + interval);
        } else
        {
            System.out.println("没实现RandomAccess接口,使用迭代器!");
            startTime = System.currentTimeMillis();
            for (int a = 1; a <= count; a++)
            {
                for (Iterator iter = list.iterator(); iter.hasNext();)
                {
                    iter.next();
                }
            }
            endTime = System.currentTimeMillis();
            long interval = endTime - startTime;
            System.out.println("间隔时间:" + interval);
        }
    }
}
我在命令行输入:java TestDifferent 100 10000
输出结果是:
遍历ArrayList
不使用迭代器的间隔时间:31
使用迭代器的间隔时间:63
遍历LinkedList
不使用迭代器的间隔时间:93
使用迭代器的间隔时间:32

以上结果随着JVM的运行环境而变化。
当元素个数>100并且遍历次数大于10000次时效果明显。
实例2:
import java.util.ArrayList;
import java.util.Iterator;
public class Test {
 /**
  * @param args
  */

 public static void main(String[] args) {
  ArrayList <String> list=new ArrayList<String>(10000);
  for(int i=0;i<10000;i++)
   list.add(""+System.currentTimeMillis());
  int count=1000;
  long timeStart=System.currentTimeMillis();
  long timeEnd=0;
  String name=null;
  int k=0;
  for (int a = 1; a <= count; a++)
  {
   for(int i=0;i<list.size();i++)
   {
    name=list.get(i);
    k=k+1;
   }
  }
  timeEnd=System.currentTimeMillis();
  System.out.println("Random access use time:"+(timeEnd-timeStart));
  timeStart=System.currentTimeMillis();
        for (int a = 1; a <= count; a++)
        {
            for (Iterator<String> iter = list.iterator(); iter.hasNext();)
            {
                iter.next();
                k=k+1;
            }
        }
        timeEnd=System.currentTimeMillis();
        System.out.println("iterator1 access use time:"+(timeEnd-timeStart));
    timeStart=System.currentTimeMillis();
  
        for (int a = 1; a <= count; a++)
        {
            for (String name2:list)
            {
             k=k+1;
            }
        }
        timeEnd=System.currentTimeMillis();
        System.out.println("iterator2 access use time:"+(timeEnd-timeStart));
 }
}
结果:
Random access use time:125
iterator1 access use time:406
iterator2 access use time:391
  评论这张
 
阅读(718)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017