背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

数据结构为何重要

数据结构

数据是一个宽泛的术语，可以指代所有类型的信息。最基本的数据就是数和字符串。事实上，即便最复杂的数据通常也是由数和字符串组成的。

数据结构指的是数据的组合方式。

array = ["Hello! ", "How are you ", "today?"]
print array[0] + array[1] + array[2]

数据结构不仅仅是数据的组合方式，还会极大地影响代码运行速度。你组合数据的方式可能会让程序的运行速度提高或者降低几个数量级。如果要写一个处理大量数据的程序，或是开发一个允许上千人同时访问的网页应用，那么你选择的数据结构可能直接决定软件会不会因为负载太高而崩溃。

数组：基础数据结构

数组是计算机科学中最基本的数据结构之一。我猜你以前用过数组，所以大概知道数组就是一系列数据元素。数组的用途广泛，在许多场合能发挥作用。

数组大小指的是数组能存放的数据元素的数量。

数组的索引可以用来标记数据在数组中的位置。在大多数编程语言中，索引从0开始。

许多数据结构有以下4种基本使用方法，我们称其为操作。

• 读取：从数据结构的特定位置查看某数据。对数组来说，就是查看特定索引的值。
• 查找：寻找数据结构中的特定值。对数组来说，就是检查数组中是否存在这个值。如果存在，就检查它的索引。
• 插入：向数据结构中添加新的值。对数组来说，就是给数组增加一个位置，在里面添加一个新值。
• 删除：从数据结构中移除一个值。对数组来说，这意味着把其中一项移除。如果把"bananas"从购物清单中去掉，就从数组中删除了这个值。

速度计量

1、如何衡量一个操作的速度呢？

衡量一个操作的“速度”时，不是用纯粹的时间长短，而是用步骤数来衡量。

2、为什么用步骤数来衡量代码的速度呢？

因为我们永远不能确定一个操作所需的时间。一段代码在某一台计算机上可能需要5秒运行完成，而在旧计算机上可能运行得更久。相同的代码在未来的超级计算机上可能运行得更快。因为运行时间与硬件有关，所以用时间来衡量一个操作的速度是不可靠的。

不过，用所需计算步骤的数量就能衡量操作的速度了。如果操作A需要5步，操作B需要500步，那么就可以说在任何硬件上操作A都比操作B快。因此，衡量步骤数就成了分析操作速度的关键。

集合：差之毫厘，“慢”之千里

另一个数据结构：集合。集合中包含的元素不能重复。

集合有多种类型，但本节只讨论基于数组的集合。这种集合和数组很相似，它们都是存储值的简单列表，二者的唯一区别在于，不能往集合中插入重复的值。

集合的读取和数组的读取完全一致，即计算机检查特定索引处的值只需要1步。这是因为计算机能跳转到集合内的任意索引，而这只需简单地计算并跳转到其内存地址即可。

集合的查找也和数组的查找没什么区别，即查找集合中的值最多需要N步。集合和数组的删除操作也一模一样，即要删除一个值并移动其他数据来填空最多需要N步。

集合的插入和数组的插入则不同。先来看看在集合末尾插入值。这对数组来说只需要1步，是最好的情况。但集合不同，计算机需要先判断这个值是否存在于集合中——因为集合的规则是不允许插入重复数据。

计算机要如何确保新数据不在集合中呢？记住，计算机一开始并不知道数组或者集合的格子中存储了什么值。因此，它必须先在集合中查找，才能知道要插入的值是否已经存在。只有集合中不存在这个新值的时候，计算机才能继续执行插入操作。所以，所有的插入操作都需要先进行查找。

对包含N个元素的集合来说，在集合末尾插入值最多需要N +1步。这是因为确定集合中不含该值需要N步，而实际的插入还需要1步。数组的相同操作则只需要1步。

向集合开头插入值是最坏的情况。为此，计算机需要先查找N个格子来确保该值不在集合中，然后再用N步来右移全部数据，最后再用1步来插入新值。全部加起来是2N +1步。数组的相同操作则只需要N +1步。

如果要确保数据不重复，那么集合对你来说就很重要。但如果没有这种需求，那么数组可能更适合你，毕竟数组的插入效率更高。你必须分析自己的需求，然后再决定哪个数据结构更合适。

总结

分析操作需要的步骤数是理解数据结构性能的核心。在程序中选择正确的数据结构决定了程序在处理大量数据时会不会崩溃。

阅读本文，可以帮助读者了解如何分析特定应用中数组和集合的优劣。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。