前景

首先通讯录中就有接近十万条数据，而产品要求用户发短信时能够直接选择全部用户，并且还能够手动取消勾选某个用户。需求不难，后端提供了返回通讯录全部数据的接口，我只需要维护一个id数组，并且在用户进行select, selectAll, selectCancel, selectAllCancel这四个情况下进行相应的操作即可。 但是一通实现下来发现，性能很差，甚至在selectAllCancel时可能需要等待3~4秒才有反应， 这怎么能忍！最终通过使用合理的数据结构来进行时间复杂度的优化，使其基本无感知更新。

原本实现

在取消全选时会触发onSelectAllCancel函数，但是selects是一个空的数组，因此额外用一个pageMembers来保存了当前分页内的数据。 思路也很简单，看当前分页的数据是否记录在维护的allMember中，存在的话就把它删掉。但是反应真的很慢，后来问了Chat GPT老师，才知道是splice的问题，之前大概知道splice性能不好，因为对某个元素进行删除，会导致后续下标的元素都要更新下标。 这次就来看看具体是为啥。

最新实现

分析

第一段代码中的问题：

1. 使用 forEach 循环遍历 pageMembers.value 数组，并在其中执行查找和删除操作，这样做的时间复杂度为 O(n^2)，其中 n 是 allMember.value 和 pageMembers.value 数组的长度之和。

1. 每次调用 splice 方法都会导致数组的重新排序和重新索引，如果 allMember.value 数组很大，这样的操作开销会很大。

第二段代码的优点：

1. 使用 Set 数据结构创建了一个 idsToRemove 集合，其中包含了需要移除的元素的 id。

1. 使用 map 方法从 pageMembers.value 数组中提取所有的 id，并使用 Set 的 has 方法来快速检查元素是否存在于集合中，其时间复杂度为 O(1)。

1. 使用 filter 方法，根据 idsToRemove 集合中的 id 进行过滤操作，这样的时间复杂度为 O(n)。

因此，第二段代码的性能更好，因为它避免了在循环内部执行删除操作，并且使用了 Set 数据结构来提高查找效率，以及使用 filter 方法来优雅地过滤数组。

总结下来就两点

1. 之前的实现时间复杂度是O(n^2),而使用Set这个数据结构，其提供的has方法进行查询是O(1)的，因此降低了一个数量级，最终时间复杂度变成了O(n)。

1. splice操作会导致数组重新排序和重新建立索引，性能开销会比较大，不如filter一次遍历建立数组

杂谈

突然想到去年实习的时候也是遇到过同样类似的场景，当时写的时候不由自主的就想到用Map建立一个映射，但是现在反而没有太多这种思考了，果然不能太掉以轻心，时刻得提醒自己如何写出优雅高效的代码。

Prev

🆚开发一个VSCode插件

Next

🅱️ 优化一下打包部署流程