精华内容
下载资源
问答
  • 下面小编就为大家带来一篇java代码效率优化方法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 代码效率优化方法

    2020-07-12 23:51:15
    代码效率优化方法论复杂度:如何衡量程序运行的效率数据结构:将“昂贵”的时间复杂度转换成“廉价”的空间复杂度 复杂度:如何衡量程序运行的效率 复杂度是什么 复杂度是衡量代码运行效率的重要的度量因素。在...

    复杂度:如何衡量程序运行的效率

    • 复杂度是什么
      • 复杂度是衡量代码运行效率的重要的度量因素。在介绍复杂度之前,有必要先看一下复杂度和计算机实际任务处理效率的关系,从而了解降低复杂度的必要性。
      • 计算机通过一个个程序去执行计算任务,也就是对输入数据进行加工处理,并最终得到结果的过程。每个程序都是由代码构成的
    • 怎么衡量复杂度
      • 实际衡量时,我们通常会围绕以下2 个维度进行。首先,这段代码消耗的资源是什么。一般而言,代码执行过程中会消耗计算时间和计算空间,那需要衡量的就是时间复杂度和空间复杂度。
      • 例子:某个十字路口没有建立立交桥时,所有车辆通过红绿灯分批次行驶通过。当大量汽车同时过路口的时候,就会分别消耗大家的时间。但建了立交桥之后,所有车辆都可以同时通过了,因为立交桥的存在,等于是消耗了空间资源,来换取了时间资源。
        在这里插入图片描述
    • 这段代码对于资源的消耗是多少
      • 我们不会关注这段代码对于资源消耗的绝对量,因为不管是时间还是空间,它们的消耗程度都与输入的数据量高度相关,输入数据少时消耗自然就少。为了更客观地衡量消耗程度,我们通常会关注时间或者空间消耗量与输入数据量之间的关系。
    • 复杂度是一个关于输入数据量 n 的函数
      • 假设你的代码复杂度是 f(n),那么就用个大写字母 O 和括号,把 f(n) 括起来就可以了,即 O(f(n))。例如,O(n) 表示的是,复杂度与计算实例的个数 n 线性相关;O(logn) 表示的是,复杂度与计算实例的个数 n 对数相关。
    • 线型相关解释:在向量空间V的一组向量A: 在这里插入图片描述,如果存在不全为零的数 k1, k2, ···,km , 使
      在这里插入图片描述
      则称向量组A是线性相关的 ,否则数 k1, k2, ···,km全为0时,称它是线性无关。
      由此定义看出 在这里插入图片描述是否线性相关,就看是否存在一组不全为零的数 k1, k2, ···,km使得上式成立。
      即是在这里插入图片描述看这个齐次线性方程组是否存在非零解,将其系数矩阵化为最简形矩阵,即可求解。此外,当这个齐次线性方程组的系数矩阵是一个方阵时,这个系数矩阵存在行列式为0,即有非零解,从而在这里插入图片描述 线性相关。
    • 对数:如果a的x次方等于N(a>0,且a≠1),那么数x叫做以a为底N的对数(logarithm),记作x=log_a N。其中,a叫做对数的底数,N叫做真数
    • 时间复杂度与代码结构的关系
      • 一个顺序结构的代码,时间复杂度是 O(1)。
      • 二分查找,或者更通用地说是采用分而治之的二分策略,时间复杂
      • 度都是 O(logn)。这个我们会在后续课程讲到。
      • 一个简单的 for 循环,时间复杂度是 O(n)。
      • 两个顺序执行的 for 循环,时间复杂度是 O(n)+O(n)=O(2n),其实也是 O(n)。
      • 两个嵌套的 for 循环,时间复杂度是 O(n²)。

    复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点。

    它与具体的常系数无关,O(n) 和 O(2n) 表示的是同样的复杂度。
    复杂度相加的时候,选择高者作为结果,也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。
    O(1) 也是表示一个特殊复杂度,即任务与算例个数 n 无关。
    复杂度细分为时间复杂度和空间复杂度,其中时间复杂度与代码的结构设计高度相关;空间复杂度与代码中数据结构的选择高度相关。会计算一段代码的时间复杂度和空间复杂度,是工程师的基本功。

    数据结构:将“昂贵”的时间复杂度转换成“廉价”的空间复杂度

    • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
    • 第二步,无效操作处理。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
    • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移。
    展开全文
  • 重学数据结构与算法(1) 代码效率优化方法论 一、代码效率优化方法论 二、将“昂贵”的时间复杂度转换成“廉价”的空间复杂度

    一、代码效率优化方法论

    熟练应用数据结构的知识,建立算法思维,完成代码效率的优化。

    复杂度是衡量代码运行效率的重要度量因素

    • 计算机通过一个个程序去执行计算任务,也就是对输入数据进行加工处理,并最终得到结果的过程;
    • 每个程序都是由代码构成的,编写代码的核心就是要完成计算;
    • 但对于同一个计算任务,不同计算方法得到结果的过程复杂程度是不一样的,这对实际的任务处理效率就有了非常大的影响;
    • 在实际应用中需要讲究合理的计算方法,去通过尽可能低复杂程度的代码完成计算任务;

    那提到降低复杂度,我们首先需要知道怎么衡量复杂度。

    代码执行过程中会消耗计算时间和计算空间,那需要衡量的就是时间复杂度和空间复杂度。

    不管是时间还是空间,它们的消耗程度都与输入的数据量高度相关,输入数据少时消耗自然就少。为了更客观地衡量消耗程度,我们通常会关注时间或者空间消耗量与输入数据量之间的关系。

    复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n),那么就用个大写字母 O 和括号,把 f(n) 括起来就可以了,即 O(f(n))。例如,O(n) 表示的是,复杂度与计算实例的个数 n 线性相关;O(logn) 表示的是,复杂度与计算实例的个数 n 对数相关。

    通常,复杂度的计算方法遵循以下几个原则:

    • 复杂度与具体的常系数无关:例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下,O(2n) 等于 O(n+n),也等于 O(n) + O(n)。也就是说,一段 O(n) 复杂度的代码只是先后执行两遍 O(n),其复杂度是一致的。
    • 多项式级的复杂度相加的时候,选择高者作为结果:例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是,O(n²)+O(n) = O(n²+n)。随着 n 越来越大,二阶多项式的变化率是要比一阶多项式更大的。因此,只需要通过更大变化率的二阶多项式来表征复杂度即可。
    • O(1) 表示一个特殊复杂度:含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是,与输入数据量 n 无关。

    一些经验性的结论:

    • 一个顺序结构的代码,时间复杂度是 O(1);
    • 二分查找,或者更通用地说是采用分而治之的二分策略,时间复杂度都是 O(logn);
    • 一个简单的 for 循环,时间复杂度是 O(n);
    • 两个顺序执行的 for 循环,时间复杂度是 O(n)+O(n)=O(2n),其实也是 O(n);
    • 两个嵌套的 for 循环,时间复杂度是 O(n²);

    降低时间复杂度的必要性:

    假设某个计算任务需要处理 10 万 条数据,你编写的代码:

    • 如果是 O(n²) 的时间复杂度,那么计算的次数就大概是 100 亿次左右;
    • 如果是 O(n),那么计算的次数就是 10 万 次左右;
    • 如果能写出高效算法,在 O(log n) 的复杂度下完成任务,那么计算的次数就是 17 次左右(log 100000 = 16.61,计算机通常是二分法,这里的对数可以以 2 为底去估计)

    通常在小数据集上,时间复杂度的降低在绝对处理时间上没有太多体现。但在当今的大数据环境下,时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师必须具备的工程开发基本意识。

    复杂度通常包括时间复杂度和空间复杂度,在具体计算复杂度时需要注意以下几点:

    • 它与具体的常系数无关,O(n) 和 O(2n) 表示的是同样的复杂度;
    • 复杂度相加的时候,选择高次项作为结果,也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度;
    • O(1) 也是表示一个特殊复杂度,即任务与算例个数 n 无关;
    • 时间复杂度与代码的结构设计高度相关;
    • 空间复杂度与代码中数据结构的选择高度相关;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            for (k = 0; k < n; k++) {
            
            }
            for (m = 0; m < n; m++) {
            
            }
        }
    }
    
    时间复杂度为O(n^3)
    

    二、将“昂贵”的时间复杂度转换成“廉价”的空间复杂度

    代码效率优化就是要将可行解提高到更优解,最终目标是:要采用尽可能低的时间复杂度和空间复杂度,去完成一段代码的开发。

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

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

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

    • 除 5 余 2
    • 除 7 余 3

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

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

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

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

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

    在程序开发中,连接时间和空间的桥梁就是数据结构。对于一个开发任务,如果你能找到一种高效的数据组织方式,采用合理的数据结构的话,那就可以实现时间复杂度的再次降低。同样的,这通常会增加数据的存储量,也就是增加了空间复杂度。

    程序优化的核心的思路如下:

    • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
    • 第二步,处理无效操作。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
    • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移,以空间换时间。

    举例如下:

    假设有任意多张面额为 2 元、3 元、7 元的货币,现要用它们凑出 100 元,求总共有多少种可能性。

    count = 0
    for i in range(0, 100 // 7 + 1):
        for j in range(0, 100 // 3 + 1):
            for k in range(0, 100 // 2 + 1):
                if i * 7 + j * 3 + k * 2 == 100:
                    count += 1
    
    print(f'总共有 {count} 种可能性')
    
    运行结果如下:
    总共有 134 种可能性
    

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

    count = 0
    for i in range(0, 100 // 7 + 1):
        for j in range(0, 100 // 3 + 1):
            if (100 - 7 * i - 3 * j) >= 0 and (100 - i * 7 - j * 3) % 2 == 0:
                count += 1
    
    print(f'总共有 {count} 种可能性')
    
    运行结果如下:
    总共有 134 种可能性
    

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

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

    a = [1, 2, 3, 4, 6, 5, 6, 6]
    val_max, time_max = -1, 0
    for i in range(0, len(a)):
        time_tmp = 0
        for j in range(0, len(a)):
            if a[i] == a[j]:
                time_tmp += 1
            # 出现次数大于之前最大的   重新复制 value 和出现次数
            if time_tmp > time_max:
                time_max = time_tmp
                val_max = a[i]
    
    print(val_max, time_tmp)     
    
    运行结果如下:
    6 3 
    

    采用两层的 for 循环完成计算, 很显然时间复杂度是 O(n²)。第一层循环,对数组每个元素遍历。第二层循环,则是对第一层遍历的数字,去遍历计算其出现的次数。这样,全局再同时缓存一个出现次数最多的元素及其次数就可以实现。代码中,几乎没有冗余的无效计算。如果还需要再去优化,就要考虑采用一些数据结构方面的手段,来把时间复杂度转移到空间复杂度了。

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

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

    a = [1, 2, 3, 4, 6, 5, 6, 6]
    d = {}
    for i in a:
        if i in d.keys():
            d[i] += 1
        else:
            d[i] = 1
    
    print(d)
    
    for k, v in d.items():
        if v > temp_max:
            time_max = v
            print(temp_max)
            val_max = k
    print(val_max, time_max)
    
    运行结果如下:
    6 3 
    

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

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

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

    降低复杂度,优化程序的核心的思路如下:

    • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
    • 第二步,处理无效操作。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
    • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移,以空间换时间。

    作者:叶庭云
    CSDN:https://yetingyun.blog.csdn.net/
    本文仅用于交流学习,未经作者允许,禁止转载,更勿做其他用途,违者必究。
    觉得文章对你有帮助、让你有所收获的话,期待你的点赞呀,不足之处,也可以在评论区多多指正。

    展开全文
  • 将“烂代码优化为高效率代码方法和路径 复杂度:衡量程序执行效率 场景:程序执行好几个小时、甚至好几天的情况,或者是执行过程中电脑几乎死机的情况 如果这个效率低下的系统是离线的,那么它会让我们的开发...

    将“烂代码”优化为高效率代码的方法和路径

    复杂度:衡量程序执行效率

    场景:程序执行好几个小时、甚至好几天的情况,或者是执行过程中电脑几乎死机的情况

    如果这个效率低下的系统是离线的,那么它会让我们的开发周期、测试周期变得很长。

    如果这个效率低下的系统是在线的,那么它随时具有时间爆炸或者内存爆炸的可能性。

    衡量代码的运行效率对于一个工程师而言,是一项非常重要的基本功

    复杂度是什么

    复杂度是衡量代码运行效率的重要度量因素。

    计算机通过一个个程序去执行计算任务,也就是对输入数据进行加工处理,并最终得到结果的过程。每个程序都是由代码构成的。编写代码的核心就是要完成计算。但对于同一个计算任务,不同计算方法得到结果的过程复杂程度是不一样的,这对你实际的任务处理效率就有了非常大的影响

    需要讲究合理的计算方法,去通过尽可能低复杂程度的代码完成计算任务。

    衡量复杂度

    • 代码消耗的资源是什么?
      代码执行过程中会消耗计算时间和计算空间,那需要衡量的就是时间复杂度和空间复杂度

      1. 时间复杂度
      2. 空间复杂度
    • 代码对于资源的消耗是多少?
      不会关注这段代码对于资源消耗的绝对量,因为不管是时间还是空间,它们的消耗程度都与输入的数据量高度相关,输入数据少时消耗自然就少。为了更客观地衡量消耗程度,我们通常会关注时间或者空间消耗量与输入数据量之间的关系。

    • 如何去计算复杂度?
      复杂度是一个关于输入数据量 n 的函数
      假设你的代码复杂度是 f(n),那么就用个大写字母 O 和括号,把 f(n) 括起来就可以了,即 O(f(n))。例如,O(n) 表示的是,复杂度与计算实例的个数 n 线性相关;O(logn) 表示的是,复杂度与计算实例的个数 n 对数相关。

    复杂度的计算方法遵循以下几个原则:

    • 首先,复杂度与具体的常系数无关,例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下,O(2n) 等于
      O(n+n),也等于 O(n) + O(n)。也就是说,一段 O(n) 复杂度的代码只是先后执行两遍 O(n),其复杂度是一致的。
    • 其次,多项式级的复杂度相加的时候,选择高者作为结果,例如 O(n²)+O(n) 和 O(n²)
      表示的是同样的复杂度。具体分析一下就是,O(n²)+O(n) = O(n²+n)。随着 n
      越来越大,二阶多项式的变化率是要比一阶多项式更大的。因此,只需要通过更大变化率的二阶多项式来表征复杂度就可以了。
    • O(1) 也是表示一个特殊复杂度,含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是,与输入数据量 n 无关。

    代码任务

    对于输入的数组,输出与之逆序的数组。例如,输入 a=[1,2,3,4,5],输出 [5,4,3,2,1]。

    • 方法一,建立并初始化数组 b,得到一个与输入数组等长的全零数组。通过一个 for 循环,从左到右将 a 数组的元素,从右到左地赋值到 b 数组中,最后输出数组 b 得到结果。
    public void s1_1() {
        int a[] = { 1, 2, 3, 4, 5 };
        int b[] = new int[5];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }
        for (int i = 0; i < a.length; i++) {
            b[a.length - i - 1] = a[i];
        }
        System.out.println(Arrays.toString(b));
    }
    

    这段代码的输入数据是 a,数据量就等于数组 a 的长度。代码中有两个 for 循环,作用分别是给b 数组初始化和赋值,其执行次数都与输入数据量相等。因此,代码的时间复杂度就是 O(n)+O(n),也就是 O(n)。

    空间方面主要体现在计算过程中,对于存储资源的消耗情况。上面这段代码中,我们定义了一个新的数组 b,它与输入数组 a 的长度相等。因此,空间复杂度就是 O(n)。

    • 第二种编码方法,它定义了缓存变量 tmp,接着通过一个 for 循环,从 0 遍历到a 数组长度的一半(即 len(a)/2)。每次遍历执行的是什么内容?就是交换首尾对应的元素。最后打印数组 a,得到结果。
    public void s1_2() {
        int a[] = { 1, 2, 3, 4, 5 };
        int tmp = 0;
        for (int i = 0; i < (a.length / 2); i++) {
            tmp = a[i];
            a[i] = a[a.length - i - 1];
            a[a.length - i - 1] = tmp;
    	}
            System.out.println(Arrays.toString(a));
    }
    

    这段代码包含了一个 for 循环,执行的次数是数组长度的一半,时间复杂度变成了 O(n/2)。根据复杂度与具体的常系数无关的性质,这段代码的时间复杂度也就是 O(n)。

    空间方面,我们定义了一个 tmp 变量,它与数组长度无关。也就是说,输入是 5 个元素的数组,需要一个 tmp 变量;输入是 50 个元素的数组,依然只需要一个 tmp 变量。因此,空间复杂度与输入数组长度无关,即 O(1)。

    小结:

    对于同一个问题,采用不同的编码方法,对时间和空间的消耗是有可能不一样的。因此,工程师在写代码的时候,一方面要完成任务目标;另一方面,也需要考虑时间复杂度和空间复杂度,以求用尽可能少的时间损耗和尽可能少的空间损耗去完成任务

    时间复杂度与代码结构的关系

    代码的时间复杂度,与代码的结构有非常强的关系,我们一起来看一些具体的例子。

    例 1,定义了一个数组 a = [1, 4, 3],查找数组 a 中的最大值,代码如下:

    public void s1_3() {
        int a[] = { 1, 4, 3 };
        int max_val = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max_val) {
                max_val = a[i];
            }
        }
        System.out.println(max_val);
    }
    
    例子比较简单,实现方法就是,暂存当前最大值并把所有元素遍历一遍即可。因为代码的结构上需要使用一个 for 循环,对数组所有元素处理一遍,所以时间复杂度为 O(n)

    例2,下面的代码定义了一个数组 a = [1, 3, 4, 3, 4, 1, 3],并会在这个数组中查找出现次数最多的那个数字:

    public void s1_4() {
        int a[] = { 1, 3, 4, 3, 4, 1, 3 };
        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);
    }
    这段代码中,我们采用了双层循环的方式计算:第一层循环,我们对数组中的每个元素进行遍历;第二层循环,对于每个元素计算出现的次数,并且通过当前元素次数 time_tmp 和全局最大次数变量 time_max 的大小关系,持续保存出现次数最多的那个元素及其出现次数。由于是双层循环,这段代码在时间方面的消耗就是 n*n 的复杂度,也就是 O()

    结论:

    • 一个顺序结构的代码,时间复杂度是 O(1)。
    • 二分查找,或者更通用地说是采用分而治之的二分策略,时间复杂度都是 O(logn)。这个我们会在后续课程讲到。
    • 一个简单的 for 循环,时间复杂度是 O(n)。
    • 两个顺序执行的 for 循环,时间复杂度是 O(n)+O(n)=O(2n),其实也是 O(n)。
    • 两个嵌套的 for 循环,时间复杂度是 O(n²)。

    降低时间复杂度的必要性

    实际的在线环境中,用户的访问请求可以看作一个流式数据。假设这个数据流中,每个访问的平均时间间隔是 t。如果你的代码无法在 t
    时间内处理完单次的访问请求,那么这个系统就会一波未平一波又起,最终被大量积压的任务给压垮。这就要求工程师必须通过优化代码、优化数据结构,来降低时间复杂度。

    为了更好理解,我们来看一些数据。假设某个计算任务需要处理 10 万 条数据。
    你编写的代码:

    • 如果是 O(n²) 的时间复杂度,那么计算的次数就大概是 100 亿次左右。
    • 如果是 O(n),那么计算的次数就是 10 万 次左右。
    • 如果这个工程师再厉害一些,能在 O(log n) 的复杂度下完成任务,那么计算的次数就是 17 次左右(log 100000 =
      16.61,计算机通常是二分法,这里的对数可以以 2 为底去估计)。

    数字是不是一下子变得很悬殊?通常在小数据集上,时间复杂度的降低在绝对处理时间上没有太多体现。但在当今的大数据环境下,时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师必须具备的工程开发基本意识。

    总结

    复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点。

    它与具体的常系数无关,O(n) 和 O(2n) 表示的是同样的复杂度。

    复杂度相加的时候,选择高者作为结果,也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。

    O(1) 也是表示一个特殊复杂度,即任务与算例个数 n 无关。

    复杂度细分为时间复杂度和空间复杂度,其中时间复杂度与代码的结构设计高度相关;空间复杂度与代码中数据结构的选择高度相关。会计算一段代码的时间复杂度和空间复杂度,是工程师的基本功。

    数据结构:将“昂贵”的时间复杂度转换成“廉价”的空间复杂度

    将代码的时间复杂度或者空间复杂度,是否还有降低的可能性
    代码效率优化就是要将可行解提高到更优解,最终目标是:要采用尽可能低的时间复杂度和空间复杂度,去完成一段代码的开发。

    时间昂贵、空间廉价

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

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

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

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

    数据结构连接时空

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

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

    1. 能被 3 整除;
    2. 除 5 余 2。

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

    复杂度比较低或者可以接受,那自然万事大吉。可如果暴力解法复杂度比较高的话,那就要考虑采用程序优化的方法去降低复杂度了。

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

    我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等

    而降低空间复杂度的方法,就要围绕数据结构做文章了。
    降低空间复杂度的核心思路就是,能用低复杂度的数据结构能解决问题,就千万不要用高复杂度的数据结构。
    可以通过某种方式,把时间复杂度转移到空间复杂度的话,就可以把无价的东西变成有价了

    程序开发中,连接时间和空间的桥梁就是数据结构
    

    对于一个开发任务,如果你能找到一种高效的数据组织方式,采用合理的数据结构的话,那就可以实现时间复杂度的再次降低。同样的,这通常会增加数据的存储量,也就是增加了空间复杂度。

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

    • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
    • 第二步,无效操作处理。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
    • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移。

    降低复杂度的案例

    第 1 个例子,假设有任意多张面额为 2 元、3 元、7 元的货币,现要用它们凑出 100 元,求总共有多少种可能性。假设工程师小明写了下面的代码:
    public void s2_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 s2_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 s2_3() {
        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 s2_4() {
    
        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)。

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

    总结

    降低复杂度的方法就是这三个步骤

    • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
    • 第二步,无效操作处理。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
    • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移
    展开全文
  • 时间复杂度与代码的结构设计高度相关。 空间复杂度与代码中数据结构的选择高度相关。 时间变空间 将“昂贵”的时间复杂度转换为“廉价”的空间复杂度。 假定在不限时间、也不限空间的情况下,可以完成某个任务的代码...

    复杂度

    复杂度通常包括时间复杂度与空间复杂度

    复杂度的计算
    它与具体的常系数无关,O(n)和O(2n)表示同样同样的复杂度。
    复杂度相加的时候,选择高者作为结果,也就是O(nn)+O(n) 与O(nn)表示相同的复杂度。
    O(1)也是表示一个特殊的复杂度,即任务与算例个数n无关。

    时间复杂度与代码的结构设计高度相关。
    空间复杂度与代码中数据结构的选择高度相关。

    时间变空间

    将“昂贵”的时间复杂度转换为“廉价”的空间复杂度。

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

    在程序开发中,连接时间和空间的桥梁就是数据结构
    对于一个开发任务,如果能找到一种高效的数据组织方式,采用合理的数据结构
    就可以实现时间复杂度的再次降低,这通常会增加数据的存储量,也就是增加了空间复杂度。

    程序优化最核心的思路:
    第一步,暴力解法:
    在没有任何时间、空间约束下,完成代码任务的开发。
    第二步,无效操作处理:
    将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
    第三步,时空转换:
    设计合理数据结构,完成时间复杂度向空间复杂度的转移。

    降低复杂度的案例:
    1)有任意多张面额为2元、3元、7元的货币,现要用他们凑出100元,求总共有多少总可能?
    在这里插入图片描述
    2)求一个输入数组中,查找出现次数最多的元素?

    解法一:时间复杂度为O(n*n)
    在这里插入图片描述
    解法二:利用数据结构,空间换时间,O(n)

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • Java代码效率优化

    2019-02-28 15:32:23
    JAVA代码效率优化 java代码效率性能优化 1、 尽量指定类的final修饰符 带有final修饰符的类是不可派生的。 如果指定一个类为final,则该类所有的方法都是final。Java编译器会寻找机会内联(inline)所有的 final方法...
  • 文章目录代码效率优化1、优化的最终目标2、时间和空间的比较3、数据结构连接时空4、实例分析5、总结 ❤️阅文后请用一句话总结您的心得和建议!动心请点赞❤️ 代码效率优化 整理自课程《重学数据结构与算法》 1、...
  • JAVA代码效率优化

    2018-10-16 17:02:51
    以下是我找的一些关于代码效率优化方法。 原文地址是:http://blog.163.com/user_zhaopeng/blog/static/16602270820122105731329/ 1、 尽量指定类的final修饰符 带有final修饰符的类是不可派生的。 如果指定一个...
  • java代码效率优化

    2016-07-08 13:09:37
    java代码效率优化 1、 尽量指定类的final修饰符 带有final修饰符的类是不可派生的。  如果指定一个类为final,则该类所有的方法都是final。Java编译器会寻找机会内联(inline)所有的 final方法(这和具体的...
  •  什么时候才需要代码效率优化? 1. 吃饭午饭,喝杯茶,然后兴冲冲的把代码翻出来整啊整。 2. 项目进行到一半,忽然发现以前有几个地方的代码看着不顺眼,沙沙,划掉重来。 3. 程序已经在很休闲的运行着,有一天...
  • 而软件效率与操作系统,语言,编译器都有关,切记每一种方法都需要自己去验证才知不知道适合自己,而不是仅仅依照别人的方法) 1. 将局域变量放在循环内和循环外定义 int i = 0; int bit = 0; f
  • 1、用单引号代替双引号来包含字符串,这样做会更快一些。因为PHP会在双引号包围的字符串中搜寻变量... 2、如果能将类的方法定义成static,就尽量定义成static,它的速度会提升将近4倍。 3、$row[‘id’] 的速度是...
  • PHP代码效率优化

    2013-09-24 17:50:00
    1、如果能将类的方法定义成static,就尽量定义成static,它的速度会提升将近4倍。 2、$row['id'] 的速度是$row[id]的7倍。 3、echo 比 print 快,并且使用echo的多重参数(译注:指用逗号而不是句点)代替字符串连接,...
  • 一、利用内表缓冲减少数据库访问次数 REPORT zmmi003. data: it_vbap type table of vbap,wa_vbap type vbap,it_makt type table of makt...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,516
精华内容 1,006
关键字:

代码效率优化方法