数组操作 和 list到数组

常在看代码的时候，看到这样的数组的操作：

Integer[] arr1 = new Integer[0];
for (int i=0; i < 100000; i++) {
	Integer[] arr2 = new Integer[arr1.length + 1];
	System.arraycopy(arr1, 0, arr2, 0, arr1.length);
	arr2[arr1.length] = i;
	arr1 = arr2;
}

  实现的就是，向数组中加元素，这个数组是不定常的，所以里面会新new一个数组，然后又copy，又赋值的。感觉就是头大，效率不高，代码写的太朴实无华了。

 

比较List的实现：

public class Tst {
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		List<Integer> list = new ArrayList<Integer>();
		for (int i=0; i < 10000000; i++)
			list.add(i);
		list.toArray(new Integer[list.size()]);
		System.out.println("Runned time : " + (System.currentTimeMillis()-startTime));

		startTime = System.currentTimeMillis();
		Integer[] arr1 = new Integer[0];
		for (int i=0; i < 100000; i++) {
			Integer[] arr2 = new Integer[arr1.length + 1];
			System.arraycopy(arr1, 0, arr2, 0, arr1.length);
			arr2[arr1.length] = i;
			arr1 = arr2;
		}
		System.out.println("Runned time : " + (System.currentTimeMillis()-startTime));
	}
}

 

结果：

写道

Runned time : 3422
Runned time : 21407

 

list加入了10000000个元素在变换成数组，数组方式是100000数量，比list小两个数量级，居然还慢这么多。

好，果然慢。猜想是多的，数组那种方式效率是不高，原因呢？list在调用add的时候，先看它已经有的数组能不能放，如果不够的话，它是这样扩大的

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
	    if (newCapacity < minCapacity)
	newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

  

也就 newCapacity = (oldCapacity * 3)/2 + 1;

并不是数组那种总是加1的方式。