javascript - 有没有比 for(for()) 更快的方法来在多维数组中查找值并返回其所有索引？

Question

我需要找到二维数组的值并返回其索引。例如，如果我搜索的术语在 array[i][j] 中，那么我希望返回 [i, j]。

自然地，我想出了这个简单的解决方案:

function find(str){
    for(let o = 0; o < array.length; o++){
        for(let k = 0; k < array[o].length; k++){
            if(array[o][k] == str){
                return [o, k];
            }
        }
    }
}

现在我需要使用这个方法数百次作为算法的一部分，而且它非常耗时。有没有更有效的方法？

我创建了一个简单的完整示例，包括“基准”:

// setup to hide foo in an array
var array = [];
for(let i = 0; i < 100; i++){
    array.push([])
    for(let j = 0; j < 100; j++){
        if(i == 99 && j == 99) array[i].push("foo"); // intentionally hiding the searched term at the worst-case position for the algorithm of find()
        else array[i].push("bar");
    }
}

// function to find foo
function find(str){
    for(let o = 0; o < array.length; o++){
        for(let k = 0; k < array[o].length; k++){
            if(array[o][k] == str){
                return [o, k];
            }
        }
    }
}

// lets say we need to find foo 200 times
var a = window.performance.now();
for(let i = 0; i < 200; i++){
    console.log(i, find("foo")); // if you're happy and you know it, tell us what you found
}
var b = window.performance.now();

// print performance result
$('body').html((b-a) + " ms");

JSfiddle 基准示例:http://jsfiddle.net/3t0db1cq/11/

(注意:在那个基准测试示例中，我搜索了“foo”200次，所以你可能会问为什么我不简单地缓存它。实际上，我会搜索不同的术语，所以缓存几乎不会提高性能。而且我故意确实将搜索项放在该基准测试数组的最坏情况位置)

你能帮我找到一个更好的 find() 算法吗？为了公平地进行性能测试，如果您想比较结果，请将搜索项重新定位在算法数组中最坏情况的位置。

(目标是网站，所以所有常见浏览器都应该支持它)

Answer 1

在我看来，您正在将一个键(整数对)映射到一个字符串值，并且您想要返回该值的键。

由于您使用的是数组，因此每个搜索操作总是 O(n^2) 最坏的情况，因此没有使用该数据结构的“智能”方法

正如@Richrd所说，您可以构建从字符串值到一对整数的反向映射并进行搜索。简单的方法是使用 javascript Map() ( HashMap )。尽管您可能想研究字符串到整数映射的 trie 实现。

但这引出了一个问题:如果您要执行大量反向查找，那么为什么首先将这些数据存储为字符串的二维数组呢？您可以通过首先将此数据存储为字符串到整数的映射来节省更多时间。