帮助IT团队快速构建符合jt808协议部标的基于java技术的GPS和视频平台(2379423771@qq.com)

List集合随机排序算法分析

List集合随机排序算法分析

先说一下JDK 对List的随机排序的实现:

public static void shuffle(List list, Random rnd) {    
      final int SHUFFLE_THRESHOLD        =    5;  //这应当是一个经验值吧

        int size = list.size();
  /** 为什么要判断,后面有论述 */
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));  //这一种方法是直接调用List.set方法,属于RandomAccess中的方法
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            ListIterator it = list.listIterator();      //如果不是Random Access实现,就使用迭代器遍历
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }


再说一下我自己的笨拙实现:
  public static List randomSortList(List ls, Random random) {
                List randomList = new ArrayList();               
                int size = list.size();
               while (size > 0) {
                  int randomNum = random.nextInt(size);
                  randomList.add(ls.get(randomNum));
                  ls.remove(randomNum); //这一步,对于RandomAccess的集合来说,是O(1)操作
               }
               return randomList;
     }
评述:
  如果List的实现是ArrayList,在时间效率上要多循环一次,但在空间上,我的方法非常差,多生成一个List集合,如果List很大,就更差了。同时我的算法如果用于Sequence List上,效率是相当的差,只能适合ArrayList,有很大的局限性。
  这是因为: 如果集合类是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()){}
    }
   我的项目中List都是基于ArrayList的,所以基本上很少用迭代器来遍历,而是用for循环来遍历,对于迭代器的作用我当然很清楚,但是我觉得有点庸人自扰了。
   除非你经常用Collection作为你的接口方法中的输入或输出的集合参数类型时,你也就只能用Iterator。
   但我一般在接口方法中,一般用List,所以我就不用迭代器,除非我的List是Linked List实例。
   好的作法是:在供外部调用的接口方法中,使用Collection作为集合参数类型,在内部实现当中,使用List,而不是一味的使用Collections及Iterator,这样做无异于作茧自缚。
   顺便说一下JDK中推荐的是对List集合尽量要实现RandomAccess接口。

posted on 2006-07-31 18:25 Speed 阅读(4294) 评论(0)  编辑  收藏 所属分类: Algorithm theory & practice


只有注册用户登录后才能发表评论。


网站导航:
 

导航

留言簿(15)

随笔分类

值得一看的博客

积分与排名

最新评论

阅读排行榜