版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 问题描述 蛇形遍历矩阵 按下图的方法蛇形遍历矩阵 矩阵为m行n列 解题思路 观察可以发现 结论1. 在矩阵中移动的动作 只有以下4种 4种动作，对应的向量分别为 1）(0，1) 2) (1, -1) 3) (1, 0) 4) (-1, 1) 结论2 对于动作1和动作3 最多连续走一步 对于动作2和动作4，保持动作到矩阵边界 结论3 如果要变换方向则按照上次动作的Next动作开始尝试 沿着动作1、动作2、动作3、动作4的顺序进行尝试 完整程序 # -*- coding: utf-8 -*- actions = [(0,1), (1, -1), (1,0), (-1, 1)] def snake(matrix, m, n): # start # (0, 0) # end # (m - 1, n - 1) pos = (0, 0) num = 1 matrix[pos[0]][pos[1]] = num last_action_idx = None while pos != (m-1, n-1): num += 1 print "***************" print "current pos=", pos print "prepare to num", num, last_action_idx print "last action", last_action_idx print # 尝试走出一步 if last_action_idx is None: last_action_idx = 0 # 尝试继续按原动作前进且下一个位置也是合法的 # 继续走 elif last_action_idx in set([1, 3]) and valid(matrix, pos, actions[last_action_idx], m, n): pass else: # 必须要换方向 for i in xrange(4): last_action_idx = (last_action_idx + 1) % 4 if valid(matrix, pos, actions[last_action_idx], m, n): break print "execute action", last_action_idx action = actions[last_action_idx] pos = (pos[0] + action[0], pos[1] + action[1]) print 'track', pos, num matrix[pos[0]][pos[1]] = num def valid(matrix, pos, action, m, n): pos = (pos[0] + action[0], pos[1] + action[1]) # 不能超过边界，且从来没有走过 if pos[0] >= 0 and pos[0] < m and pos[1] >= 0 and\ pos[1] < n and matrix[pos[0]][pos[1]] == 0: return True return False def print_matrix(matrix): for line in matrix: for item in line: print item, print print '-' * 10 if __name__ == '__main__': matrix = [] matrix.append([0,0,0]) matrix.append([0,0,0]) matrix.append([0,0,0]) matrix.append([0,0,0]) snake(matrix, 4, 3) print "result", '=' * 10 print_matrix(matrix) 总结 这类问题的核心是寻找规律，规律找到了，问题也就迎刃而解了。与之类似的还有螺旋遍历2维数组。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 问题描述 在一个有序整型数组中，从其中任意挑2个数(不重复)相加等于目标值target 求所有这样的组合 比如有以下数组 case1: target=6 [1, 2, 3, 4, 5, 7, 9] 返回结果为 [(1,5), (2,4)] case2: target=6 [1, 7, 9] 返回结果为 [] case3: target=9 [1, 2, 3, 4, 5, 7, 9] 返回结果为 [(2,7)] 解题思路 对这个问题，我们可以这样思考，以case1 为例 如果对于1, 可以从右向左找，可以找到5，与1相加可以等于目标值6 这时候再看2有没有合适的值能够与之相加等于目标值的时候，我们只需要找 [3, 4]就可以了，这是因为左边的数增大了，右边已经查找过的数，显然已经太大 方案 1）设2个指针分别指向数组的最左和最右 2) 移动右边的指针直到无法找到合适的值或者已经找到合适的值 3）移动左边的指针 4）持续步骤2和3，直到左右2个指针重合 时间复杂度为O(n) 完整代码: def find(array, target): i = 0 j = len(array) - 1 res = [] while i < j: while i < j and array[j] > (target - array[i]): j -= 1 if (array[i] + array[j]) == target and i != j: res.append((i, j)) i += 1 return res def main(): a = [1,2,3,4,5,7] print find(a, 6) a = [1,7,9] print find(a, 6) a = [1, 2, 3, 5, 7, 9] print find(a, 9) if __name__ == "__main__": main() 请我喝瓶饮料

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 前言 Golang很多语法特征都和C++非常相似, stuct对象的赋值操作，会导致struct被copy（浅拷贝） test_copy.go package main import "fmt" type Car struct{ Name string Age int XList []int } func main(){ a := Car{Name:"buick", Age: 10, XList:make([]int, 10)} b := a b.Age = 9 fmt.Printf("address a:%p\n", &a) fmt.Printf("address b:%p\n", &b) fmt.Println("----------------------") fmt.Printf("Car a:%v\n", a) fmt.Printf("Car a:%v\n", len(a.XList)) fmt.Printf("Car b:%v\n", b) fmt.Printf("Car b:%v\n", len(b.XList)) } 输出 address a:0xc420068180 address b:0xc4200681b0 ---------------------- Car a:{buick 10 [0 0 0 0 0 0 0 0 0 0]} Car a:10 Car b:{buick 9 [0 0 0 0 0 0 0 0 0 0]} Car b:10 可以看出a和b已经是完全不同的对象，对b的修改不会影响a ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 imroc/req 作为目前最好用的request库深受Gopher的喜爱，但是它的连接池，在使用时仍然有些要注意的事项。 2. 简述 imroc/req内部仍然使用的是标准库net/http来管理连接 所以我们首先要理解net/http 是如何管理连接池的 transport.go type Transport struct { idleMu sync.Mutex wantIdle bool // user has requested to close all idle conns idleConn map[connectMethodKey][]*persistConn // most recently used at end idleConnCh map[connectMethodKey]chan *persistConn // MaxIdleConns controls the maximum number of idle (keep-alive) // connections across all hosts. Zero means no limit. MaxIdleConns int // MaxIdleConnsPerHost, if non-zero, controls the maximum idle // (keep-alive) connections to keep per-host. If zero, // DefaultMaxIdleConnsPerHost is used. MaxIdleConnsPerHost int 这里的 connectMethodKey可以用来标识一个目标 显然它是proxy，scheme, addr 构成的三元组 MaxIdleConnsPerHost限制的是相同connectMethodKey的空闲连接数量 DefaultMaxIdleConnsPerHost的默认值是2，这对一个大并发的场景是完全不够用的。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 前言 公司的测试的网络硬盘太小，我一直想要一个NAS盘，用云主机来做NAS确实太贵，平常又用不了，能不能用对象存储来做网盘呢，用多少，付多少钱，还可以无限扩容。 最近青云推出了QingStor™对象存储本地盘 QingStor™ 对象存储本地盘可将 QingStor™ 对象存储的存储空间挂载为 Windows /Linux 等平台下的磁盘或文件目录，由 QingStor™ 对象存储为其提供无限容量的在线文件存储空间，而不占用本地磁盘空间。用户可以像操作本地磁盘一样方便、快捷地访问或存取 QingStor™ 对象存储存储空间（Bucket）中的各常用类型文件（如文档、图片、音视频、二进制归档、压缩文件等）。 下面的qsfs就是青云的对象存储，通过qsfs-fuse，青云的对象存储可以像网盘一样挂载主机上，无论是云主机还是本地主机 root@ecs-hb-xxx:/qincloud$ df -Th Filesystem Type Size Used Avail Use% Mounted on /dev/vda1 ext4 40G 29G 8.8G 77% / tmpfs tmpfs 1.9G 0 1.9G 0% /dev/shm qsfs fuse.qsfs 16E 9.8M 16E 1% /qincloud 上面是在我的阿里云主机上使用qsfs-fuse的例子 如果你的对象存储不在pek3a，你需要指定zone，否则会提示 root@ecs-hb-hb1-xxxx:~$ qsfs bucket01 /qincloud/ -c=/root/.qincloud -d FUSE library version: 2.8.3 nullpath_ok: 0 unique: 1, opcode: INIT (26), nodeid: 0, insize: 56 INIT: 7.14 flags=0x0000f07b max_readahead=0x00020000 E0410 17:25:45.466140 1405 Drive.cpp:212] [ERROR] NotFound, QingStorHeadBucket:NotFound(404) E0410 17:25:45.466606 1405 Operations.cpp:1511] [ERROR] Unable to connect bucket ut-bucket01 INIT: 7.12 flags=0x00000011 max_readahead=0x00020000 max_write=0x00020000 unique: 1, success, outsize: 40 Segmentation fault 启动命令 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 前言 Golang常常被用在对性能有较高需求的场景。为了避免高频的创建对象和GC我们，需要使用对象池，可以使用它默认提供的sync.pool。 但是每次gc时，sync.pool中的cache的对象都会被释放，如果我们对性能的要求更高，且需求更加明确，我们可以使用自定义的对象池 实现 下面对象池的简易实现，大家可以参考 package main import ( "fmt" ) type Car struct { name string age int } type CarPool struct { Cached chan *Car Size int } func NewCarPool(size int) *CarPool { x := CarPool{} x.Cached = make(chan *Car, size) x.Size = size return &x } func (c *CarPool) Get() *Car { var res *Car select { case res = <-c.Cached: fmt.Println("---get--") default: fmt.Println("---create one--") res = &Car{} } return res } func (p *CarPool) Put(c *Car) { select { case p.Cached <- c: fmt.Println("---put--") default: c = nil fmt.Println("---destroy--") } } func main() { carPool := NewCarPool(3) for i := 0; i < 5; i++ { x := carPool.Get() carPool.Put(x) } } 参考资料： 1.广发证券Go在证券行情系统中的应用 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 众所周知, Golang标准库"encoding/json"的性能并不好，现在比较热的替代库是"json-iterator/go" 传送门: json-iterator/go 我们的日志打成json格式，然后做集中收集，为了提高性能用json-iterator替换encoding/json。打火焰图，却发现（JSON序列化日志）耗时占总时间的比重没有下降 2. 重新测试 难道json-iterator出的性能压测数据都是吹牛逼，只要自己又重新测试了一下，以下是测试代码 json_test.go package tjson import ( "testing" "encoding/json" jsoniter "github.com/json-iterator/go" ) type Car struct { Name string Name1 string Name2 string Name3 string } func BenchmarkStructJsoniter(b *testing.B) { c := Car{Name1:"xxxxxxxxxxxxx", Name2:"xxxxxxxxxxxxxxxxxxxx", Name3:"xxxxxxxxxxxxxxxxxx", Name: "buickxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"} for i := 0; i < b.N; i++ { //use b.N for looping jsoniter.Marshal(&c) } } func BenchmarkStructStd(b *testing.B) { c := Car{Name1:"xxxxxxxxxxxxx", Name2:"xxxxxxxxxxxxxxxxxxxx", Name3:"xxxxxxxxxxxxxxxxxx", Name: "buickxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"} for i := 0; i < b.N; i++ { //use b.N for looping json.Marshal(&c) } } func BenchmarkMapJsoniter(b *testing.B) { mymap := make(map[string]string, 10000) mymap["Name1"] = "xxxxxxxxxxxxx" mymap["Name2"] = "xxxxxxxxxxxxxxxxxxxx" mymap["Name3"] = "xxxxxxxxxxxxxxxxxx" mymap["Name"] = "buickxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" for i := 0; i < b.N; i++ { //use b.N for looping jsoniter.Marshal(&mymap) } } func BenchmarkMapStd(b *testing.B) { mymap := make(map[string]string, 10000) mymap["Name1"] = "xxxxxxxxxxxxx" mymap["Name2"] = "xxxxxxxxxxxxxxxxxxxx" mymap["Name3"] = "xxxxxxxxxxxxxxxxxx" mymap["Name"] = "buickxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" for i := 0; i < b.N; i++ { //use b.N for looping json.Marshal(&mymap) } } BenchMark脚本 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 前言 Channel是Golang中非常重要的数据结构, 默认它是阻塞的。那么如何实现一个非阻塞队列呢，你可以参考我的实现。 实现1 package main import ( "errors" "fmt" ) func push(q chan int, item int) error { select { case q <- item: return nil default: return errors.New("queue full") } } func get(q chan int) (int, error) { var item int select { case item = <-q: return item, nil default: return 0, errors.New("queue empty") } } func main() { q := make(chan int, 5) x := []int{1, 2, 3, 4, 5, 6} for _, value := range x { err := push(q, value) fmt.Printf("error:%v\n", err) } for _, value := range x { fmt.Println(value) v, err := get(q) fmt.Printf("v:%v, error:%v\n", v, err) } } 实现2 我们还可以把channel变成一个带超时的阻塞队列 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 工作中有一个场景是，我们要从可以用的N台机器中，随机选出M台机器， 当时因为时间有限，我实现不是优雅，且性能上，估计也会差点。今天晚上有空重新对这个问题进行了思考 2. 分析 提到这个问题，我们很容易联想到排列组合中，从袋子中摸球的问题。 袋子中有N个球，编号分别是0 ~ N -1, 每次从袋子中取出一个球（不放回），共取出M次。 在实际工作中，可能会很多类似的场景 从N个汽车型号中随机选出M个 从N个候选人中选出M个 在随机选择的过程中，我们不一定要直接操作这些实体（汽车，候选人），只用对它们所对应的编号进行操作即可 3. 结果 基于2. 中的分析，我实现了代码，并封装成了库，有兴趣的朋友可以看看 传送门：randomchoice Quick Start package main import ( rc "github.com/vearne/randomchoice" "fmt" ) type Car struct{ color string name string } func (c *Car) String() string{ return c.color + "-" + c.name } func main(){ // example 1 var children []string children = []string{"lily", "rose","lisa"} // randomly select 2 kids from children idxSlice := rc.RandomChoice(len(children), 2) result := make([]string, 0, 2) for _, v := range idxSlice{ result = append(result, children[v]) } // result: selected kids fmt.Println(result) // example 2 var carSlice []*Car= make([]*Car, 0, 3) bmw := Car{color:"black", name:"bmw"} carSlice = append(carSlice, &bmw) buick := Car{color:"silvery", name:"buick"} carSlice = append(carSlice, &buick ) skoda := Car{color:"white", name:"skoda"} carSlice = append(carSlice, &skoda ) // random select 2 kinds from carSlice idxSlice = rc.RandomChoice(len(carSlice), 2) cars := make([]*Car, 0, 2) for _, v := range idxSlice{ cars = append(cars, carSlice[v]) } fmt.Println(cars) } 性能指标 测试环境 CPU Model Name: 2.3 GHz Intel Core i5 CPU Processors: 4 Memory: 8GB ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 引言 我们的打算对某个golang的服务，统计一下它每秒的QPS, go-metrics成为我们不二的选择。 在我的文章METRICS的简易实现 我简单的给出了对这个问题的一种简易实现。 1. 简易实现的优缺点 优点 实现方式相对直观 缺点 为了一个指标，所带来的开销很大 每个指标需要1个专门的协程，每秒钟做一次"快照" 1分的的QPS需要60个点, 如果还需要5分钟, 15分钟的QPS 那么共需记录 60 * (1 + 5 + 15) = 1260 个点 2. go-metrics的实现 传送门 meter.go 2.1 理论 go-metrics中对于Meter的实现基于EWMA(Exponentially Weighted Moving-Average) 中文译为指数加权移动平均法 它是一种特殊的加权移动平均法。其特点是: 第一，指数平滑法进一步加强了观察期近期观察值对预测值的作用，对不同时间的观察值所赋予的权数不等，从而加大了近期观察值的权数，使预测值能够迅速反映市场实际的变化。权数之间按等比级数减少，此级数之首项为平滑常数a,公比为(1- a)。第二，指数平滑法对于观察值所赋予的权数有伸缩性，可以取不同的a 值以改变权数的变化速率。如a取小值，则权数变化较迅速，观察值的新近变化趋势较能迅速反映于指数移动平均值中。因此，运用指数平滑法，可以选择不同的a 值来调节时间序列观察值的均匀程度(即趋势变化的平稳程度)。 EWMA 在实际应用中，主要是用于预测股价变化等等 注意 下面公式中的λ和上面文献中的a 是同一个参数，特此说明 预测的方法是，每隔一段时间进行一次采样，每次采样完成之后，就对预测值进行一次修正，这种方法的特点是近期的采样值对预测值的影响大，远期的影响较小 这种理论是有合理性的，尤其是对于了连续变化的曲线 2.2 实现 meter.go 中，重要的结构有2个 type StandardMeter struct { lock sync.RWMutex snapshot *MeterSnapshot a1, a5, a15 EWMA startTime time.Time stopped bool } // 定时调用StandardMeter的tick方法 ...