ArrayLists - using initial capacity constructor

Hello experts,

  I have a question about ArrayLists. A friend of mine says that using the constructor that sets the initial capacity on an arrayList is a useful thing to do when you are only adding one item to the list. Why have 10 slots when only one is used. I however thought I read that array lists auto resize when the capacity reaches a certain level. So by setting it to one and adding an item to it it actualy takes longer because it now has to resize its self defeating all benefit of that initial capacity. I read that its only beneficial when you are add a lot of items to the list 1000 or more because then it wont resize until after it get too full.

 I attempted to prove this case in a small test program but was not able to make my point because I cannot see what that real capacity of the arrayLists are, only the count of members in the list. Is there a way to prove my case better in a simple program.


import java.util.*;

public class TestArrayList {


    private ArrayList defaultList = new ArrayList();
    private ArrayList oneMember  = new ArrayList(1);
       
    public static void main(String args[]){
        System.out.println("Starting: " + new java.util.Date());
        TestArrayList testMe = new TestArrayList();
       
           
        testMe.test();

    }


    public void test(){

        System.out.println("defaultList.size= " + defaultList.size() );
        System.out.println("oneMember.size= "   + oneMember.size() );


        System.out.println("add to default and see how it resizes");
        // add ten items to default
      for(int i=0; i<10; i++) {
            System.out.println("add to default 1" );
          defaultList.add("stuff");
            System.out.println("defaultList.size= " + defaultList.size() );
        }

         
        System.out.println("add to one member and see how it resizes");
        // add ten items to default
      for(int i=0; i<10; i++) {
            System.out.println("add to oneMember 1" );
          oneMember.add("stuff");
            System.out.println("oneMember.size= " + oneMember.size() );
        }

    }

}
enterciteAsked:
Who is Participating?
 
zzynxSoftware engineerCommented:
bloodredsun, I think your test program should look like this to prove the author's point
(it's about adding the 1st element):

public class TestArrayList {

     public static void main(String args[]){
          ArrayList defaultList = null;
          ArrayList oneMember = null;
          int size = 100000 ;
          System.out.println("Starting: " + new java.util.Date());
       
        long t0 = System.currentTimeMillis() ;
          for(int i=0; i<size ; i++) {
               oneMember = new ArrayList(1);
               oneMember.add( Double.toString(Math.random()) ) ;
          }
          long t1 = System.currentTimeMillis() ;
          for(int i=0; i<size ; i++) {
               defaultList = new ArrayList();
               defaultList.add( Double.toString(Math.random()) ) ;
          }          
          long t2 = System.currentTimeMillis() ;
         
          System.out.println("oneMember took " + (t1-t0) + "ms") ;
          System.out.println("defaultList took " + (t2-t1) + "ms") ;
    }
}
0
 
zzynxSoftware engineerCommented:
You could try with Vector() which has a capacity() method
0
 
zzynxSoftware engineerCommented:
I quote from the java doc about ArrayList:

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list.
It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.
The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation.
This may reduce the amount of incremental reallocation.

and

This class is roughly equivalent to Vector, except that it is unsynchronized.
0
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

 
bloodredsunCommented:
How about this:
--------------------
package com.bloodredsun;

import java.util.*;

public class TestArrayList {

     public static void main(String args[]){
            ArrayList defaultList = new ArrayList();
            ArrayList oneMember  = new ArrayList(1);
            int size = 100000 ;
        System.out.println("Starting: " + new java.util.Date());
       
        long t0 = System.currentTimeMillis() ;
            for(int i=0; i<size ; i++) {
                  oneMember.add( Double.toString(Math.random()) ) ;
            }
            long t1 = System.currentTimeMillis() ;
            for(int i=0; i<size ; i++) {
                  defaultList.add( Double.toString(Math.random()) ) ;
            }            
            long t2 = System.currentTimeMillis() ;
            
            System.out.println("oneMember took " + (t1-t0) + "ms") ;
            System.out.println("defaultList took " + (t2-t1) + "ms") ;
    }
}
0
 
zzynxSoftware engineerCommented:
>> So by setting it to one and adding an item to it it actualy takes longer
>> because it now has to resize its self defeating all benefit of that initial capacity.
I don't think the initial capacity (which you specified as being 1) will change if you add the first item.
I think it will change if you add the 2nd.
0
 
zzynxSoftware engineerCommented:
FYI: defaultList always takes about 100 ms less then oneMember.
Which seems to indicate that using new ArrayList(1) has no benefit.
0
 
bloodredsunCommented:
Ah, I just cobbled something together from that BigInteger Prime Number question, which is why it looked like that (well, that and mis-understanding the question a little!!!).

I can't remember ever using ArrayList (int InitialCapacity)...I've never needed that type of perfomance tuning but it's a good academic excercise.
0
 
SuperKarateMonkeyCommented:
Why bother doing all this testing?  If you really want to know how ArrayList workd, there's no need to test your way into what is essentially reverse-engineering it's logic: Just check the source code of the ArrayList class.  It ought to be in the root of your java install directory in a file: src.zip

Extract out ArrayList.java and take a look at it, like I am right now.  ArrayList is implemented with an array of Objects:

private transient Object elementData[];

When you instantiate an ArayList, it will either initialize elementData to a 10-item array, (in the case of the zero-argument constructor,) or as an x-item array, if you use the overloaded constructor to designate an initial capacity of x.  If you instantiate an ArrayList with a Collection in the constructor, then it will specify an additional 10% capacity to allow for growth.

Now, the other question is about how it resizes:

It calls a public method called ensureCapacity( int minCapacity ), which does a couple of things:

1.  It checks to see if minCapacity < currentCapacity, where currentCapacity is the current size of the underlying elementData[].  If so, it does nothing.

2.  It checks to see if minCapacity < ((1.5)*currrentCapacity + 1).  If so, it just increases the currentCapacity value by 50%, (the same as multiplying by 1.5,) and then adds one.

3.  If both those tests fail, it just sets currentCapacity = minCapacity, which is to say it resizes the elementData[] to your minCapacity value.

Now, this applies if you're resizing the ArrayList manually, by calling ensureCapacity( int ) your self, or implicitly, if you keep calling add( Object ) method 'till the ArrayList runs out of space.

I didn't know this until 5 minutes ago.  I just unzipped the source files and read them formyself.  While this information is valid for 1.4.2, and I validated the source in unchanged in 1.5, you should understand that these are Sun source code files, and Sun makes no guarantees that these files will remain unchanged.  All Sun promises is that they'll honor the public interfaces, (explicit or implied,) that these classes represent.  Sun, at one point or another, may take it into their heads that there's a better way to implement array resizing internally in the ArrayList class.  Then things might change.  But this is how things are now.
0
 
SuperKarateMonkeyCommented:
Oh, one more thing:  Your code above is wrong:  the size() method of the ArrayList class does not report the size of the underlying elementData[] array.  It reports the number of items in the ArrayList that have actually been stored.  elementData[] is private, and you can't easily get to it, (not even by subclassing ArrayList, since it's private,) so you'll have to either reference the source code or take my word for it.

If you REALLY want to verify what I've told you, I'd suggest you not only extract out ArrayList.java from the original source, but ALSO recompile it as your own class.  You'll need to refactor the code for a different package, and preferably a different name, but then you can add one last method:

public int getRealSize()
{
  return elementData.length;
}

That will give you the underlying array's size.  But at the end of the day, do you need to go through all this trouble?  This is the beauty of java:  You don't WANT to know how the sausage is made! :D
0
 
zzynxSoftware engineerCommented:
>> I've never needed that type of perfomance tuning
Me neither
>> but it's a good academic excercise
:°)
0
 
enterciteAuthor Commented:
Thanks everyone...

 You know how sometimes a programmer wants to prove a point more than what it is really worth. This is a good example of that. I know it wont in the grand scheme of things change anything. I dont want to reverse-engineering anything. I just wanted to prove that it safes nothing by setting the default to 1 and adding an item versus not setting the capacity and adding one. The code provided by zzynx does just that.

Thanks.

-ec
0
 
zzynxSoftware engineerCommented:
Thanks for accepting
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.