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 行代码循环执行了 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 } …… 阅读全文

摘要：仅执行一次 C#中的单例模式（懒汉式，线程安全） public class Singleton { private static volatile Singleton instance; private static readonly object syncRoot = new object(); private Singleton() { } public static Singleton GetInstance() { if (instance == null) { lock (syncRoot) { if (instance == null) { instance = new Singleton(); } } } return instance; } } Go的实现 type Singleton struct { data string } var singleInstance *Singleton var once sync.Once func GetSingletonObj() *Singleton { once.Do(func() { fmt.Println(Create Obj) singleInstance = new(Singleton) }) return singleInstance } 测试 func TestGetSingletonObj(t *testing.T) { var wg sync.WaitGroup for i := 0; i 5; i++ { wg.Add(1) go func() { obj := GetSingletonObj() fmt.Printf(%X\n, unsafe.Pointer(obj)) …… 阅读全文

摘要：协程机制（Groutine） Thead VS Groutine 创建时默认的 stack 的⼤⼩ JDK5 以后 Java Thread stack 默认为1M Groutine 的 Stack 初始化⼤⼩为2K 和 KSE （Kernel Space Entity) 的对应关系 Java Thread 是 1:1 Groutine 是 M:N MPG模型 M 代表着一个内核线程，也可以称为一个工作线程。goroutine就是跑在M之上的 P代表着(Processor)处理器 它的主要用途就是用来执行goroutine的，一个P代表执行一个Go代码片段的基础（可以理解为上下文环境），所以它也维护了一个可运行的goroutine队列，和自由的goroutine队列，里面存储了所有需要它来执行的goroutine G 代表着goroutine 实际的数据结构(就是你封装的那个方法)，并维护者goroutine 需要的栈、程序计数器以及它所在的M等信息 我们在看上面这个图，图中P正在执行的Goroutine为蓝色的，处于待执行状态的Goroutine为灰色的，灰色的Goroutine形成了一个队列runqueues 。 我们再看一下三者的宏观图： 由上图可以看出Groutine与KSE是M:N的多对多关系。在这里，当一个P关联多个G时，就会处理G的执行顺序，就是并发，当一个P在执行一个协程工作时，其他的会在等待，当正在执行的协程遇到阻塞情况，例如IO操作等，go的处理器就会去执行其他的协程，因为对于类似IO的操作，处理器不知道你需要多久才能执行结束，所以他不回去等你执行完。 正是因为是非抢占式的，所以才轻松的构造上万的协程，如果是抢占式，那么就会在切换任务时，保存当前的上下文环境，因为当前线程如果正在做一件事，做到一半，我们就强制停止，这时我们就必须多保存很多信息，避免再次切换回来时任务出错。 线程是操作系统层面的多任务，而go的协程属于编译器层面的多任务，go有自己的调度器来调度。一个协程在哪个线程上是不确定的，这个是由调度器来决定的，多个协程可能在一个或多个线程上运行。 编写一个Groutine func TestGroutine(t *testing.T) { for i := 0; i 10; i++ { g…… 阅读全文