javascript - 在多维数组中查找值的最快方法？

Question

我正在创建一个在多个数组中查找值的函数，但我遇到了一些性能问题，因为数组可能非常长。到目前为止，我发现的最佳性能是这样的:

function isValInArray(arr, value) {
    var bool = false;
    var myArr = arr;
    var myVal = value;
    var i = 0;
    var j = 0;

    for (i = 0; i < myArr.length; i++) {
        for (j = 0; j < myArr[i].length; j++){
            if (myArr[i][j] === myVal ) {
               bool = true;
            }
        }
    }
    return bool;
}

我尝试了一些不同的方法，但前一个函数的性能是迄今为止最好的。

关于如何让它更快一点有什么想法吗？

Answer 1

由于您只关心某个值是否在数组中，因此您可以先将它们展平，然后使用 native 函数仅执行一次搜索。

function isValInArray(arr, value) {
  var myArr = [].concat.apply([], arr);  // from stackoverflow.com/a/10865042/1677912
  return ( myArr.indexOf(value) >= 0 );
}

我修改了@torazaburo提出的jsPerf测试，参见revision 2 。原始测试存在致命偏差，因为它只在一个小数组中搜索单个值，而该值是最后一行中的倒数第二个项目。 (递减循环会找到第二项 - 因此存在偏差。)为了反射(reflect)更真实的场景，现在:

• 样本数据较大；可配置的 10 x 100 方阵。 (OP 指出数组可能非常长。)
• 每次测试搜索三个数据点；第一个、最后一个和中间。 (这可以进一步扩展，但此选择涵盖基于循环的解决方案的最佳、最差和平均值。)
• 值是字符串而不是数字；虽然这会在一定程度上抵消搜索算法的影响，因为字符串比较比数字比较慢，但由于 OP 没有指示值的性质，所以这是一个更现实的假设。

此测试表明所有建议的解决方案都表现相似，这强化了 @torazaburo 的观点，这些类型的微优化是否值得担心是值得怀疑的。

我建议您使用最容易维护的解决方案。如果性能对您来说是一个实际问题，请使用真实反射(reflect)您情况的数据来测试您的选择。

如果您想知道，此解决方案在测试中显示为concat。