首页 » Java » [Java]洗牌效果Model的实现及RandomAccess接口

[Java]洗牌效果Model的实现及RandomAccess接口

原文 http://blog.csdn.net/Shenpibaipao/article/details/79189262

2018-01-29 02:00:31阅读(528)

洗牌效果的实现并不复杂,主要使用的是Collections的静态方法shuffle(List<?> list):

List list = new LinkedList();
list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);
Collections.shuffle(list);//list将被打乱
list.forEach(System.out::println);
shuffle的内部实现主要是基于swap方法的:

public static void shuffle(List<?> list, Random rnd) {
        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));
        } 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
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }
其复杂度是线性的。为了提升效率和避免把复杂度上升到平方级别(某些类的迭代方法是平方级别的或高于for语句等访问形式),当这个List尺寸过大(默认阈值为5)及其不是一个RandomAccess接口的实现类时,那么将把这个list转为一个Object[],并执行以下的swap方法:

    private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
很容易看出来这就是个最常见的swap算法。再进行这个swap之后,再通过迭代器把Objcet[]转为list。

否则,将经过for(i=list.size();i>=0;i--)直接调用Collection的swap方法:

    public static void swap(List<?> list, int i, int j) {
        final List l = list;
        l.set(i, l.set(j, l.get(i)));
    }


这里涉及到一个问题:为什么要这么做?

我们需要了解RandomAccess接口。这是一个标记(Marker)接口,其内部方法全空,可以理解成一个打在类标记上的注解,用来标示这个类的某项特性,属于接口的非典型用法。


RandomAccess并不是完全意义上的“随机访问”,他是相对迭代器的“顺序访问”而言的。它的“随机访问”,实际上是表示了该类的一种特性:利用迭代器遍历该类并不是效率最高的方法,希望程序员可以考虑用for(i=0;i<size;i++)的方法去访问该类。


当某个类自定义的访问方法快过利用迭代器访问,那么应当标上这个标记接口,用于告知其他程序访问、遍历该集合的正确选择——例如对于for(i=0;i<list.size();i++)或for(i=list.size();i>=0;i--)、其他任意“访问序”快过利用while(Iterator().next())的时候,该RandomAccess标记接口就可以被标上。显然对于for(i=0;i<list.size();i++),字面上看就是“顺序访问”,但这并不妨碍其被称为“是RandomAccess的”。



最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹