Collections Times

As you spend a lot of years in your career, you would be working on preparing and discussing plans, making choices from the available options, reviewing others’ work products and monitoring progress of plans. When I think I am becoming too strategic and too managerial, meaning not doing much myself, I pull myself back and try to go down to lower level, meaning do something myself. Ideally it would mean going all the way to the bare metal level on the computer, but having spent almost all my career in commercial / business application programming, I rarely venture even into the operating system code. But doing stuff with Java, is surely well within the realm of my fluency.

Participating in training of fresh programmers offers one such opportunity. This year, like the last few years, I was overseeing the training program of campus recruits in collaboration with the training department. During a review of the training material, I noticed a bullet point : Use LinkedList if frequent operation is insertion or deletion. My immediate thought was that rather than just repeating theory from book, it’s better if we ourselves back such points with our own performance test data.

So, Swapna Shetty, our training and recruitment executive and I got together and wrote a couple of programs. The first program is SetTest.java that tests HashSet, LinkedHashSet and TreeSet. It has three operations :
1) Add 2,500 integers.
2) Use an iterator and while loop to print the integers out.
3) Use a foreach loop to print the integers out.

The second program is MapTest.java that tests HashMap, LinkedHashMap and TreeMap. It first populates an ArrayList with 1000 random strings, each of 20 characters length. Then it runs three operations :
1) Put these 1000 random strings in a map, with the string as the key and the integer index as the value.
2) Use an iterator and while loop to print the key and value.
3) Use a foreach loop to print the key and value.

Here is the source code :

	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.LinkedHashSet;
	import java.util.Set;
	import java.util.TreeSet;
	public class SetTest {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println("/***************HashSet***************/");
	Set<Integer> hs = new HashSet<Integer>();
	System.out.println("/*********Insertion***********/");
	long t1 = System.currentTimeMillis();
	for(int i = 0; i < 2500; i++) {
	hs.add(i);
	}
	long t2 = System.currentTimeMillis();
	long t3 = t2 - t1;
	System.out.println("/********while-loop*************/");
	long t4 = System.currentTimeMillis();
	Iterator<Integer> i = hs.iterator();
	while(i.hasNext()) {
	Integer i1 = i.next();
	System.out.print(i1 + "\t");
	}
	long t5 = System.currentTimeMillis();
	long t6 = t5 - t4;
	System.out.println();
	System.out.println("/********for-loop*************/");
	long t7 = System.currentTimeMillis();
	for(Integer num : hs) {
	System.out.print(num + "\t");
	}
	long t8 = System.currentTimeMillis();
	long t9 = t8 - t7;
	System.out.println();
	System.out.println("/***************LinkedHashSet***************/");
	Set<Integer> lhs = new LinkedHashSet<Integer>();
	System.out.println("/*********Insertion***********/");
	long t10 = System.currentTimeMillis();
	for(int i1 = 0; i1 < 2500; i1++) {
	lhs.add(i1);
	}
	long t11 = System.currentTimeMillis();
	long t12 = t11 - t10;
	System.out.println("/********while-loop*************/");
	long t13 = System.currentTimeMillis();
	Iterator<Integer> i1 = lhs.iterator();
	while(i1.hasNext()) {
	Integer element1 = i1.next();
	System.out.print(element1 + "\t");
	}
	long t14 = System.currentTimeMillis();
	long t15 = t14 - t13;
	System.out.println();
	System.out.println("/********for-loop*************/");
	long t16 = System.currentTimeMillis();
	for(Integer num : lhs) {
	System.out.print(num + "\t");
	}
	long t17 = System.currentTimeMillis();
	long t18 = t17 - t16;
	System.out.println();
	System.out.println("/***************TreeSet***************/");
	Set<Integer> ts = new TreeSet<Integer>();
	System.out.println("/********Insertion*************/");
	long t19 = System.currentTimeMillis();
	for(int i2 = 0; i2 < 2500; i2++) {
	ts.add(i2);
	}
	long t20 = System.currentTimeMillis();
	long t21 = t20 - t19;
	System.out.println("/********while-loop*************/");
	long t22 = System.currentTimeMillis();
	Iterator<Integer> i2 = ts.iterator();
	while(i2.hasNext()) {
	Integer element2 = i2.next();
	System.out.print(element2 + "\t");
	}
	long t23 = System.currentTimeMillis();
	long t24 = t23 - t22;
	System.out.println();
	System.out.println("/********for-loop*************/");
	long t25 = System.currentTimeMillis();
	for(Integer num : ts) {
	System.out.print(num + "\t");
	}
	long t26 = System.currentTimeMillis();
	long t27 = t26 - t25;
	System.out.println();
	System.out.println("/******************Summary of Times*********************/");
	System.out.println("/***************HashSet***************/");
	System.out.println("Time taken for Insertion: " + t3);
	System.out.println("Time taken for iterating and printing using while loop is: " + t6);
	System.out.println("Time taken for iterating and printing using for-each loop: " + t9);
	System.out.println();
	System.out.println("/***************LinkedHashSet***************/");
	System.out.println("Time taken for Insertion: " + t12);
	System.out.println("Time taken for iterating and printing using while loop is: " + t15);
	System.out.println("Time taken for iterating and printing using for-each loop: " + t18);
	System.out.println();
	System.out.println("/***************TreeSet***************/");
	System.out.println("Time taken for insertion: " + t21);
	System.out.println("Time taken for iterating and printing using while loop is: " + t24);
	System.out.println("Time taken for iterating and printing using for-each loop: " + t27);
	}
	}

view raw SetTest.java hosted with ❤ by GitHub

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.LinkedHashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.Random;
	import java.util.TreeMap;
	public class MapTest {
	/**
	* @param args
	*/
	static final String AB = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	static Random rnd = new Random();
	public static void main(String[] args) {
	List<String> al = new ArrayList<String>();
	al = randomString(20);
	System.out.println("/************HashMap****************/");
	Map<String, Integer> map = new HashMap<String, Integer>();
	System.out.println("/***********Insertion***************/");
	long t1 = System.currentTimeMillis();
	for (int i = 1; i < 1000; i++) {
	map.put(al.get(i), i);
	}
	long t2 = System.currentTimeMillis();
	long t3 = t2 - t1;
	System.out.println("/***********while-loop***************/");
	long t4 = System.currentTimeMillis();
	Iterator<String> i = map.keySet().iterator();
	while(i.hasNext()) {
	String key = (String) i.next();
	System.out.println(key + " = " + map.get(key));
	}
	long t5 = System.currentTimeMillis();
	long t6 = t5 - t4;
	System.out.println();
	System.out.println("/***********for-loop***************/");
	long t7 = System.currentTimeMillis();
	for(String s : map.keySet()) {
	System.out.println(s + " = " + map.get(s));
	}
	long t8 = System.currentTimeMillis();
	long t9 = t8 - t7;
	System.out.println();
	System.out.println("/************LinkedHashMap****************/");
	Map<String, Integer> lhmap = new LinkedHashMap<String, Integer>();
	System.out.println("/***********Insertion***************/");
	long t10 = System.currentTimeMillis();
	for (int i1 = 1; i1 < 1000; i1++) {
	lhmap.put(al.get(i1), i1);
	}
	long t11 = System.currentTimeMillis();
	long t12 = t11 - t10;
	System.out.println("/***********while-loop***************/");
	long t13 = System.currentTimeMillis();
	Iterator<String> it = lhmap.keySet().iterator();
	while(it.hasNext()) {
	String key = (String) it.next();
	System.out.println(key + " = " + lhmap.get(key));
	}
	long t14 = System.currentTimeMillis();
	long t15 = t14 - t13;
	System.out.println();
	System.out.println("/***********for-loop***************/");
	long t16 = System.currentTimeMillis();
	for(String s : lhmap.keySet()) {
	System.out.println(s + " = " + lhmap.get(s));
	}
	long t17 = System.currentTimeMillis();
	long t18 = t17 - t16;
	System.out.println("/************TreeMap****************/");
	Map<String, Integer> tmap = new TreeMap<String, Integer>();
	System.out.println("/***********Insertion***************/");
	long t19 = System.currentTimeMillis();
	for (int i2 = 1; i2 < 1000; i2++) {
	tmap.put(al.get(i2), i2);
	}
	long t20 = System.currentTimeMillis();
	long t21 = t20 - t19;
	System.out.println();
	System.out.println("/***********while-loop***************/");
	long t22 = System.currentTimeMillis();
	Iterator<String> it1 = tmap.keySet().iterator();
	while(it1.hasNext()) {
	String key = (String) it1.next();
	System.out.println(key + " = " + tmap.get(key));
	}
	long t23 = System.currentTimeMillis();
	long t24 = t23 - t22;
	System.out.println();
	System.out.println("/***********for-loop***************/");;
	long t25 = System.currentTimeMillis();
	for(String s : tmap.keySet()) {
	System.out.println(s + " = " + tmap.get(s));
	}
	long t26 = System.currentTimeMillis();
	long t27 = t26 - t25;
	System.out.println();
	System.out.println("/******************Summary of Times*********************/");
	System.out.println("/***************HashMap***************/");
	System.out.println("Time taken for Insertion: " + t3);
	System.out.println("Time taken for iterating and printing using while loop: " + t6);
	System.out.println("Time taken for iterating and printing using for-each loop: " + t9);
	System.out.println();
	System.out.println("/***************LinkedHashMap***************/");
	System.out.println("Time taken for Insertion: " + t12);
	System.out.println("Time taken for iterating and printing using while loop: " + t15);
	System.out.println("Time taken for iterating and printing using for-each loop: " + t18);
	System.out.println();
	System.out.println("/***************TreeMap***************/");
	System.out.println("Time taken for insertion: " + t21);
	System.out.println("Time taken for iterating and printing using while loop: " + t24);
	System.out.println("Time taken for iterating and printing using for-each loop: " + t27);
	}
	static List<String> randomString(int len) {
	StringBuffer sb = new StringBuffer();
	ArrayList<String> al = new ArrayList<String>();
	for(int word = 0; word < 1000; word++) {
	for( int i = 0; i < len; i++ ) {
	int idx = new Random().nextInt(AB.length());
	sb.append(AB.charAt(idx));
	}
	al.add(sb.toString());
	sb.setLength(0);
	}
	return al;
	}
	}

view raw MapTest.java hosted with ❤ by GitHub

Using jdk 1.6, we ran the programs on three computers -
1) My Windows laptop : Dell Latitude E6410 with Microsoft Windows 7 on Intel Core i5 M520 processer @2.40 GHz speed. [S1]
2) Swapna’s desktop : Microsft Windows XP Professional with Intel Pentium 4 processor @2.40 GHz speed. [S2]
3) My Apple iMac : OS X 10.8 (Mountain Lion) on Intel Core 2 duo @2.4 GHz speed. [S3]
We ran each program four times and took the averages. The complete results are in the xls on mediafire.

Set ------------ HashSet----------- LinkedHashSet----------- TreeSet
S1
Insertion---------- 2.75 ----------- 5.25 ----------- 22
while-print------- 451.75 ----------- 350.25 ----------- 161.25
foreach-print---- 328 ----------- 239.75 ----------- 161.25

S2
Insertion---------- 7.5 ----------- 12 ----------- 31.25
while-print------- 183.75 ----------- 70.25 ----------- 62.5
foreach-print---- 74 ----------- 90 ----------- 46.75

S3
Insertion---------- 3.75 ----------- 8 ----------- 22
while-print------- 86.75 ----------- 62.75 ----------- 161.25
foreach-print---- 91.75 ----------- 89.25 ----------- 20.75

Map ------------ HashMap----------- LinkedHashMap----------- TreeMap
S1
Insertion---------- 4.5 ---------- 1.75 ----------- 5.25
while-print------- 365 ----------- 129.25 ----------- 140.5
foreach-print---- 147.25 ----------- 192 ----------- 120.25

S2
Insertion---------- 4 ----------- 7.75 ----------- 35.25
while-print------- 155.75 ----------- 66.25 ----------- 281.25
foreach-print---- 82.5 ----------- 74.25 ----------- 101.5

S3
Insertion---------- 1.75 ----------- 2.75 ----------- 7.25
while-print------- 84 ----------- 41.5 ----------- 49.25
foreach-print---- 39.25 ----------- 44.5 ----------- 54.5

So here are the observations. In set operations, HashSet was the fastest for insertion. It took 2.75 ms on S1, my Windows laptop, 7.5 ms on S2, Swapna’s desktop and 3.75 ms on S3, my iMac. LinkedHashSet took twice the time and TreeSet took about four times the time of HashSet.

For iterating and printing the members, TreeSet performed the fastest. It took 161.25 ms on S1 for both while and foreach, 62.5 ms / 46.75 ms (while / foreach) on S2, and 23 / 20.75 ms (while / foreach) on S3. The for-each loop is faster than the while loop in 2 out of the 3 systems.

Since HashSet is not concerned with preserving insertion order or maintaining elements in a sorted order, it performs the fastest for insertion operation. Iteration is the fastest for TreeSet, probably because it is implemented using arrays for which index-based traversal makes our iteration very fast.

For maps, we ran into some confusion. For insertion, HashMap was the fastest on S2 and S3 whereas LinkedHashMap was the fastest on S1. For iteration, LinkedHashMap was the fastest on S2. On S1, while-loop iteration was fastest by LinkedHashMap whereas the foreach iteration was fastest by TreeMap. On S3, HashMap was the fastest for insertion, LinkedHashMap was the fastest with while-loop iteration and HashMap was the fastest with foreach loop iteration. Meaning there are no consistent results across systems.

These results are only indicative, they are in no way helpful in making a choice. You choose the data structure depending on your need. HashSet is the basic data structure implementing the Set interface and it’s what you would use if having unique elements is your criteria. In addition, LinkedHashSet preserves the insertion order. TreeSet maintains the elements in a sorted order. With regard to map, perhaps they are implemented in different ways in different jdks.