快速对JavaScript数组进行分组

Question

我有一个包含数千个字符串的数组

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

我目前正在运行以下代码，以字符串分组并获取最大分组值：

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

有没有改进这段代码以使其运行速度更快的方法？

编辑： 结果已经出来：http://jsperf.com/javascript-array-grouping2

编辑编辑：那个测试有误。 Mike Samuel 的代码是最快的。

6000 条目测试 -> http://jsperf.com/javascript-array-grouping2

10K 条目测试 -> http://jsperf.com/javascript-array-grouping

- Joe

---

似乎需要前往http://codereview.stackexchange.com/找人来审查代码。 - Sebastian Paaske Tørholm

@Sebastian，抱歉，我还不太会提问。我能自己迁移吗？ - Joe

@Joey：我看到下面有几个不错的答案。你可以尝试使用jsperf.com进行测试，我很想看看结果。 - Flambino

@Joey：如果您希望迁移，可以标记管理员关注，但是问题在这里似乎运行良好。 :) 看你自己。 - Sebastian Paaske Tørholm

Answer 1

如果您确定这是一个热点，并且速度非常重要，我建议尝试通过内联max和map来减少数千个函数调用。

您还可以通过削减比较来加快函数体的速度。

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; }
}

最好的方法是在你关心的浏览器上进行测量。

- Mike Samuel

---

为什么要使用1 - - x而不是1 + x？ - 6502

我只是闲扯。1 - - x 是明确的数值运算，而 1 + x 如果 x 不是 nullish、布尔或数值类型可能会变成字符串拼接。不过在这种情况下这个区别是不必要的，因为 (x | 0) 肯定是数值类型，所以不可能发生字符串拼接。 - Mike Samuel

Answer 2

当然可以。我会在每个迭代过程中计算最大值，而不是每次都计算，同时还不需要使用 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];
}

编辑：正如Mike Samuel所说，使用索引而不是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];
}

- orlp

---

@Joey：第二个循环遍历分组结果，并根据输入情况循环遍历更少的元素。 - orlp

Answer 3

我认为这取决于你将在哪个JS引擎上运行此代码。另一个值得尝试的选择是使用

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

对于每个元素。

我认为可能使用常规循环会更快，因为您将使用的变量只是本地变量，而不是闭包的封闭变量（通常较慢），并且您还将节省每个元素的函数调用。如果实现可以内联此闭包，则这两个问题都不是问题，但我不知道是否有足够聪明的JS实现。

- 6502