Fast grouping of a javascript array

Question

I have an array of a couple thousand strings

['7/21/2011', '7/21/2011', '7/21/2011', '7/20/2011', etc]

I am currently, running this code to group by the string and get the max group value:

var max = 0;
var group = {};
arr.map(function (value) {
  if (group[value]) {
    group[value]++;
  } else {
    group[value] = 1;
  }
  max = Math.max(max, group[value]);
});

Are there any improvements to make this code run faster?

EDIT: The results are in: http://jsperf.com/javascript-array-grouping2

EDIT EDIT: that test was flawed. Mike Samuel's code was the fastest.

6000 entries test -> http://jsperf.com/javascript-array-grouping2

10K entries test -> http://jsperf.com/javascript-array-grouping

@Sebastian, Sorry, still new to asking questions? Can I migrate it myself? — Joe
– Joe, Commented Jul 21, 2011 at 19:42
@Joey: I see a couple of good answers below. You could try them out using jsperf.com - I'd be curious to see the results — Flambino
– Flambino, Commented Jul 21, 2011 at 20:02
@Joey: If you wish to migrate, you can flag for moderator attention, but it looks like the question worked fine here. :) Up to you, really. — Sebastian Paaske Tørholm
– Sebastian Paaske Tørholm, Commented Jul 31, 2011 at 12:27

Mike Samuel · Accepted Answer · 2011-07-21 19:44:36Z

10

If you're sure this is a hotspot and speed is really important, I would try to cut out several thousand function calls by inlining max and map.

You can also make the body of your function faster by cutting out a comparison.

var max = 0;
var group = {};
for (var i = arr.length; --i >= 0;) {
  var value = arr[i];
  var n = group[value] = 1 - -(group[value] | 0);
  if (n > max) { max = n; }
}

The best thing to do is measure on the browsers you care about.

answered Jul 21, 2011 at 19:44

Mike Samuel

121k30 gold badges230 silver badges255 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

6502 Over a year ago

why 1 - - x instead of 1 + x?

Mike Samuel Over a year ago

Just me being silly. 1 - - x is unambiguously a numeric operation while 1 + x could be string concatenation if x is not nullish, boolean, or numeric. It's an unnecessary distinction in this case though since (x | 0) is guaranteed to be numeric so there's no chance of a string concatenation happening.

orlp · Accepted Answer · 2011-07-21 19:51:25Z

3

Yes certainly. I would calculate the max last, instead of every iteration, and not use an if:

var group = {};
arr.map(function (value) {
    group[value] = (group[value] || 0) + 1;
});

var max = 0;
for (key in group) {
    if (group[key] > max) max = group[key];
}

EDIT: As Mike Samuel says you might get faster by using an index instead of map:

var group = {};
var max = 0;

for (var i = arr.length; --i >= 0;) {
    group[value] = (group[value] || 0) + 1;
}
for (key in group) {
    if (group[key] > max) max = group[key];
}

edited Jul 21, 2011 at 19:51

answered Jul 21, 2011 at 19:43

orlp

119k39 gold badges226 silver badges324 bronze badges

1 Comment

orlp Over a year ago

@Joey: The second loop goes over the grouped results and (depending on the input) will loop over a lot less elements.

6502 · Accepted Answer · 2011-07-21 19:45:30Z

2

I think it really depends on the JS engine that you will run this code on. An alternative I think it's worth a shot is using

n = group[value] = (group[value]||0) + 1;
if (n > max) max = n;

for each element.

I also think that may be using a regular loop can be faster because the variables you will use will be just locals and not closed-over variables of a closure (that are normally slower) and you will also save a function call per element. Both those problems are non-issues if the implementation can inline this closure, but I don't know if there are JS implementations smart enough for that.

answered Jul 21, 2011 at 19:45

6502

115k17 gold badges177 silver badges277 bronze badges

Collectives™ on Stack Overflow

Fast grouping of a javascript array

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related