之前在《换个角度看数据结构,可以让编程更高效》我们学习了两种数据结构,并明白了选择合适的数据结构将会显著地提升代码的性能。即使是像数组和集合这样相似的两种数据结构,在高负荷的运行环境下也会表现得天差地别。
而今天,你将会发现,就算数据结构确定了,代码的速度也还会受另一重要因素影响,那就是算法。
算法这个词听起来很深奥,其实不然。它只是解决某个问题的一套流程。准备一碗麦片的流程也可以说是一种算法,它包含以下4 步(对我来说是4 步吧)。
(1) 拿个碗。
(2) 把麦片倒进碗里。
(3) 把牛奶倒进碗里。
(4) 把勺子放到碗里。
在计算机的世界里,算法则是指某项操作的过程。之前我们研究了4 种主要操作,包括读取、查找、插入和删除。下面我们还是会经常提到它们,而且一种操作可能会有不止一种做法。也就是说,一种操作会有多种算法的实现。
我们很快会看到不同的算法能使代码变快或者变慢——高负载时甚至慢到停止工作。不过,现在我们先来认识一种新的数据结构:有序数组。它的查找算法就不止一种,我们将会学习如何选出正确的那种。
有序数组跟之前讨论的数组几乎一样,唯一区别就是有序数组要求其值总是保持有序(你猜对了)。即每次插入新值时,它会被插入到适当的位置,使整个数组的值仍然按顺序排列。常规的数组则并不考虑是否有序,直接把值加到末尾也没问题。
以数组[3,17,80,202]为例。
假设这是个常规的数组,你准备将75 插入,那就可以把它放到尾端,如下所示。
计算机只要1 步就能完成这种操作。
但如果这是一个有序数组,你就必须要找到一个适当的位置,使插入75 之后整个数组依然有序。
做起来可不像说的那么简单。整个过程不可能一步完成,因为计算机需要先找出那个适当的位置,然后将其及以后的值右移来腾出空间给75。下面就来介绍分解的步骤。
先回顾一下原始的数组。
第1 步:检查索引0 的值,看75 应该在它的左边还是右边。
因为75 大于3,所以75 应该在它右边的某个位置。而具体的位置,目前还是不能确定,于是,再检查下一个格子。
第2 步:检查下一格的值。
因为75 大于17,所以继续。
第3 步:检查下一格的值。
这次是80,大于75。因为这是第一次遇到大于75 的值,可想而知,必须把75 放在80 的左侧以使整个数组维持有序。但要在这里插入75,还得先将它的位置空出来。
第4 步:将最后一个值右移。
第5 步:将倒数第二个值右移。
第6 步:终于可以把75 插入到正确的位置上了。
可以看到,往有序数组中插入新值,需要先做一次查找以确定插入的位置。这是它跟常规数组的关键区别(在性能方面)之一。
虽然插入的性能比不上常规数组,但在查找方面,有序数组却有着特殊优势。
之前我们介绍了常规数组的查找方式:从左至右,逐个格子检查,直至找到。这种方式称为线性查找。
接下来看看有序数组的线性查找跟常规数组有何不同。
设一个常规数组[17,3,75,202,80],如果想在里面查找22(其实并不存在),那你就得逐个元素去检查,因为22 可能在任何一个位置上。要想在到达末尾之前结束检查,那么所找的值必须在末尾之前出现。
然而对于有序数组来说,即便它不包含要找的值,我们也可以提早停止查找。假设要在有序数组[3,17,75,80,202]里查找22,我们可以在查到75 的时候就结束,因为22 不可能出现在75的右边。
以下是用Ruby 语言实现的有序数组线性查找。
因此,有序数组的线性查找大多数情况下都会快于常规数组。除非要找的值是最后那个,或者比最后的值还大,那就只能一直查到最后了。
只看到这里的话,可能你还是不会觉得这两种数组在性能上有什么巨大区别。
这是因为我们还没释放算法的潜能。这是接下来就要做的。
至今我们提到的查找有序数组的方法就只有线性查找。但其实,线性查找只不过是查找算法的其中一种而已。这种逐个格子检查直至找到为止的过程,并不是查找的唯一途径。
有序数组相比常规数组的一大优势就是它可以使用另一种查找算法。此种算法名为二分查找,它比线性查找要快得多。
你小时候或许玩过这样一种猜谜游戏(或者现在跟你的小孩玩过):我心里想着一个1 到100之间的数字,在你猜出它之前,我会提示你的答案应该大一点还是小一点。
你应该凭直觉就知道这个游戏的策略。一开始你会先猜处于中间的50,而不是1。为什么?因为不管我接下来告诉你更大或是更小,你都能排除掉一半的错误答案!
如果你说50,然后我提示要再大一点,那么你应该会选75,以排除掉剩余数字的一半。如果在75 之后我告诉你要小一点,你就会选62 或63。总之,一直都猜中间值,就能不断地缩小一半的范围。
下面来演示这个过程,但仅以1 到10 为例。
这就是二分查找的通俗描述。
有序数组相比常规数组的一大优势就是它除了可以用线性查找,还可以用二分查找。常规数组因为无序,所以不可能运用二分查找。
为了看出它的实际效果,假设有一个包含9 个元素的有序数组。计算机不知道每个格子的值,如下图所示。
然后,用二分查找来找出7,过程如下。
第1 步:检查正中间的格子。因为数组的长度是已知的,将长度除以2,我们就可以跳到确切的内存地址上,然后检查其值。
值为9,可推测出7 应该在其左边的某个格子里。而且,这下我们也排除了一半的格子,即9 右边的那些(以及9 本身)。
第2 步:检查9 左边的那些格子的最中间那个。因为这里最中间有两个,我们就随便挑了左边的。
它的值为4,那么7 就在它的右边了。由此4 左边的格子也就排除了。
第3 步:还剩两个格子里可能有7。我们随便挑个左边的。
第4 步:就剩一个了。(如果还没有,那就说明这个有序数组里真的没有7。)
终于找到7 了,总共4 步。是的,这个有序数组要是用线性查找也会是4 步,但稍后你就会见识到二分查找的强大。
以下是二分查找的Ruby 实现。
def binary_search(array, value)# 首先,设定下界和上界,以限定所查之值可能出现的区域。# 在开始时,以数组的第一个元素为下界,以最后一个元素为上界lower_bound = 0upper_bound = array.length - 1# 循环检查上界和下界之间的最中间的元素while lower_bound <= upper_bound do# 如此找出最中间的格子之索引#(无须担心商是不是整数,因为Ruby 总是把两个整数相除所得的小数部分去掉)midpoint = (upper_bound + lower_bound) / 2# 获取该中间格子的值value_at_midpoint = array[midpoint]# 如果该值正是我们想查的,那就完事了。# 否则,看你是要往上找还是往下找,来调整下界或上界if value < value_at_midpointupper_bound = midpoint - 1elsif value > value_at_midpointlower_bound = midpoint + 1elsif value == value_at_midpointreturn midpointendend# 当下界超越上界,便知数组里并没有我们所要找的值return nilend
对于长度太小的有序数组,二分查找并不比线性查找好多少。但我们来看看更大的数组。
对于拥有100 个值的数组来说,两种查找需要的最多步数如下所示。
用线性查找的话,如果要找的值在最后一个格子,或者比最后一格的值还大,那么就得查遍每个格子。有100 个格子,就是100 步。
二分查找则会在每次猜测后排除掉一半的元素。100 个格子,在第一次猜测后,便排除了50 个。
再换个角度来看,你就会发现一个规律。
长度为3 的有序数组,二分查找所需的最多步数是2。
若长度翻倍,变成7(以奇数为例会方便选择正中间的格子,于是我们把长度翻倍后又增加了一个数),则最多步数会是3。
若再翻倍(并加1),变成15 个元素,那么最多步数会是4。
规律就是,每次有序数组长度乘以2,二分查找所需的最多步数只会加1。
这真是出奇地高效。
相反,在3 个元素的数组上线性查找,最多要3 步,7 个元素就最多要7 步,100 个元素就最多要100 步,即元素有多少,最多步数就是多少。数组长度翻倍,线性查找的最多步数就会翻倍,而二分查找则只是增加1 步。
这种规律可以用下图来展示。
如果数组变得更大,比如说10 000 个元素,那么线性查找最多会有10 000 步,而二分查找最多只有14 步。再增大到1 000 000 个元素,则线性查找最多有1 000 000 步,二分查找最多只有20 步。
不过还要记住,有序数组并不是所有操作都比常规数组要快。如你所见,它的插入就相对要慢。衡量起来,虽然插入是慢了一些,但查找却快了许多。还是那句话,你得根据应用场景来判断哪种更合适。
关于算法的内容暂时就是这些。很多时候,计算一样东西并不只有一种方法,换种算法可能会极大地影响程序的性能。
同时你还应意识到,世界上并没有哪种适用于所有场景的数据结构或者算法。你不能因为有序数组能使用二分查找就永远只用有序数组。在经常插入而很少查找的情况下,显然插入迅速的常规数组会是更好的选择。
之后,我们还将需要学习如何规范地描述数据结构和算法的时间复杂度。有了这种通用的表达方式,就能更容易地观察出哪种算法符合我们的实际需求。
可以结合下面这本书,继续接下来的学习。本文内容也来源于此。
这是本数据结构与算法的入门指南,不局限于某种特定语言,没有复杂的数学公式,用通俗易懂的方式针对编程初学者介绍数据结构与算法的基本概念,培养编程逻辑。
它的主旨就是数据结构与算法,具体内容如下。
第1章和第2章,解释数据结构和算法是什么,并探索时间复杂度这一判断算法效率的概念。此过程中还会经常提及数组、集合和二分查找。
第3章,以老奶奶都听得懂的方式去揭示大O记法的本质。因为大O记法全书都会用到,所以对这一章的理解非常重要。
第4章、第5章和第6章,进一步探索大O记法,并以实例来演示如何利用它来加快代码运行速度。这一路上,还会提到各种排序算法,包括冒泡排序、选择排序和插入排序。
第7章和第8章会再探讨几种数据结构,包括散列表、栈和队列,展示它们对代码速度和可读性的影响,并学会用其解决实际问题。
第9章会介绍递归,计算机科学中的核心概念。作者对其进行了分解,考察它在某些问题上的利用价值。第10章会运用递归来实现一些飞快的算法,例如快速排序和快速选择,提升读者的算法开发能力。
第11章、第12章和第13章会探索基于结点的数据结构,包括链表、二叉树和图,并展示它们在各种应用中的完美表现。
最后一章,第14章,介绍空间复杂度。当程序运行环境的内存空间不多,或处理的数据量很大时,理解空间复杂度便显得特别重要。
——
【图灵教育】
阅读改变世界,阅读塑造人生
让我们站在巨人的肩膀上,解锁更多IT技能!
联系客服