efficient of sets over lists

[futSecGuy1990]

so im reading this chapter about sets lists and maps and one of the sections talks about the efficiency of sets over list and then it goes on to give code to demonstrate this very thing. however my results are different from the books. way different, can anyone explain to me why this is. my results say that lists are more efficient then sets. i have the output of running the code on my computer fallowed by the output given in the book.

import java.util.*;

public class SetListPerformanceTest {
	static final int N = 50000;
	
	public static void main(String[] args) {
		// Add numbers 0, 1, 2, ... N-1 to the array list
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < N; i++)
			list.add(i);
		Collections.shuffle(list); // shuffle the array list
		
		// Create a hash set,and test its performance
		Collection<Integer> set1 = new HashSet<Integer>(list);
		System.out.println("Member test time for hash set is " +
				getTestTime(set1) + " milliseconds");
		System.out.println("Remove element time for hash set is " +
				getRemoveTime(set1) + " milliseconds");
				

		// Create a linked hash set,and test its performance
		Collection<Integer> set2 = new LinkedHashSet<Integer>(list);
		System.out.println("Member test time for linked hash set is " +
				getTestTime(set2) + " milliseconds");
		System.out.println("Remove element time for linked hash set is " +
				getRemoveTime(set2) + " milliseconds");
		

		// Create a tree set,and test its performance
		Collection<Integer> set3 = new TreeSet<Integer>(list);
		System.out.println("Member test time for tree set is " +
				getTestTime(set3) + " milliseconds");
		System.out.println("Remove element time for tree set is " +
				getRemoveTime(set3) + " milliseconds");
		

		// Create a array list,and test its performance
		Collection<Integer> list1 = new HashSet<Integer>(list);
		System.out.println("Member test time for array list is " +
				getTestTime(list1) + " milliseconds");
		System.out.println("Remove element time for array list is " +
				getRemoveTime(list1) + " milliseconds");
		

		// Create a linked list,and test its performance
		Collection<Integer> list2 = new HashSet<Integer>(list);
		System.out.println("Member test time for linked list is " +
				getTestTime(list2) + " milliseconds");
		System.out.println("Remove element time for linked list is " +
				getRemoveTime(list2) + " milliseconds");
	}// END OF MAIN METHOD

	public static long getTestTime(Collection<Integer> c) {
		long startTime = System.currentTimeMillis();
		
		// Test if a number is in the collection
		for (int i = 0; i < N; i++)
			c.contains((int)(Math.random() * 2 * N));
		
		return System.currentTimeMillis() - startTime;
	}// END OF GET TEST TIME METHOD
	
	public static long getRemoveTime(Collection<Integer> c) {
		long startTime = System.currentTimeMillis();
		
		for (int i = 0; i < N; i++)
			c.remove(i);
		
		return System.currentTimeMillis() - startTime;
	}// END OF GET REMOVE TIME METHOD
}// END OF SET LIST PERFORMANCE TEST CLASS

my output >>>> books output
Member test time for hash set is 13 milliseconds >>> 20 millis
Remove element time for hash set is 9 milliseconds >> 27 millis
Member test time for linked hash set is 7 milliseconds >> 27
Remove element time for linked hash set is 12 milliseconds >>26
Member test time for tree set is 11 milliseconds >> 47
Remove element time for tree set is 22 milliseconds >> 34
Member test time for array list is 4 milliseconds >> 39802
Remove element time for array list is 1 milliseconds >> 16196
Member test time for linked list is 3 milliseconds >> 52197
Remove element time for linked list is 1 milliseconds >> 14870

[chaarmann]

Sorry to say that but your tests are written in a way that comparison results are not meaningful. That is why your results are different from the ones in the book.

You should only test the find/remove of your collection. But you are also taking in account the time of additional commands.
Line 58 for example:

 c.contains((int)(Math.random() * 2 * N));

here you are measuring the total time for the contains method (the one you want to test) plus the time for the random method, for the multiplications and for the casting to an int (the ones you do not want to test).

Second example:
In Line 38 and 46 you are creating the same collection type (HashSet) that you are testing, but in the comment above you wrote it should be an array list and a linked list. Copy-and-paste error?

Third example:
If you measure the time to remove a member at a random position, then you also adding the time to find this position.

Fourth example: You are not testing the weakest and strongest path of the algorithm:
Let us say you have a list of 1000 items and you want to find/remove the item at position 500, then you would get following times:
find: hashset (accessing directly via hash value without comparing elements directly ) is much faster than array list or linked list where you have to go through the first 500 elements and compare each one with the current.
removal: linked list (only changing the 2 pointer of previous and next element) is much faster than array list or hashset, where you have to move all 500 elements down one position to fill the gap.

What I want to say is that you should always take into account how you use these sets.
If you search by random access, or you always search for one of the first elements, or in most cases for the last elements, makes a big difference in the times you measure.