之前写了篇性能相关的文章: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元素)
网友评论