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）。通过控制反转，对象在被创建的时候，由一个调控系统内所有对象的外界实体将其所依赖的对象的引用传递给它。也可以说，依赖被注入到对象中。 控制反转是一种思想，依赖注入是一种设计模式。 阅读全文

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

摘要：Deployment 使用 Kubernetes提供了一种更加简单的更新RC和Pod的机制，叫做Deployment。通过在Deployment中描述你所期望的集群状态，Deployment Controller会将现在的集群状态在一个可控的速度下逐步更新成你所期望的集群状态。Deployment主要职责同样是为了保证pod的数量和健康，90%的功能与Replication Controller完全一样，可以看做新一代的Replication Controller。但是，它又具备了Replication Controller之外的新特性：Replication Controller全部功能：Deployment继承了上面描述的Replication Controller全部功能。 事件和状态查看：可以查看Deployment的升级详细进度和状态。 回滚：当升级pod镜像或者相关参数的时候发现问题，可以使用回滚操作回滚到上一个稳定的版本或者指定的版本。 版本记录: 每一次对Deployment的操作，都能保存下来，给予后续可能的回滚使用。 暂停和启动：对于每一次升级，都能够随时暂停和启动。 多种升级方案：Recreate----删除所有已存在的pod,重新创建新的; RollingUpdate----滚动升级，逐步替换的策略，同时滚动升级时，支持更多的附加参数，例如设置最大不可用pod数量，最小升级间隔时间等等。 #创建命令：kubectl create -f deployment.yaml --record #使用rollout history命令，查看Deployment的历史信息：kubectl rollout history deployment cango-demo #使用rollout undo回滚到上一版本: kubectl rollout undo deployment cango-demo #使用–to-revision可以回滚到指定版本: kubectl rollout undo deployment hello-deployment --to-revision=2 1234 ConfigMap 配置 在几乎所有的应用开发中，都会涉及到配置文件的变更，比如说在web的程序中，需要连接数据库，缓存甚至是队列等等。 一些大公司专门开发了自己…… 阅读全文

摘要：webapi：使用asp.net core使用c#创建的Restful服务，就是webapi, webapi中的控制器是派生自ControllerBase的类， ControllerBase类 不要通过从 Controller 类派生来创建 Web API 控制器。 Controller 派生自 ControllerBase，并添加对视图的支持，因此它用于处理 Web 页面，而不是 Web API 请求。 此规则有一个例外：如果打算为视图和 Web API 使用相同的控制器，则从 Controller 派生控制器。 ControllerBase 类提供了很多用于处理 HTTP 请求的属性和方法。 例如，ControllerBase.CreatedAtAction 返回 201 状态代码： 下面是 ControllerBase 提供的方法的更多示例。 方法 说明 BadRequest 返回 400 状态代码。 NotFound 返回 404 状态代码。 PhysicalFile 返回文件。 TryUpdateModelAsync 调用模型绑定。 TryValidateModel 调用模型验证。 特性 Microsoft.AspNetCore.Mvc 命名空间提供可用于配置 Web API 控制器的行为和操作方法的属性。 下述示例使用属性来指定受支持的 HTTP 操作动作和所有可返回的已知 HTTP 状态代码： HttpPost [ProducesResponseType(StatusCodes.Status400BadRequest)] public ActionResult Create(Pet pet) { pet.Id = _petsInMemoryStore.Any() ? _petsInMemoryStore.Max(p = p.Id) + 1 : 1; _petsInMemoryStore.Add(pet); return CreatedAtAction(nameof(GetById), new { id = pet.Id }, pet); } 特性 说明 [[Route\]] 指定控制器或操作的 URL 模式。 [[Bind\]] 指定要包含的前缀和属性，以进行模型绑定。 [[HttpGet\…… 阅读全文

摘要：什么是API API全称Aplication Programming Itererface即应用程序编程接口， 我们在开发应用程序时经常用到。API作为接口，用来“连接”两个不同的系统，并使其中一方为另一 方提供服务，比如在操作系统上运行的应用程序能够访问操作系统所提供的API,并通过这些API来调用操,作系统的各种功能。因此，API 是一个系统向外暴露或公开的一套接口， 通过这些接口，外部应用程序能够访问该系统。在Web应用程序中，Web API具有同样的特性，它作为一个Web应用程序，向外提供了,在Web应用程序中，Web API具有同样的特性，它作为一个Web应用程序，向外提供了一些接口， 这些接口的功能通常是对数据进行操作,一些接口， 这些接口的功能通常是对数据进行操作(如获取或修改数据等)，它们能够被外部应用程序，比如桌面应用程序、手机应用甚至其他Web应用程序(如ASP.NET Core MVC视图应用、单页Web应用)等访问并调用。WebAPI能够实现不同应用程序之间的访问，它与平台或编程语言无关，可以使用不同的技术来构建Web API,如Java、.NET等; 什么是REST REST(Representational State Transfer) 表述性传递状态，Roy Fielding博士在2000年他的博士论文中提出来的一种软件架构风格，作为一种web服务的设计与开发方式，Rest可以降低开发的复杂性，提高系统的可伸缩性。 REST是一种基于资源的架构风格，在REST中，资源(Resource)是最基本的概念任何能够命名的对象都是资源，如：user,team,order,docment。他表示web服务要操作的一个实体，一个资源具有一个统一资源标识符。(Uniform Resource Identifier URI),如 users/123。通过资源能够标识并访问资源。 资源标识 主键编号进行标识 资源集合 除了单个资源外，资源集合表示多个相同类型的资源，如users。在系统设计时，不同的实体之间往往存在着某种关联关系。如一个用户有多个订单。同样，在REST中，这种关联关系也能够有资源之间的层次关系体现出来。如users/123/orders/1 由于REST资源为中心，因此REST接口的端点(Endpoint)均以资源或资源集合结尾，它…… 阅读全文

摘要：OpenID Connect 如果要谈单点登录和身份认证，就不得不谈OpenID Connect (OIDC)。最典型的使用实例就是使用Google账户登录其他应用，这一经典的协议模式，为其他厂商的第三方登录起到了标杆的作用，被广泛参考和使用。 OpenID Connect简介 OpenID Connect是基于OAuth 2.0规范族的可互操作的身份验证协议。它使用简单的REST / JSON消息流来实现，和之前任何一种身份认证协议相比，开发者可以轻松集成。 OpenID Connect允许开发者验证跨网站和应用的用户，而无需拥有和管理密码文件。OpenID Connect允许所有类型的客户,包括基于浏览器的JavaScript和本机移动应用程序,启动登录流动和接收可验证断言对登录用户的身份。 OpenID的历史是什么？ OpenID Connect是OpenID的第三代技术。首先是原始的OpenID，它不是商业应用，但让行业领导者思考什么是可能的。OpenID 2.0设计更为完善，提供良好的安全性保证。然而，其自身存在一些设计上的局限性，最致命的是其中依赖方必须是网页，但不能是本机应用程序；此外它还要依赖XML，这些都会导致一些应用问题。 OpenID Connect的目标是让更多的开发者使用，并扩大其使用范围。幸运的是，这个目标并不遥远，现在有很好的商业和开源库来帮助实现身份验证机制。 OIDC基础 简要而言，OIDC是一种安全机制，用于应用连接到身份认证服务器（Identity Service）获取用户信息，并将这些信息以安全可靠的方法返回给应用。 在最初，因为OpenID1/2经常和OAuth协议（一种授权协议）一起提及，所以二者经常被搞混。 OpenID是Authentication，即认证，对用户的身份进行认证，判断其身份是否有效，也就是让网站知道“你是你所声称的那个用户”； OAuth是Authorization，即授权，在已知用户身份合法的情况下，经用户授权来允许某些操作，也就是让网站知道“你能被允许做那些事情”。 由此可知，授权要在认证之后进行，只有确定用户身份只有才能授权。 (身份验证)+ OAuth 2.0 = OpenID Connect OpenID Connect是“认证”和“授权”的结合，因为其基于OAuth协议，…… 阅读全文