Welcome to MDGSF's Blog!

This is my github blog

[GO] GoPath管理

2017-11-20

build.sh

#!/bin/bash
WDIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )"
export GOPATH=$WDIR
go install accserver
go install dfmjserver
go install dtmjserver

Read All

进程、线程和协程

2017-11-16

miscellanea

Process Thread Coroutine

进程、线程和协程

进程拥有自己独立的堆和栈，既不共享堆，亦不共享栈，进程由操作系统调度。

线程拥有自己独立的栈和共享的堆，共享堆，不共享栈，线程亦由操作系统调度(标准线程是的)。

协程和线程一样共享堆，不共享栈，协程由程序员在协程的代码里显示调度。

协程和线程的区别是：协程避免了无意义的调度，由此可以提高性能，但也因此，程序员必须自己承担调度的责任，同时，协程也失去了标准线程使用多CPU的能力。

进程和线程都是由操作系统来调用的

协程是协作式调度的

go语言的协程Goroutines是语言层面支持的，不需要开发人员去调度，使用起来就像是线程一样。

Goroutines

https://golang.org/doc/effective_go.html#goroutines

They’re called goroutines because the existing terms—threads, coroutines, processes, and so on—convey inaccurate connotations. A goroutine has a simple model: it is a function executing concurrently with other goroutines in the same address space. It is lightweight, costing little more than the allocation of stack space. And the stacks start small, so they are cheap, and grow by allocating (and freeing) heap storage as required.

Goroutines are multiplexed onto multiple OS threads so if one should block, such as while waiting for I/O, others continue to run. Their design hides many of the complexities of thread creation and management.

并发与并行

你吃饭吃到一半，电话来了，你一直到吃完了以后才去接，这就说明你不支持并发也不支持并行。

你吃饭吃到一半，电话来了，你停了下来接了电话，接完后继续吃饭，这说明你支持并发。

你吃饭吃到一半，电话来了，你一边打电话一边吃饭，这说明你支持并行。

并发的关键是你有处理多个任务的能力，不一定要同时。

并行的关键是你有同时处理多个任务的能力。

所以我认为它们最关键的点就是：是否是『同时』。

https://talks.golang.org/2012/waza.slide

Read All

[算法学习][leetcode] 104 Maximum Depth of Binary Tree

2017-11-16

mdgsf

Art

Leetcode

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

题目

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

题目翻译

题目解析

参考答案

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    iLeftDepth := maxDepth(root.Left)
    iRightDepth := maxDepth(root.Right)

    iMax := 0
    if iLeftDepth > iRightDepth {
        iMax = iLeftDepth
    } else {
        iMax = iRightDepth
    }

    return iMax + 1
}

Read All

[GO] A simple load balancer

2017-11-16

func Run() {
   in, out := make(chan *Work), make(chan *Work)
   for i := 0; i < NumWorkers; i++ {
       go worker(in, out)
   }
   go sendLotsOfWork(in)
   receiveLotsOfResults(out)
}

Read All

[vk_mj] Go实现赖子胡牌

2017-11-14

vk_mj

参考链接：

https://github.com/yuanfengyun/qipai

核心思想：

1、名词解释：eye(将），字牌（feng、东南西北中发白），花色（万、筒、条、字牌）

2、分而治之：检查手牌是否能胡是依次检查万、筒、条、字牌四种花色是否能组成胡牌的一部分。

3、单一花色要能满足胡牌的部分，则要么是3n(不带将)，要么是3n+2（带将）。3*n中的3带表三张牌一样的刻子，或三张连续的牌如1筒2筒3筒。

4、判断是否满足胡牌的单一花色部分，需要根据是否有将，有几个赖子，查询不同的表。表内容表示表里的元素加上对应的赖子数量能组成3n 或3n+2。赖子数是表名最后的数字，带有eye的表表示满足3n+2，没有的表示满足3n。

5、查表的key值，是直接根据1-9有几张牌就填几（赖子不算），如1-9万各一张，则key为111111111。如1万3张，9万2张，则key为300000002。

6、组合多种花色，判断是否能胡牌。将赖子分配给不同的花色，有若干种分配方式，只要有一种分配能让所有花色满足单一花色胡牌部分，则手牌能胡。如：手上有3个赖子，可以分配万、筒、条各一张，也可以万、同、字牌各一张。

7、根据是否有将、是否字牌分为4种表，每种表又根据赖子个数0-8分别建表，共36张表，具体如下：

赖子个数	带将表	不带将的表	字牌带将表	字牌不带将表
0	eye_table_0	table_0	feng_eye_table_0	feng_table_0
1	eye_table_1	table_1	feng_eye_table_0	feng_table_1
2	eye_table_2	table_2	feng_eye_table_0	feng_table_2
3	eye_table_3	table_3	feng_eye_table_0	feng_table_3
4	eye_table_4	table_4	feng_eye_table_0	feng_table_4
5	eye_table_5	table_5	feng_eye_table_0	feng_table_5
6	eye_table_6	table_6	feng_eye_table_0	feng_table_6
7	eye_table_7	table_7	feng_eye_table_0	feng_table_7
8	eye_table_8	table_8	feng_eye_table_0	feng_table_8

步骤：

1、统计手牌中鬼牌个数 nGui，将鬼牌从牌数据中去除。

2、不同花色分开处理，分别校验是否能满足将、顺子、刻子。

3、分析东南西北风中发白时，不需要分析顺子的情况，简单很多。

4、分析单一花色时，直接根据1-9点对应数字得出一个9位的整数，每位上为0-4代表该点数上有几张牌。

比如：

1筒2筒3筒3筒3筒3筒6筒7筒8筒2万3万3万3万4万

筒: 1,1,4,0,0,1,1,1,0 得出的数字为114001110

万: 0,1,3,1,0,0,0,0,0 得出的数字为13100000

5、组合多种花色，判断是否能胡牌。将赖子分配给不同的花色，有若干种分配方式，只要有一种分配能让所有花色满足单一花色胡牌部分，则手牌能胡。

比如：

手上有3个赖子，可以分配万、筒、条各一张，也可以万、同、字牌各一张

每种花色与赖子组合，如果所有花色都能配型成功则可胡牌

检查配型时，每种花色的牌数量必需是3n 或者 3n + 2

根据赖子个数、带不带将，查找对应表，看能否满足3n 或 3n+2的牌型

非字牌表的产生:

穷举万字牌所有满足胡牌胡可能，将对应的牌型记录为数字，根据是否有将、放入eye_table_0或table_0中。具体是每次加入一个刻子，顺子或是将（将只能加入一对）,最多加入四组外带将牌。
将table_0中牌去掉一张，放入table_1中，表示去掉的牌用1张赖子代替。eye_table_0中牌去掉一张，放入到eye_table_1中。
将table_1中牌去掉一张，放入table_2中，表示去掉的牌用1张赖子代替。eye_table_1中牌去掉一张，放入到eye_table_2中。
将table_2中牌去掉一张，放入table_3中，表示去掉的牌用1张赖子代替。eye_table_2中牌去掉一张，放入到eye_table_3中。
将table_3中牌去掉一张，放入table_4中，表示去掉的牌用1张赖子代替。eye_table_3中牌去掉一张，放入到eye_table_4中。
将table_4中牌去掉一张，放入table_5中，表示去掉的牌用1张赖子代替。eye_table_4中牌去掉一张，放入到eye_table_5中。
将table_5中牌去掉一张，放入table_6中，表示去掉的牌用1张赖子代替。eye_table_5中牌去掉一张，放入到eye_table_6中。
将table_6中牌去掉一张，放入table_7中，表示去掉的牌用1张赖子代替。eye_table_6中牌去掉一张，放入到eye_table_7中。
将table_7中牌去掉一张，放入table_8中，表示去掉的牌用1张赖子代替。eye_table_7中牌去掉一张，放入到eye_table_8中。

字牌表的产生：

与非字牌表的产生方法相同，只是第一步中，不能加入顺子（除非麻将玩法字牌是能组成顺子的）

表的大小：总量在2M左右

表生成耗时：2-3S

package main

import (
    "bufio"
    "fmt"
    "io"
    "mjlib_go/src/mjlib"
    "os"
    "strconv"
)

const LaiZiNum = 9

//只保存最终正确的结果。
var tableXuShu [LaiZiNum]*map[int]bool
var tableXuShuWithEye = [LaiZiNum]*map[int]bool{}
var tableZi = [LaiZiNum]*map[int]bool{}
var tableZiWithEye = [LaiZiNum]*map[int]bool{}

//除了保存最终正确的结果，还要把中间计算过的错误结果也保存起来，防止重复计算。
var tableXuShuTemp [LaiZiNum]*map[int]bool
var tableXuShuWithEyeTemp = [LaiZiNum]*map[int]bool{}
var tableZiTemp = [LaiZiNum]*map[int]bool{}
var tableZiWithEyeTemp = [LaiZiNum]*map[int]bool{}

var curTable *[LaiZiNum]*map[int]bool
var curTableTemp *[LaiZiNum]*map[int]bool
var curCardsTypeNum int

func main() {

    fmt.Println("main start")

    for i := 0; i < LaiZiNum; i++ {
        tableXuShu[i] = &map[int]bool{}
        tableXuShuWithEye[i] = &map[int]bool{}
        tableZi[i] = &map[int]bool{}
        tableZiWithEye[i] = &map[int]bool{}

        tableXuShuTemp[i] = &map[int]bool{}
        tableXuShuWithEyeTemp[i] = &map[int]bool{}
        tableZiTemp[i] = &map[int]bool{}
        tableZiWithEyeTemp[i] = &map[int]bool{}
    }

    genTableXuShu()
    genTableXuShuWithEye()
    genTableZi()
    genTableZiWithEye()

    dumpTableXuShu()
    dumpTableXuShuWithEye()
    dumpTableZi()
    dumpTableZiWithEye()

    //test()
}

func test() {
    loadTableXuShu()
    loadTableXuShuWithEye()
    loadTableZi()
    loadTableZiWithEye()

    fmt.Println("start test")
    mjlib.Init()
    mjlib.MTableMgr.LoadTable()
    mjlib.MTableMgr.LoadFengTable()

    table1 := mjlib.MTableMgr.GetTable(0, false, false)
    myTable1 := tableZi[0]

    fmt.Println("myTable1 = ", len(*myTable1))
    fmt.Println("table1 = ", len(table1.Tbl))

    for key := range *myTable1 {
        _, ok := table1.Tbl[key]
        if ok {
            delete(*myTable1, key)
            delete(table1.Tbl, key)
        } else {
            //fmt.Println("myTable1 contains = ", key)
        }
    }
    fmt.Println("myTable1 = ", len(*myTable1))
    fmt.Println("table1 = ", len(table1.Tbl))

    if len(*myTable1) > 0 {
        for key := range *myTable1 {
            fmt.Println("myTabl1 = ", key)
        }
    }
    if len(table1.Tbl) > 0 {
        for key := range table1.Tbl {
            fmt.Println("table1 = ", key)
        }
    }
}

func genTableXuShu() {
    fmt.Println("genTableXuShu start")

    curTable = &tableXuShu
    curTableTemp = &tableXuShuTemp
    curCardsTypeNum = 9
    cards := []int{0, 0, 0, 0, 0, 0, 0, 0, 0}
    genXuShuPuZi(cards, 1)

    fmt.Println("genTableXuShu success")
}

func genTableXuShuWithEye() {
    fmt.Println("genTableXuShuWithEye start")

    curTable = &tableXuShuWithEye
    curTableTemp = &tableXuShuWithEyeTemp
    curCardsTypeNum = 9

    cards := []int{0, 0, 0, 0, 0, 0, 0, 0, 0}
    for i := 0; i <= 8; i++ {
        cards[i] = 2
        fmt.Println("genTableXuShuWithEye jiang = ", i)
        addToXuShu(cards)
        genXuShuPuZi(cards, 1)
        cards[i] = 0
    }

    fmt.Println("genTableXuShuWithEye success")
}

func genXuShuPuZi(cards []int, level int) {

    if level > 4 {
        return
    }

    for i := 0; i <= 8; i++ {

        if cards[i] <= 3 {
            cards[i] += 3
            addToXuShu(cards)
            genXuShuPuZi(cards, level+1)
            cards[i] -= 3
        }

        if i+1 <= 8 && i+2 <= 8 && cards[i] <= 5 && cards[i+1] <= 5 && cards[i+2] <= 5 {
            cards[i]++
            cards[i+1]++
            cards[i+2]++
            addToXuShu(cards)
            genXuShuPuZi(cards, level+1)
            cards[i]--
            cards[i+1]--
            cards[i+2]--
        }
    }
}

func addToXuShu(cards []int) {
    if !checkAndAdd(cards, 0) {
        return
    }

    addToXuShuSub(cards, 1)
}

func addToXuShuSub(cards []int, iLaiZiNum int) {
    if iLaiZiNum >= LaiZiNum {
        return
    }

    for i := 0; i < curCardsTypeNum; i++ {
        if cards[i] == 0 {
            continue
        }

        cards[i]--
        if !checkAndAdd(cards, iLaiZiNum) {
            cards[i]++
            continue
        }

        addToXuShuSub(cards, iLaiZiNum+1)
        cards[i]++
    }
}

func checkAndAdd(cards []int, iLaiZiNum int) bool {

    key := 0
    for i := 0; i < curCardsTypeNum; i++ {
        key = key*10 + cards[i]
    }

    HandCardsMapTemp := curTableTemp[iLaiZiNum]
    _, exists := (*HandCardsMapTemp)[key]
    if exists {
        return false
    }

    (*HandCardsMapTemp)[key] = true

    for i := 0; i < curCardsTypeNum; i++ {
        if cards[i] > 4 {
            return true
        }
    }

    HandCardsMap := curTable[iLaiZiNum]
    (*HandCardsMap)[key] = true
    return true
}

func genTableZi() {
    fmt.Println("genTableZi start")

    curTable = &tableZi
    curTableTemp = &tableZiTemp
    curCardsTypeNum = 7
    cards := []int{0, 0, 0, 0, 0, 0, 0}
    genZiPuZi(cards, 1)

    fmt.Println("genTableZi success")
}

func genTableZiWithEye() {
    fmt.Println("genTableZiWithEye start")

    curTable = &tableZiWithEye
    curTableTemp = &tableZiWithEyeTemp
    curCardsTypeNum = 7

    cards := []int{0, 0, 0, 0, 0, 0, 0}
    for i := 0; i < curCardsTypeNum; i++ {
        cards[i] = 2
        fmt.Println("genTableZiWithEye jiang = ", i)
        addToXuShu(cards)
        genZiPuZi(cards, 1)
        cards[i] = 0
    }

    fmt.Println("genTableZiWithEye success")
}

func genZiPuZi(cards []int, level int) {
    if level > 4 {
        return
    }

    for i := 0; i < curCardsTypeNum; i++ {
        if cards[i] > 3 {
            continue
        }

        cards[i] += 3
        addToXuShu(cards)
        genZiPuZi(cards, level+1)
        cards[i] -= 3
    }
}

func loadFromFile(name string, table *map[int]bool) {
    file, _ := os.Open(name)
    defer file.Close()

    reader := bufio.NewReader(file)
    for {
        buf, _, err := reader.ReadLine()
        if err == io.EOF {
            break
        }
        str := string(buf)
        key, _ := strconv.Atoi(str)
        (*table)[key] = true
    }
}

func loadTableXuShu() {
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableXuShu_%d.tbl", i)
        HandCardsMap := tableXuShu[i]
        loadFromFile(name, HandCardsMap)
    }
}

func loadTableXuShuWithEye() {
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableEyeXuShu_%d.tbl", i)
        HandCardsMap := tableXuShuWithEye[i]
        loadFromFile(name, HandCardsMap)
    }
}

func loadTableZi() {
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableZi_%d.tbl", i)
        HandCardsMap := tableZi[i]
        loadFromFile(name, HandCardsMap)
    }
}

func loadTableZiWithEye() {
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableEyeZi_%d.tbl", i)
        HandCardsMap := tableZiWithEye[i]
        loadFromFile(name, HandCardsMap)
    }
}

func dumpToFile(name string, table *map[int]bool) {
    file, _ := os.OpenFile(name, os.O_WRONLY|os.O_CREATE, 0666)
    defer file.Close()
    buf := bufio.NewWriter(file)
    for key := range *table {
        fmt.Fprintf(buf, "%d\n", key)
    }
    buf.Flush()
}

func dumpTableXuShu() {
    fmt.Println("dumpTableXuShu start")
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableXuShu_%d.tbl", i)
        HandCardsMap := tableXuShu[i]
        dumpToFile(name, HandCardsMap)
        fmt.Println(name, len(*HandCardsMap))
    }
}

func dumpTableXuShuWithEye() {
    fmt.Println("dumpTableXuShuWithEye start")
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableEyeXuShu_%d.tbl", i)
        HandCardsMap := tableXuShuWithEye[i]
        dumpToFile(name, HandCardsMap)
        fmt.Println(name, len(*HandCardsMap))
    }
}

func dumpTableZi() {
    fmt.Println("dumpTableZi start")
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableZi_%d.tbl", i)
        HandCardsMap := tableZi[i]
        dumpToFile(name, HandCardsMap)
        fmt.Println(name, len(*HandCardsMap))
    }
}

func dumpTableZiWithEye() {
    fmt.Println("dumpTableZiWithEye start")
    for i := 0; i < LaiZiNum; i++ {
        name := fmt.Sprintf("tableEyeZi_%d.tbl", i)
        HandCardsMap := tableZiWithEye[i]
        dumpToFile(name, HandCardsMap)
        fmt.Println(name, len(*HandCardsMap))
    }
}

Read All

[锁] 悲观锁和乐观锁

2017-11-13

miscellanea

Lock

转载自公众号：码农翻身作者刘欣前IBM架构师

旺财和小强生活在一个网上商城的系统中，是一对儿线程好基友。

星期一刚上班，旺财接到领导电话说，要把一个商品的库存减少20，旺财不敢怠慢，赶快把库存取出来一看，哦，现在有1000个。

与此同时，小强也接到电话说要把同一商品的库存减少30，他一看，哦，现在有1000个。

旺财计算出最新的库存值980，保存！

小强也计算出最新的库存值970，保存 !

旺财的数据被小强覆盖了！

领导一看，本来卖出了50个商品，现在库存只扣了30个，这样持续下去就天下大乱了。

旺财和小强，各打二十大板，长长记性！

小强说：“哥，要不我们还是想个办法吧，再这样下去要被打死的。”

旺财悲催地说： “这样，以后我们每次访问库存之前，都要先加锁，加了锁，就禁止别人再进入访问，只能等待持有锁的人来释放。”

星期二，领导让旺财再次把库存减少20 ，旺财这次万分小心，先把库存给锁住，然后慢慢修改。

小强也接到了把库存减少的指令，但是旺财哥已经把库存锁住了，不能操作，小强只好去阻塞车间喝茶聊天，然后到就绪车间等待调度运行。

好不容易等到可以再次执行了，小强一看，这库存怎么还锁着呢！？只好再次去阻塞车间喝茶。

领导一看，小强你怎么回事，老是喝茶聊天？！还干不干活了？

小强争辩说旺财哥一直锁着库存，我没法操作。

领导不管这些，把小强和旺财又打了二十大板。

（备注：这种加锁的方式就是悲观锁了，悲观锁正如其名，每次取读写数据时候总认为数据会被别人修改，所以将数据加锁，置于锁定状态，不让别人再访问。缺点是如果持有锁的时间太长，其他用户需要等待很长时间。）

旺财说： “兄弟，这一次哥对不住你啊，处理得慢了一些，不过哥刚才挨打的时候想了一个好办法：乐观锁。”

小强说：“拉倒吧你，屁股都快被打烂了还乐观？”

“你听我说嘛，我们在那个库存字段的旁边，再加上一个版本(version)的字段，例如刚开始的时候（库存= 1000，版本=1），每次你去读的时候不仅要读出库存，还要读出版本号，等到你修改了库存，往回写的时候一定要检查一下版本号，看看和你读的时候是否一样。”

“如果不一样呢？” 小强问

“那就放弃这次写的操作，重新读取库存和版本号，重新来过。”

“如果一样呢？ ”

“那就放心大胆地把新的库存值写回去。把版本号也加1”

“我似乎有点明白了，我们试试，不过你要想好，我可不想再挨板子了。”

星期三，旺财奉命把库存减去30，他先读到了（库存= 1000，版本=1）；小强也要改库存了，他要把库存减去50，于是他也读到了（库存= 1000，版本=1）。

旺财计算出新的库存值970 ，写回成功，现在版本变成了（库存= 970，版本=2）。

小强也计算出新库存950 ，也准备写回，他战战兢兢地去看最新的版本号，已经变成版本2了，按照之前的约定，只好重新读取了。

小强再次读取（库存= 970，版本=2），计算出最新缓存值920（970减去50），再次试图更新，没想到又被别人抢了先，现在版本号已经变成3了，最新的数据是（库存= 900，版本= 3）。

唉，只好重新来过，计算出最新缓存值850（900减去50），第三次终于更新成功了，最新的库存是（库存=850，版本= 4）

领导看到旺财和小强忙得热火朝天，一刻不停，并且库存值也没有乱掉，满意地点了点头：好同志啊。

（备注：这种方式就是所谓的乐观锁了，旺财和小强这次乐观了一点，觉得一般情况下不会有太多人修改库存，所以没有加锁，放心地去操作，只有在最后更新的时候才去看是否冲突。这种方式适合于冲突不多的场景，如果冲突很多，数据争用激烈，会导致不断地尝试，反而降低了性能。）

—————END—————

Read All

34/97

Welcome to MDGSF's Blog!

[GO] GoPath管理

build.sh

进程、线程和协程

进程、线程和协程

Goroutines

并发与并行

[算法学习][leetcode] 104 Maximum Depth of Binary Tree

题目

题目翻译

题目解析

参考答案

[GO] A simple load balancer

[vk_mj] Go实现赖子胡牌

[锁] 悲观锁和乐观锁