Go语言 排序与搜索切片

Python016

Go语言 排序与搜索切片,第1张

Go语言标准库中提供了sort包对整型,浮点型,字符串型切片进行排序,检查一个切片是否排好序,使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

关于sort包内的函数说明与使用,请查看 https://godoc.org/sort

在这里简单讲几个sort包中常用的函数

在Go语言中,对字符串的排序都是按照字节排序,也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法:每次只需要比较㏒₂n个元素,其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数:所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数,该函数是一个闭包,如果该有序切片是升序排列,那么在判断时使用 有序切片的元素 >= 目标元素。该函数返回一个int值,表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引

基本设计思路:

类型转换、类型断言、动态派发。iface,eface。

反射对象具有的方法:

编译优化:

内部实现:

实现 Context 接口有以下几个类型(空实现就忽略了):

互斥锁的控制逻辑:

设计思路:

(以上为写被读阻塞,下面是读被写阻塞)

总结,读写锁的设计还是非常巧妙的:

设计思路:

WaitGroup 有三个暴露的函数:

部件:

设计思路:

结构:

Once 只暴露了一个方法:

实现:

三个关键点:

细节:

让多协程任务的开始执行时间可控(按顺序或归一)。(Context 是控制结束时间)

设计思路: 通过一个锁和内置的 notifyList 队列实现,Wait() 会生成票据,并将等待协程信息加入链表中,等待控制协程中发送信号通知一个(Signal())或所有(Boardcast())等待者(内部实现是通过票据通知的)来控制协程解除阻塞。

暴露四个函数:

实现细节:

部件:

包: golang.org/x/sync/errgroup

作用:开启 func() error 函数签名的协程,在同 Group 下协程并发执行过程并收集首次 err 错误。通过 Context 的传入,还可以控制在首次 err 出现时就终止组内各协程。

设计思路:

结构:

暴露的方法:

实现细节:

注意问题:

包: "golang.org/x/sync/semaphore"

作用:排队借资源(如钱,有借有还)的一种场景。此包相当于对底层信号量的一种暴露。

设计思路:有一定数量的资源 Weight,每一个 waiter 携带一个 channel 和要借的数量 n。通过队列排队执行借贷。

结构:

暴露方法:

细节:

部件:

细节:

包: "golang.org/x/sync/singleflight"

作用:防击穿。瞬时的相同请求只调用一次,response 被所有相同请求共享。

设计思路:按请求的 key 分组(一个 *call 是一个组,用 map 映射存储组),每个组只进行一次访问,组内每个协程会获得对应结果的一个拷贝。

结构:

逻辑:

细节:

部件:

如有错误,请批评指正。

除了Java、Python和JavaScript之外,如果要开始学习一门新语言的话,我想应该是Go!

Go语言正在被越来越多的公司使用。我们公司的后端服务已经全面采用Go语言实现了。

最开始接触Go语言是去年将一份Go代码“翻译”成Python并集成到测试平台上,说来也挺神奇,我从来没学过Go却完成了这个工作,这也侧面反应了Go的语法还是很平易近人的。

今年,在海翔飞调岗之后已经没有太多时间写代码了,但如果要开始学习一个新的语言或技术的话,我最想学的是Go!

目前来看,Go似乎还并没有太多测试人员使用的场景,不过,我之前介绍过的BDD行为驱动框架gauge是由Go开发的,当然,它也支持使用Go来编写BDD测试代码。

对于,已经有一定开发经验的同学,如何快速的开始学习Go语言呢?我这里给一些思路。

#### 第一步:下载和安装

在配置环境的时候你需要重点了解GOROOT、GOPATH的作用。

你还要准备一款称手的编辑器,如果你像我一样,一直都在使用VS Code的话,那么就它就可以了。

#### 第二步:从hello world开始

先运行一个hello world程序,认识Go语言的语法。

package main

import (    "fmt")

func main(){

fmt.Println("helloworld!")

}

#### 第三步:熟悉Go的语法

接下来,你可能要花一周左右的时间熟悉Go语言的语法。比如,变量定义、if/for、函数、Map、跨文件的程序调用…等,当然,还有一些Go特有的知识。

当然,我更喜欢看视频教程,虽然质量参差不齐,但我仍然觉得看视频比我自己看书更有效率。

熟悉一段Go代码:

package main

import"fmt"

func myFunc() {

i := 0

Here:   //这行的第一个词,以冒号结束作为标签

fmt.Println(i)

i++    if i <10{        goto Here   //跳转到Here去

}

}func main() {    //调用函数

myFunc()

}

#### 第四步:Go如何做单元测试

针对Go做测试也非常简单。比如,这是一个被测试文件:add.go。

package test_demofunc Add(a int, b int) int{    return a + b

}

下面针对Add()函数编写测试用例,test_add.go

package test_demo

import (    "testing")

func TestAdd1(t *testing.T){

r:= Add(1, 2)    if r !=3{

t.Errorf("Add(1, 2)failed. Got %d, expected 3.", r)

}

}

func TestAdd2(t *testing.T){

r:= Add(2, 2)    if r !=4{

t.Errorf("Add(2, 2)failed. Got %d, expected 4.", r)

}

}

你只需要执行 go test 命令就可以运行上面的测试了。

#### 第五步:从哪儿找第三方库

当然,你只学习go语言本身,基本是做不了什么事的,必须要使用第三方扩展库。

这里罗列了Go语言的第三方库,通过这些第三方库的介绍,我们也可以大概知道Go可以用来干什么。

如果你知道库的名字的话,也可以在这个网站上搜索。

据我了解,Go的第三方库大多都在GitHub上面。

#### 第六步:用Go做Web开发

Go是静态语言,而且支持并发编程,所以,他有天然的性能优势,大多公司主要使用Go也是开发后端服务(即API)。

终于到了实战阶段,如果我们真的要掌握一门语言,那么一定要用它来开发一个项目出来。这个过程大概需要一个月。

Beego是Go下在主流的Web开发框架,资料相对比较丰富,而且有完善的文档。你可为此制定一个目标,比如用它来开发一个Blog,为此,你需要详细阅读Beego文档,以及学习相关的Web开发技术。

等你完成这个项目的时候,我想你已经会使用Go语言了。