Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

  




 

 

Thinking in Java
Prev Contents / Index Next

Choosing between Lists

The most convincing way to see the differences between the implementations of List is with a performance test. The following code establishes an inner base class to use as a test framework, then creates an array of anonymous inner classes, one for each different test. Each of these inner classes is called by the test( ) method. This approach allows you to easily add and remove new kinds of tests.

//: c11:ListPerformance.java
// Demonstrates performance differences in Lists.
// {Args: 500}
import java.util.*;
import com.bruceeckel.util.*;

public class ListPerformance {
  private static int reps = 10000;
  private static int quantity = reps / 10;
  private abstract static class Tester {
    private String name;
    Tester(String name) { this.name = name; }
    abstract void test(List a);
  }
  private static Tester[] tests = {
    new Tester("get") {
      void test(List a) {
        for(int i = 0; i < reps; i++) {
          for(int j = 0; j < quantity; j++)
            a.get(j);
        }
      }
    },
    new Tester("iteration") {
      void test(List a) {
        for(int i = 0; i < reps; i++) {
          Iterator it = a.iterator();
          while(it.hasNext())
            it.next();
        }
      }
    },
    new Tester("insert") {
      void test(List a) {
        int half = a.size()/2;
        String s = "test";
        ListIterator it = a.listIterator(half);
        for(int i = 0; i < reps * 10; i++)
          it.add(s);
      }
    },
    new Tester("remove") {
      void test(List a) {
        ListIterator it = a.listIterator(3);
        while(it.hasNext()) {
          it.next();
          it.remove();
        }
      }
    },
  };
  public static void test(List a) {
    // Strip qualifiers from class name:
    System.out.println("Testing " +
      a.getClass().getName().replaceAll("\\w+\\.", ""));
    for(int i = 0; i < tests.length; i++) {
      Collections2.fill(a, Collections2.countries.reset(),
        quantity);
      System.out.print(tests[i].name);
      long t1 = System.currentTimeMillis();
      tests[i].test(a);
      long t2 = System.currentTimeMillis();
      System.out.println(": " + (t2 - t1));
    }
  }
  public static void testArrayAsList(int reps) {
    System.out.println("Testing array as List");
    // Can only do first two tests on an array:
    for(int i = 0; i < 2; i++) {
      String[] sa = new String[quantity];
      Arrays2.fill(sa, Collections2.countries.reset());
      List a = Arrays.asList(sa);
      System.out.print(tests[i].name);
      long t1 = System.currentTimeMillis();
      tests[i].test(a);
      long t2 = System.currentTimeMillis();
      System.out.println(": " + (t2 - t1));
    }
  }
  public static void main(String[] args) {
    // Choose a different number of
    // repetitions via the command line:
    if(args.length > 0)
      reps = Integer.parseInt(args[0]);
    System.out.println(reps + " repetitions");
    testArrayAsList(reps);
    test(new ArrayList());
    test(new LinkedList());
    test(new Vector());
  }
} ///:~


To provide a base class for the specific tests, the inner class Tester is abstract. It contains a String to be printed when the test starts and an abstract method test( ) that does the work. All the different types of tests are collected in one place, the array tests, which is initialized with different anonymous inner classes that inherit from Tester. To add or remove tests, simply add or remove an inner class definition from the array, and everything else happens automatically.

To compare array access to container access (primarily against ArrayList), a special test is created for arrays by wrapping one as a List using Arrays.asList( ). Note that only the first two tests can be performed in this case, because you cannot insert or remove elements from an array.

The List that’s handed to test( ) is first filled with elements, then each test in the tests array is timed. The results will vary from machine to machine; they are intended to give only an order of magnitude comparison between the performance of the different containers. Here is a summary of one run:

Type

Get

Iteration

Insert

Remove

array

172

516

na

na

ArrayList

281

1375

328

30484

LinkedList

5828

1047

109

16

Vector

422

1890

360

30781

As expected, arrays are faster than any container for random-access lookups and iteration. You can see that random accesses (get( )) are cheap for ArrayLists and expensive for LinkedLists. (Oddly, iteration is faster for a LinkedList than an ArrayList, which is a bit counterintuitive.) On the other hand, insertions and removals from the middle of a list are dramatically cheaper for a LinkedList than for an ArrayListespecially removals. Vector is generally not as fast as ArrayList, and it should be avoided; it’s only in the library for legacy code support (the only reason it works in this program is because it was adapted to be a List in Java 2). The best approach is probably to choose an ArrayList as your default and to change to a LinkedList if you discover performance problems due to many insertions and removals from the middle of the list. And of course, if you are working with a fixed-sized group of elements, use an array.
Thinking in Java
Prev Contents / Index Next


 
 
   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire