回炉重造12时辰-代码效率优化方法论(二)

回炉重造12时辰-代码效率优化方法论(二)

—-将昂贵的时间复杂度转化为廉价的空间复杂度

 

 

时间昂贵、空间廉价

  一段代码会消耗计算时间、资源空间,从而产生时间复杂度和空间复杂度,那么你是否尝试过将时间复杂度和空间复杂进行下对比呢?其实对比过后,你就会发现一个重要的现象。

  假设一段代码经过优化后,虽然降低了时间复杂度,但依然需要消耗非常高的空间复杂度。 例如,对于固定数据量的输入,这段代码需要消耗几十 G 的内存空间,很显然普通计算机根本无法完成这样的计算。如果一定要解决的话,一个最简单粗暴的办法就是,购买大量的高性能计算机,来弥补空间性能的不足。

  反过来,假设一段代码经过优化后,依然需要消耗非常高的时间复杂度。 例如,对于固定数据量的输入,这段代码需要消耗 1 年的时间去完成计算。如果在跑程序的 1 年时间内,出现了断电、断网或者程序抛出异常等预期范围之外的问题,那很可能造成 1 年时间浪费的惨重后果。很显然,用 1 年的时间去跑一段代码,对开发者和运维者而言都是极不友好的。

  

 

  这告诉我们一个什么样的现实问题呢?代码效率的瓶颈可能发生在时间或者空间两个方面。如果是缺少计算空间,花钱买服务器就可以了。这是个花钱就能解决的问题。相反,如果是缺少计算时间,只能投入宝贵的人生去跑程序。即使你有再多的钱、再多的服务器,也是毫无用处。相比于空间复杂度,时间复杂度的降低就显得更加重要了。因此,你会发现这样的结论:空间是廉价的,而时间是昂贵的。

 

数据结构连接时空

  假定在不限制时间、也不限制空间的情况下,你可以完成某个任务的代码的开发。这就是通常我们所说的暴力解法,更是程序优化的起点。

  例如,如果要在 100 以内的正整数中,找到同时满足以下两个条件的最小数字:

  (1)能被 3 整除;

  (2)除 5 余 2。

  最暴力的解法就是,从 1 开始到 100,每个数字都做一次判断。如果这个数字满足了上述两个条件,则返回结果。这是一种不计较任何时间复杂度或空间复杂度的、最直观的暴力解法。

  当你有了最暴力的解法后,就需要用上一讲的方法评估当前暴力解法的复杂度了。如果复杂度比较低或者可以接受,那自然万事大吉。可如果暴力解法复杂度比较高的话,那就要考虑采用程序优化的方法去降低复杂度了。

  为了降低复杂度,一个直观的思路是:梳理程序,看其流程中是否有无效的计算或者无效的存储。

  我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划。而降低空间复杂度的方法,就要围绕数据结构做文章了。

  降低空间复杂度的核心思路就是,能用低复杂度的数据结构能解决问题,就千万不要用高复杂度的数据结构

  经过了前面剔除无效计算和存储的处理之后,如果程序在时间和空间等方面的性能依然还有瓶颈,又该怎么办呢?前面我们提到过,空间是廉价的,最不济也是可以通过购买更高性能的计算机进行解决的。然而时间是昂贵的,如果无法降低时间复杂度,那系统的效率就永远无法得到提高。

  这时候,开发者们想到这样的一个解决思路。如果可以通过某种方式,把时间复杂度转移到空间复杂度的话,就可以把无价的东西变成有价了。在程序开发中,这种时空转移的思想也是可以使用的,而连接时间和空间的桥梁就是数据结构。对于一个开发任务,如果你能找到一种高效的数据组织方式,采用合理的数据结构的话,那就可以实现时间复杂度的再次降低。同样的,这通常会增加数据的存储量,也就是增加了空间复杂度。

  以上就是程序优化的最核心的思路,也是这个专栏的整体框架。我们简单梳理如下:

  第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。

  第二步,无效操作处理。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。

  第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移

 

 

降低复杂度的案例

  有了如上的方法论,我们给出一个例子,帮助你加深理解。

  第 1 个例子,假设有任意多张面额为 2 元、3 元、7 元的货币,现要用它们凑出 100 元,求总共有多少种可能性。假设工程师小明写了下面的代码:

public void testOne_1() {

    int count = 0;

    for (int i = 0; i <= (100 / 7); i++) {

        for (int j = 0; j <= (100 / 3); j++) {

            for (int k = 0; k <= (100 / 2); k++) {

                if (i * 7 + j * 3 + k * 2 == 100) {

                    count += 1;

                }

            }

        }

    }

    System.out.println(count);

}

  在这段代码中,使用了 3 层的 for 循环。从结构上来看,是很显然的 O( n³ ) 的时间复杂度。然而,仔细观察就会发现,代码中最内层的 for 循环是多余的。因为,当你确定了要用 i 张 7 元和 j 张 3 元时,只需要判断用有限个 2 元能否凑出 100 – 7* i – 3* j 元就可以了。因此,代码改写如下:

public void testOne_2() {

    int count = 0;

    for (int i = 0; i <= (100 / 7); i++) {

        for (int j = 0; j <= (100 / 3); j++) {

            if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {

                count += 1;

            }

        }

    }

    System.out.println(count);

}

  经过改造后,代码的结构由 3 层 for 循环,变成了 2 层 for 循环。很显然,时间复杂度就变成了O(n²) 。这样的代码改造,就是利用了方法论中的步骤二,将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。

 

 

 

  再看第二个例子。查找出一个数组中,出现次数最多的那个元素的数值。例如,输入数组 a = [1,2,3,4,5,5,6 ] 中,查找出现次数最多的数值。从数组中可以看出,只有 5 出现了 2 次,其余都是 1 次。显然 5 出现的次数最多,则输出 5。

  工程师小明的解决方法是,采用两层的 for 循环完成计算。第一层循环,对数组每个元素遍历。第二层循环,则是对第一层遍历的数字,去遍历计算其出现的次数。这样,全局再同时缓存一个出现次数最多的元素及其次数就可以了。具体代码如下:

public void testTwo_1() {

    int a[] = { 1, 2, 3, 4, 5, 5, 6 };

    int val_max = -1;

    int time_max = 0;

    int time_tmp = 0;

    for (int i = 0; i < a.length; i++) {

        time_tmp = 0;

        for (int j = 0; j < a.length; j++) {

            if (a[i] == a[j]) {

            time_tmp += 1;

        }

            if (time_tmp > time_max) {

                time_max = time_tmp;

                val_max = a[i];

            }

        }

    }

    System.out.println(val_max);

}

  在这段代码中,小明采用了两层的 for 循环,很显然时间复杂度就是 O(n²)。而且代码中,几乎没有冗余的无效计算。如果还需要再去优化,就要考虑采用一些数据结构方面的手段,来把时间复杂度转移到空间复杂度了。

  我们先想象一下,这个问题能否通过一次 for 循环就找到答案呢?一个直观的想法是,一次循环的过程中,我们同步记录下每个元素出现的次数。最后,再通过查找次数最大的元素,就得到了结果。

  具体而言,定义一个 k-v 结构的字典,用来存放元素-出现次数的 k-v 关系。那么首先通过一次循环,将数组转变为元素-出现次数的一个字典。接下来,再去遍历一遍这个字典,找到出现次数最多的那个元素,就能找到最后的结果了。

具体代码如下:

public void testTwo_2() {

    int a[] = { 1, 2, 3, 4, 5, 5, 6 };

    Map<Integer, Integer> d = new HashMap<>();

    for (int i = 0; i < a.length; i++) {

        if (d.containsKey(a[i])) {

            d.put(a[i], d.get(a[i]) + 1);

        } else {

            d.put(a[i], 1);

        }

    }

    int val_max = -1;

    int time_max = 0;

    for (Integer key : d.keySet()) {

        if (d.get(key) > time_max) {

            time_max = d.get(key);

            val_max = key;

        }

    }

    System.out.println(val_max);

}

  我们来计算下这种方法的时空复杂度。代码结构上,有两个 for 循环。不过,这两个循环不是嵌套关系,而是顺序执行关系。其中,第一个循环实现了数组转字典的过程,也就是 O(n) 的复杂度。第二个循环再次遍历字典找到出现次数最多的那个元素,也是一个 O(n) 的时间复杂度。

  因此,总体的时间复杂度为 O(n) + O(n),就是 O(2n),根据复杂度与具体的常系数无关的原则,也就是O(n) 的复杂度。空间方面,由于定义了 k-v 字典,其字典元素的个数取决于输入数组元素的个数。因此,空间复杂度增加为 O(n)。

  这段代码的开发,就是借鉴了方法论中的步骤三,通过采用更复杂、高效的数据结构,完成了时空转移,提高了空间复杂度,让时间复杂度再次降低

 

文章知识点来源于自购课程《重学数据结构与算法》,在这里做一个简单的整理总结分析分享给大家。

敬请期待接下来会更新的博客–《回炉重造12时辰-数据处理不变应万变》。

我是帝莘,希望能在博客园和你进行技术交流和思想交流!