optimise this script

Question

Can anyone suggest a way to shave any time off this script?

var countObject = new Object();
var length = data.length;
for(var i = 0; i < length; i += 4) {
  var key = data[i] + ',' + data[i+1] + ',' + data[i+2];
  if(typeof(countObject[key]) == 'number') {
    countObject[key]++
  } else {
    countObject[key] = 0
  }  
}

It is to build up a count of occurrences of RGB values found in data retrieved from a canvas. Presumably the data from context.getImageData() is already an optimised array type...?

EDIT: I do not require the RGB value in the format "255,255,255" necessarily, it's just all I could come up with for use as the array key. A different approach is also welcome :-D

maybe you can get rid of l=length and just use length, maybe put the ++ in front of countObject and maybe some short if.. — Huangism, Jun 20 '12 at 20:46
Thanks Ates, I should properly use the correct terminology ;-) and @Huangism I didn't realise short ifs or ++ before var name had any performance benefit... I'll have a look into it — joevallender, Jun 20 '12 at 20:51
@joevallender I read some article awhile back about the +, I am not sure if the shortcut if does anything but it's less code. Here http://stackoverflow.com/questions/1546981/post-increment-vs-pre-increment-javascript-optimization — Huangism, Jun 20 '12 at 20:52

Hamish · Accepted Answer · 2012-06-20T23:49:15.107

2

I don't know if this is going to make any significant difference (you'd have to have a lot of values to see any appreciable performance difference), but you could:

Create keys using fast bit shifting operations instead of slow string concatenation
Cut out a few steps in the assignment:

So:

for(var i = 0, l = length; i < l; i += 4) {
   var key = (data[i] << 16) + (data[i+1] << 8) + data[i];
   countObject[key] = (countObject[key] || 0) + 1;
}

EDIT: Since you mentioned getting the RGB value back from the key, here is how it's done:

/** 
 * From a color key (integer)  return an object 
 * with keys 'r', 'g' and 'b'
 */
var colorFromKey = function(key) {
   return {
      'r': (key >> 16) & 0xFF,
      'g': (key >> 8) & 0xFF,
      'b': key & 0xFF
   };
}

edited Jun 20 '12 at 23:49

answered Jun 20 '12 at 20:53

Hamish

22,860
8
53
67

Just be careful with the shifts. Each color is 8 bits, so the correct should be `data[i] << 16 + data[i+1] << 8 + data[i+2]` – linepogl Jun 20 '12 at 20:57
1

He wants `countObject[key]` initialized to 0 if it doesn't already exist, but this would initialize it to 1 unless you change the part of the assignment to `(countObject[key] || -1)`... but since 0 evals to false, there's still a problem here. Should be `typeof countObject[key] !== 'undefined' ? countObject[key] : 0;` – mVChr Jun 20 '12 at 20:59
2

@mVChr yeah, I'm wondering if that's a bug in the original code though. joevallender can you elaborate? Shortcuiting the undefined value is a useful optimization, avoiding typeof and string comparison is best if you want speed, so better to subtract 1 from all at the end if it comes down to it. – Hamish Jun 20 '12 at 21:02
Well, it 'works' so I'm not sure if there is a bug as such. If it helps for background, I'm setting this up so I can then grab the x most commonly occurring colours. Really interesting read all this though, so thanks all for the replies! – joevallender Jun 20 '12 at 21:05
I should also say that the method in the original post gained a ~25% performance increase (based on some limited testing). I'll have to see whether I incur any slowness later in the script with knock ons from changing the data format. But thanks! Very interesting – joevallender Jun 20 '12 at 21:11
Marking this one as accepted as the bitshifting seems to be where the performance increased was – joevallender Jun 20 '12 at 21:17
Actually, at the risk of just babbling to myself.. I've taken that off until I can undo the shift later in the script to regain a usable RGB value... anyway, time to turn off the laptop.. it's half ten here... thanks! – joevallender Jun 20 '12 at 21:22
@joevallender PS: since you're using an object, I got rid of the unnecessary `.toString()` which should save some time. Also fixed an operator precendence error in the key generation and added a func to turn the key back into RGB :) – Hamish Jun 20 '12 at 23:50
How foolish I was to remove to accepted answer :-) Great stuff Hamish, thanks. Nice thing to learn too! Could you put the +2 in as suggested by the first comment in case anyone finds this please. – joevallender Jun 21 '12 at 08:19

score 1 · Answer 2 · answered Jun 20 '12 at 20:55

Can anyone suggest a way to shave any time off this script?

No, seems fine, but I have some other suggestions:

var countObject = new Object(); // use {} instead, that's more common
var length = data.length; // why that? You are already using var l=...
for(var i = 0, l = length; i < l; i += 4) {
  var key = data[i] + ',' + data[i+1] + ',' + data[i+2];
  if(typeof(countObject[key]) == 'number') { // remove the brackets. typeof is no function
    countObject[key]++ // ; missing
  } else {
    countObject[key] = 0 // are you sure this should not start with 1?
  }  
}

If you have a colorful image, it may be faster to do the initialisation of the countObject before (setting every possible key to 0). Then you save the if-condition for every iteration.

Thanks for this. I actually did have {} in a previous file, I've just been messing round with the script :-) Re length, I read before you should only get the length of an array once (statement in for fired each time?) but I've unnecessarily re-assigned - I'll correct that. I'll have a look at initialising the countObject, but this happens synchronously after an image is uploaded so I guess it would end up adding to the overall time — joevallender, Jun 20 '12 at 21:08

optimise this script

2 Answers2