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 行代码循环执行了 n2遍， 2n2 * unit_time 的执行时间。所以，整段代码总的执行时间…… 阅读全文

摘要：别让性能被“锁”住 我们来看一段代码 var cache map[string]string const NUM_OF_READER int = 40 const READ_TIMES = 100000 func init() { cache = make(map[string]string) cache[a] = aa cache[b] = bb } func lockFreeAccess() { var wg sync.WaitGroup wg.Add(NUM_OF_READER) for i := 0; i NUM_OF_READER; i++ { go func() { for j := 0; j READ_TIMES; j++ { _, err := cache[a] if !err { fmt.Println(Nothing) } } wg.Done() }() } wg.Wait() } func lockAccess() { var wg sync.WaitGroup wg.Add(NUM_OF_READER) m := new(sync.RWMutex) for i := 0; i NUM_OF_READER; i++ { go func() { for j := 0; j READ_TIMES; j++ { m.RLock() _, err := cache[a] if !err { fmt.Println(Nothing) } m.RUnlock() } wg.Done() }() } wg.Wait() } 这段程序一个没有锁，一个有锁。我们看一下测试结果 func BenchmarkLockFree(b *testing.B) { b.ResetTimer() for i := 0; i b.N; i++ { lockFreeAccess() } } //169 6618595 ns/op 77 B/op 1 allocs/op func BenchmarkLock(b *testing.B) { b.R…… 阅读全文

摘要：json解析 内置json解析 利⽤反射实现，通过FeildTag来标识对应的json 值 type BasicInfo struct { Name string `json:name` Age int `json:age` } type JobInfo struct { Skills []string `json:skills` } type Employee struct { BasicInfo BasicInfo `json:basic_info` JobInfo JobInfo `json:job_info` } var jsonStr = `{ basic_info:{ name:Mike, age:30 }, job_info:{ skills:[Java,Go,C] } } ` func TestEmbeddedJson(t *testing.T) { e := new(Employee) err := json.Unmarshal([]byte(jsonStr), e) if err != nil { t.Error(err) } fmt.Println(*e) if v, err := json.Marshal(e); err == nil { fmt.Println(string(v)) } else { t.Error(err) } } 更快的JSON解析 EasyJSON 采用代码生成而非反射 安装：go get -u github.com/mailru/easyjson/... (后面的...需要带上) 使⽤：easyjson -all 结构定义.go (会生成一些代码) 1.比如我们有结构文件 struct_def.go type BasicInfo struct { Name string Age int } type JobInfo struct { Skills []string } type Employee struct { BasicInfo BasicInfo JobInfo JobInfo } 2.执行 easyjson -all struct_def.go会生成 struct_def_easyjs…… 阅读全文

摘要：什么是微内核架构 微内核架构（Microkernel Architecture），也被称为插件化架构（Plugin-in Architecture），是一种面向功能进行拆分的可扩展架构。例如 VS Code、Eclipse 这一类 IDE 软件、UNIX 操作系统等等，都是参照微内核架构设计实现的。 微内核架构的两个核心组件 微内核架构包含两类核心的组件：核心系统（Core System）和插件模块（Plug-in modules）。核心系统负责与具体功能无关的通用功能，例如应用生命周期的管理、插件模块的管理（包括：插件模块的注册、载入、卸载等等）；插件模块负责实现具体的功能，例如一个 Web 框架基本上会按照功能模块拆分成如下的插件模块：路由模块、安全模块、HTTP 编解码模块等等，每个模块都通过插件实现，每一个插件都只做一件事情。 微内核基本架构示意图如下所示： 核心系统功能尽量保持稳定，不要因为插件模块的扩展而不断修改，插件模块可以根据功能需求进行不断扩展。 特点与要点 特点 易于扩展 错误隔离 保持架构⼀致性 要点 内核包含公共流程或通⽤逻辑 将可变或可扩展部分规划为扩展点 抽象扩展点⾏为，定义接⼝ 利⽤插件进⾏扩展 实例 如下图，我们希望实现Agent在系统主机上，这个Agent可以手机文件信息、进程信息、应用信息，以及提供一个扩展点，可以扩展未来其他要收集的信息，因此我们需要提供一个Extension Point。 1.接口Collector定义 type Collector interface { Init(evtReceiver EventReceiver) error Start(agtCtx context.Context) error Stop() error Destory() error } type Event struct { Source string Content string } type EventReceiver interface { OnEvent(evt Event) } 2.定义Agent结构体 type Agent struct { collectors map[string]Collector evtBuf chan Event cancel c…… 阅读全文

摘要：Pipe-Filter 模式，即管道过滤器模式，这是一种非常经典的架构模式，这种模式与工业制造生产流水线非常类似，就像薯片的生产过程，从土豆的清洗、去皮、切片、烘干、油炸，到最后打包完成，整个生产过程被拆分成了多个环节，每个环节处理完成之后，通过传送带传送到下一个环节的机器。整个生产过程每个环节都是独立的，但又环环相扣，只要有一个环节出问题了，生产出来的薯片就会有质量问题。 适用的场景 ⾮常适合与数据处理及数据分析系统 Filter封装数据处理的功能 Pipe⽤于连接Filter传递数据或者在异步处理过程中缓冲数据流 进程内同步调⽤时，pipe演变为数据在⽅法调⽤间传递 松耦合：Filter只跟数据（格式）耦合 Filter 和组合模式 23 个经典设计模式里面有一个设计模式叫组合模式，当 Pipe-Filter 遇上组合模式时，多个 Filter 又可以再组合成一个新的 Filter，如下图所示，组合出来的 Filter 接收的数据与第一个 Filter 保持一致，返回的数据与最后一个 Filter 保持一致。通过组合，就可以将多个简单的 Filter 可以组合成一个更复杂的 Filter。应用这一套理论去实践，我们会发现，Filter 既可以做的很轻便，也可以做得很强大。 实例 接下来我们用Go语言实现上图实例： 1.定义filter接口 // Package pipefilter is to define the interfaces and the structures for pipe-filter style implementation package pipefilter // Request is the input of the filter type Request interface{} // Response is the output of the filter type Response interface{} // Filter interface is the definition of the data processing components // Pipe-Filter structure type Filter interface { Process(data Request) (Respons…… 阅读全文

摘要：“不完全”行为的危险性，go语言中是不支持类型转换的，但我们使用“不安全“编程可以将类型的指针转换成任意其他类型，如下： func TestUnsafe(t *testing.T) { i := 10 f := *(*float64)(unsafe.Pointer(i)) t.Log(unsafe.Pointer(i)) t.Log(f) //5e-323, 并不能得到理想的结果 } 也有能转换成功的例子，比如我们对类型起的别名： type MyInt int //合理的类型转换 func TestConvert(t *testing.T) { a := []int{1, 2, 3, 4} b := *(*[]MyInt)(unsafe.Pointer(a)) t.Log(b) //[1 2 3 4] } 原子类型操作 func TestAtomic(t *testing.T) { var shareBufPtr unsafe.Pointer writeDataFn := func() { data := []int{} for i := 0; i 100; i++ { data = append(data, i) } //写完后再通过原子操作，将指针重新指向 atomic.StorePointer(shareBufPtr, unsafe.Pointer(data)) } readDataFn := func() { data := atomic.LoadPointer(shareBufPtr) fmt.Println(data, *(*[]int)(data)) } var wg sync.WaitGroup writeDataFn() for i := 0; i 10; i++ { wg.Add(1) go func() { for i := 0; i 10; i++ { writeDataFn() time.Sleep(time.Microsecond * 100) } wg.Done() }() wg.Add(1) go func() { for i := 0; i 10; i++ { readDataFn(…… 阅读全文

摘要：reflect.TypeOf vs. reflect.ValueOf reflect.TypeOf 返回类型 (reflect.Type) reflect.ValueOf 返回值 (reflect.Value) 可以从 reflect.Value 获得类型 通过 kind 的来判断类型 func CheckType(v interface{}) { t := reflect.TypeOf(v) switch t.Kind() { case reflect.Float32, reflect.Float64: fmt.Println(Float) case reflect.Int, reflect.Int32, reflect.Int64: fmt.Println(Integer) default: fmt.Println(Unknown, t) } } func TestBasicType(t *testing.T) { var f float64 = 12 CheckType(f) //Float CheckType(f) //Unknown *float64 } func TestTypeAndValue(t *testing.T) { var f int64 = 10 t.Log(reflect.TypeOf(f), reflect.ValueOf(f)) //int64 10 t.Log(reflect.ValueOf(f).Type()) //int64 } 利用反射编写灵活的代码 按名字访问结构的成员 reflect.ValueOf(*e).FieldByName(Name) 按名字访问结构的方法 reflect.ValueOf(e).MethodByName(UpdateAge).Call([]reflect.Value{reflect.ValueOf(1)}) 实例 type Employee struct { EmployeeID string Name string `format:normal` Age int } …… 阅读全文