检查数组中唯一数字的数量是否超过n

Question

正如标题所示，我需要检查数组中唯一条目的数量是否超过n。

Array.prototype.some()似乎非常适合此处，因为它会立即停止在数组中循环，因此会找到肯定的答案，因此，请不要建议滤除非唯一记录并测量结果数据集长度的方法，因为性能很重要这里。

到目前为止，我使用以下代码来检查是否存在n=2唯一数字以外的其他数字：

const res = [1,1,2,1,1,3,1,1,4,1].some((e,_,s,n=2) => s.indexOf(e) != s.lastIndexOf(e) ? false : n-- ? false : true);

console.log(res);

.as-console-wrapper { min-height: 100%}

然后返回false，显然有3个唯一数字（2,3,4）。

非常感谢您帮助找出我的（愚蠢）错误。

ps我正在寻找纯JS解决方案

Answer 1

要知道一个值是唯一的还是重复的，整个数组需要至少扫描一次（好吧，在一个非常大的数组上，可以进行测试以查看还剩下多少元素需要扫描，但是这种开销测试会使速度变慢）

该版本使用了两个Set

function uniqueLimit(data,limit) {
  let
    dup = new Set(),
    unique = new Set(),
    value = null;
  for (let i = 0, len = data.length; i < len; ++i) {
    value = data[i];
    if ( dup.has(value) ) continue;
    if ( unique.has(value) ) {
      dup.add(value);
      unique.delete(value);
      continue;
    }
    unique.add(value);
  }
  return unique.size > limit;
}

我也尝试过这个版本，使用数组：

function uniqueLimit(data, limit) {
  let unique=[], dup = [];
  for (let idx = 0, len = data.length; idx < len; ++idx) {
    const value = data[idx];
    if ( dup.indexOf(value) >= 0 ) continue;
    const pos = unique.indexOf(value); // get position of value
    if ( pos >= 0 ) {
      unique.splice(pos,1); // remove value
      dup.push(value);
      continue;
    }
    unique.push(value);
  }
  return unique.length > limit;
};

我测试了该线程中的几个解决方案，您可以在此处找到结果。如果只有几个唯一值，则使用数组的方法是最快的，但如果有很多唯一值，它很快就会变得最慢，并且在大型数组上最慢几个数量级。

更多分析

我用节点 v12.10.0 做了更多测试。在每次测试的最快方法之后对结果进行归一化。

最坏的情况：1000000 个条目，全部都是唯一的：

Set     1.00     // See this answer
Map     1.26     // See answer by Nikhil
Reduce  1.44     // See answer by Bali Balo
Array   Infinity // See this answer

最好的情况：1000000 个条目，全部相同：

Array   1.00
Set     1.16
Map     2.60
Reduce  3.43

问题测试用例：[1, 1, 2, 1, 1, 3, 1, 1, 4, 1]

Array    1.00
Map      1.29
Set      1.47
Reduce   4.25

另一个测试用例：[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1, 1,1,1 ,1,1,1,1,3,4,1,1,1,1,1,1,1,2,1,1,1, 1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5]

Array    1.00
Set      1.13
Map      2.24
Reduce   2.39

结论

使用 Set 的方法适用于小型和大型数组，并且无论是否有许多唯一值，都表现良好。如果唯一值很少，则使用数组的版本可能会更快，但如果唯一值很多，则很快就会变得非常慢。