蓝桥-10种简单代码优化下集

10种简单代码优化下集

2017-09-05

  6、避免递归

    现在,类似Scala这样的函数式编程语言都鼓励使用递归。因为递归通常意味着能分解到单独个体优化的尾递归(tail-recursing)。如果你使用的编程语言能够支持那是再好不过。不过即使如此,也要注意对算法的细微调整将会使尾递归变为普通递归。希望编译器能自动探测到这一点,否则本来我们将为只需使用几个本地变量就能搞定的事情而白白浪费大量的堆栈框架(stack frames)。

  7、使用entrySet()

    当我们想遍历一个用键值对形式保存的 Map 时,必须要为下面的代码找到一个很好的理由:

22.png

    更不用说下面的写法:

23.png

    在我们使用 N.O.P.E. 分支应该慎用map。因为很多看似时间复杂度为 O(1) 的访问操作其实是由一系列的操作组成的。而且访问本身也不是免费的。至少,如果不得不使用map的话,那么要用 entrySet() 方法去迭代!这样的话,我们要访问的就仅仅是Map.Entry的实例。

  8、使用EnumSet或EnumMap

    在某些情况下,比如在使用配置map时,我们可能会预先知道保存在map中键值。如果这个键值非常小,我们就应该考虑使用 EnumSet 或 EnumMap,而并非使用我们常用的 HashSet 或 HashMap。下面的代码给出了很清楚的解释:

24.png

    上段代码的关键实现在于,我们用数组代替了哈希表。尤其是向map中插入新值时,所要做的仅仅是获得一个由编译器为每个枚举类型生成的常量序列号。如果有一个全局的map配置(例如只有一个实例),在增加访问速度的压力下,EnumMap 会获得比 HashMap 更加杰出的表现。原因在于 EnumMap 使用的堆内存比 HashMap 要少 一位(bit),而且 HashMap 要在每个键值上都要调用hashCode() 方法和 equals() 方法。

  9、优化自定义hasCode()方法和equals()方法

    在不能使用EnumMap的情况下,至少也要优化 hashCode() 和 equals() 方法。一个好的 hashCode() 方法是很有必要的,因为它能防止对高开销 equals() 方法多余的调用。在每个类的继承结构中,需要容易接受的简单对象。让我们看一下jOOQ的 org.jooq.Table 是如何实现的?最简单、快速的 hashCode() 实现方法如下:

1504576001831542.png

    name即为表名。我们甚至不需要考虑schema或者其它表属性,因为表名在数据库中通常是唯一的。并且变量 name 是一个字符串,它本身早就已经缓存了一个 hashCode() 值。这段代码中注释十分重要,因继承自 AbstractQueryPart 的 AbstractTable 是任意抽象语法树元素的基本实现。普通抽象语法树元素并没有任何属性,所以不能对优化 hashCode() 方法实现抱有任何幻想。覆盖后的 hashCode() 方法如下:

1504576021905370.png

    换句话说,要触发整个SQL渲染工作流程(rendering workflow)来计算一个普通抽象语法树元素的hash代码。equals() 方法则更加有趣:

1504576040588419.png

    首先,不要过早使用 equals() 方法(不仅在N.O.P.E.中),如果:this == argument;this“不兼容:参数;注意:如果我们过早使用 instanceof 来检验兼容类型的话,后面的条件其实包含了argument == null。在我们对以上几种情况的比较结束后,应该能得出部分结论。比如jOOQ的 Table.equals() 方法说明是,用来比较两张表是否相同。不论具体实现类型如何,它们必须要有相同的字段名。比如下面两个元素是不可能相同的:com.example.generated.Tables.MY_TABLE;DSL.tableByName(“MY_OTHER_TABLE”)如果我们能方便地判断传入参数是否等于实例本身(this),就可以在返回结果为 false 的情况下放弃操作。如果返回结果为 true,我们还可以进一步对父类(super)实现进行判断。在比较过的大多数对象都不等的情况下,我们可以尽早结束方法来节省CPU的执行时间。

    一些对象的相似度比其它对象更高。在jOOQ中,大多数的表实例是由jOOQ的代码生成器生成的,这些实例的 equals() 方法都经过了深度优化。而数十种其它的表类型(衍生表 (derived tables)、表值函数(table-valued functions)、数组表(array tables)、连接表(joined tables)、数据透视表(pivot tables)、公用表表达式(common table expressions)等,则保持 equals() 方法的基本实现。


  10、考虑使用set而并非单个元素

    最后,还有一种情况可以适用于所有语言而并非仅仅同Java有关。除此以外,我们以前研究的 N.O.P.E. 分支也会对了解从 O(N3) 到 O(n log n)有所帮助。不幸的是,很多程序员的用简单的、本地算法来考虑问题。他们习惯按部就班地解决问题。这是命令式(imperative)的“是/或”形式的函数式编程风格。这种编程风格在由纯粹命令式编程向面对象式编程向函数式编程转换时,很容易将“更大的场景(bigger picture)”模型化,但是这些风格都缺少了只有在SQL和R语言中存在的:声明式编程。在SQL中,我们可以在不考虑算法影响下声明要求数据库得到的效果。数据库可以根据数据类型,比如约束(constraints)、键(key)、索引(indexes)等不同来采取最佳的算法。在理论上,我们最初在SQL和关系演算(relational calculus)后就有了基本的想法。在实践中,SQL的供应商们在过去的几十年中已经实现了基于开销的高效优化器CBOs (Cost-Based Optimisers) 。然后到了2010版,我们才终于将SQL的所有潜力全部挖掘出来。但是我们还不需要用set方式来实现SQL。所有的语言和库都支持Sets、collections、bags、lists。使用set的主要好处是能使我们的代码变的简洁明了。比如下面的写法:

28.png

而不是

1504576067838511.png

    有些人可能会对函数式编程和Java 8能帮助我们写出更加简单、简洁的算法持有不同的意见。但这种看法不一定是对的。我们可以把命令式的Java 7循环转换成Java 8的Stream collection,但是我们还是采用了相同的算法。但SQL风格的表达式则是不同的:

30.png

    上面的代码在不同的引擎上可以有1000种不同的实现。我们今天所研究的是,在调用 INTERSECT 操作之前,更加智能地将两个set自动的转化为 EnumSet 。甚至我们可以在不需要调用底层的 Stream.parallel() 方法的情况下进行并行 INTERSECT 操作。


  总结

    在这篇文章中,我们讨论了关于N.O.P.E.分支的优化。比如深入高复杂性的算法。作为jOOQ的开发者,我们很乐于对SQL的生成进行优化。每条查询都用唯一的StringBuilder来生成。模板引擎实际上处理的是字符而并非正则表达式。选择尽可能的使用数组,尤其是在对监听器进行迭代时。对JDBC的方法敬而远之等等。jOOQ处在“食物链的底端”,因为它是在离开JVM进入到DBMS时,被我们电脑程序所调用的最后一个API。位于食物链的底端意味着任何一条线路在jOOQ中被执行时都需要 N x O x P 的时间,所以我要尽早进行优化。我们的业务逻辑可能没有N.O.P.E.分支那么复杂。但是基础框架有可能十分复杂(本地SQL框架、本地库等)。所以需要按照我们今天提到的原则,用Java Mission Control 或其它工具进行复查,确认是否有需要优化的地方。

1504576095763407.png


上一篇:我见过的最糟糕的代码

下一篇:你想知道的人工智能真相在蓝桥