Android开发(java基础一)ArrayList、LinkedList与for循环

itlao6 Android 原创 开发&源码评论950字数 6998阅读23分19秒阅读模式

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

代码示例

程序员写作惯例,先看代码文章源自IT老刘-https://itlao6.com/59.html

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不同数量级时的耗时比较文章源自IT老刘-https://itlao6.com/59.html

结果分析

我们先来看看上述代码运行的结果文章源自IT老刘-https://itlao6.com/59.html

Android开发(java基础一)ArrayList、LinkedList与for循环
thinkinDemo.png

重点看红线标注的值。文章源自IT老刘-https://itlao6.com/59.html

横向对比:

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

纵向对比:

①.ArrayList使用add(N)速度明显高于add(0,N);
②.LinkedList.get(size >> 1)耗时远高于get(10)及get(size - 10)
③.LinkedList使用forEach和iterrator效率原告与普通for循环文章源自IT老刘-https://itlao6.com/59.html

为什么?(源码分析)

下面,带着这一系列结果,我们来深入了解下ArrayList,LinkedList及forEach文章源自IT老刘-https://itlao6.com/59.html

我们先看看ArrayList,可以了解到ArrayList是基于数组的实现,而且默认初始长度是10,最大储存长度是2147483639文章源自IT老刘-https://itlao6.com/59.html

    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源码文章源自IT老刘-https://itlao6.com/59.html

    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做了啥?文章源自IT老刘-https://itlao6.com/59.html

    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)耗时会更多。文章源自IT老刘-https://itlao6.com/59.html

再来看看LinkedList,LinkedList是基于链表的实现,记录有first节点和last节点,其节点定义中包含prev和next节点文章源自IT老刘-https://itlao6.com/59.html

    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)文章源自IT老刘-https://itlao6.com/59.html

    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++文章源自IT老刘-https://itlao6.com/59.html

add(0,N)是怎么样的呢?文章源自IT老刘-https://itlao6.com/59.html

    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的差距那么大文章源自IT老刘-https://itlao6.com/59.html

然后,我们再看看看ArrayList与LinkedList的get方法:
首先是ArrayList:文章源自IT老刘-https://itlao6.com/59.html

    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

ArrayaList的get方法很简单,直接去数组的第index个元素
我们再来看看LinkedList的get方法是怎样实现的:文章源自IT老刘-https://itlao6.com/59.html

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

可以看到,在检查完index是否合法后,调用了node(index)去获取inde节点,我们再看看node(index)的实现文章源自IT老刘-https://itlao6.com/59.html

    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速度越快文章源自IT老刘-https://itlao6.com/59.html

最后,来看看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元素)


作者:ThinkinLiu
链接:http://www.jianshu.com/p/deb2f92788e7
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
继续阅读
weinxin
我的微信公众号
微信扫一扫关注公众号,不定时更新
itlao6
  • 本文由 发表于 2017年 12月 1日 22:12:29
  • 转载请务必保留本文链接:https://itlao6.com/59.html
评论  0  访客  0
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定