美文网首页开发者日记Android开发Android开发经验谈
Android开发(java基础)ArrayList、Linke

Android开发(java基础)ArrayList、Linke

作者: IT老五 | 来源:发表于2017-12-01 22:09 被阅读42次

    之前写了篇性能相关的文章:Android开发: 关于性能需要考虑的,都是一些文字描述,纯理论文;现在补充点实际的,以便更深刻的了解代码/数据结构/算法等对性能的影响...就从使用较多的list和for循环开始...

    代码示例

    程序员写作惯例,先看代码

    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.List;
    public class MyClass {
    
        public static void main(String[] args) {
            System.out.println("使用LinkedList, 10000 * 2次");
            test(10000, new LinkedList<N>());
    
            System.out.println("使用ArrayList, 10000 * 2次");
            test(10000, new ArrayList<N>());
    
            System.out.println("使用LinkedList, 500000 * 2次");
            test(500000, new LinkedList<N>());
    
            System.out.println("使用ArrayList, 500000 * 2次");
            test(500000, new ArrayList<N>());
        }
    
        private static void test(int num, List<N> list) {
    
            long start = System.currentTimeMillis();
            // 使用 list.add(N)增加num条数据
            for (int i = 0; i < num; i++) {
                list.add(new N(i));
            }
            System.out.println("list add(N)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            start = System.currentTimeMillis();
            // 使用 list.add(0, N)增加num条数据
            for (int i = 0; i < num; i++) {
                list.add(0, new N(i));
            }
            System.out.println("list add(0, N)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            int size = list.size(); // 数组长度
    
            start = System.currentTimeMillis();
            list.get(10); // 取第10个
            System.out.println("list get(10)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            start = System.currentTimeMillis();
            list.get(size - 10); // 取倒数第十个
            System.out.println("list get(size - 10)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            start = System.currentTimeMillis();
            list.get(size >> 1); // 取中间值
            System.out.println("list get(size >> 1)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            N n;
            start = System.currentTimeMillis();
            // 普通for循环
            for (int i = 0; i < size; i++) {
                n = list.get(i);
            }
            System.out.println("普通for循环使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            start = System.currentTimeMillis();
            // 增强型for循环(forEach)
            for (N c2 : list) {
            }
            System.out.println("增强for循环使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            start = System.currentTimeMillis();
            //迭代器遍历
            for (Iterator<N> it = list.iterator(); it.hasNext(); ) {
                n = it.next();
            }
            System.out.println("Iterator for循环使用了"+ (System.currentTimeMillis() - start)+"毫秒");
    
            list.clear();
            list = null;
        }
    }
    
    class N {
        int i;
        N(int i) {
            this.i = i;
        }
     }
    

    上次代码针对ArrayList和LinkedList及for循环做了多个测试,分为:
    横向比较:ArrayList和LinkedList之间针对add(T)和add(int, T)耗时比较;使用for循环耗时比较
    纵向比较:同一list的add和add(int,T)耗时比较;同一list使用不同for循环的耗时比较;以及同一list不同数量级时的耗时比较

    结果分析

    我们先来看看上述代码运行的结果 thinkinDemo.png

    重点看红线标注的值。

    横向对比:

    ①.在使用liast.add(T)时,ArrayList和LinedList耗时差别不大,当数据为10000 * 2时,几乎无差别,在数据达到500000 * 2时,LinkedList耗时多于ArrayList.
    ②.在使用list.add(0, T)时,耗时差距就很明显了,LinkedList明显优于ArrayList. 我们先接着看数据,原因稍后分析
    ③.再看看for循环获取指定对象,不管是普通for循环,forEach,还是iterator,ArrayList都优于LinkedList

    纵向对比:

    ①.ArrayList使用add(N)速度明显高于add(0,N);
    ②.LinkedList.get(size >> 1)耗时远高于get(10)及get(size - 10)
    ③.LinkedList使用forEach和iterrator效率原告与普通for循环

    为什么?(源码分析)

    下面,带着这一系列结果,我们来深入了解下ArrayList,LinkedList及forEach

    我们先看看ArrayList,可以了解到ArrayList是基于数组的实现,而且默认初始长度是10,最大储存长度是2147483639

        private static final int DEFAULT_CAPACITY = 10;
        private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
        transient Object[] elementData;
        private int size;
        private static final int MAX_ARRAY_SIZE = 2147483639;
    

    再看看ArrayList的add方法和add(0,N):打开ArrayList源码

        public boolean add(E var1) {
            this.ensureCapacityInternal(this.size + 1);
            this.elementData[this.size++] = var1;
            return true;
        }
    
        public void add(int var1, E var2) {
            this.rangeCheckForAdd(var1);
            this.ensureCapacityInternal(this.size + 1);
            System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
            this.elementData[var1] = var2;
            ++this.size;
        }
    

    add(N)做了两个操作,一个是ensureCapacityInternal,另一个是赋值,我们先看看ensureCapacityInternal做了啥?

        private void ensureCapacityInternal(int var1) {
            if(this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                var1 = Math.max(10, var1);
            }
    
            this.ensureExplicitCapacity(var1);
        }
    
        private void ensureExplicitCapacity(int var1) {
            ++this.modCount;
            if(var1 - this.elementData.length > 0) {
                this.grow(var1);
            }
    
        }
    
        private void grow(int var1) {
            int var2 = this.elementData.length;
            int var3 = var2 + (var2 >> 1);
            if(var3 - var1 < 0) {
                var3 = var1;
            }
    
            if(var3 - 2147483639 > 0) {
                var3 = hugeCapacity(var1);
            }
    
            this.elementData = Arrays.copyOf(this.elementData, var3);
        }
    

    这么一大段代码,其实是做了扩容操作(包含数组copy,扩容规则是变成原来最大容量的1.5倍+1,将原数组copy到新的数组中)
    而add(0,N)与add(N)相比,在扩容之前先调用rangeCheckForAdd判断0位置是否可以插入,扩容后还需要进行一次数组copy,会移动0位置及之后的元素
    所以,在ArrayLsit中add(0,N)相比于add(N)耗时会更多。

    再来看看LinkedList,LinkedList是基于链表的实现,记录有first节点和last节点,其节点定义中包含prev和next节点

        transient LinkedList.Node<E> first;
        transient LinkedList.Node<E> last;
    
        private static class Node<E> {
            E item;
            LinkedList.Node<E> next;
            LinkedList.Node<E> prev;
    
            Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
                this.item = var2;
                this.next = var3;
                this.prev = var1;
            }
        }
    

    其add(N)和add(0,N)操作是怎样的呢?
    首先看看add(N)

        public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    

    可以看到,LinkedList的add操作及其简单,在链表末端enw一个节点newNode,newNode的prev指向前一个元素,前一个元素的next指向newNode,然后size++

    add(0,N)是怎么样的呢?

        public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    

    可以看到,add(0, N)同样很简单,多了一个checkPositionIndex检测0位置是否合法,然后如果0位置位于链表最尾端,则与add(0)进行同样的操作linkLast,如果不是,则进行LinkBefore操作,LinkBefore会new一个newNode节点置于0位置,并修改其前后节点的next或prev值,size++
    因此:LinkedList的add(0, N)虽然比add(0)慢,但不像ArrayList的差距那么大

    然后,我们再看看看ArrayList与LinkedList的get方法:
    首先是ArrayList:

        public E get(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    
            return (E) elementData[index];
        }
    

    ArrayaList的get方法很简单,直接去数组的第index个元素
    我们再来看看LinkedList的get方法是怎样实现的:

        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    

    可以看到,在检查完index是否合法后,调用了node(index)去获取inde节点,我们再看看node(index)的实现

        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    

    可以看到node(index)使用了折半的方式,但由于LinkedList是基于链表,需要通过首节点不断next或者尾节点不断prev才能获取到想要的index节点,这就很好的解释了为什么LinkedList的get方法耗时远低于ArrayList,而且同一个LinkedList,越靠近首尾位置的节点,get速度越快

    最后,来看看for循环
    看了上面get的源码,我们已经很清楚为什么LinkedList进行普通for循环时为什么会耗时这么久(普通for循环需要通过get去获取list中的元素),而使用forEach和Iterator为什么会快这么多呢?
    我们先看看forEach是怎样实现的(好吧,这个没看到源码,但网上搜一下有不少解释,其实它会由编译器解释成iterator)...好吧,其实还是基于iterator的for循环,不过forEach更容易让人理解,使用起来也更方面。然后我们需要看看iterator:

    public interface Iterator<E> {
        boolean hasNext();
        E next();
        default void remove() {
            throw new UnsupportedOperationException("remove");
        }
        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
        }
    

    这是一个接口,包含next(),然后我们可以发现List实现了Collection接口,而Collection接口继承了Iterator接口。
    好吧!其实forEach只是在按照顺序不断的next(),这相比于LinkedList每次调用get()去循环查找效率当然高了几个数量级;

    总结

    由于ArrayList和LinkedList分别基于数组和链表,所以ArrayList更适合于查找以及顺序的增加add(index),而LinkedList则更适合于随机的增加add(index, E)和删除;

    在内存上,ArrayList因为是按照1.5倍的扩容,在尾端可能会有内存浪费,而LinkedList每个节点存在着prev和next的内存开销。

    由于ArrayList存在扩容,如果数据量大,可以将初始容量设置更合理(默认10),减少扩容太多次的开销,特别在addAll时。

    LinkedList尽量不要选用普通for循环,使用forEach或者iterator(可以remove元素)

    相关文章

      网友评论

        本文标题:Android开发(java基础)ArrayList、Linke

        本文链接:https://www.haomeiwen.com/subject/hdfwbxtx.html