Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By JosAH

Thread: why is Array access by index an order of magnitude faster than Map access by key?

  1. #1
    bendcotrton is offline Member
    Join Date
    May 2013
    Posts
    1
    Rep Power
    0

    Default why is Array access by index an order of magnitude faster than Map access by key?

    theoretically, both are O(1) time complexity operations. But, the following code demonstrates that array access by index is 10x faster that map access by key. Is it simply (and exclusively) due to the overhead of computing the hashCode()?
    Java Code:
    import java.util.HashMap;
    import java.util.Random;
    
    
    public class PerfTest {
    	static HashMap<String, Double> map;
    	//static double[] array;
    	static Double[] array = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};
    	
    	static long nTimes = 1000000;
    	
    	static{
    		map = new HashMap<String, Double>();
    		map.put("1", 	new Double(1));
    		map.put("2", 	new Double(2));
    		map.put("3", 	new Double(3));
    		map.put("4", 	new Double(4));
    		map.put("5", 	new Double(5));
    		map.put("6", 	new Double(6));
    		map.put("7", 	new Double(7));
    		map.put("8", 	new Double(8));
    		map.put("9", 	new Double(9));
    		map.put("10", 	new Double(10));
    		
    		//array = new double[]{1,2,3,4,5,6,7,8,9,10};		
    	}
    
    	public static void main(String[] args){
    		
    		String asdf = "asdf" + null;
    		
    		StringBuffer sb = new StringBuffer();
    		sb.append("asdf" + null);
    		//System.out.println("asdf " + null);
    		
    		PerfTest tester = new PerfTest();
    		long timeInMap 	= tester.testHashMap();
    		long timeInArray 	= tester.testArray();
    		
    		Random rnd = new Random();
    		long startTime = System.nanoTime();
    		double sum = 0;
    		for (int i=0; i <nTimes; i++){
    			for (int j =1; j<=map.size(); j++){
    				sum += rnd.nextDouble();
    			}
    		}	
    				
    		long elapsedTime = System.nanoTime() - startTime;
    		
    		//System.out.println("Base nextDouble time: " + elapsedTime/1000000000.0);
    		//System.out.println("Time elapsed in map(in seconds): " 		+ timeInMap/1000000000.0);
    		//System.out.println("Time elapsed in array(in seconds): " 	+ timeInArray/1000000000.0);
    		
    		System.out.println("Corrected time elapsed in map(in seconds): " 		+ (timeInMap-elapsedTime)/1000000000.0);
    		System.out.println("Corrected time elapsed in array(in seconds): " 	+ (timeInArray-elapsedTime)/1000000000.0);
    	}
    	
    	private long testHashMap(){
    		long startTime = System.nanoTime();
    		
    		String str = "1";
    		Random rnd = new Random();
    		
    		for (int i=0; i <nTimes; i++){
    			double sum = 0;			
    			for (int j =1; j<=map.size(); j++){
    				//sum += map.get(String.valueOf(j));
    				//sum += map.get(String.valueOf(j)) + rnd.nextDouble();
    				sum += map.get(str) + rnd.nextDouble();								
    			}
    		}
    		long elapsedTime = System.nanoTime() - startTime;
    		
    		return elapsedTime;
    	}
    	
    	private long testArray(){
    		long startTime = System.nanoTime();
    				
    		Random rnd = new Random();
    		
    		for (int i=0; i <nTimes; i++){
    			double sum = 0;
    			for (int j=0; j< array.length; j++) {		
    				sum += array[j] +rnd.nextDouble();
    			}
    		}
    		long elapsedTime = System.nanoTime() - startTime;
    		
    		return elapsedTime;
    	}
    }

  2. #2
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,820
    Rep Power
    19

    Default Re: why is Array access by index an order of magnitude faster than Map access by key?

    There's any number of things going on there.
    O(1) does not mean "everything that's O(1) takes the same time"...it means that "accessing item A in this thing takes the same time as accessing item Z".

    As for the difference in time:
    For starters, a map needs to get the hash value for the key, get the bucket for that hash, then check fro equality...compared to just accessing an index.
    Then you have the calculation using a random number.
    For the array that's easy as it is an array of double primitives.
    For the map the compiler has had to write code to unbox the Double object into a coulbe and then do the calculation.
    So the above code compare access times anyway.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,361
    Blog Entries
    7
    Rep Power
    20

    Default Re: why is Array access by index an order of magnitude faster than Map access by key?

    Quote Originally Posted by Tolls View Post
    For the map the compiler has had to write code to unbox the Double object into a coulbe and then do the calculation.
    A 'coulbe'? Erm, yes coulbes are notably slow because they're made of sticky bits and those bits don't want flip their values. They wanted to be eeprom bits but never made it that far; nasty bits ...

    kindest regards,

    Jos ;-)
    DarrylBurke likes this.
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,820
    Rep Power
    19

    Default Re: why is Array access by index an order of magnitude faster than Map access by key?

    What can I say?
    It's a technical term.
    Not my fault you're such a hack you don't understand it...

    Or, put another way, *thrrrrrrrrrp*
    Please do not ask for code as refusal often offends.

    ** This space for rent **

Similar Threads

  1. A magnitude pole of an array problem
    By Java2012 in forum New To Java
    Replies: 8
    Last Post: 04-21-2013, 12:00 PM
  2. Replies: 1
    Last Post: 02-11-2013, 01:29 PM
  3. Replies: 0
    Last Post: 01-10-2011, 06:26 AM
  4. Default Access (package access) confusion
    By gauravrajbehl in forum New To Java
    Replies: 1
    Last Post: 11-18-2009, 10:48 AM
  5. Noob here, trying to access index in string
    By madmax2006 in forum New To Java
    Replies: 14
    Last Post: 03-08-2009, 05:08 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •