XIAOSUO 记录个人学习的足迹

摘要：如何理解“栈” 栈是一种操作受限的数据结构，只支持入栈和出栈操作。 典型的“栈”结构：后进者先出，先进者后出。 从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 顺序栈的实现 type Item interface { } type ArrayStack struct { items []Item // 数组 count int //栈中元素个数 size int //栈的大小 } func CreateStack(cap int) *ArrayStack { if cap == 0 { panic(不能创建容量为0的栈！) } return ArrayStack{ items: make([]Item, cap), count: 0, size: cap, } } func (a *ArrayStack) Push(e Item) { if a.size=a.count { panic(栈已经满了！) } a.items[count] = e a.count++ } func (a *ArrayStack) Pop() *Item { if a.count == 0 { panic(栈已经空了！) } tmp = a.items[a.count-1] a.count-- return tmp; } } 链式栈实现 type Item interface { } type StackNode struct { el Item next *StackNode } type ListStack struct { top *StackNode count int //栈中元素个数 } func CreateStack() *ListStack { return new(LinkStack) } func (l *LinkStack) Push(el Item) { s := StackNode{el: el, next: l.top} l.t…… 阅读全文

摘要：什么是链表 和数组一样，链表也是一种线性表。 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。 链表的特点 插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。 常用链表 链表结构五花八门，本文来看一下最常见的三种链表结构，它们分别是：单链表、双向链表和循环链表。 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。 从图中可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。 循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。它像一个环一样首尾相连，所以叫作“循环”链表。 双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。 从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。 插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种…… 阅读全文

摘要：数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。 数组如何实现随机访问 数组是一种线性表 顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。 连续的内存空间和相同类型的数据 正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。 低效的插入和删除 插入：从最好O(1) 最坏O(n) 平均O(n) 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。作者举例说明 删除：从最好O(1) 最坏O(n) 平均O(n) 多次删除集中在一起，提高删除效率 记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。 支持动态扩容的数组实现 考虑3个问题 主要的操作 扩容的策略 数据迁移策略 package array type Array struct { data []interface{} size int } func CreateArray(cap int) *Array { if cap == 0 { panic(不能创建容量为0的数组！) } return Array{ data: make([]interface{}, cap), size: 0, } } func (a *Array) GetSize() int { return a.size } func (a *Array) GetCap() int { return len(a.data) } func (a *Array) Get(inde…… 阅读全文

摘要：最近一直在学习Go语言，因为工作中并没有用到Go，为了不让学到的知识点很快忘掉，我打算用Go语言来撸一遍基本的算法，巩固一下Go语法，也温习一下算法基础。今天是这个系列的第一篇，我们来谈谈什么是复杂度分析。 其实，只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而且认为复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。 大 O 复杂度表示法 算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？ 这里有段非常简单的代码，求 1,2,3…n 的累加和。现在，我就带你一块来估算一下这段代码的执行时间。 func cal(n int) int { sum := 0 for i := 0; i = n; i++ { sum += i } return sum } 从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？ 第 2 行代码分别需要 1 个 unit_time 的执行时间，第 3、4行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+1)*unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。 按照这个分析思路，我们再来看这段代码。 func cal(n int) int { sum := 0 for i := 0; i = n; i++ { for j := 0; j = n; j++ { sum += i * j } } return sum } 我们依旧假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢？ 第 2 行代码，每行都需要 1 个 unit_time 的执行时间，第 3 行代码循环执行了 n 遍，需要 n * unit_time 的执行时间，第 4、5 行代码循环执行了 n​2​遍， 2n​2​ * unit_time 的执行时间。所以，整段代码总的…… 阅读全文

摘要：制反转（Inversion of Control，缩写为IoC），是面向对象编程中的一种设计原则，可以用来减低计算机代码之间的耦合度。其中最常见的方式叫做依赖注入（Dependency Injection，简称DI），还有一种方式叫“依赖查找”（Dependency Lookup）。通过控制反转，对象在被创建的时候，由一个调控系统内所有对象的外界实体将其所依赖的对象的引用传递给它。也可以说，依赖被注入到对象中。 控制反转是一种思想，依赖注入是一种设计模式。 阅读全文

摘要： 重构概述 重构的目的：为什么重构（why）？ 对于项目来言，重构可以保持代码质量持续处于一个可控状态，不至于腐化到无可救药的地步。对于个人而言，重构非常锻炼一个人的代码能力，并且是一件非常有成就感的事情。它是我们学习的经典设计思想、原则、模式、编程规范等理论知识的练兵场。 重构的对象：重构什么（what）？ 按照重构的规模，我们可以将重构大致分为大规模高层次的重构和小规模低层次的重构。大规模高层次重构包括对代码分层、模块化、解耦、梳理类之间的交互关系、抽象复用组件等等。这部分工作利用的更多的是比较抽象、比较顶层的设计思想、原则、模式。小规模低层次的重构包括规范命名、注释、修正函数参数过多、消除超大类、提取重复代码等等编程细节问题，主要是针对类、函数级别的重构。小规模低层次的重构更多的是利用编码规范这一理论知识。 重构的时机：什么时候重构（when）？ 我们一定要建立持续重构意识，把重构作为开发必不可少的部分，融入到日常开发中，而不是等到代码出现很大问题的时候，再大刀阔斧地重构。 重构的方法：如何重构（how）？ 大规模高层次的重构难度比较大，需要组织、有计划地进行，分阶段地小步快跑，时刻让代码处于一个可运行的状态。而小规模低层次的重构，因为影响范围小，改动耗时短，所以，只要你愿意并且有时间，随时随地都可以去做。 单元测试 什么是单元测试？ 单元测试是代码层面的测试，由研发自己来编写，用于测试“自己”编写的代码的逻辑的正确性。单元测试顾名思义是测试一个“单元”，有别于集成测试，这个“单元”一般是类或函数，而不是模块或者系统。 为什么要写单元测试？ 写单元测试的过程本身就是代码 Code Review 和重构的过程，能有效地发现代码中的 bug 和代码设计上的问题。除此之外，单元测试还是对集成测试的有力补充，还能帮助我们快速熟悉代码，是 TDD 可落地执行的改进方案。 如何编写单元测试？ 写单元测试就是针对代码设计各种测试用例，以覆盖各种输入、异常、边界情况，并将其翻译成代码。我们可以利用一些测试框架来简化单元测试的编写。除此之外，对于单元测试，我们需要建立以下正确的认知： 编写单元测试尽管繁琐，但并不是太耗时； 我们可以稍微放低对单元测试代码质量的要求； 覆…… 阅读全文

摘要： 经典的设计原则，其中包括，SOLID、KISS、YAGNI、DRY、LOD 等。SOLID 原则，实际上，SOLID 原则并非单纯的 1 个原则，而是由 5 个设计原则组成的，它们分别是：单一职责原则、开闭原则、里式替换原则、接口隔离原则和依赖反转原则，依次对应 SOLID 中的 S、O、L、I、D 这 5 个英文字母。 单一职责原则(SRP) 如何理解单一职责原则（SRP）？ 一个类只负责完成一个职责或者功能。不要设计大而全的类，要设计粒度小、功能单一的类。单一职责原则是为了实现代码高内聚、低耦合，提高代码的复用性、可读性、可维护性。 如何判断类的职责是否足够单一？ 不同的应用场景、不同阶段的需求背景、不同的业务层面，对同一个类的职责是否单一，可能会有不同的判定结果。实际上，一些侧面的判断指标更具有指导意义和可执行性，比如，出现下面这些情况就有可能说明这类的设计不满足单一职责原则：类中的代码行数、函数或者属性过多；类依赖的其他类过多，或者依赖类的其他类过多；私有方法过多；比较难给类起一个合适的名字；类中大量的方法都是集中操作类中的某几个属性。 类的职责是否设计得越单一越好？ 单一职责原则通过避免设计大而全的类，避免将不相关的功能耦合在一起，来提高类的内聚性。同时，类职责单一，类依赖的和被依赖的其他类也会变少，减少了代码的耦合性，以此来实现代码的高内聚、低耦合。但是，如果拆分得过细，实际上会适得其反，反倒会降低内聚性，也会影响代码的可维护性。 出现下面这些情况就有可能说明这类的设计不满足单一职责原则： 类中的代码行数、函数或者属性过多； 类依赖的其他类过多或者依赖类的其他类过多； 私有方法过多； 比较难给类起一个合适的名字； 类中大量的方法都是集中操作类中的某几个属性。 开闭原则(OCP) 如何理解“对扩展开放、对修改关闭”？ 添加一个新的功能，应该是通过在已有代码基础上扩展代码（新增模块、类、方法、属性等），而非修改已有代码（修改模块、类、方法、属性等）的方式来完成。关于定义，我们有两点要注意。第一点是，开闭原则并不是说完全杜绝修改，而是以最小的修改代码的代价来完成新功能的开发。第二点是，同样的代码改动，在粗代码粒度下，可能被认定为“修改”；在细代码粒度下，可能又被认定…… 阅读全文

摘要： 面向对象概述 什么是面向对象编程？ 面向对象编程是一种编程范式或编程风格。它以类或对象作为组织代码的基本单元，并将封装、抽象、继承、多态四个特性，作为代码设计和实现的基石 。 什么是面向对象编程语言？ 面向对象编程语言是支持类或对象的语法机制，并有现成的语法机制，能方便地实现面向对象编程四大特性（封装、抽象、继承、多态）的编程语言。 如何判定一个编程语言是否是面向对象编程语言？ 如果按照严格的的定义，需要有现成的语法支持类、对象、四大特性才能叫作面向对象编程语言。如果放宽要求的话，只要某种编程语言支持类、对象语法机制，那基本上就可以说这种编程语言是面向对象编程语言了，不一定非得要求具有所有的四大特性。 面向对象编程和面向对象编程语言之间有何关系？ 面向对象编程一般使用面向对象编程语言来进行，但是，不用面向对象编程语言，我们照样可以进行面向对象编程。反过来讲，即便我们使用面向对象编程语言，写出来的代码也不一定是面向对象编程风格的，也有可能是面向过程编程风格的。 什么是面向对象分析和面向对象设计？ 简单点讲，面向对象分析就是要搞清楚做什么，面向对象设计就是要搞清楚怎么做。两个阶段最终的产出是类的设计，包括程序被拆解为哪些类，每个类有哪些属性方法、类与类之间如何交互等等。 面向对象四大特性 关于封装特性 封装也叫作信息隐藏或者数据访问保护。类通过暴露有限的访问接口，授权外部仅能通过类提供的方式来访问内部信息或者数据。它需要编程语言提供权限访问控制语法来支持，例如 C# 中的 private、protected、public 关键字。封装特性存在的意义，一方面是保护数据不被随意修改，提高代码的可维护性；另一方面是仅暴露有限的必要接口，提高类的易用性。 关于抽象特性 封装主要讲如何隐藏信息、保护数据，那抽象就是讲如何隐藏方法的具体实现，让使用者只需要关心方法提供了哪些功能，不需要知道这些功能是如何实现的。抽象可以通过接口类或者抽象类来实现，但也并不需要特殊的语法机制来支持。抽象存在的意义，一方面是提高代码的可扩展性、维护性，修改实现不需要改变定义，减少代码的改动范围；另一方面，它也是处理复杂系统的有效手段，能有效地过滤掉不必要关注的信息。 关于继承特性 继承是用来…… 阅读全文

摘要： 一、引言：为什么关注代码质量？ “任何一个傻瓜都能写出计算机可以理解的代码，唯有能写出人类容易理解的代码的，才是优秀的程序员。” —— Martin Fowler 代码质量直接决定： 系统长期维护成本 缺陷修复效率 团队协作流畅度 技术债务积累速度 二、核心评价维度（思维导图模块解析） 1. 如何评价代码质量的高低？ 核心矛盾：主观性 vs 客观标准 解决方案：多维度综合评估（如图所示） graph LR A[代码质量] -- B[技术维度] A -- C[业务维度] B -- D[可维护性] B -- E[可读性] B -- F[性能] C -- G[需求契合度] C -- H[变更响应速度] 2. 最常用的7大标准（优先级排序） | 标准 | 重要性 | 关键表现 | | :----------: | :----: | :--------------------------: | | 可维护性 | ★★★ | 修改成本低，风险可控 | | 可读性 | ★★★ | 命名清晰，结构直观，文档完备 | | 可扩展性 | ★★☆ | 新功能添加无需重构核心逻辑 | | 可测试性 | ★★☆ | 单元测试覆盖率80% | | 灵活性 | ★★☆ | 支持多种使用场景 | | 简洁性 | ★★☆ | 无过度设计，YAGNI原则 | | 可复用性 | ★☆☆ | 模块化程度高，依赖清晰 | 💡 黄金三角：可维护性、可读性、可扩展性是质量基石（如图重点标注） 三、实践方法论 如何才能写出高质量代码？ 具体实施建议： 设计四重奏 封装变化点（如用策略模式替代if-else） 依赖接口而非实现（DIP原则） 限界上下文划分（领域驱动设计） 代码可读性技巧 // Bad ❌ boolean f = (a 5) (b 10); // Good ✅ boolean isWithinValidRa…… 阅读全文

摘要： 中央处理器（CPU），是电子计算机的主要设备之一，电脑中的核心配件。其功能主要是解释计算机指令以及处理计算机软件中的数据。CPU是计算机中负责读取指令，对指令译码并执行指令的核心部件。中央处理器主要包括两个部分，即控制器、运算器，其中还包括高速缓冲存储器及实现它们之间联系的数据、控制的总线。电子计算机三大核心部件就是CPU、内部存储器、输入/输出设备。中央处理器的功效主要为处理指令、执行操作、控制时间、处理数据。 [2] 在计算机体系结构中，CPU 是对计算机的所有硬件资源（如存储器、输入输出单元） 进行控制调配、执行通用运算的核心硬件单元。CPU 是计算机的运算和控制核心。计算机系统中所有软件层的操作，最终都将通过指令集映射为CPU的操作。 在计算机体系结构中，CPU 是对计算机的所有硬件资源（如存储器、输入输出单元） 进行控制调配、执行通用运算的核心硬件单元。CPU 是计算机的运算和控制核心。计算机系统中所有软件层的操作，最终都将通过指令集映射为CPU的操作。 阅读全文