js array的方法—js中array对象的常用方法 收藏 0

Map 会比 Lodash 更快吗？JS 数组性能优化终极

• 本文的目的绝非压榨代码性能，本文提供通俗易懂的方法，而不需要深度学习数据结构和算法。
• 具备 Map/Set 的知识储备会有所助益，因为本文的所有示例需要使用它们。
• 对于所有示例，我们都会测评 3 种不同方案： 原生 JS 数组方法（filter/reduce/map 等） Lodash 工具库 Map/Set
• 所有示例均包含性能基准测试，因为除非我们测评，否则性能优化没有任何统计学意义。
• 在大多数中，Lodash 比 Map/Set 有过之而无不及。但我仍会表演 Map/Set 的方案，毕竟我们可能不想安装 Lodash 依赖。
• 我只表演不可变操作，因为我的大部分工作都受益于不可变操作。

代码示例

基准测试

根据基准测试，此代码在处理 10_000 到 100_000 条记录时性能差强人意，超过该阈值则无法接受。

如果此代码在浏览器运行，那么在此期间我们的网站会卡死大约 3 分钟。

代码示例

基准测试

夭寿啦！一旦高达 1_000_000 条记录，速度就会快近 4_000 倍！Lodash 绝对是正确的打开方式。

上述优化性能惊人，但能且仅能用于原始值（字符串、数字、布尔值等）。

如果我们想基于属性实现元素唯一性，那该怎么办呢？

代码示例

基准测试

虽然性能降低了一点点，但测评仍低于 100 毫秒！

代码示例

Set 的方案简单粗暴，这能奏效，因为 Set 能且仅能接受唯一值。

基准测试

测评和 Lodash 平分秋色！现在我们可以把 Lodash 删了吧！

如果我们用非原始值测评上述例子，这无法奏效，因为 Set 能且仅能识别原始值的唯一性。此乃 Map 的用武之地！

代码示例

Map 的工作机制与 Set 类似，因为键值必须唯一，虽然但是，它们的键会映射到值！

基准测试

测评比 Lodash 慢了 2 倍。

虽然但是，如果我们想避免非必要的依赖，私以为这种性能也差强人意。

代码示例

当我百度一下“JS 中的数组比较”时，StackOverflow 上爆料的首个答案是：

基准测试

测评完全达咩。100_000 条记录一共需要 30 秒，速度慢如龟速。

但一旦达到 1_000_000，就耗时将近一小时。让我们瞄一下其他方案能否成功优化。

代码示例

基准测试

舒服了。即使有 1_000_000 条记录，我们连一秒钟都不需要！

代码示例

举一反一，如果我们在非原始值的情况下测评，它不再奏效。

幸运的是，Lodash 提供了解决方案。

基准测试

测评慢了 200 毫秒，但性能仍对原生数组方法“降维打击”。

代码示例

基准测试

举一反一，测评比 Lodash 慢，但比原生数组方法快。

此方案比使用原生数组方法更快，是因为 Set.has 能奏效。Set 在存值时会计算其哈希值，并将该值存储在该键下。

这使得读写一个值需要 O(1) 时间复杂度，而 Array.includes 需要 O(n) 时间复杂度。

简直酷毙了，对不？

代码示例

基准测试

这是第一个突破 1 秒标记的优化。

测评仍比原生方法更快，但 2 倍的速度提升可能使得在项目中导入 Lodash 变得物有所值。

此操作采用 2 个具有共同属性的列表，并返回包含这些匹配对象的对象列表。

粉丝请注意：对于此操作，我们基于以下假设：

• 两个列表长度相同。
• 任一列表中都具有重复属性的元素。
• 每个列表中的每个元素在另一个列表中都有对应的元素。

代码示例

基准测试

梅开二度，使用 JS 数组方法又变慢了。

在为此操作的 Map/Set 版本进行基准测试时，我发现了另一种更高效的方案，来使用原生数组方法执行此操作。

代码示例

在此示例中，我们将其中一个列表处理为一个对象，然后在查找另一个列表的对象时索引到该列表。

基准测试

夭寿啦！使用原生 JS 数组方法，这一次并没有慢得令人窒息！

代码示例

我无法找到 Lodash 提供的开箱即用的方法，但我有一个大胆的想法。如果不满足上述任何假设，那么该方法也爱莫能助。

基准测试

令人喵瞪狗呆的是，使用 Lodash 并不能吊打原生 JS 数组的性能！

这可能因为，在实际将两个数组合并之前，需要对它们排序造成的。

代码示例

基准测试

这次原生方法可能击败了 Lodash，但在此情况下，使用 Map 似乎是其中最快的。

这些是我在这些基准测试中收获的东东。

运行这些基准测试后，我阅读了我使用的 Lodash 方法的源码。

大多数情况下，Lodash 使用 Map 和 Set 来获得这种性能。

虽然但是，Lodash 也进行了为微调，挤出了额外的性能优势。

因此，如果性能对您而言兹事体大，且您不介意导入 npm 包，那么如果您正在处理包含海量元素的数据，您可以优先使用 Lodash。

然而情况并非总是如此，因此粉丝请务必深度学习多种方案，运行基准测试。

虽然 Lodash 是最快的，但如果没有 Lodash，我们也有其他无限逼近其速度的技术方案。

运行所有基准测试后，我肯定会开始在代码中更多地使用 Set/Map。

它们不仅速度惊人，而且有手就行，并提供了良好的 API 来操作。

如果运行的数组的元素数量不超过 10_000，那可能不需要过早的性能优化。

我进行基准测试的所有操作，在该体量的数据集上执行的时间都超过 300 毫秒。

如何用 JS 实现各种数组排序？

引言

数组排序是你在 JavaScript 编程过程中经常会遇到的，也是面试中会考察的。那么思考两个问题，数据结构中稳定的排序算法和不稳定的排序算法分别有哪些？时间复杂度和空间复杂度分别代表了什么？

时间复杂度&空间复杂度

关于时间复杂度，说得更多的是通过 O(nlogn) 以及 O(n) 等来衡量。下面是一张时间复杂度的曲线图，图中用颜色区分了最优的、一般的、比较差的时间复杂度。

关于空间复杂度，就是对一个算法在运行过程中临时占用存储空间大小的度量。

各种排序的 JS 实现

数据结构算法中排序有很多种，根据它们的特性，可以大致分为两种类型：

1）比较类排序

通过比较来决定元素间的相对次序，其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。

2）非比较类排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

冒泡排序

冒泡排序是最基础的排序，一般在最开始学习数据结构的时候就会接触它。

快速排序

通过排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。

插入排序

插入排序算法描述的是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果。

选择排序

选择排序是一种简单直观的排序算法，首先将最小的元素存放在序列的起始位置，再从剩余未排序的元素中继续寻找最小元素，然后放到已排序的序列后面，以此类推，直到所有元素均排序完毕。

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子节点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列，先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为二路归并。

归并排序是一种稳定的排序算法，归并排序的性能不受输入数据的影响，但表现比选择排序好得多，代价是需要额外的内存空间。

总结

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com