从零开始学golang之Dijkstra

freedbg 发表了文章 • 3 个评论 • 227 次浏览 • 2018-01-31 04:14 • 来自相关话题

package main

import (
    "fmt"
)

const MAX_SIZE int = 5
const MAX_V... 			查看全部
					
package main

import (
"fmt"
)

const MAX_SIZE int = 5
const MAX_VALUE int = 9999

func main() {
fmt.Println("Dijkstra")
var gg Graph
var vexs = []string{"A", "B", "C", "D", "E"}
gg.vexnum = 5
gg.vexs = vexs
initGG(&gg, vexs)
PrintG(gg, 5)
Dijkstra(&gg, 1)
}

type Graph struct {
vexs []string //定点集合
vexnum int //定点数量
edgnum int //边数量
matrix [MAX_SIZE][MAX_SIZE]int //邻接矩阵
}

type Edge struct {
start string
end string
weight int
}

func Dijkstra(gg *Graph, start int) {

var dist [MAX_SIZE]int //路劲长度数组
var ss [MAX_SIZE]bool //最短路劲节点集合

//init
dist = gg.matrix[start]
ss[start] = true //find start to start
dist[start] = 0 //start to start length

for i := 0; i < gg.vexnum; i++ {
k := 0
min := MAX_VALUE
fmt.Println("-----------")
fmt.Println(dist, ss)
//find next 贪心
for j := 0; j < len(dist); j++ {
if ss[j] == false && dist[j] != MAX_VALUE && dist[j] < min {
min = dist[j]
k = j
}
}

//set find
ss[k] = true

//update dist length
for u := 0; u < gg.vexnum; u++ {
if gg.matrix[k][u] != MAX_VALUE && ss[u] == false {
weight := min + gg.matrix[k][u]
if weight < dist[u] {
dist[u] = weight
}
}
}

}

for i := 0; i < gg.vexnum; i++ {
fmt.Printf("shortest %s->%s = %d\n", gg.vexs[start], gg.vexs[i], dist[i])
}
}

func initGG(gg *Graph, vexs []string) {
for i := 0; i < len(vexs); i++ {
for j := 0; j < len(vexs); j++ {
gg.matrix[i][j] = MAX_VALUE
}
}
gg.matrix[0][1] = 5
gg.matrix[0][2] = 3

gg.matrix[1][0] = 5
gg.matrix[1][3] = 99
gg.matrix[1][4] = 4

gg.matrix[2][0] = 3
gg.matrix[2][3] = 6

gg.matrix[3][1] = 7
gg.matrix[3][2] = 6
gg.matrix[3][4] = 1

gg.matrix[4][1] = 4
gg.matrix[4][3] = 1

gg.edgnum = 12 / 2
}

func PrintG(gg Graph, l int) {
for i := 0; i < l; i++ {
fmt.Println(gg.matrix[i])
}
}

喜欢拉代码得兄弟自己下载


https://github.com/godla/golang-sort-data-structures-study.git


一起每天写一点

golang pprof 性能分析工具

hatlonely 发表了文章 • 1 个评论 • 302 次浏览 • 2018-01-30 22:50 • 来自相关话题

性能优化是个永恒的话题,而很多时候我们在作性能优化的时候,往往基于代码上面的直觉,把所有能想到的优化都优化了一遍,不错过任何小的优化点,结果整个代码的逻辑变得极其复杂,而性能上面并没有太大的提升。事实上,性能问题往往集中在某些小点,有时候很小的改动就能有... 查看全部

性能优化是个永恒的话题,而很多时候我们在作性能优化的时候,往往基于代码上面的直觉,把所有能想到的优化都优化了一遍,不错过任何小的优化点,结果整个代码的逻辑变得极其复杂,而性能上面并没有太大的提升。事实上,性能问题往往集中在某些小点,有时候很小的改动就能有巨大的提升,所以问题的关键是是怎么去找出这些优化点,幸运的是 golang 在设计的时候就考虑了这个问题,原生提供了性能分析的工具,可以很方便地帮我们找到性能瓶颈


pprof 简介


golang 的性能分析库在 runtime/pprof 里,主要提供下面几个接口


// 堆栈分析
func WriteHeapProfile(w io.Writer) error
// cpu分析
func StartCPUProfile(w io.Writer) error
func StopCPUProfile()

使用上面比较简单,只需要将文件指针传给对应的函数即可,性能数据将写入到文件中,然后可以使用 golang 自带的 pprof 工具生成 svg,pdf 的可视化图,然后就可以很直观地从这些图里面看到主要的性能消耗了


举个例子


首先需要一个程序


首先需要在你的程序里面注入 pprof 代码,下面是一段示例代码,完整代码在:https://github.com/hatlonely/hellogolang/blob/master/cmd/pprof_runtime.go,这里使用的 PPCmd 方法,是为了方便使用,做的一个简单封装,代码在:https://github.com/hatlonely/easygolang/blob/master/pprof/pprof.go


func main() {
go doSomething1()
go doSomething2()
go doSomething3()

if err := pprof.PPCmd("cpu 10s"); err != nil {
panic(err)
}

if err := pprof.PPCmd("mem"); err != nil {
panic(err)
}
}

编译,运行上面代码会生成两个 pprof 文件,cpu.pprof.yyyymmddhhmmssmem.pprof.yyyymmddhhmmss,编译运行的方法如下:


cd $GOPATH/src
git clone git@github.com:hatlonely/hellogolang.git
cd hellogolang
glide install
go build cmd/pprof_runtime.go
./pprof_runtime

pprof 文件分析


pprof 文件是二进制的,不是给人读的,需要翻译一下,而 golang 原生就给我们提供了分析工具,直接执行下面命令即可,会生成一张很直观的 svg 图片,直接用 chrome 就可以打开,当然也可以生成别的格式(pdf,png 都可以),可以用 go tool pprof -h 命令查看支持的输出类型


go tool pprof -svg ./pprof_runtime cpu.pprof.201801301415 > cpu.svg

注意这个工具依赖于 graphviz 工具,Mac 上可用 brew install graphviz,centos yum install graphviz 即可


性能分析图


http 接口


net/http/pprof 里面对 runtime/pprof 作了一些封装,对外提供了 http 接口,可以直接通过浏览器访问,但是只是一些字符串的结果,没有作可视化,体验并不是很好,用 go tool 访问体验能好一点


go tool pprof http://localhost:3000/debug/pprof/profile
go tool pprof http://localhost:3000/debug/pprof/heap

个人感觉这个接口比较鸡肋,首先最大的问题是展示上面并不直观,要是能直接在网页上面可视化地展示可能还真的挺方便的;还有就是需要额外的提供一个 http 的端口,而这个接口还依赖 net/http这就意味着如果你的应用使用的是其他第三方的 http 库,可能还需要解决兼容性的问题;实际上,我再使用这个接口的时候,在服务器压力较大的场景下,会出现访问超时,而这种压力较大情况下的性能可能才是真正的性能瓶颈。


建议在根据的需求,自己封装 runtime/pprof 的接口,当然是用场景比较简单也可以用我上面的封装,然后在服务里面自己提供一个专门的性能分析接口(可能是 gprc,thrift,或者其他的第三方 http 框架)


火焰图


除了上面生成的 svg 图,还可以生成火焰图,这是 uber 提供的一个工具,在显示上面可能更直观一些


安装命令如下:


go get github.com/uber/go-torch
git clone git@github.com:brendangregg/FlameGraph.git
export PATH=$PATH:/path/to/FlameGraph

使用方法如下:


go-torch --binaryname=./pprof_runtime --binaryinput=cpu.pprof.201801301415

性能分析图


参考链接




转载请注明出处
本文链接:http://hatlonely.github.io/2018/01/29/golang-pprof-性能分析工具/


golang json 性能分析

hatlonely 发表了文章 • 2 个评论 • 407 次浏览 • 2018-01-28 16:46 • 来自相关话题

Json 作为一种重要的数据格式,具有良好的可读性以及自描述性,广泛地应用在各种数据传输场景中。Go 语言里面原生支持了这种数据格式的序列化以及反序列化,内部使用反射机制实现,性能有点差,在高度依赖 json 解析的应用里,往往会成为性能瓶颈,好在已有很... 查看全部

Json 作为一种重要的数据格式,具有良好的可读性以及自描述性,广泛地应用在各种数据传输场景中。Go 语言里面原生支持了这种数据格式的序列化以及反序列化,内部使用反射机制实现,性能有点差,在高度依赖 json 解析的应用里,往往会成为性能瓶颈,好在已有很多第三方库帮我们解决了这个问题,但是这么多库,对于像我这种有选择困难症的人来说,到底要怎么选择呢,下面就给大家来一一分析一下


ffjson


go get -u github.com/pquerna/ffjson

原生的库性能比较差的主要原因是使用了很多反射的机制,为了解决这个问题,ffjson 通过预编译生成代码,类型的判断在预编译阶段已经确定,避免了在运行时的反射


但也因此在编译前需要多一个步骤,需要先生成 ffjson 代码,生成代码只需要执行 ffjson <file.go> 就可以了,其中 file.go 是一个包含 json 结构体定义的 go 文件。注意这里 ffjson 是这个库提供的一个代码生成工具,直接执行上面的 go get 会把这个工具安装在 $GOPATH/bin 目录下,把 $GOPATH/bin 加到 $PATH 环境变量里面,可以全局访问


另外,如果有些结构,不想让 ffjson 生成代码,可以通过增加注释的方式


// ffjson: skip
type Foo struct {
Bar string
}

// ffjson: nodecoder
type Foo struct {
Bar string
}

easyjson


go get -u github.com/mailru/easyjson/...

easyjson 的思想和 ffjson 是一致的,都是增加一个预编译的过程,预先生成对应结构的序列化反序列化代码,除此之外,easyjson 还放弃了一些原生库里面支持的一些不必要的特性,比如:key 类型声明,key 大小写不敏感等等,以达到更高的性能


生成代码执行 easyjson -all <file.go> 即可,如果不指定 -all 参数,只会对带有 //easyjson:json 的结构生成代码


//easyjson:json
type A struct {
Bar string
}

jsoniter


go get -u github.com/json-iterator/go

这是一个很神奇的库,滴滴开发的,不像 easyjson 和 ffjson 都使用了预编译,而且 100% 兼容原生库,但是性能超级好,也不知道怎么实现的,如果有人知道的话,可以告诉我一下吗?


使用上面,你只要把所有的


import "encoding/json"

替换成


import "github.com/json-iterator/go"

var json = jsoniter.ConfigCompatibleWithStandardLibrary

就可以了,其它都不需要动


codec-json


go get -u github.com/ugorji/go/codec

这个库里面其实包含很多内容,json 只是其中的一个功能,比较老,使用起来比较麻烦,性能也不是很好


jsonparser


go get -u github.com/buger/jsonparser

严格来说,这个库不属于 json 序列化的库,只是提供了一些 json 解析的接口,使用的时候需要自己去设置结构里面的值,事实上,每次调用都需要重新解析 json 对象,性能并不是很好


就像名字暗示的那样,这个库只是一个解析库,并没有序列化的接口


性能测试


对上面这些 json 库,作了一些性能测试,测试代码在:https://github.com/hatlonely/hellogolang/blob/master/internal/json/json_benchmark_test.go,下面是在我的 Macbook 上测试的结果(实际结果和库的版本以及机器环境有关,建议自己再测试一遍):


BenchmarkMarshalStdJson-4                    1000000          1097 ns/op
BenchmarkMarshalJsonIterator-4 2000000 781 ns/op
BenchmarkMarshalFfjson-4 2000000 941 ns/op
BenchmarkMarshalEasyjson-4 3000000 513 ns/op
BenchmarkMarshalCodecJson-4 1000000 1074 ns/op
BenchmarkMarshalCodecJsonWithBufio-4 1000000 2161 ns/op
BenchmarkUnMarshalStdJson-4 500000 2512 ns/op
BenchmarkUnMarshalJsonIterator-4 2000000 591 ns/op
BenchmarkUnMarshalFfjson-4 1000000 1127 ns/op
BenchmarkUnMarshalEasyjson-4 2000000 608 ns/op
BenchmarkUnMarshalCodecJson-4 20000 122694 ns/op
BenchmarkUnMarshalCodecJsonWithBufio-4 500000 3417 ns/op
BenchmarkUnMarshalJsonparser-4 2000000 877 ns/op

golang_json_performance


从上面的结果可以看出来:



  1. easyjson 无论是序列化还是反序列化都是最优的,序列化提升了1倍,反序列化提升了3倍

  2. jsoniter 性能也很好,接近于easyjson,关键是没有预编译过程,100%兼容原生库

  3. ffjson 的序列化提升并不明显,反序列化提升了1倍

  4. codecjson 和原生库相比,差不太多,甚至更差

  5. jsonparser 不太适合这样的场景,性能提升并不明显,而且没有反序列化


所以综合考虑,建议大家使用 jsoniter,如果追求极致的性能,考虑 easyjson


参考链接


ffjson: https://github.com/pquerna/ffjson
easyjson: https://github.com/mailru/easyjson
jsoniter: https://github.com/json-iterator/go
jsonparser: https://github.com/buger/jsonparser
codecjson: http://ugorji.net/blog/go-codec-primer



转载请注明出处
本文链接:http://hatlonely.github.io/2018/01/28/golang-json-性能分析/


nxlog4go 简介 - 基于log4go的下一代日志系统

ccpaging 发表了文章 • 2 个评论 • 1773 次浏览 • 2018-01-28 00:22 • 来自相关话题

nxlog4go的项目网址:

https://github.com/ccpaging/nxlog4go

项目历史

... 查看全部

nxlog4go的项目网址:


https://github.com/ccpaging/nxlog4go


项目历史


ccpaging's log4go forked from https://github.com/alecthomas/log4go


The latest release is 4.0.3 详见:https://github.com/ccpaging/log4go/releases


修复了一些bug。在修改的过程中产生了不少想法。详见:http://www.cnblogs.com/ccpaging/p/7205226.html


实现这些想法要修改log4go的基本框架,因此,项目更名为 nxlog4go


nxlog4go 简介


nxlog4go 融合了log4net 与 go log的基本框架。


Logger 是日志记录容器。包含了若干 Filter。另外,nxlog4go的Logger兼容了go log的io.Writer,同样支持io,MultiWriter。


Filter 基于level过滤日志。每个 Filter 包含一个 Appender。


Appender 输出日志。例如,输出到彩色终端、滚动文件、TCP/IP网络日志服务器等。


Layout 格式化日志。


详细了解log4net的结构请参考:




  1. log4net Tutorial



  2. log4net教程


Logger


Logger 的结构如下:


type Logger struct {
mu sync.Mutex // ensures atomic writes; protects the following fields

prefix string // prefix to write at beginning of each line
caller bool // runtime caller skip

out io.Writer // destination for output
level Level // The log level
layout Layout // format record for output

filters *Filters // a collection of Filters
}

分成几个部分:




  1. 锁。协调写日志和改变配置。如果能保证在写日志前配置,锁不是必须的。




  2. 前缀和取源程序文件名行号的开关。由于后者消耗了大量的cpu,可能不适合生产环境,因此,设置了开关可以关闭。前缀可以在多模块的系统中用于区分不同的模块。也许在网络搜集日志的模型中可用于过滤和分发。




  3. go log兼容的 io.Writer 以及附加的level过滤和layout格式化。nxlog4go 的 logger 直接使用而无需添加任何的 Appender。方便程序员在开发环境下使用。



  4. filter容器的指针。使用指针可以容易的设置和重置。


新建 Logger 有三种方式:




  1. 使用 nxlog4go 内建的 logger。




  2. 在main.go中新建全局变量。



  3. 在多模块系统中,设置单独的模块新建全局变量供其它模块调用。


如果在package开发中使用,建议增加函数:


func GetLogger() *Logger {
return ...
}


返回 Logger 的变量指针,方便使用package的程序对 Logger 进行设置。


Filter


Filter 的结构如下:


type Filter struct {
Level Level
Appender

rec chan *LogRecord // write queue
closing bool // true if filter was closed at API level
}

nxlog4go 提供了标准的 go routine 框架,最大程度的方便程序员开发新的 Appender。


Appender


Appender 的结构如下:


type Appender interface {
// Set option about the Appender. The options should be set as default.
// Must be set before the first log message is written if changed.
// You should test more if have to change options while running.
SetOption(name string, v interface{}) error

// This will be called to log a LogRecord message.
Write(rec *LogRecord)

// This should clean up anything lingering about the Appender, as it is called before
// the Appender is removed. Write should not be called after Close.
Close()
}

Appender 是一个接口定义。有以下特点:




  1. 可扩展性。Filter 自动调用 Write,程序员可以编写自己的 Write,例如将日子存入map file、存入数据库等等。




  2. nxlog4go 提供了一些基础的Appender,例如:



    • color 目录下的彩色屏幕日志输出

    • file 目录下可用于生产环境的定时滚动日志文件输出

    • socket 目录下支持TCP/UDP Client的网络日志输出


    这些 Appender 可以作为开发新输出接口的参考。




Layout


Layout 的结构如下:


type Layout interface {
// Set option about the Layout. The options should be set as default.
// Must be set before the first log message is written if changed.
// You should test more if have to change options while running.
Set(name string, v interface{}) Layout

Get(name string) string

// This will be called to log a LogRecord message.
Format(rec *LogRecord) []byte
}

在早期的 log4go 中只提供了一个函数接口,基于字符串处理。在nxlog4go中使用[]byte,避免反复转换造成的效率降低。


对效率提高影响最大的则是借用了 go log 的 itoa 函数。


// Cheap integer to fixed-width decimal ASCII. Give a negative width to avoid zero-padding.
func itoa(buf *[]byte, i int, wid int) {
// Assemble decimal in reverse order.
var b [20]byte
bp := len(b) - 1
for i >= 10 || wid > 1 {
wid--
q := i / 10
b[bp] = byte('0' + i - q*10)
bp--
i = q
}
// i < 10
b[bp] = byte('0' + i)
*buf = append(*buf, b[bp:]...)
}

加上 log4net 的 timeCacheType,为 nxlog4go 提供了高效率低cpu消耗的 PatternLayout。


同时还提供了扩展 Layout 可能性。例如参照https://github.com/nblib/log4go/做的jsonLayout,据称比json编码的效率高一倍。


配置


log4net,作为一个.net程序用的是xml配置文件驱动的。go lang里边如果这样做,如log4go那样,Appender的扩展性将受到限制。


go lang 中的日志系统如此之多,似乎没有程序员满意其他人做的日志。扩展性比配置驱动更加重要。


nxlog4go 提供了使用 xml、json 配置文件的示例程序。详见 example 目录。




将来也许还会写 nxlog4go 的使用。敬请关注……


目前 nxlog4go 还正在开发中,有些细节可能还会调整。欢迎大家 Fork and Star,提供Issues and Pull Request。


https://github.com/ccpaging/nxlog4go

golang 依赖管理

hatlonely 发表了文章 • 5 个评论 • 324 次浏览 • 2018-01-27 18:17 • 来自相关话题

依赖管理是一个语言非常重要的特性,很大程度上决定着一个语言的流行程度,流行的语言大多都有非常成熟的依赖管理工具,java 的 maven 和 gradle,javascript 的 npm,python 的 pip,这些工具极大地降低了我们使用第三方库的... 查看全部

依赖管理是一个语言非常重要的特性,很大程度上决定着一个语言的流行程度,流行的语言大多都有非常成熟的依赖管理工具,java 的 maven 和 gradle,javascript 的 npm,python 的 pip,这些工具极大地降低了我们使用第三方库的成本,提高了生产效率,而 c++ 比较奇葩,并没有这样统一的依赖管理工具,大公司好一点,有专门的团队去做这样的工具解决依赖的问题,小公司就只能自己把源码拉下来,放到固定的目录,然后编译成二进制,运气不好的话,还要自己解决各种兼容性的问题,如果有版本更新,这个过程还得重复一遍,第三方库的使用和维护成本之高,让人简直就想放弃……


Golang 是自带依赖管理工具的,直接 go get <packages> 就可以把依赖拉下来,但是这种方式有个缺陷,没有版本控制,你每次拉下来的 package 都是 master 分支上的版本,这样是很危险的,源代码更新可能会有一些对外接口上面的调整,这些调整很有可能就导致你的程序编译通不过,而更致命的是,新的代码引入了一些新的 bug 或者接口语义上的变化会导致你的程序崩溃,所以早期的 gopher 开发了另一个依赖管理工具 godep解决了版本管理的问题,最近,golang 官方也在开发一个新的依赖管理工具 dep,但今天我给大家推荐的是 glide 这款工具,和其他工具相比呢,这款工具支持更多的特性,包括支持依赖的自动分析,指定版本范围,依赖清理等等,而且使用起来也比较简单。这里有一些工具的对比:https://github.com/Masterminds/glide/wiki/Go-Package-Manager-Comparison


下面我给大家简单介绍一下 glide 在实际项目中的使用


glide使用


安装


Linux


curl https://glide.sh/get | sh

Mac


brew install glide

初始化


glide init

这个命令会自动分析你代码里面的依赖,然后创建一个 glide.yaml 来描述你当前项目的依赖,生成的这个文件是可以手动编辑的,可以手动修改一些版本之类的信息


提醒一下,这个操作必须在 $GOPATH/src/ 的子目录下面,这个和 golang 本身的包管理机制有关,如果没有设置 $GOPATH,记得设置一下 export GOPATH=<directory>


依赖下载


glide update

这个命令会下载 glide.yaml 里面的依赖库,并且同样会分析并下载依赖库依赖的其他第三方库,下载的依赖会放到与 glide.yaml 同级的 vendor 目录,同时还会生成一个 glide.lock 文件,这个文件里面描述了当前依赖的版本信息,不要手工编辑这个文件


如果你在中国,这个步骤里面可能会碰到有些 gopkg 的库拉不下来,也不知道为啥要把这个也禁了……如果你碰到这个问题,你可以手动把这些库下载到 ${GOROOT}/src/golang.org/x 下面


git clone https://github.com/golang/crypto.git
git clone https://github.com/golang/sys.git
git clone https://github.com/golang/sync.git
git clone https://github.com/golang/text.git
git clone https://github.com/golang/net.git

添加依赖


glide get --all-dependencies github.com/foo/bar

也可以指定版本


glide get --all-dependencies github.com/foo/bar#^1.2.3

除了 github 上的依赖,也可以是其他的平台,比如 gitee,或者自己公司搭建的 gitlab,只要有权限就可以,还有一点需要注意,版本必须是三位数字的版本号,否则可能识别不了


安装依赖


glide install

这个命令是在一个已经使用 glide 管理依赖的项目里,需要在新环境下重新安装依赖使用的,这个命令会按照 glide.lock 的信息,把所有的依赖拉取到本地,和 glide update 不同的是,glide update 会来去最新的版本,并且会修改 glide.lock,而 glide install 只下载之前的依赖


参考链接


glide github: https://github.com/Masterminds/glide
glide 官网: https://glide.sh/
go依赖包管理工具对比: https://ieevee.com/tech/2017/07/10/go-import.html



转载请注明出处
本文链接:http://hatlonely.github.io/2018/01/27/golang依赖管理/


从零开始学golang之 Prim

freedbg 发表了文章 • 0 个评论 • 212 次浏览 • 2018-01-27 00:05 • 来自相关话题

package main

import (
    "container/list"
    "fmt"
)

const MAX_SIZ... 			查看全部
					
package main

import (
"container/list"
"fmt"
)

const MAX_SIZE int = 5

//为了看上去 好一些
const MAX_VALUE int = 9

func main() {
fmt.Println("Prim")
var gg Graph
var vexs = []string{"B", "A", "C", "D", "E"}
gg.vexnum = 5
gg.vexs = vexs

for i := 0; i < len(vexs); i++ {
for j := 0; j < len(vexs); j++ {
gg.matrix[i][j] = MAX_VALUE
}
}
initGG(&gg)
fmt.Println(gg.vexs)
fBFS(&gg)
fDFS(&gg)

//listgg := list.New()
prim(&gg, 0)
PrintG(gg, len(vexs))
}

func PrintG(gg Graph, l int) {
for i := 0; i < l; i++ {
fmt.Println(gg.matrix[i])
}
}

type Graph struct {
vexs []string //定点集合
vexnum int //定点数量
edgnum int //边数量
matrix [MAX_SIZE][MAX_SIZE]int //邻接矩阵
}

func initGG(gg *Graph) {
gg.matrix[0][1] = 5
gg.matrix[0][2] = 3

gg.matrix[1][0] = 5
gg.matrix[1][3] = 7
gg.matrix[1][4] = 4

gg.matrix[2][0] = 3
gg.matrix[2][3] = 6

gg.matrix[3][1] = 7
gg.matrix[3][2] = 6
gg.matrix[3][4] = 1

gg.matrix[4][1] = 4
gg.matrix[4][3] = 1

gg.edgnum = 12 / 2
}

//深度遍历
func DFS(gg *Graph, visit *[]bool, i int) {

fmt.Println(gg.vexs[i])
for j := 0; j < gg.vexnum; j++ {
if gg.matrix[i][j] != MAX_VALUE && !(*visit)[j] {
(*visit)[j] = true
DFS(gg, visit, j)
}
}
}

func fDFS(gg *Graph) {
visit := make([]bool, 10, 10)
fmt.Println(visit)
visit[0] = true
DFS(gg, &visit, 0)
}

//广度遍历
func fBFS(gg *Graph) {
listq := list.New()
visit := make([]bool, 10, 10)

//first push
visit[0] = true
listq.PushBack(0)

for listq.Len() > 0 {
index := listq.Front()
fmt.Println(gg.vexs[index.Value.(int)])
for i := 0; i < gg.vexnum; i++ {
if !visit[i] && gg.matrix[index.Value.(int)][i] != MAX_VALUE {
visit[i] = true
listq.PushBack(i)
}
}
listq.Remove(index)
}
}

func prim(gg *Graph, start int) {
index := 0
sum := 0
prims := make([]string, 10, 10)
var weights [5][2]int //[[0 0] [0 5] [0 3] [0 9] [0 9]]

prims[index] = gg.vexs[start]
index++

//next vex
for i := 0; i < gg.vexnum; i++ {
weights[i][0] = start //k
weights[i][1] = gg.matrix[start][i] //v
}

//delete vex
weights[start][1] = 0

for i := 0; i < gg.vexnum; i++ {
//fmt.Println(weights)
if start == i {
continue
}

min := MAX_VALUE
next := 0
for j := 0; j < gg.vexnum; j++ {
if weights[j][1] != 0 && weights[j][1] < min {
min = weights[j][1]
next = j
}
}

fmt.Println(gg.vexs[weights[next][0]], gg.vexs[next], "权重", weights[next][1])
sum += weights[next][1]
prims[index] = gg.vexs[next]
index++

//delete vex
weights[next][1] = 0

//update
for j := 0; j < gg.vexnum; j++ {
if weights[j][1] != 0 && gg.matrix[next][j] < weights[j][1] {
weights[j][1] = gg.matrix[next][j]
weights[j][0] = next
}
}
}

fmt.Println("sum:", sum)
fmt.Println(prims)
}

func get_position(gg *Graph, ch string) int {
for i := 0; i < gg.vexnum; i++ {
if gg.vexs[i] == ch {
return i
}
}
return -1
}

所有代码地址


https://github.com/godla/golang-sort-data-structures-study.git


每天撸一点gopher

从零开始学golang之图-邻接矩阵

buscoop 回复了问题 • 2 人关注 • 1 个回复 • 267 次浏览 • 2018-01-26 23:50 • 来自相关话题

golang slice性能分析

hatlonely 发表了文章 • 0 个评论 • 238 次浏览 • 2018-01-26 22:20 • 来自相关话题

golang在gc这块的做得比较弱,频繁地申请和释放内存会消耗很多的资源。另外slice使用数组实现,有一个容量和长度的问题,当slice的容量用完再继续添加元素时需要扩容,而这个扩容会把申请新的空间,把老的内容复制到新的空间,这是一个非常耗时的操作。有... 查看全部

golang在gc这块的做得比较弱,频繁地申请和释放内存会消耗很多的资源。另外slice使用数组实现,有一个容量和长度的问题,当slice的容量用完再继续添加元素时需要扩容,而这个扩容会把申请新的空间,把老的内容复制到新的空间,这是一个非常耗时的操作。有两种方式可以减少这个问题带来的性能开销:



  1. 在slice初始化的时候设置capacity(但更多的时候我们可能并不知道capacity的大小)

  2. 复用slice


下面就针对这两个优化设计了如下的benchmark,代码在: https://github.com/hatlonely/hellogolang/blob/master/internal/buildin/slice_test.go


BenchmarkAppendWithoutCapacity-8                     100      21442390 ns/op
BenchmarkAppendWithCapLessLen10th-8 100 18579700 ns/op
BenchmarkAppendWithCapLessLen3th-8 100 13867060 ns/op
BenchmarkAppendWithCapEqualLen-8 200 6287940 ns/op
BenchmarkAppendWithCapGreaterLen10th-8 100 18692880 ns/op
BenchmarkAppendWithoutCapacityReuse-8 300 5014320 ns/op
BenchmarkAppendWithCapEqualLenReuse-8 300 4821420 ns/op
BenchmarkAppendWithCapGreaterLen10thReuse-8 300 4903230 ns/op

主要结论:



  1. 在已知 capacity 的情况下,直接设置 capacity 减少内存的重新分配,有效提高性能

  2. capacity < length,capacity越接近length,性能越好

  3. capacity > lenght,如果太大,反而会造成性能下降,这里当capacity > 10 * length时,与不设置capacity的性能差不太多

  4. 多次使用复用同一块内存能有效提高性能

golang 几种字符串的连接方式

hatlonely 发表了文章 • 0 个评论 • 215 次浏览 • 2018-01-26 22:19 • 来自相关话题


title: golang 几种字符串的连接方式 date: 2018-01-24 13:45:55 tags: [golang, string] thumbnail: /img/blog/genome.jpg

最近在做性... 查看全部



title: golang 几种字符串的连接方式
date: 2018-01-24 13:45:55
tags: [golang, string]
thumbnail: /img/blog/genome.jpg


最近在做性能优化,有个函数里面的耗时特别长,看里面的操作大多是一些字符串拼接的操作,而字符串拼接在 golang 里面其实有很多种实现。


实现方法


1. 直接使用运算符


func BenchmarkAddStringWithOperator(b *testing.B) {
hello := "hello"
world := "world"
for i := 0; i < b.N; i++ {
_ = hello + "," + world
}
}

golang 里面的字符串都是不可变的,每次运算都会产生一个新的字符串,所以会产生很多临时的无用的字符串,不仅没有用,还会给 gc 带来额外的负担,所以性能比较差


2. fmt.Sprintf()


func BenchmarkAddStringWithSprintf(b *testing.B) {
hello := "hello"
world := "world"
for i := 0; i < b.N; i++ {
_ = fmt.Sprintf("%s,%s", hello, world)
}
}

内部使用 []byte 实现,不像直接运算符这种会产生很多临时的字符串,但是内部的逻辑比较复杂,有很多额外的判断,还用到了 interface,所以性能也不是很好


3. strings.Join()


func BenchmarkAddStringWithJoin(b *testing.B) {
hello := "hello"
world := "world"
for i := 0; i < b.N; i++ {
_ = strings.Join([]string{hello, world}, ",")
}
}

join会先根据字符串数组的内容,计算出一个拼接之后的长度,然后申请对应大小的内存,一个一个字符串填入,在已有一个数组的情况下,这种效率会很高,但是本来没有,去构造这个数据的代价也不小


4. buffer.WriteString()


func BenchmarkAddStringWithBuffer(b *testing.B) {
hello := "hello"
world := "world"
for i := 0; i < 1000; i++ {
var buffer bytes.Buffer
buffer.WriteString(hello)
buffer.WriteString(",")
buffer.WriteString(world)
_ = buffer.String()
}
}

这个比较理想,可以当成可变字符使用,对内存的增长也有优化,如果能预估字符串的长度,还可以用 buffer.Grow() 接口来设置 capacity


测试结果


BenchmarkAddStringWithOperator-8            50000000             30.3 ns/op
BenchmarkAddStringWithSprintf-8 5000000 261 ns/op
BenchmarkAddStringWithJoin-8 30000000 58.7 ns/op
BenchmarkAddStringWithBuffer-8 2000000000 0.00 ns/op

这个是在我的自己 Mac 上面跑的结果,go 版本 go version go1.8 darwin/amd64,这个结果仅供参考,还是要以实际生产环境的值为准,代码在:https://github.com/hatlonely/hellogolang/blob/master/internal/buildin/string_test.go


主要结论



  1. 在已有字符串数组的场合,使用 strings.Join() 能有比较好的性能

  2. 在一些性能要求较高的场合,尽量使用 buffer.WriteString() 以获得更好的性能

  3. 性能要求不太高的场合,直接使用运算符,代码更简短清晰,能获得比较好的可读性

  4. 如果需要拼接的不仅仅是字符串,还有数字之类的其他需求的话,可以考虑 fmt.Sprintf


参考链接


go语言字符串拼接性能分析: http://herman.asia/efficient-string-concatenation-in-go

golang开发目录结构

hatlonely 发表了文章 • 0 个评论 • 363 次浏览 • 2018-01-25 19:04 • 来自相关话题

在实际的项目中发现大家的目录结构都比较凌乱,基本每个人都有每个人的风格,一个项目在不断地变大,一些新的文件或目录又不断地被添加进来,从这里面去找到自己需要的信息的成本越来越高,一个统一的通用的目录结构非常有必要。

以下内容来自于github... 查看全部

在实际的项目中发现大家的目录结构都比较凌乱,基本每个人都有每个人的风格,一个项目在不断地变大,一些新的文件或目录又不断地被添加进来,从这里面去找到自己需要的信息的成本越来越高,一个统一的通用的目录结构非常有必要。


以下内容来自于github上的这个项目(https://github.com/golang-standards/project-layout


/cmd


main函数文件(比如 /cmd/myapp.go)目录,这个目录下面,每个文件在编译之后都会生成一个可执行的文件。


不要把很多的代码放到这个目录下面,这里面的代码尽可能简单。


/internal


应用程序的封装的代码,某个应用私有的代码放到 /internal/myapp/ 目录下,多个应用通用的公共的代码,放到 /internal/common 之类的目录。


/pkg


一些通用的可以被其他项目所使用的代码,放到这个目录下面


/vendor


项目依赖的其他第三方库,使用 glide 工具来管理依赖


/api


协议文件,Swagger/thrift/protobuf


/web


web服务所需要的静态文件


/configs


配置文件


/init


服务启停脚本


/scripts


其他一些脚本,编译、安装、测试、分析等等


/build


持续集成目录


云 (AMI), 容器 (Docker), 操作系统 (deb, rpm, pkg)等的包配置和脚本放到 /build/package/ 目录


/deployments


部署相关的配置文件和模板


/test


其他测试目录,功能测试,性能测试等


/docs


设计文档


/tools


常用的工具和脚本,可以引用 /internal 或者 /pkg 里面的库


/examples


应用程序或者公共库使用的一些例子


/assets


其他一些依赖的静态资源

Ubuntu下编译golang的GXUI

回复

jinheking 发起了问题 • 1 人关注 • 0 个回复 • 238 次浏览 • 2018-01-25 11:00 • 来自相关话题

在 AWS Lambda 上寫 Go 語言搭配 API Gateway

appleboy 发表了文章 • 1 个评论 • 190 次浏览 • 2018-01-24 10:56 • 来自相关话题

本篇轉錄自: 『在 AWS Lambda 上寫 Go 語言搭配 API Gateway

查看全部

本篇轉錄自: 『在 AWS Lambda 上寫 Go 語言搭配 API Gateway


Snip20180124_2


這應該不是什麼新消息了,就是 AWS Lambda 正式支援 Go 語言,也就是可以將 Go 語言編譯出來的二進制檔案直接放進去 Lambda Function 內,前面可以搭配 API Gateway,後面可以搭配 CloudWatchS3,本文章會教大家如何將 Gin 打包編譯進 Lambda,官網其實也有提供 Library 或範例方便大家實作,大家可以參考看看。



撰寫 Lambda function


如果想搭配 API Gateway 後端 Lambda 可能接 Restful 或 GraphQL API 的話,肯定要 Listen 單一 Http Port,底下是用 Gin 來實現一個簡單的 http 伺服器:


package main

import (
"log"
"net/http"
"os"

"github.com/gin-gonic/gin"
)

func helloHandler(c *gin.Context) {
name := c.Param("name")
c.String(http.StatusOK, "Hello %s", name)
}

func welcomeHandler(c *gin.Context) {
c.String(http.StatusOK, "Hello World from Go")
}

func rootHandler(c *gin.Context) {
c.JSON(http.StatusOK, gin.H{
"text": "Welcome to gin lambda server.",
})
}

func routerEngine() *gin.Engine {
// set server mode
gin.SetMode(gin.DebugMode)

r := gin.New()

// Global middleware
r.Use(gin.Logger())
r.Use(gin.Recovery())

r.GET("/welcome", welcomeHandler)
r.GET("/user/:name", helloHandler)
r.GET("/", rootHandler)

return r
}

func main() {
addr := ":" + os.Getenv("PORT")
log.Fatal(http.ListenAndServe(addr, routerEngine()))
}

可以很清楚看到在 Gin 內,只要實現 Router 部分,就可以透過 http.ListenAndServe 方式來啟動小型 Web 服務,但是上面的程式碼不能跑在 Lambda 內,這邊就要使用 Go 大神 TJ 所開發的 apex/gateway,只要將 http.ListenAndServe 換成 gateway.ListenAndServe 就可以了


func main() {
addr := ":" + os.Getenv("PORT")
log.Fatal(gateway.ListenAndServe(addr, routerEngine()))
}

有沒有簡單到不行?詳細範例可以參考此 GitHub Repo


建立 Lambda function


Snip20180124_3


這邊不詳細說明了,重點是在下拉選單請選擇 Go 1.x 版本即可,不知道官方什麼時候要升級 Node.js 版本 XD


編譯 Go 檔案並上傳


AWS Lambda 只有支援 Linux 架構,所以只需要透過底下指令就可以編譯出來:


$ GOOS=linux go build -o main .
$ zip deployment.zip main

把輸出檔案設定為 main,最後透過 zip 方式打包成 deployment.zip,並且從 AWS Web Console 頁面上傳。


Snip20180124_5


覺得每次都要手動上傳有點麻煩,歡迎大家試試看 drone-lambda,可以透過指令方式更新 Lambda function。下一篇會教大家自動化更新 Lambda


$ drone-lambda --region ap-southeast-1 \
--access-key xxxx \
--secret-key xxxx \
--function-name upload-s3 \
--zip-file deployment.zip

API Gateway + Cloud Watch


快速參考底下測試方式


Snip20180124_6


可以看到在網址輸入 /user/appleboy 可以很快速拿到 Response,接著看看 Cloud Watch


Snip20180124_7


效能測試 Benchmark


預設 AWS Lambda 使用 128 MB 記憶體,那下面透過 vegeta 來看看 Go 的效能。之後有機會可以跟 Python 或 Node.js 比較看看。底下是 128 MB 記憶體。每秒打 1024 request 並且持續 10 秒


$ vegeta attack -rate=1024 -duration=10s -targets=target2.txt | tee results.bin | vegeta report
Requests [total, rate] 10240, 1024.10
Duration [total, attack, wait] 20.335101947s, 9.999018014s, 10.336083933s
Latencies [mean, 50, 95, 99, max] 6.091282008s, 4.893951645s, 14.508009942s, 17.11847442s, 20.128384389s
Bytes In [total, mean] 143360, 14.00
Bytes Out [total, mean] 0, 0.00
Success [ratio] 100.00%
Status Codes [code:count] 200:10240

換 512 MB 每秒打 1024 request 並且持續 10 秒


Requests      [total, rate]            10240, 1024.10
Duration [total, attack, wait] 11.989730554s, 9.999012371s, 1.990718183s
Latencies [mean, 50, 95, 99, max] 1.491340336s, 1.114643849s, 4.112241113s, 6.087949237s, 10.107294516s
Bytes In [total, mean] 143360, 14.00
Bytes Out [total, mean] 0, 0.00
Success [ratio] 100.00%
Status Codes [code:count] 200:10240

可以看到 128MB Latencies 是 6.091282008s 而 512MB 可以降到 1.491340336s


所有資料請直接參考 gin-lambda

Grep on the fly in SpaceVim

SpaceVim 发表了文章 • 0 个评论 • 170 次浏览 • 2018-01-24 09:49 • 来自相关话题

Asynchronous grep on the fly

https://spacevim.org/grep-on-... 查看全部

Asynchronous grep on the fly


https://spacevim.org/grep-on-the-fly-in-spacevim/


FlyGrep means grep on the fly, it will update the result as you type. Of course, it is running
asynchronously. Before using this feature, you need to install a searching tool. FlyGrep works
through search tools: ag, rg, ack, pt and grep, Choose one you like.


This ia a built-in plugin in SpaceVim, and we also separated a plugin : FlyGrep.vim


Features



  • Search in a project


In SpaceVim, you can use SPC s p or SPC s / to search in the current project.


searching project



  • Search in current file


You can use SPC s s to search in the current file. To search word under the cursor, you can press SPC s S.


searching current file



  • Search in all loaded buffers


To searching in all loaded buffers, you need to press SPC s b, and you can also use SPC s B to search word under the point.


searching-loaded-buffer



  • Search in an arbitrary directory


If you want to searching in a different directory instead of current directory, you can
use SPC s f. Then insert the path of the arbitrary directory.



  • Search in a project in the background


If you need background searching, you can press SPC s j, after searching is done, the index will be displayed on statusline. you can use SPC s l to list all the search results.


Key bindings


The search commands in SpaceVim are organized under the SPC s prefix with the next key is the tool to use and the last key is the scope. For instance SPC s a b will search in all opened buffers using ag.


If the last key (determining the scope) is uppercase then the current word under the cursor is used as default input for the search. For instance SPC s a B will search with word under cursor.


If the tool key is omitted then a default tool will be automatically selected for the search. This tool corresponds to the first tool found on the system of the list g:spacevim_search_tools, the default calling sequence is rg, ag, pt, ack then grep. For instance SPC s b will search in the opened buffers using pt if rg and ag have not been found on the system.


The tool keys are:































Tool Key
ag a
grep g
ack k
rg r
pt t

The available scopes and corresponding keys are:























Scope Key
opened buffers b
files in a given directory f
current project p

Within FlyGrep buffer:



























































Key Binding Description
<Esc> close FlyGrep buffer
<Enter> open file at the cursor line
<Tab> move cursor line down
<C-j> move cursor line down
<S-Tab> move cursor line up
<C-k> move cursor line up
<Bs> remove last character
<C-w> remove the word before the cursor
<C-u> remove the line before the cursor
<C-k> remove the line after the cursor
<C-a>/<Home> Go to the beginning of the line
<C-e>/<End> Go to the end of the line

url编码问题

zsy619 回复了问题 • 2 人关注 • 2 个回复 • 252 次浏览 • 2018-01-22 21:44 • 来自相关话题

url编码问题

回复

flewliu 发起了问题 • 1 人关注 • 0 个回复 • 197 次浏览 • 2018-01-22 15:49 • 来自相关话题