性能:findIndex与Array.prototype.map [英] Performance: findIndex vs Array.prototype.map

问题描述

在2019年，如果我正在处理长度为15000以北的对象数组，则需要按值查找对象的索引，以下哪种方法将是我最佳的性能选择吗?

In 2019, if I am handling an array of objects, with a length north of say 15000 and I need to find an index of an object by value, which of the following methods is going to be my best option performance-wise?

六岁的答案": findIndex

array.findIndex(object => foo === object.id);

Array.prototype.map

array.map(object => object.id).indexOf(foo);

推荐答案

从概念上讲，这两个摘要实现了相同的目标，但实现方式却截然不同.要了解两种解决方案的不同之处，我们首先来看一下

Conceptually, these two snippets accomplish the same goal, but they go about it very different ways. To understand how the two solutions are different, let's first look at findIndex:

findIndex方法对数组中的每个数组索引0..length-1(含)执行一次callback函数，直到找到callback返回真实值的地方.
_{^强调我的}

The findIndex method executes the callback function once for every array index 0..length-1 (inclusive) in the array until it finds one where callback returns a truthy value.
_{^{emphasis mine}}

换句话说，它会在找到您要查找的商品后立即停止. indexOf 具有类似的行为，因为它将返回找到的第一项的索引.

In other words, it will stop as soon as it finds the item you're looking for. indexOf has a similar behavior, because it will return the index of the first item found.

另一方面，查看 map :

On the other hand, looking at map:

map按顺序对数组中的每个元素调用一次provided回调函数，然后从结果中构造一个新数组.
_{^强调我的}

map calls a provided callback function once for each element in an array, in order, and constructs a new array from the results.
_{^{emphasis mine}}

换句话说，map不在乎您要搜索的项目.即使您要查找的项目是数组中的第一个项目，map仍将遍历14999个其他项目，以创建一个新的id数组.这意味着就时间复杂度(遍历所有这些项目需要更多时间)和空间复杂度(需要更多的内存来存储该临时数组)而言，您将要做大量的工作来获得相同的结果.

In other words, map doesn't care what item you're search for. Even if the item you're looking for is the first item in the array, map will still loop through 14999 other items to create a new array of id's. This means you'll end up doing quite a lot more work to achieve the same results, both in terms of temporal complexity (more time needed to loop through all those items) and spatial complexity (more memory needed to store that temporary array).

旁注:如果您使用迭代器/生成器，从某种意义上讲可以向前看"，以查看是否需要做更多的工作.但是我认为这超出了这个问题的范围.

Side note: The above is not necessarily true if you use iterators / generators, which can sort of 'look ahead' in a sense to see if more work is needed. But I think this is outside the scope of this question.

但是，如果您真的担心性能，那么对自己进行测试始终是一个好主意.这是一个快速的基准测试，用于演示这两种实现方式的相对性能.在我的机器上，我得到findIndex: 0.023ms/map+indexOf: 0.572ms.您的里程可能会有所不同:

However, if you're really concerned about performance, it's always a good idea to run a test for yourself. Here's a quick benchmark to demonstrate the relative performance of the two implementations. On my machine, I get findIndex: 0.023ms / map+indexOf: 0.572ms. Your mileage may vary somewhat:

var suite = new Benchmark.Suite();

const haystack = [];
let needle;

suite
  .add('findIndex', () => haystack.findIndex(o => o.id === needle))
  .add('map+indexOf', () => haystack.map(o => o.id).indexOf(needle))
  .on('start', () => {
    for (let i = 0; i < 15000; i++) {
      haystack.push({
        id: Math.random().toString(36).substring(7)
      });
    }
    console.log('Starting test.');
  })
  .on('cycle', () => {
    needle = haystack[Math.floor(Math.random() * haystack.length)].id;
  })
  .on('complete', () => {
    console.log('Test results (lower is better):')
    suite.forEach((bench) => {
      console.log(`  ${bench.name}: ${(bench.stats.mean * 1000).toFixed(3)}ms`);
    });
  })
  .run({
    'async': true
  });

<script src="//cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.11/lodash.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/platform/1.3.5/platform.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

这篇关于性能:findIndex与Array.prototype.map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！