您会感到有些奇怪：似乎在平日的编码进程中，单独去留意数据结构和算法已非必需，那为何还得依据场景来设计数据结构和算法呢？存有这样的念头实属正常，毕竟我们的确能够察觉到，在实际的业务范畴里，需要我们开发人员直接进行数据结构与算法设计的机遇愈发稀少。 例如：在互联网服务场景之中，性能耗费主要汇聚于数据库的 CRUD 操作上，因而鲜有关注业务内数据结构与算法设计的性能；随着越来越多的核心业务算法内置到芯片当中，对于从事嵌入式研发工作的工程师而言，主要的工作重点落在了管理配置各类硬件资源方面，所以并不会时常设计和运用数据结构与算法；众多语言以及标准库当中已然内置了丰富的数据结构与算法，不太需要开发人员亲自去设计和开发；…… 但实际上，我们过往所运用的性能优化手段（像是热点代码分析优化、编译器优化等等），对于系统性能的提升是以百分制来衡量的，这属于一种线性粒度的性能提升。举个简易的例子，倘若您在对代码进行 Profiling 分析之后，识别出了一个频繁调用的热点函数，将其内联或者优化后性能提升能够达到 3% 至 5%，就已然属于相当显著的优化提升了。而通过数据结构与算法的设计来改良的系统性能，所获取的性能收益极有可能是非线性的，甚至可能是指数级的。就拿典型的查找问题来讲，使用链表的遍历查找算法和数组向量的二分查找算法，在查找速度上的性能或许会有好几倍的差距呢！ 所以，合理地设计数据结构与算法，对于软件系统的性能提升而言极其关键当然，也许您已经系统地学习过数据结构与算法，对相关的知识原理有着较为深入的领会，也可能您对于现有的数据结构与算法的了解相对有限，但这都不会对您学习这节课的内容造成影响。我仅仅聚焦于一个视角，那便是根据业务开发中数据特征和计算逻辑的典型差别，从性能维度出发，系统性地选取和设计数据结构与算法，以此助力您在软件编码的过程中，更易于开发出高性能的软件。那么接下来，我就从剖析计算机软件执行原理开始，引领您去知晓选择不同的数据结构与算法，会给系统性能带来怎样的影响。 数据结构与算法选择对性能的影响提及数据结构与算法的开销，或许您首先想到的会是大 O 标记表示法。诚然，这是一种极为重要的算法复杂度表示方式，然而这并非衡量数据结构与算法性能的全部。 实际上，衡量数据结构与算法的实现复杂度，存在几类较为常用的指标，像是最优时间开销、最差时间开销、平均时间开销、空间使用开销、摊销时间开销。此时您可能会问：平均时间开销是决定系统负载的关键指标，那是不是只需着重关注平均时间开销就行？实则不然，不同的业务场景所关注的指标各不相同。我为您举几个例子，您便会明白：在内存资源极度受限的业务场景下，对空间使用开销的关注度会更高；对于实时性要求极高的场景，通常重点关注的是最差时间开销，而平均时间开销的意义不大；针对关注最大吞吐量的业务系统，此时平均时间开销则成为了最为重要的指标。 所以，我们不能仅仅关注平均时间开销，而是要关注对业务更具价值的指标。那么接下来，您或许还会产生这样的疑惑：是不是仅依据算法复杂度来选择算法就行？答案是否定的，相同的算法复杂度并不意味着相同的性能。要知道，性能还会受到软件编码实现方式、数据结构存储特性等诸多方面的影响。例如对于二分查找算法来说，基于循环遍历的实现和基于递归调用的实现，二者在性能上就会存在显著差异。 首先我们来看一个类定义，其中包含了一个构造函数和比较运算符，代码如下： 复制 struct Kv{char const *key; unsigned int value; Kv(const char *key, unsigned int value) : //构造函数 key(key), value(value) { }bool operator==(Kv const &rht) // 比较运算符，当两个对象实例比较时使用 {return (strcmp(key, rht.key) == 0) && (value == rht.value); }};1.2.3.4.5.6.7.8.9.10.11.12.13.那么针对这个类，我选择了两种数据结构进行记录，然后使用相同的查询算法来对比性能。 第一种数据结构类型为数组： 复制 Kv arrayKvs[] = {...}1.然后，使用 STD 标准库中的线性查找算法，算法复杂度为 O(n)，如下所示： 复制 Kv *result = std::find(std::begin(arrayKvs), std::end(arrayKvs), Kv("bbb", 2));1.第二种数据结构类型为链表： 复制 std::list listKvs;1.然后，这里我使用的也是标准库中的线性查找算法，算法复杂度为 O(n)，如下所示： 复制 std::list::iterator result = std::find(listKvs.begin(),listKvs.end(), Kv("bbb", 2));1.至此，您不妨先思考一番，上述两种实现选用了相同的算法，实现复杂度相同，那么它们的性能表现会是一致的吗？答案显然是否定的。 当运用数组时，顺序访问数据的局部性较高（数据内存地址是连续的）；但使用链表时，鉴于链表中的元素位置并非相邻，并且数据不连续，这就潜在致使内存 Cache Miss（缓存未命中）的概率大幅增加，进而导致性能开销增大。 所以，单纯的算法复杂度实际上无法精准地反映性能，数据结构对性能的影响亦十分巨大，而这一部分并未在算法复杂度上得到良好的体现。 OK，最后我们再来思考一个问题：选择数据结构与算法之后，软件性能就决定了吗？ 答案也是否定的，因为数据结构和算法转换成的二级制代码执行是否高效，会受到很多因素的影响，比如编码实现、编译优化等。这里咱们再来分析一下上述业务场景中的比较逻辑： 复制 bool Kv::operator==(Kv const &rht){return (strcmp(key, rht.key) == 0) && (value == rht.value); /*先比较字符串key, 再比较数字value */}1.2.3.4.5.倘若在这个类的所有节点数据里，近乎所有的 value 值皆不相同，并且 key 的长度较大，那么我们能够对代码中的比较顺序予以调整，因为整数比较的效率更高，能够进一步提升性能。 总之，数据结构与算法的不同编码实现过程和方式，对于软件的性能而言至关重要。您在软件实现的进程中，不但要留意数据结构和算法的选取，还需要关注其具体的编码实现过程，如此方能真正开发出高性能的软件。 好了，在明白了数据结构和算法怎样影响软件性能之后，接下来咱们就进一步探讨，如何依据领域数据的特征来挑选对应的算法。 根据领域数据特征去选择算法可能你之前已经发现了，我们从教科书上学习的数据结构与算法，通常都是标准的，但是在解决具体的业务问题时，我们需要处理的数据与算法却经常不是标准的。怎么个不标准法儿呢？我认为主要体现在以下两个方面。 一方面，很多场景的领域数据是不标准的。 在大 O 标记法当中，存在一个假定，即在任意的数据集中，通过软件所实现的算法的运行时间大致相同，然而实际上，不少算法对于数据的特性是极为敏感的。 例如针对排序算法，如果待排序的数据集已经颇为接近有序状态，那么相较于快速排序，选取直接插入排序算法的优势将会更大。咱们来看一个例子。 假设有一个数据集，其具有如下特点：数据集的规模为 10 万条；数据集完全处于乱序状态；这 10 万条数据里，有 1/3 的数值小于 1000，另外 1/3 的数值在 1000 到 2000 之间，还有 1/3 的数值大于 2000 。 那么此刻，您需要对这个数据集进行完整排序，应当如何选择算法呢？倘若您没有关注到第三点特征，选择了一个极为高效的排序算法后，确实也能够将算法复杂度降低到 O (N*log₂ N)。 但是当您留意到了第三点特征时，上述的排序过程就能够拆分为 3 个子数据集的排序，而后再将排序结果合并到一起。基于这种方式实现之后，算法复杂度就能够降低到 O (N/3log₂(N/3)) * 3 = O(Nlog₂(N/3))，从而能够进一步提升性能。 除此之外，针对上面这个业务场景，我们也不难想到，采用并发模式，将数据集中的 3 个子数据集的排序过程，通过子任务并发处理，进而就能够进一步降低业务的处理时延。 所以说，我们务必要仔细挖掘领域数据的各类特性，只要挖掘出的领域数据中的特性越多，其潜在的优化数据结构与算法的性能空间也就越大。 另一方面，业务算法通常是不标准的。 要明白，除了领域数据不规范之外，业务场景里的算法通常也并非标准的，因而我们需要依据具体的业务逻辑来设计算法，以实现性能的最大化提升，而不能仅仅照搬现有的标准算法实现。我为您举一个真实的例子，这是我曾经参与设计的一个资源调度子系统中的算法案例。为了便于您理解，我将问题进行了简化和抽象，即如何从 1000 个用户中，依照优先级选出前 10 位用户来进行资源分配。 那么面对这个问题，您所选择的算法方案会是什么呢？例如，会不会是以下这两种方案：方案 1：依据 1000 个用户的优先级进行全面排序，然后选取前 10 个；方案 2：运用冒泡排序算法，对 1000 个用户全部遍历 10 次，选出前 10 个用户。 倘若您选择方案 1，那么您将会浪费大量不必要的计算机资源，性能必然会很差。而此时，您可能很容易就想到了方案 2，认为这个方案效率颇高。那么方案 2 会是最优的解决办法吗？显然不是，我们再来看另外一个方案：方案 3：首先选取前 10 个用户作为优先级最高的 10 个，然后对 1000 个用户全面遍历一次，当某个用户的优先级超过这 10 个用户时，就更新到前 10 个用户当中。 现在您可以思考一下，方案 3 在性能上是否会优于方案 2 呢？或者是否还有其他的算法实现方式？相信在认真思考了这些问题之后，您就迈出了基于业务选择和优化算法的第一步。 实际上，对于这个案例而言，由于它的业务计算逻辑较为特殊，所以我们需要针对典型的计算逻辑，单独设计算法的实现逻辑。因此，最终我们选择了方案 3，通过针对前 10 位用户的资源分配，取得了较好的性能效果。 好的，在依据业务逻辑定制化设计算法和实现之后，我们还需要综合考量各种典型操作，才能够选出最符合业务逻辑的数据结构与算法，所以接下来咱们具体看一看。 权衡综合各种操作选择数据结构与算法我们知晓，数据结构与算法往往是一对多的关系，在业务里，针对同一个数据结构可能存在诸如排序、搜索等不同的算法业务逻辑。然而，同一个数据结构在不同算法上的性能差异是较大的，所以此时，我们就需要综合各类功能操作，进而选择数据结构和算法。 举个简单的例子，对于数据结构，颇为典型的方法包含了删除、增加、查找元素等等。当然数据结构还能够有众多其他方法，只是每种方法的操作频率各不相同，优先级也有差别，比方说：在某些业务场景中，插入和删除操作极为频繁，而查询操作极少，选择链表类数据结构进行保存会较为适宜；在有些业务场景里，插入和删除操作非常少，而查询操作频繁，故而考虑选择数组类数据结构，系统的性能会相对较好；另外，当查询操作极为频繁时，或许还需要考虑对数据保持实时排序，以进一步提升性能。 所以，为了更有效地权衡，我们在设计数据结构与算法时，有时甚至需要同时选取多种数据结构来记录数据。例如，把绝大部分的稳定数据保存在序列数组中，针对偶尔变更的数据记录保存在链表中，毕竟业务中并未限定必须使用相同的结构类型来保存相同类型的数据。 那么为了更直观地阐释从业务操作的不同频率出发，选择数据结构与算法的意义，在此我就通过两种较为典型的数据库类型的设计原理，为您举例说明一下。第一种是分析数据库，例如 ClickHouse。它绝大部分的操作请求都会聚焦在批量数据分析上，所以在设计时，就必须确保批量数据分析的性能，而这会导致数据的修改性能开销较大。第二种是文档数据库，比如 MongoDB 等。不过很多时候，我们为了追求单文档级别的 CRUD 性能，就不得不在批量数据分析计算性能上做出让步。实际上，针对大型业务系统，我们通常需要选取多种数据存储方案进行数据冗余，从而综合满足各种业务场景下的性能需求。同样，我们在业务内部设计数据结构与算法时，不能什么都想要，必须做出取舍，只有综合各类操作之后，才能够权衡利弊做出选择。 学会降低算法精确度提升性能好了，最后我要带你掌握的知识点，就是要学会降低算法精确度，以此来进一步提升系统性能。我们都知道，算法通常都是精确的、严格的，但在很多业务场景下，我们并不需要那么高的精确性。就拿我自己来说，我过去参与的诸多项目中，有过太多次降低算法精度与性能之间的权衡，所以接下来，我也用一个简单的例子来给你说明下原因。 假设现在有一个已经排序后的链表： 复制 std::list SortedKvs;1.随后，它在每个周期内都会有新数据输入，在正常状况下，每插入一条数据都需要进行遍历以寻找插入点，以此确保整个链表中的数据是有序的。通过这样对业务的分析发现，排序的正确性实际上并不需要特别高，并且经过认真的评估分析与验证后，我们发觉其实能够把待插入数据先放入链表的尾部，这样当积累了 5 到 10 条待插入数据之后，再遍历一遍链表插入所有数据，通过这种实现方式，能够将插入数据的运行开销降低好几倍。由此可见，在实际的业务场景当中，我们务必要依照性能要求标准来选取恰当的算法精确度。 好啦，我们再来看一看前面我所介绍的那个资源调度的例子，想一想，从 1000 个用户中选择 10 个高优先级用户进行资源调度，是否还有其他通过降低算法精确度来提升系统性能的方案呢？实际上，我们能够将 1000 个用户拆分成 2 个组，每个组包含 500 个用户，接着交替在 2 个组内选择 10 个高优先级用户进行资源分配。如此通过在代码实现上较小的改动，就能够在性能上提升将近一倍。但在这里您要留意一点，那就是您还需要验证调整后的算法实现是否满足了业务需求。存在许多种降低算法精确度的实现方式，您需要精确地分析并验证，选择背后的业务逻辑是否依然能够满足业务需求。 更多资讯，点击全场景直播解决方案-航天云网解决方案