javascript - 检查 N > 2 个数组之间的相等性并获得最大性能？

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

最佳答案

如果数组中只有数字 - 使用基本 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 算法确实使用异或，所以你很好。这是 CRC 算法: https://en.wikipedia.org/wiki/Cyclic_redundancy_check

这是一些开源实现:https://github.com/emn178/js-crc/blob/master/src/crc.js 在 prima vista 上似乎遵循该算法，但我不确定它的质量如何，所以请尽职调查!

关于javascript - 检查 N > 2 个数组之间的相等性并获得最大性能？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52616603/