Own String container versus ArrayList<String>

Question

Why adding strings to my own container is much less efficient than adding string to an ArrayList<String>?

I don't know exactly how the ArrayList generic class is implemented, but I cannot understand why the add method of the ArrayList class is much faster than my add method.

This is my simple container class:

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;
    }
}

In the Main class:

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);
    }

}

These are some results I obtained:

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

EDIT

New implementation of the method 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;
}

New results:

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

rgettman · Accepted Answer · 2014-08-27 22:33:21Z

5

You are re-allocating the entire array and copying the old contents to the new array each time an element is added. Not only does memory allocation suffer a performance hit, you have to copy the already existing elements each time.

What ArrayList does is when it needs more space, it allocates an array that is double the length of the previous length, so that it cuts way down on memory re-allocations. If the ArrayList was at capacity 100, then the new capacity is 200 and no re-allocation needs to take place until the list is double its previous length.

answered Aug 27, 2014 at 22:33

rgettman

179k30 gold badges282 silver badges365 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

rgettman Over a year ago

If you know the maximum number of elements beforehand, just allocate that number of elements in the array from the start. If you don't know the maximum beforehand, allocate a certain amount, and when you re-allocate, double the length.

coffeeaddict Over a year ago

@usar better approach would be to re-allocate as little as possible. java implementation does this by doubling size each time it reaches capacity. like rgettman said, if you know your maximum ahead of time, the best is to simply allocate that many from the start.

Eran · Accepted Answer · 2014-08-27 22:32:41Z

3

Your add method creates a new array every time (and copies the Strings of the current array to the new array), even if the existing array is large enough to insert a new String to it. That's why it's much slower than ArrayList.

Compare it to this implementation of ArrayList :

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

A new array would only be created if there's no room for the new element in the current array.

answered Aug 27, 2014 at 22:32

Eran

395k57 gold badges726 silver badges793 bronze badges

Collectives™ on Stack Overflow

Own String container versus ArrayList<String>

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related