java - 自己的 String 容器与 ArrayList

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，并且无需重新分配，直到列表的长度达到之前的两倍。