Algorithm

Add Two Numbers

给定两个非空正整数链表,除了0外,链表不以0结尾,数字被反向存储在链表中,每个节点的两个数相加,产生新的链表并返回。

Example:

Input: $(2->4->3)+(5->6->4)$

Output:$7->0->8$

Explanation:$342+465=807$.

最直接的思路,就是递归的去加。但是当我写代码的时候,发现写不出来😂。只能硬着头皮,先一位一位的加,然后找规律,提取递归方法,然后不停的提交测试,最终是通过了。感觉丑陋无比,回头看也完全看不懂的代码跑出来的结果还是让我有些惊喜的。my solution

Detail

Runtime: 2 ms, faster than 97.70% of Java online submissions for Add Two Numbers.

Memory Usage: 46 MB, less than 55.21% of Java online submissions for Add Two Numbers.

我实现的方法时间复杂度就是$O(n)$,$n$就是两个链表的最大长度。空间复杂度应该也是一样的,应该是因为我的代码时间过多的中间变量的创建导致的内存占用较大。

官网解题思路

official solution 解读

参考官方的解题思路获得的启发,问题过来千万别着急想着解决它,先分析问题中的所有条件,以及可能涉及的信息,提炼解题模型,然后在写代码。代码还是要多看,多写,多感受,然后总结自己的套路。

Review

文章来源耗子叔、极客时间左耳听风专栏79讲推荐文章

另外,也推荐一下 [JVM Anatomy Park JVM][]解剖公园,这是一个系列的文章,每篇文章都不长,但是都很精彩,带你一点一点地把 JVM 中的一些技术解开。

极客时间版权所有: https://time.geekbang.org/column/article/10216

Q: Java 是否对循环中的锁也进行了锁粗化优化呢 (lock coarsening optimizations)

我们知道:

1
2
3
4
5
6
synchronized (obj) {
// statements 1
}
synchronized (obj) {
// statements 2
}

Convert into :

1
2
3
4
synchronized (obj) {
// statements 1
// statements 2
}

那么:

1
2
3
4
5
for (...) {
synchronized (obj) {
// something
}
}

是否会被优化为:

1
2
3
4
5
synchronized (this) {
for (...) {
// something
}
}

我们可以使用JMH(Java Microbenchmark Harness),进行验证。

官方推荐通过Maven构建测试项目。然后运行的时候不要Debug模式运行,先mvn clean installrun
读到这里,下面的内容对于我来说就有些难度了,不过我也不陷入技术的无限深入了,这里我明确两个目标:学习常见技术英文单词,找到问题的答案即可。

我自己的实验结果:

Running at i7,16GB CPU,macOS 10.14.4,JDK 1.8.0_171

1
2
Benchmark                     Mode  Samples     Score  Score error  Units
o.s.MyBenchmark.testMethod avgt 5 5423.944 59.737 ns/op

仅仅从这串数字中,我们无法获得答案,我们需要内部发生了什么。

cmpxchg compare-and-sets又见到它了,在小马哥的视频中我也听过一次。

既然有缘稍微查询下资料,了解一下。这是一个cpu提供的原子性操作指令。Java 中很多实现都是基于这个指令。

进行-prof perfasm:mergeMargin=1000 的操作时,发现自建的项目中,无法设置了,这时回头参考了文中连接的 JMH 官方地址。继续进行实验。这一步要将热点代码附近的操作打印出来。

这个实验没跑出来,继续,留给以后的自己

实验结论就是循环被拆成了4个小循环。接下来验证是不是因为循环的展开带来的性能提升,通过设置-XX:LoopUnrollLimit=1排除干扰。

我的实验结果:

1
2
Benchmark               Mode  Cnt      Score     Error  Units
weekTwo.LockRoach.test avgt 5 21607.139 ± 288.376 ns/op

确实性能上有4倍的差距。再次通过-prof perfasm:mergeMargin=1000 查看返回内容是否知识一个循环。

实验过后,得证。

结论

HotSpot 不会对整个循环进行锁粗化,通过进行循环展开的方式,为常态的锁粗化奠定基础。循环展开后就是多个连续的加锁-解锁序列,如此获得了性能上的收益,并且避免了过度粗化。

Tips

在 mac 上使用 VM function 部署 Centos 7 时,希望固定 ip,在网上搜了好久,没有找到解决办法,最后在进行 Nginx+Keepalived 的高可用实验的时候,发现可以通过 Keepalived 达到固定 ip 的效果。并且网上很多配置检测 Nginx 是否存在的脚本,我这都不生效,最终找到了一个这里分享一份我的配置。

keepalived.conf ,nginx-check.sh

Share

在进行 ARTS 任务过程中,翻阅了耗子叔的博客,他的座右铭让我深有感触。

芝兰生于深谷,不以无人而不芳
君子修身养德,不以穷困而改志

可能是工作的压力,技术的恐慌,学习的迷茫。我看到这句话的时候,真的哭了,似乎真的忘记了来时的自己,毕业3年多了,为了生活,为了工作,身边的同时换了一批又一批,多少次仅仅因为钱的问题迷失自我,多少次因为虚荣放纵了自我。人人都想成为君子,但是真的很难。

回想自己进入这个行业是为了什么呢,好像也没有想为了什么,仅仅是为了毕业后能有一份工作。3年应该是一个节点吧,虽然现在承担着技术负责人的工作,但是个人觉得技术的成长才是我前10年的重点,不想分心太多去处理管理、沟通、协调资源等问题上。

如果你很有责任心,那么最后什么事都会落在你的头上,当然这也会带给你技术上的飞速成长。

看着耗子叔的座右铭,想想现在的自己:

非芝兰,蒹葭一束,慕芝兰之芳。然随风浮荡,望江波荡漾,思绪万千。
受诱于富贵享乐,奋进之心不坚。念他人之才,苦寒之气不受。
古人之语,惊醒梦中之人,君当以“千磨万击还坚韧,任尔东南西北风”。

留言

⬆︎TOP