Processing 1.0 - Processing Discourse - Hashmap vs Array speed

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Syntax Questions › Hashmap vs Array speed

‹ Previous Topic | Next Topic ›

Pages: 1

Hashmap vs Array speed (Read 1542 times)

Jeremy Abel

Hashmap vs Array speed
Jan 21^st, 2010, 8:36am

So I have this function that takes a source color, and maps it to the nearest color that is a member of a Hashmap color pallet:

Code:

color getClosestColor(color sourceColor) {
  int targetID = 0;
  double smallestDistance = 999999999;
  
  // Convert color to vector
  PVector c = new PVector( (sourceColor >> 16) & 0xFF, (sourceColor >> 8) & 0xFF, sourceColor & 0xFF );

  // Find closest
  for (int i = 0; i < pallet.size(); i++) {
    // Get pallet color as a vector
    int palletColor = int(pallet.get(i).toString());
    PVector p = new PVector( (palletColor >> 16) & 0xFF, (palletColor >> 8) & 0xFF, palletColor & 0xFF );
    
    // Calculate distance
    int currentDistance = int(c.dist(p));
    
    // Replace larger distances
    if (currentDistance < smallestDistance) {
	smallestDistance = currentDistance;
	targetID = i;
    }
  }
  return int(pallet.get(targetID).toString());

Would it be faster to just have a plain array of PVectors to represent the pallet, which would allow me to avoid the int(pallet.get(i).toString()) business? Or, since I'm only processing a 160x120 image, would the speedup not be noticeable?

JR Full Member Offline Posts: 149	Re: Hashmap vs Array speed Reply #1 - Jan 21^st, 2010, 9:07am Why do you need the toString business?

Jeremy Abel YaBB Newbies Offline Posts: 7	Re: Hashmap vs Array speed Reply #2 - Jan 21^st, 2010, 9:09am because HashMap.get(i) returns an Object, which, to my knowledge, can't really be changed into anything else. I put an int in, but it gives me back an Object, so I use toString() to get that object as a string, which is much more useful.

Re: Hashmap vs Array speed
Reply #3 - Jan 21^st, 2010, 9:15am

Your hashmap contains a color correct?

If so, try:

color c = (Integer)(hash.get(i));

And I'd get rid of the hashmap altogether because you use an int as the key, so you should _always_ use an array (or ArrayList, Vector, ...). (Unless you have a large key-domain and a sparsely populated list of objects, but I'm assuming that's not the case)

PhiLho

Re: Hashmap vs Array speed
Reply #4 - Jan 21^st, 2010, 9:21am

Jeremy Abel wrote on Jan 21^st, 2010, 8:36am:

would the speedup not be noticeable

The only definitive answer... would be to code the alternative and measure the speeds!

If the ID are contiguous, or not too sparse, using an array is certainly faster! HashMap are more designed for non-numerical keys. And has some overhead, as it has to wrap the int ID in an Integer object, hash it, access the data, unwrap it...
Now, I don't know if the speed gain is interesting.
I wonder why you chose to use HashMap.

About the toString: it is probably more efficient (and logical) to do something like:
Code:

return ((Integer) pallet.get(targetID)).intValue();

(Could use auto-unboxing, I use intValue to prove the point)

Jeremy Abel

Re: Hashmap vs Array speed
Reply #5 - Jan 21^st, 2010, 9:25am

yes. if it helps, here's the code that sets up the hashmap.

Code:

HashMap makePallet(PImage img) {
  HashMap pallet = new HashMap();
  int i = 0;
  
  for (int y = 0; y < img.height; y++) { 
    for (int x = 0; x < img.width; x++) {
	color c = img.get(x, y);
	if (pallet.containsValue(c) == false) {
	  pallet.put(i, c);
	  i++;
	}
    }
  }
  return pallet;
}

I used a hash map because it enabled me to simply check whether or not an item is in the hashmap. I'll write a contains() function for arrays too, and then test the speed, I suppose.

Jeremy Abel YaBB Newbies Offline Posts: 7	Re: Hashmap vs Array speed Reply #6 - Jan 21^st, 2010, 9:46am Yep, array's are definitely faster in this case. Thanks for the help!

davbol

Re: Hashmap vs Array speed
Reply #7 - Jan 21^st, 2010, 2:08pm

fwiw...

depends on what's taking the most time, building or searching.

a hashmap would be a good choice for building your unique palette, but not necessarily the best for searching it by "closest" (which implies full iteration on either of those datatypes)

you'd add your colors like this: "if (!pallet.containsKey(c)) pallet.put(c,c);" using the color itself as the key- since searching for keys is wayyy faster than searching for values. And now use a proper Iterator in your search code, since that old "i" key no longer exists. (or convert it back to an array: ar = hm.keySet().toArray();)

for searching, the choice of array vs hashmap is probably trivial compared to all those sqrt()'s from calling PVector's dist(). you only need to compare distance-squared, which you can calc yourself and save a ton of unnecessary heavy math calls.

beyond that, some sort of octree (or kd, or etc/equiv) datatype is probably what you'd need to optimize the "who is nearest to me in 3-space?" question of your search. then you have to determine if it's worth the time building it compared to what you gain searching it.

Pages: 1

‹ Previous Topic | Next Topic ›