Monday, August 15, 2011

Time cost for creating a HashSet from an ArrayList

I ran this simple test to get a "feel":
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;

public class Test {
 public static void main(String... args) {
  List<String> bigList = new ArrayList<String>();
  List<String> smallList = new ArrayList<String>();

  Random random = new Random();

  // builds a 10000 items list made of items
  // with string values generated from random
  // numbers between 1000000 and 1999999
  // this list has a higher chance to have duplicates
  for (int i = 0; i < 10000; i++)
   smallList.add(String.valueOf(random.nextInt(1000000) + 1000000));

  // builds a 1000000 items list made of items
  // with string values generated from random
  // numbers between 1000000 and 1999999
  for (int i = 0; i < 1000000; i++)
   bigList.add(String.valueOf(random.nextInt(1000000) + 1000000));

  int tests = 100;
  
  double smallListTransformationsTotalTime = 0;
  
  for (int i = 0; i < tests; i++) {
   long start = System.currentTimeMillis();
   new HashSet<String>(smallList);
   long end = System.currentTimeMillis() - start;
   smallListTransformationsTotalTime += end;
  }  
  System.out.println("Small list transformation average: " + (smallListTransformationsTotalTime / tests));
  
  double bigListTransformationsTotalTime = 0;
  
  for (int i = 0; i < tests; i++) {
   long start = System.currentTimeMillis();
   new HashSet<String>(bigList);
   long end = System.currentTimeMillis() - start;   
   bigListTransformationsTotalTime += end;
  }
  System.out.println("Big list transformation average: " + (bigListTransformationsTotalTime / tests));  
 }
}
Running this (100 tests) on my computer (i7 quad core using eclipse) yielded the following:

  • Small list transformation averaged 0.81ms 
  • Big list transformation averaged 196.31ms