以最高性能检查 N > 2 个数组之间的相等性？

Question

我想检查 n 个数组是否都包含 JavaScript 中的相同整数？什么是最有效的方法？

Answer 1

如果数组中只有数字 - 使用基本 CRC 算法的一些变体 - 每个数组的复杂度为 O(n)，因此这将是最快的 https://en.wikipedia.org/wiki/Cyclic_redundancy_check

类似的想法，计算sum(array)和product(array)，你可以用O(n)来计算这两个值。例如：

   1, 5, 6, 7 ,8      sum=27, prod=1680
   7, 8, 1, 5, 6      sum=27, prod=1680

但是

   3, 8, 5, 5, 6      sum=27, prod=3600

注意特例为 0！由于这将使产品无效，因此所有值都应使用 +1。

注2 请记住，CRC 算法背后的想法是使用一个字节或双字变量作为总数，该变量最终会溢出。

例如字节：250 + 10 = 5，因为字节在255处溢出。但是没关系，因为两个数组都会溢出并且错误报告的机会很小。我相信，如果我们努力尝试，我们可以从数学上证明这是可以的。

但是，如果您懒于计算并且需要绝对的确定性，您可以使用此方法快速过滤所有否定候选，然后仅排序+比较肯定候选。仍然比仅使用排序+比较要快得多。

注3： 刚刚意识到您正在使用 JS，而 JS 对大数字有点混乱，并且不会真正溢出算术运算。

但是它确实会因逻辑运算符而溢出，并且 CRC 算法确实使用了 xor，所以你很好。这是 CRC 算法： https://en.wikipedia.org/wiki/Cyclic_redundancy_check

这是一些开源实现：https://github.com/emn178/js-crc/blob/master/src/crc.js prima vista上好像是按照算法来的，但是我不确定它的质量如何，所以你尽职调查！

Answer 2

此解决方案避免使用 sort，使算法复杂度为 O(n²)，其中 n 是数组的数量和长度。它具有不改变数组的额外好处，还允许您传递包含任何类型的数组，而不仅仅是数字。它通过计算每个数组项的频率包来运行，然后评估它们是否都包含相同的数据。 toBag 和 bagsEqual 函数都是 O(n)。这使得主要算法 arraysSame O(n²)。使用 sort 而不是频率包会使解决方案 O(n²log(n))，这几乎没有那么有利。

function arraysSame(...arrays) {
  if(arrays.length < 2) return true;

  let bag1 = toBag(arrays[0]);
  for(let i = 1; i < arrays.length; i++) {
    const bag2 = toBag(arrays[i]);
    if(!bagsEqual(bag1, bag2)) return false;
  }

  return true;
}

function bagsEqual(bag1, bag2) {
  if(bag1.size != bag2.size) return false;

  for(const [key, value] of bag1) {
    if(!bag2.has(key)) return false;
    if(value != bag2.get(key)) return false;
  }

  return true;
}

function toBag(array) {
  const bag = new Map();

  for(const val of array) {
    const count = bag.get(val) || 0;
    bag.set(val, count + 1);
  }

  return bag;
}

以最高性能检查 N > 2 个数组之间的相等性？

Check equality between N > 2 arrays with maximum performance?

javascript

arrays

equality