概要
关于“彩蛋”，数据结构与算法系列博客中，如有可能，博主尽量会在每一篇博客里埋下彩蛋。彩蛋的意义在刚开始写博客的开篇有说明过，实际就是算法实现过程的一些小技巧，而这些小技巧往往都是可以改进执行效率的。关于所有的彩蛋都会有特别的解释说明，千里之行始于足下，共勉～
LeetCode进阶1086-Hash思想
彩蛋
仔细观察上述两种思路的实现代码会发现，有几处for循环的时候使用的都是++i
说明
在循环次数不是特别大的时候++i比i++执行效率高，直接上代码：
public static void main(String[] args) {
long start1 = System.nanoTime();
for (int i = 0; i < 1000; i++) {
}
System.out.println("i++ use time(ms):" + Long.toString((System.nanoTime() - start1) / 1000));
long start2 = System.nanoTime();
for (int i = 0; i < 1000; ++i) {
}
System.out.println("++i use time(ms):" + Long.toString((System.nanoTime() - start2) / 1000));
}
- 循环次数1000
i++ 耗时(ms):24
++i 耗时(ms):9
- 循环次数10000
i++ 耗时(ms):68
++i 耗时(ms):46
- 循环次数100000
i++ 耗时(ms):595
++i 耗时(ms):576
- 循环次数1000000
i++ 耗时(ms):1370
++i use time(ms):2157
可以看到：大概在100000次循环之前，++i的效率优于i++；而在1000000的时候i++则优于++i,看到网上很多博客千篇一律的结论是一样实际是错误的，当然博主也验证了两者的字节码确实也是一样：
- 源码
public static void test1() {
for (int i = 0; i < 1000; i++) {
}
}
public static void test2() {
for (int i = 0; i < 1000; ++i) {
}
}
- 字节码
public static void test1();
Code:
0: iconst_0
1: istore_0
2: iload_0
3: sipush 1000
6: if_icmpge 15
9: iinc 0, 1
12: goto 2
15: return
public static void test2();
Code:
0: iconst_0
1: istore_0
2: iload_0
3: sipush 1000
6: if_icmpge 15
9: iinc 0, 1
12: goto 2
15: return
测试的结果在循环次数较小的时候大约100000次以下，++i更高效。那么到底该如何选择，个人建议根据实际项目中的循环次数做估计，可以写个简单UT测试。一样的字节码执行的效率不一样的原因在于JVM编译器，在源码Java文件最终编译成机器码的过程是有细微差别的，具体差别本文暂不分析。对编译器编译感兴趣的可以先参考JVM基础系列第4讲：从源代码到机器码，发生了什么？
LeetCode进阶1025-动态规划
彩蛋
仔细观察第二种方法实现的时候，并不是使用N % 2 == 0来判断奇偶，而是通过(N & 1) == 0来判断
说明
"&"与运算 二进制码的每一位进行与运算，只有两位同时为1时结果为1，其余均为0。因此在N & 1时若结果为0则说明N最后一位必然为0，而二进制最后一位为0必然是2的倍数即偶数。"&"与运算比"%"模运算快的原因是，与运算直接对整数在内存中的二进制位进行操作，因此执行效率高。比较简单，本篇不做实际验证。想要深入学习位运算，推荐位运算有什么奇技淫巧？
LeetCode进阶1029-贪心
彩蛋
观察上面实现代码会发现在sort数组中存储前往B和A城市int差价和在costs数组中下标位置时，使用了左移8位再加i的操作
说明
int整数为4字节32位，本题确定数字在1～1000之间小于2的10次方，即数字大小转化为二进制小于11位，左移8位相当于当前数字扩大2的8次方倍，再加当前索引值i，而i同理在1～100之间转化为二进制显然低于8位。本质上移位再加索引是为了保证数字大小相对关系不变的情况还存储当前的索引下标，这样方便排序，排序的结果与不进行位移加索引操作的结果是一致的，由于相对简单，本篇不再验证。
LeetCode进阶944-算法优化
彩蛋
进阶版对比普通版效率上有质的提高，主要是将双重for循环的内存循环拆成了独立的方法
944的彩蛋分析由于流程相对复杂，后续会单独开一篇博客进行详细说明，敬请期待_
扫一扫 关注我的微信订阅号
网友评论