极客时间官方21天打卡行动第一期

作者:杨润炜
日期:2019/12/25 23:21

极客时间上的21天打卡

立个flag,完成极客时间的21天打卡行动(完结)。

从 2019-12-19 到 2020-01-08 连续21天不间断打卡,即使中间有时候遇到很忙碌的情况,还是会想着学习一会打个卡,而且慢慢会养成固定时间学习的习惯。虽然21天学习下来知识没怎么涨,但习惯的养成估计更有价值。希望这次“跨年之战”的热情和精神能继续发扬,最终形成自己的学习习惯。

第二十一天(2020-01-08):

《数据结构与算法之美》

学习了跳表这种数据结构。跳表使用空间换时间的设计思路,通过构建多级索引来提高查询的效率,实现了基于链表的“二分查找”。跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都是 O(logn);

如果链表节点有变动,需要动态更新多级索引来维持跳表的“平衡性”,一般是通过随机函数实现的,从概率上能够保证跳表的索引大小和数据大小平衡性,不至于性能过度退化;

redis的有序集合就是用跳表实现的;

跳表的空间复杂度是 O(n)。不过,跳表的实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单,但是作为一种动态数据结构,比起红黑树来说,实现要简单多了。所以很多时候,我们为了代码的简单、易读,比起红黑树,我们更倾向用跳表。

第二十天(2020-01-07):

《数据结构与算法之美》

二分查找是一种非常高效的查找算法,O(logn)对数时间复杂度,比如在 42 亿个数据中用二分查找一个数据,最多需要比较 32 次,极其高效;

二分查找应用场景的局限性:
二分查找依赖的是顺序表结构,简单点说就是数组;
二分查找针对的是有序数据;
数据量太小或太大不适合二分查找,太小不必要用这么复杂的算法,太大又会占用太多连续内存空间;
二分查找更适合处理静态数据,也就是没有频繁的数据插入、删除操作;

二分查找的核心思想理解起来非常简单,有点类似分治思想。即每次都通过跟区间中的中间元素对比,将待查找的区间缩小为一半,直到找到要查找的元素,或者区间被缩小为 0。但是二分查找的代码实现比较容易写错。你需要着重掌握它的三个容易出错的地方:循环退出条件、mid 的取值,low 和 high 的更新。

第十九天(2020-01-06):

《数据结构与算法之美》
哪种排序算法适合用来做通用的排序函数?
线性排序的适用场景比较严格,不够通用;
复杂度为O(n2)适用小规模数据集,不够通用;
剩下时间复杂度是 O(nlogn)的归并和快速排序,但归并不是原地排序,数据多了会占用更多的内存,所以快速排序比较适合来实现排序函数;

如何优化快速排序?
因为快速排序的最坏情况时间复杂度是O(n2),需要想办法优化。
O(n2) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理;
最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。

两个比较常用、比较简单的分区算法:
三数取中法;
随机法;

防止快速排序的递归导致栈溢出的办法:
第一种是限制递归深度。一旦递归过深,超过了我们事先设定的阈值,就停止递归;
第二种是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程,这样就没有了系统栈大小的限制。

C 语言中 qsort() 的底层实现原理:
小规模数据集用归并排序,大规模数据用快速排序,并用堆模拟栈,防止递归函数栈溢出,当元素小于4时,用的是插入排序;因为O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长,时间复杂度是个偏理论的表示方法,计算过程会省略低阶和常数,这些在极小数据集的排序时,也是影响很大的。

第十八天(2020-01-05):

学习了 3 种线性时间复杂度的排序算法,有桶排序、计数排序、基数排序。它们对要排序的数据都有比较苛刻的要求,应用不是非常广泛。但是如果数据特征比较符合这些排序算法的要求,应用这些算法,会非常高效,线性时间复杂度可以达到 O(n)。

桶排序和计数排序的排序思想是非常相似的,都是针对范围不大的数据,将数据划分成不同的桶来实现排序。基数排序要求数据可以划分成高低位,位之间有递进关系。比较两个数,我们只需要比较高位,高位相同的再比较低位。而且每一位的数据范围不能太大,因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。
重点的是掌握这些排序算法的适用场景。

第十七天(2020-01-04):

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理,理解快排的重点也是理解递推公式,还有 partition() 分区函数。

不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式,然后一步步分解推导。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是 O(n)。正因为此,它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 O(n2),但是平均情况下时间复杂度都是 O(nlogn)。不仅如此,快速排序算法时间复杂度退化到 O(n2) 的概率非常小,我们可以通过合理地选择 pivot 来避免这种情况。

第十六天(2020-01-03):

分析了三种时间复杂度是 O(n2) 的排序算法,冒泡排序、插入排序、选择排序。讲述如何分析一个“排序算法”。

排序算法的执行效率:

  1. 最好情况、最坏情况、平均情况时间复杂度;
  2. 时间复杂度的系数、常数 、低阶;
  3. 比较次数和交换(或移动)次数;

排序算法的内存消耗:
指空间复杂度大小;
原地排序指空间复杂度为O(1);

排序算法的稳定性:
如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

冒泡、插入、选择排序都是原地排序;
冒泡、插入是稳定排序;
冒泡、插入的最好时间复杂度是O(n),最坏和平均是O(n2);选择都是O(n2);

平时的小数据处理可以用插入排序,实现起来比较清晰。

第十五天(2020-01-02):

《数据结构与算法之美》
写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。
编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。
递归代码虽然简洁高效,但是,递归代码也有很多弊端。比如,堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等,所以,在编写递归代码的时候,一定要控制好这些副作用。
可以限制递归深度防止堆栈溢出;用缓存结果防止重复计算。

第十四天(2020-01-01):

《数据结构与算法之美》
队列只允许入队和出队,也像栈一样是操作受限的数据结构;
队列最大的特点就是先进先出。跟栈一样,它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就需要像环一样的循环队列。
队列的应用有阻塞队列和并发队列。阻塞队列就是入队、出队操作可以阻塞,并发队列就是队列的操作多线程安全。
对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。

第十三天(2019-12-31):

《数据结构与算法之美》
栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。
栈的功能虽然可以用数组或链表实现,但越灵活的功能可能会造成不可预估的情况,最好能让操作限制在可控可预知的范围内。所以栈虽功能有限,但特殊的结构还是能找到特定的应用场景,比如程序中的栈内存空间。
学习怎样利用均摊时间复杂度分析动态扩容顺序栈的时间度。因为它是周期性地出现大时间复杂度的操作,但这又能均摊到周期内小的时间复杂度内,所以最终时间复杂度以小的为准。

第十二天(2019-12-30):

《设计模式之美》
为什么要分 MVC 三层开发?
代码复用:
各层高内聚的封装数据和功能,可被更上层复用;
隔离变化:
每层都是对特定数据的抽象,某层数据变化不影响其它层;
隔离关注点:
各层只关注自己关心的数据,相当于代码层面的隔离;
提高代码的可测试性:
各层输入输出明确,封装性和内聚性高,便于单元测试;
应对系统的复杂性:
分层方便写出抽象清晰、高内聚、可复用的代码,适合构建复杂系统;

收获:
深入理解业务系统的设计初衷,也能提高写代码的能力

第十一天(2019-12-29):

《设计模式之美》
技术人也要有一些产品思维。对于产品设计、需求分析,我们要学会“借鉴”,一定不要自己闷头想。

面向对象设计聚焦在代码层面(主要是针对类),那系统设计就是聚焦在架构层面(主要是针对模块),两者有很多相似之处。很多设计原则和思想不仅仅可以应用到代码设计中,还能用到架构设计中。实际上,我们可以借鉴面向对象设计的步骤,来做系统设计。

面向对象设计的本质就是把合适的代码放到合适的类中。合理地划分代码可以实现代码的高内聚、低耦合,类与类之间的交互简单清晰,代码整体结构一目了然。类比面向对象设计,系统设计实际上就是将合适的功能放到合适的模块中。合理地划分模块也可以做到模块层面的高内聚、低耦合,架构整洁清晰。

第十天
《设计模式之美》

  1. 如何理解“高内聚、松耦合”?
    “高内聚、松耦合”是一个非常重要的设计思想,能够有效提高代码的可读性和可维护性,缩小功能改动导致的代码改动范围。“高内聚”用来指导类本身的设计,“松耦合”用来指导类与类之间依赖关系的设计。
    所谓高内聚,就是指相近的功能应该放到同一个类中,不相近的功能不要放到同一类中。相近的功能往往会被同时修改,放到同一个类中,修改会比较集中。所谓松耦合指的是,在代码中,类与类之间的依赖关系简单清晰。即使两个类有依赖关系,一个类的代码改动也不会或者很少导致依赖类的代码改动。
  2. 如何理解“迪米特法则”?
    不该有直接依赖关系的类之间,不要有依赖;有依赖关系的类之间,尽量只依赖必要的接口。迪米特法则是希望减少类之间的耦合,让类越独立越好。每个类都应该少了解系统的其他部分。一旦发生变化,需要了解这一变化的类就会比较少。

第九天(2019-12-27):

《设计模式之美》
理解DRY原则
核心思想:不要做重复的事;

可能遇到的重复的情况:
实现逻辑重复
这种重复并不一定是违反DRY原则的,需要再看看语义是否重复。如果是两个不同的功能,但实现逻辑有重复的,可以通过复用里层的逻辑来消除代码逻辑上的重复;

功能语义重复
这种重复需要被消除;

代码执行重复
逻辑在同一功能下被重复执行,需要消除,特别是IO操作;

如何提高代码复用性:
减少代码耦合
满足单一职责原则
模块化
通用代码下沉:越通用的代码被依赖的越多,需要下调到更底层,避免下层代码依赖上层逻辑导致依赖关系交叉;
继承、多态、封装、抽象;
应用模板等设计模式;

收获:
避免设计大而全的模块,因为它往往依赖很多,耦合度必然高,可复用性和维护性就会下降;
对于模块化、通用代码下沉思想的理解,模块功能足够内聚,可以独立使用,而且依赖是单向的,这样才能像搭积木一样由下向上地做系统;
在设计每个模块、类、函数的时候,要像设计一个外部 API 那样,去思考它的复用性;
根据实际应用进行辩证思考和灵活变通,有时候复用的实现成本高,需求又不明确的情况下,可以先实现功能,后续有复用的需求时再调整,但其它原则要尽量遵守,保持代码易懂,方便调整。

第八天(2019-12-26):

《设计模式之美》
学习了:
理解KISS原则
意思就是尽量保持代码简洁

代码行数越少就越“简单”吗?
不是。
如果代码少但难读懂、难维护,团队的成员很难接手,那便不算简单。
如用了大量大段的正则处理字符串,虽然代码行数少,但理解和维护难度增加了很多。

代码复杂就违背KISS原则了吗?
本身问题解决的难度大,那代码复杂,并不违背KISS原则。

如何写出满足KISS原则的代码?
不要使用团队成员不懂的技术去实现;
不要重复造轮子,尽量使用现有成熟的工具;
不要过度优化,考虑过多未来的扩展或复杂的条件,只会让问题变得难以实现,或做出来难以理解;
检验代码是否简洁:code review,如果同事对代码有很多疑问,那证明这个实现不够简洁;

YANGI跟KISS的区别:
YANGI的意思是:你不会需要它,核心思想是:不要过度设计;
KISS说的是“如何做”,而YANG说的是“要不要做”。

收获:
实际开发中,有时候会想得很远,想让功能变得更灵活,适应所有的变化,但这种方案往往会被否决掉,因为这一般都是过度设计,没必要为了未来可能有的东西而花大力气,就算实现了,往往也会让原本简单的流程变得复杂难懂,增加项目的可维护性,往往都是先实现再优化。
KISS原则就是想让我们用一种刚刚好、付出不多不少成本的方式解决问题,现实中需要根据实际场景评估这个边界。

第七天(2019-12-25):

《设计模式之美》
学习了:
如何理解接口隔离原则?
客户端不应该强迫依赖它不需要的接口。其中的“客户端”,可以理解为接口的调用者或者使用者。
我们可以把“接口”理解为下面三种东西:
一组 API 接口集合单个 —— 可以指类或模块;
API 接口或函数;
OOP中的接口概念;

接口隔离原则与单一职责原则的区别?
它们都可以用于类、模块、接口的设计。接口隔离原则还提供了一种判断接口的职责是否单一的标准:通过调用者如何使用接口来间接地判定。如果调用者只使用部分接口或接口的部分功能,那接口的设计就不够职责单一。

收获:
原则的使用还是具有一定的主观性,比如判定功能是否单一,在简单的应用场景下很多功能放在一个类是没问题的,用函数就可以分隔出来,但函数多了就需要类,类多了还需要模块,所以无论是接口隔离原则还是单一职责原则,都还需要结合具体的场景。

第六天(2019-12-24):

《设计模式之美》
什么是里氏替换原则?
子类对象能够替换程序中父类对象出现的任何地方,并且保证原来程序的逻辑行为不变及正确性不被破坏。

哪些代码违背这原则?
子类违背父类函数声明要实现的功能;
子类违背父类对输入、输出、异常的约定;
子类违背父类注释中所罗列的任何特殊说明。

收获
多态与里氏替换原则的区别:
多态是面向对象编程的一大特性,也是面向对象编程语言的一种语法。它是一种代码实现的思路。而里式替换是一种设计原则,是用来指导继承关系中子类该如何设计的,子类的设计要保证在替换父类的时候,不改变原有程序的逻辑以及不破坏原有程序的正确性。
里氏替换原则要求子类不修改父类,也是遵从开闭原则,要求对修改关闭,影响代码扩展性。

第五天(2019-12-23):

《设计模式之美》
理解开闭原则
开闭原则指模块、类的设计需要对扩展开放,对修改关闭。

原则内容比较简明,但实际要做到这一点需要综合实际的逻辑考虑,而不是看有没有修改类的属性或方法这种硬套的规则。
原则的设计初衷:只要它没有破坏原有的代码的正常运行,没有破坏原有的单元测试,我们就可以说,这是一个合格的代码改动。
我觉得扩展是指保持原有的核心可复用逻辑保持不变,原有的测试基本不变,修改则相反,会破坏核心的、可复用的逻辑,导致各个关联的模块都需要同时跟着调整。

如何实行这一原则?
这需要我们在开发中时刻保持扩展意识、抽象意识、封装意识,这些意识比任务开发技巧都重要。

第四天(2019-12-22):

《设计模式之美》
理解单一职责原则
它是面向对象设计的原则之一,指导类和模块甚至方法函数的设计。

如何判断职责是否单一?
从业务场景出发,某一类逻辑复杂了,就需要抽离出来作为单独的模块。
复杂可表现为:属性或方法过多,依赖的类过多,集中操作某几个属性,很难给类命名,总之只要感觉维护起来麻烦了,改个细节要考虑很多可能的影响的时候,就证明设计有问题了。原则就的初衷是为了提高代码可读性和易维护性。

功能是否越单一越好?
不是。功能考虑内聚性,试想一个共同使用的数据或依赖的逻辑写好几份在不同的模块上,改起来多痛苦!所以功能内聚了,维护和可读性就上去了。

第三天(2019-12-21):

《设计模式之美》
从一个鉴权功能的构建中学习到面向对象开发的方法:
首先是需求分析:
我们需要通过沟通、挖掘、分析、假设、梳理,搞清楚具体的需求有哪些,哪些是现在要做的,哪些是未来可能要做的,哪些是不用考虑做的。
需求分析的过程实际上是一个不断迭代优化的过程,可以先尝试做基础的版本,再逐渐深入分析和优化,迭代版本。

明确需求后,就是设计和实现的流程:
1、划分职责进而识别出有哪些类:
这一步应该是最难的,因为类抽象得过细会导致功能不够内聚,抽象的范围大了又会导致数据耦合,这应该就要根据经验来判断了吧。作者提了他的方法是将功能点列出来,找职责相似的功能点合并抽象为一类,还有一些书籍提供的方法是将功能点里的名词抽象为类;我觉得这些都可以作为前期的抽象方法,开发过程或维护过程可以再迭代调整;

2、定义类及其属性和方法:
我觉得属性就是功能点里的名词,方法就是动词,主要就是要注意方法的单一权责问题;

3、定义类与类之间的交互关系:
分为以下四种:
泛化:类间的继承关系;
实现:接口与类的关系;
组合:类实例是另一个类的成员;
依赖:类实例在另一个类中被使用;
通过这些关系,将各个类拉在一起,构成功能;

4、将类组装起来并提供执行入口:
构建一个入口(类或方法),组装各个类,暴露明确的接口给使用者。

一点启发:
如果在看这些教程之前,我设计鉴权功能,肯定是将它们包含在一个类里,然后定义各种变量、方法,子方法实现具体功能点,再用公共的方法将各个子方法组装起来。这种设计是我平时做的最多的,因为需求实现得快,但如果放任不管,随时业务迭代,变量和方法越来越多,功能维护起来就十分得困难。如果用面向对象的话来说,就是没有抽象、封装、数据耦合,这是平时用面向过程的思路去开发所带来的弊端。看了作者的实现思路,给了我另外去设计架构的思路:需求分析、抽象、封装、定义交互关系。这也解惑了我这么久以来觉得为什么看到有些框架要定义那么多类的原因,其实类就是用来抽象、封装,让数据间的关系解耦的同时又保持功能的内聚。代码被读的次数远多于被写的次数,保持易维护、易读是软件开发中必须要掌握的技能。
个人觉得:一开始可能会不习惯,但时刻保持这种意识,遇到不爽的地方多想想多改改,会是个不错的方法,因为开发本身就是个实践动手的事,理论再多没用上也是废的,不断实践锻炼意识和积累经验才能适应变化。

第二天(2019-12-20):

《设计模式之美》
了解贫血模型与充血模型:
1、贫血模型将数据与操作分离,违背了面向对象的封装要求,是一种典型的面向过程编程风格;
2、充血模型则是将数据与操作封装到同一个类,满足面向对象的封装要求,是典型的面向对象网络;
3、设计复杂业务时,充血模型比较适合,复杂业务往往涉及很多代码需要复用,充血模型更适合抽象需要复用的逻辑;
4、如果业务简单,贫血模型能够较快速地开发实现功能;
5、典型的MVC三层架构就是用贫血模型,可以通过改造业务逻辑(service)层,将其中的高业务复杂度的逻辑抽离为充血模式,保持可复用性和易维护性,再由service层依赖并暴露给controller层,service层同时保留业务简单的功能,且负责业务聚合,聚合model数据与controler数据到充血模式的领域模型中。

第一天(2019-12-19):

《设计模式之美》
为什么要多用组合少用继承?
继承和组合都能解决抽象和代码复用问题,但实际开发场景的实体往往共性少特性多,继承的方式往往需要抽象多个类并且出现多层次的关系,导致逻辑耦合过深,影响可读性。组合的方式反而更灵活和轻量。

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/100.html
邮箱:glowrypauky@gmail.com
QQ: 892413924