Week_008_ 总结

周四主要学的是数据结构与算法相关的，NP问题那块，其实没太听懂，但感觉好像也没啥影响。

数组、链表、Hash表、堆、队列、树和栈的数据结构，这些都是软件工程中基础中的基础。看的十分亲切，但它对我似乎有些陌生。

其中树可能谈的是最多的，毕竟logn的数据结构，各种不同的树，按照逻辑的发展，面对情况的不同，从而衍生出了各种各样的树，但其初衷都是不断权衡插入效率和查找效率，红黑树应该就是其中最好的范例了，既不是非常严格的平衡，又不会产生太过严重的数据倾斜问题。

跳表:这个数据结构其实感觉平时接触的机会并不多，Redis里面实现了这种数据结构。感官上觉得这是一个很好的思想，可以当成一种提升代码逼格的利器。毕竟需要的额外空间也不多，查找效率也很高。但总觉得这个跳表应该是个双向链表（因为看老师的图片，觉得跳表是个单向链表的感觉很强烈），老师说这个实现并不难...但好像感觉如果我自己实现似乎会有些困难。对于节点数值相等，但处于不同层次的节点，回退时该如何走这一块，感觉会有些卡壳。第一印象是节点的prev节点，直接指向上一层的同等值的节点。不知道是不是这样的。

贪心算法：上过算法训练营，对贪心算法也有映像，但迪杰斯特拉算法这个印象不是很深刻（白学了...）

动态规划算法：这个算法，真的很有用，基本上属于万金油那种类型，难点我觉得是在针对物理模型建模的时候。只要把表和递推算式求出来，基本上就妥了。

遗传算法：这个没太多映像，了解了一下感觉像是一个随机算式求收敛域的问题。不知道会不会出现局部最优解的问题。

周六：讲网络，这个觉得是最贴近我们一般编程人员的，我觉得当代软件的本质，应该就是数据的处理以及数据的流转。而网络通讯这块在数据跨距离流转中是不可替代的。老生常谈的OSI七层模型，但其实印象中好像并没有严格实现的例子，基本用的是四层模型。

讲数据包的时候瞬间精神了，老师扒衣服的比喻太传神了，一唠这个我就不困了。

数据链路层的负载均衡，最近看鹏飞老师的《Linux性能优化》感觉像是用DNAT这个技术实现的。

三次握手四次挥手感觉面试多多少少都会问，其实某些情况下也可以是三次挥手，因为中间的FIN和ACK包可以合并在一起发。这个阶段还有个经典的问题是，产生海量time_wait状态socket。

阻塞非阻塞，同步异步，这几兄弟一直很绕。看得多了以后感觉：阻塞和非阻塞是从请求端进程方面看的。同步异步是从服务端是否主动发送event触发来识别的。

NIO之前一直以为是非阻塞IO，发现之前的认知是错误的。原来是New IO。通过复用线程的方式来减少阻塞。

还讲了数据库设计相关的，语法分析树这个一直觉得自己写会很复杂，很头大。所以不知道这些语法分析树是不是都是需要程序员去自己撸的，是的话那太痛苦了....剩下的那些内容都是必考题目，我得多翻翻以前的资料了...这玩意好难记忆....

完毕。