XIAOSUO 记录个人学习的足迹

摘要：数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从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 的执行时间。所以，整段代码总的…… 阅读全文

摘要：别让性能被“锁”住 我们来看一段代码 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…… 阅读全文