更高效的数组搜索

Question

我想根据对象的唯一属性（即键）从对象数组中提取特定对象。

在下文中，我在 'arr' 中搜索一个元素，其中键为 8。

var myElement = arr.filter(function(element) {
  return element.key === 8;
});

这行得通，但每次运行时，它都会遍历数组中的所有元素，即使在找到正确的元素之后也是如此。例如，如果它在索引 4 处找到 myElement，但数组中有 100 个元素，则该代码段的运行量比它需要的多 25 倍。

有没有更有效的方法，或者找到 myElement 时终止 filter() 的方法？

我觉得我错过了一些明显的东西......

Answer 1

for (var i=0; i<arr.length; i++) {
    if (arr[i].key === 8) {
        console.log('FOUND ITEM AT KEY '+8);
        break;
    }
}

Answer 2

您实际上想要一个 find 函数，它在第一次出现时 return 出现。如果您使用的是 ECMAScript 6 规范，则可以使用 Array.prototype.find，或者您可以实现一个简单的 find，例如：

function find8(arr) {
    // type checks skipped for brevity
    var i = 0,
        j = arr.length;

    for (; i < j; i++) {
        if (arr[i].key === 8) {
            return arr[i];
        }
    }

    throw new Error('Not found');
}

如果你想要一个更通用的解决方案，它接受谓词（即 functions 那个 return 一个布尔值），你可以编写一个更通用的函数喜欢：

function find(arr, predicate) {
    // Again, type checks skipped for brevity
    var i = 0,
        j = arr.length;

    for (; i < j; i++) {
        // Note the condition is now a call to the predicate function
        if (predicate(arr[i])) {
            return arr[i];
        }
    }

    throw new Error('Not found');
}

Answer 3

听起来像这样你会过得更好：

function findByKey(items, key) {
    for (var index = 0; index < items.length; index++) {
        var item = items[index];
        if (item.key === key) {
            return item;
        }
    }
    return null;
}

请注意，如果您的列表已排序，您可以通过进行二进制搜索来改进它。虽然我个人建议散列（假设同一个密钥没有被使用两次）。类似于：

var array = [/* your data here... */];
var map = {};

//do this once; or once each time your array changes
for (var index = 0; index < array.length; index++) {
    var item = array[index];
    map[item.key] = item;
}

//now find things by doing this
var itemWithKey8 = map[8];

Answer 4

我会用一个简单的 for 循环来处理这个问题（使用一个函数进行通用重用）：

function findObject(arr, cond)
    for (i = 0; i < arr.length; i++) {
        if (cond(arr[i]){
            return arr[i];
        }
    }
}

// now call fincObject(myArray, function(element){element.key === 8})

或者，如果您知道自己将多次执行此操作，请创建一个映射，该映射应该快很多：

function makeMapping(arr, keyFunc){
    var mapping = {};
    for (var i = 0; i < arr.length; i++) {
        mapping[keyFunc(arr[i])] = arr[i];
    }
    return mapping;
}

这个returns一个对象映射8到key.id === 8的对象。您的 keyFunc 将是：

function keyFunc(element){
    return element.key;
}

Answer 5

为什么要重新发明轮子？这里有很多类似的答案，所以我将分享一种不同的方法——到目前为止我最喜欢的方法。有一个名为 linq.js 的优秀库（包括独立版本和 jQuery 插件版本），它使搜索、过滤、排序等变得轻而易举。

var myElement = Enumerable.From(arr).FirstOrDefault(null,         function(element) {
      return element.key === 8;
});

在上面的例子中，第一个符合条件的元素被returned。如果没有找到，则为 null returned（第一个参数是 return 的默认值）。

更高效的数组搜索

More efficient array search

javascript

arrays