自己的String容器与ArrayList <String>

Question

为什么在我自己的容器中添加字符串比在字符串中添加字符串效率低得多ArrayList<String>？

我不知道ArrayList泛型类是如何实现的,但我无法理解为什么类的add方法ArrayList比我的add方法快得多.

这是我的简单容器类:

public class MyContainer
{
    private String[] _array;
    private int _length = 0;

    public MyContainer(int length)
    {
        if(length < 0) throw new NegativeArraySizeException();
        else _length = length;
        _array = new String[length];
    }

    //This is not an efficient add method, but I wouldn't know how to implement
    //it otherwise in Java
    public void add(String newElement)
    {
        ++_length;
        String[] tmp = new String[_length];

        for(int i = 0; i < _array.length; ++i)
            tmp[i] = _array[i];

        tmp[_length - 1] = newElement;
        _array = tmp;
    }

    public String get(int position)
    {
        if(position < 0 || position >= _array.length) throw new ArrayIndexOutOfBoundsException();
        else return _array[position];
    }

    public int length()
    {
        return _length;
    }
}

在Main课堂上:

public class Main
{
    public static void main(String[] args)
    {
        int N = 20000;

        MyContainer cont = new MyContainer(0);
        ArrayList<String> list = new ArrayList<String>();

        long contTime = 0;
        long listTime = 0;

        // Counting how much time is needed to add N elements to an MyContainer
        long startCont = System.nanoTime();

        for(int i = 0; i < N; ++i)
            cont.add("aroma");

        contTime = System.nanoTime() - startCont;
        //
        // Counting how much time is needed to add N elements to an ArrayList
        //
        long startList = System.nanoTime();

        for(int i = 0; i < N; ++i)
            list.add("aroma");

        listTime = System.nanoTime() - startList;

        System.out.println("MyContainer's object contains:\n");
        for(int i = 0; i < cont.length(); ++i)
            System.out.println(cont.get(i));

        System.out.println("\n\nArrayList's objects are:\n");
        for(int i = 0; i < list.size(); ++i)
            System.out.println(list.get(i));

        System.out.printf("\nNano seconds for 'cont': %d.\n", contTime);
        System.out.printf("Nano seconds for 'list': %d.", listTime);

        System.out.printf("\nSeconds for 'cont': %f", contTime / 1E9);
        System.out.printf("\nSeconds for 'list': %f", listTime / 1E9);
    }

}

这些是我获得的一些结果:

Nano seconds for 'cont': 687564548.
Nano seconds for 'list': 3610871.
Seconds for 'cont': 0.687565
Seconds for 'list': 0.003611

编辑

该方法的新实现add:

public void add(String newElement)
{
    ++_length;

    if(_capacity < _length)//Introduced a field called _capacity
    {
        _capacity = _length * 2;
        _tmp = new String[_capacity];

        for(int i = 0; i < _array.length; ++i)
            _tmp[i] = _array[i];

        _tmp[_length - 1] = newElement;
        _array = _tmp;
    }
    else _array[_length - 1] = newElement;
}

新结果:

Nano seconds for 'cont': 11667046.
Nano seconds for 'list': 6451100.
Seconds for 'cont': 0.011667
Seconds for 'list': 0.006451

Answer 1

每次添加元素时,您都在重新分配整个数组并将旧内容复制到新数组.内存分配不仅会受到性能影响,您每次都必须复制已存在的元素.

是什么ArrayList做的是当它需要更多的空间,它分配一个数组,它是双前一长度的长度,使其削减一路下滑内存重新分配.如果ArrayList容量为100,则新容量为200,并且在列表是之前长度的两倍之前不需要重新分配.