?
Solved

ArrayLists - using initial capacity constructor

Posted on 2005-04-06
12
Medium Priority
?
480 Views
Last Modified: 2012-05-05
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() );
        }

    }

}
0
Comment
Question by:entercite
  • 7
  • 2
  • 2
  • +1
12 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 13717502
You could try with Vector() which has a capacity() method
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13717555
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
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13717640
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 37

Expert Comment

by:zzynx
ID: 13717733
>> 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
 
LVL 37

Accepted Solution

by:
zzynx earned 200 total points
ID: 13717773
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13717807
FYI: defaultList always takes about 100 ms less then oneMember.
Which seems to indicate that using new ArrayList(1) has no benefit.
0
 
LVL 29

Expert Comment

by:bloodredsun
ID: 13717940
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
 
LVL 2

Expert Comment

by:SuperKarateMonkey
ID: 13718022
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
 
LVL 2

Expert Comment

by:SuperKarateMonkey
ID: 13718090
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13718148
>> I've never needed that type of perfomance tuning
Me neither
>> but it's a good academic excercise
:°)
0
 

Author Comment

by:entercite
ID: 13719066
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
 
LVL 37

Expert Comment

by:zzynx
ID: 13724335
Thanks for accepting
0

Featured Post

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
The viewer will learn how to implement Singleton Design Pattern in Java.
Suggested Courses
Course of the Month15 days, 16 hours left to enroll

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question