提高计算效率的一种方法 -- 分类

作为程序员，我们写出来的代码的执行效率是衡量我们工作的一个重要指标，同时代码（算法）的执行效率也有衡量指标，就是时间复杂度和空间复杂度，所谓提高计算效率，这里指的就是降低算法的时间复杂度和空间复杂度，而本文的重点是如何降低时间复杂度这一层面。



从软件层面来看，提高计算效率可以有多种思路：

• 空间换时间（时间换空间），比如：缓存，索引

• 并行

• 异步

• 少做事情



本文提到的“分类”思想，对应的就是“少做事情”这个思路。我用两个例子来分析“分类”思想的运用。



快速排序

排序在计算机领域是非常常见的需求，对应的排序算法也很多。先看常见的冒泡排序和插入排序，它们都是基于数据比较的方式进行排序，时间复杂度都是O(N^2)。我们知道快速排序的时间复杂度是O(NlogN)（极端情况下会变成O(N^2)，但有方法使其概率非常低），它的计算逻辑大致如下：



1. 第一步：随机选择一个数组中的值作为枢纽值，比如88，然后将大于88的放到一边，小于或等于88的放到另一边，这样数组被分为两部分：小于等于88的和大于88的；

2. 第二步：再从上面的两部分数据中随机选择一个值作为枢纽值，比如分别为33和99，用同样的方式将每一部分又分成两部分，这时数组被分成了四部分：小于等于33，33到88，88到99，大于99。

3. 以此类推，不断将每一部分一分为二下去，直到排序完成。



从快排的计算逻辑中可以看出，每次将数据分区后，每一部分中的数据就不需要跟另一部分的数据进行比较了，这样一级一级分下去，数据比较次数就大大减少了，程序要做的事情变少了，计算效率自然就提高了。从时间复杂度也可看出快排的效率相比冒泡和插入排序是有量级上的差别的。



我们从中得到的启发是：让计算机少做事情是我们提高编码效率的重要指导思想，我们需要时刻利用这个指导思想，从不同的角度去思考如何能让程序少做事情，从而写出高效率的代码。



策略优先级

在“文本搜索”这个场景中，一种实现思路是根据匹配结果的精确度抽象成多个匹配策略，同时为了效率，多个策略会并行搜索，然后将最精确的那个结果集返回。



这里面有个“依赖”问题，就是越精确的策略的匹配结果要优先于其他策略被返回。反过来说，越精确的策略不需要等那些精确度不及它的策略返回结果。



基于上述考虑，我们会将策略分组，然后赋予不同的优先级，不同组的策略独自构建、发送请求和处理结果。高优先级的策略一旦有结果即可返回，不需要等待低优先级的策略。这也让高优先级的策略省去了等待低优先级策略的时间。



总结

对所要处理的信息或所要做的事情分门别类后，我们便可以独立地处理每个分类，在增加灵活度（对不同分类需要不同的处理策略）的同时，在某些场景下，也减少了不必要的数据操作（排序场景中的数据比较），进而提高效率。



同时，从编程领域推广到我们的学习、工作、生活方面，分类的思想依然大有用处。毕竟我们每个人的时间和精力都是有限的，如何分配我们的时间和精力来做不同的事情，需要我们对事情有个轻重缓急之分，好让我们集中时间和精力来做好最重要的事情，这样我们才能得到事半功倍的结果。