从Go标准库strings看字符串匹配算法

redstorm 发表了文章 • 0 个评论 • 24 次浏览 • 2 小时前 • 来自相关话题

Go的标准库本身质量非常高,本文主要深入strings库,从源代码中探查字符串匹配常用算法的具体实现

我们先看一个简单的例子开始。

在目标字符串中检查是否有子串等于匹配文本,这是非常常见的操作. 最容易让人想到的算法就是从目标... 查看全部

Go的标准库本身质量非常高,本文主要深入strings库,从源代码中探查字符串匹配常用算法的具体实现


我们先看一个简单的例子开始。


在目标字符串中检查是否有子串等于匹配文本,这是非常常见的操作. 最容易让人想到的算法就是从目标字符串第一位开始,逐个字符与待匹配文本比较.匹配成功则指针右移继续比较,要不然从目标文本的第二位开始和待匹配文本继续逐个比较。如果指针先到达待匹配文本末尾,则匹配成功,要不然匹配失败。该算法称之为朴素算法,非常容易理解,但效率也比较慢.具体实现如下:


#include<stdio.h>
#include<string.h>
void search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
int i;
// 只需要遍历目标文本 N-M 次, 因为从目标文本的 N-M 位开始的子串,长度永远小于 M, 所以不会匹配成功
for (i = 0; i <= N - M; i++)
{
int j;
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)
{
printf("Pattern found at index %d \n", i);
}
}
}

int main()
{
char *txt = "AABAACAADAABAAABAA";
char *pat = "AABA";
search(pat, txt);
return 0;
}

Go 标准库中的strings.Contains函数使用了Rabin-Karp算法, 主要思想如下:


假设匹配文本的长度为M,目标文本的长度为N



  1. 计算匹配文本的hash值

  2. 计算目标字符串中每个长度为M的子串的hash值(需要计算N-M+1次)

  3. 比较hash值, 如果hash值不同,字符串必然不匹配,如果hash值相同,还需要使用朴素算法再次判断


步骤2中每次都要重新计算hash, Rabin-Karp算法的优点在于设计了一个特别的hash算法,使其在计算下一个子串的hash时可以利用之前的hash结果, 以达到加速计算的效果。将每一个字节看作数字, 选择一个比较大的质数作为base. 字节的值是包含在基数之内的


举例说明:

文本为"abracadabra",base为101,那么 hash("abr") = 97 101的2次方 + 98 101的1次方 + 114 101的0次方= 999509

下一个子串 "bra"的hash值为 98
101的2次方 + 114 101的1次方 + 97 101的0次方. 我们可以利用之前"abr"的hash值, 写成:



//       base  old hash      new 'a'    old 'a' base

hash("bra") = 1011
hash("abr") + (97 × 101的0次方) - (97 × 101的3次方)



可以看出hash算法里要点是确立一个非常大的数字作为base,同时根据子串长度得到乘数因子(上述的 101的3次方,其实就是base的len(待匹配文本)次方).


src/strings/strings_amd64.go相关代码注释


// 选择非常大的一个质数16777619 作为 base 
const primeRK = 16777619

// hashStr 返回子串的hash值和乘数因子
func hashStr(sep string) (uint32, uint32) {
hash := uint32(0)
for i := 0; i < len(sep); i++ {
hash = hash*primeRK + uint32(sep[i]) //计算hash值
}
// 计算(最高位 + 1)位的乘数因子, 使用位移, 没有使用 i--, 可以有效减少循环次数. i >>=1 相当于遍历二进制的每一位
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {
if i&1 != 0 {
pow *= sq
}
sq *= sq
}
return hash, pow
}

// Index 返回sep在s里第一次匹配时的index, 无法匹配则返回-1.
func Index(s, sep string) int {
n := len(sep)
// 先分析一些常见情况, 起到进一步加速的效果
switch {
case n == 0:
return 0
case n == 1: //如果为一个字节,则调用IndixByte(汇编语言)
return IndexByte(s, sep[0])
case n <= shortStringLen: //如果sep的长度小于31且大于1, 则使用汇编代码(也是一种优化).
return indexShortStr(s, sep)
case n == len(s):
if sep == s {
return 0
}
return -1
case n > len(s):
return -1
}
// 使用Rabin-Karp算法匹配
// 步骤1 初始计算待匹配的文本的hash值和乘数因子,
hashsep, pow := hashStr(sep)
var h uint32
for i := 0; i < n; i++ {
h = h*primeRK + uint32(s[i]) // 步骤2 计算长度跟sep一样的s子串的hash值
}
if h == hashsep && s[:n] == sep {
return 0
}
for i := n; i < len(s); {
// 利用先前的hash值, 计算新的hash值
h *= primeRK // 乘以base
h += uint32(s[i]) // 加上下一个字符的 hash 值
h -= pow * uint32(s[i-n]) // 减去先前子串的第一个字符的hash值
i++
// 如果hash相等则继续使用朴素算法比较, 如果hash不一致,则直接用下一个匹配
if h == hashsep && s[i-n:i] == sep {
return i - n
}
}
return -1
}

strings库里还实现了BM算法, 在这之前,我们先来看另一个非常经典的KMP算法


假设检查bacbababaabcbab是否包含abababca, 此时发现第6位不一样


bacbababaabcbab   
abababca
|
第六位

朴素算法:
bacbababaabcbab
abababca
|
移动一位后开始重新比较

KMP算法:
bacbababaabcbab
abababca
|
直接移动两位后开始重新比较

如果按朴素算法则按上面所示需要搜索词移一位后重新从第一位开始匹配。仔细想想, 前5个字符ababa已经匹配成功,也就是我们已经知道双方的文本, 通过提前的计算,可以多移几位, 而不仅仅移一位. 这样可以加快搜索


KMP算法的主要原理如下:

s为目标文本, 长度为m

p为搜索词,长度为n

假设p[i]与s[x]匹配失败,那么p[i-1]与s[x-1]是匹配成功的, 则试图找到一个索引 j, 使得p[0:j] = p[i-j-1:i-1] (p[0:j] 包含p[j])

如果有则s[x]继续与p[j+1]进行比较, 相当于搜索词移动i-j-1位

无则s[x]与p[0]比较. (具体代码实现时无可以表示为-1, 这样+1 后正好为0) 相当于搜索词移动i位


void cal(char *p, int *next)
{
int i;
int k;
/*第一次字符前面没有索引了, 算corner case, 直接赋值为-1*/
next[0] = -1;
/* 循环每一个索引, 并计算next值 */
for (i = 1; p[i] != '\0'; i++) {
/* 获取前一个索引的next值 */
k = next[i - 1];
/* 当p[i] != p[k + 1]时, 则令 k = next[k], 直到相等或者k == -1 退出*/
while (p[i] != p[k + 1]) {
if (k == -1) {
k = -2;
break;
}
k = next[k];
}
/* 1. p[i] == p[k + 1] 则 i对应的next值为 ++k
2. 无索引时, k= -2, 则++k正好为-1
*/
next[i] = ++k;
}
}

int kmp(char *p, char*t)
{
/*next为数组, 存储搜索词里每一个索引对应的next值, 使得 p[0:next[i]] == p[i-j-1:i-1]*/
int next[strlen(p)];
cal(p, next);
int i, j;
i = 0;
j = 0;
while (p[i] != '\0' && t[j] != '\0') {
if (p[i] == t[j]) {
/* 值相等, 则指针 i, j 都递增 */
i++;
j++;
} else {
if (i == 0) {
j++;
continue;
}
i = next[i - 1] + 1;
}
}
if (p[i] == '\0') {
return 0;
} else {
return 1;
}
}

Go语言里在 strings/search.go 里使用了Boyer-Moore字符串搜索算法, 这个思想和KMP类似,都是根据Pattern自身计算出移动的步数. 有两个优化点:



  1. BM算法是从后向前逐渐匹配.

  2. kmp里的通过已匹配的文本增加移动步数的叫做好规则,那么BM里同时还增加了坏规则


假定Text为"HERE IS A SIMPLE EXAMPLE",Pattern为"EXAMPLE"。

当T[i] != P[j], P[j]右边都匹配时时, 具体的移动规则如下:

坏字符规则: 此时T[i]定义为坏字符, 如果P[0..j-1]中包含T[i]这个字符, 则移动T使坏字符与相等的字符对齐, 如果不包含,则直接移动len(P)


HERE IS A SIMPLE EXAMPLE
|
EXAMPLE

此时P为坏字符, 因EXAMPLE包含P, 则T的i指针右移二位使之对齐,然后重新开始从P的末端继续匹配(下面打X处).

HERE IS A SIMPLE EXAMPLE
| X
EXAMPLE

如下场景,T中的M与P中的E不匹配, 按Go的代码实现,是移动两位(取该字符到P末尾的最短距离),没完全按上面的规则实现
大家是不是发现没有跳跃前进,反而匹配又倒回到之前已完成的匹配过程。 Go代码这么做是为了实现简单。
因为还有好规则可以保证最终的移动步数是正确的
ABCADADEEFXYZ
|
AYEDADE
移动为
ABCADADEEFXYZ
| X
AYEDADE

好后缀规则: 当发生不匹配时,之前已经匹配成功的,称之为好字符. 如下I和A不匹配, 后面的MPLE就是好后缀. 首先检查P里是否好后缀只出现过一次: 比如此时的MPLE作为好后缀在整个字符串EXAMPLE中只出现过一次



  • 不是, 则移动P使T中的好后缀与P中长度相等的字符串对齐

  • 是, 则继续检查好后缀的所有后缀(比如PLE,PL,E)是否和同等长度的P前缀相等, 如果相等则移动P使之对齐, 不相等则移动 len(P).

    这里相当于要求后缀必须出现在P的首部, 如果非首部, 因前缀的前一个字符必然不相等,则整个字符串肯定无法匹配


HERE IS A SIMPLE EXAMPLE
||||
EXAMPLE
MPLE, PLE,LE没法和首部匹配,但后缀E和P前缀相等, 则移动T使其对齐,从打X出继续从后向前比较
HERE IS A SIMPLE EXAMPLE
| X
EXAMPLE

具体的代码注释如下:


func makeStringFinder(pattern string) *stringFinder {
f := &stringFinder{
pattern: pattern,
goodSuffixSkip: make([]int, len(pattern)),
}
// last 是pattern最后一个字符的索引
last := len(pattern) - 1

// 创建坏字符表,记录不匹配时T的i指针移动步数
// 第一阶段,初始化256个字符全部移动 len(pattern) 步
for i := range f.badCharSkip {
f.badCharSkip[i] = len(pattern)
}

// 第二阶段:从左到右遍历pattern,更新其索引与P末尾的距离,结果就是该字符到末尾的最小距离
// 没有计算last byte的距离, 因为移动至少要一步。 没有0步。
for i := 0; i < last; i++ {
f.badCharSkip[pattern[i]] = last - i
}

// 创建好后缀表
// 第一阶段: 此时pattern[i+1:]都是已经匹配的,且好后缀只出现了一次
// 计算T中的指针要移动的步数
lastPrefix := last
for i := last; i >= 0; i-- {
if HasPrefix(pattern, pattern[i+1:]) {
lastPrefix = i + 1
}
// 好后缀时T的指针移动分两步,首先移动到与 pattern的末尾对齐,即 last - i
// lastPrefix 用来记录 pattern[i+1:]中所有后缀与同等长度的前缀相等时的最大索引
// 然后移动 lastPrefix步
f.goodSuffixSkip[i] = lastPrefix + last - i
}
// 第二阶段: 好后缀在pattern前面部分还出现过, 如下计算相应的移动步数
// 会覆盖之前第一阶段的部分值。但好后缀出现过移动步数比没出现的小。所以最终值是正确的
// 举例: "mississi" 中好后缀是issi, 在pattern[1]处出现过,所以移动步数为 last-i + lenSuffix
for i := 0; i < last; i++ {
lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
// (last-i) is the shift, and lenSuffix is len(suffix).
f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
}
}
return f
}
// longestCommonSuffix 仅仅比较两个字符串的共同后缀的长度, 没有则为0
func longestCommonSuffix(a, b string) (i int) {
for ; i < len(a) && i < len(b); i++ {
if a[len(a)-1-i] != b[len(b)-1-i] {
break
}
}
return
}

// next 主要返回p在text里第一次匹配时的索引, 不匹配则返回-1
func (f *stringFinder) next(text string) int {
// i 是T(即变量text)中要检查的字符索引, j为P中要检查的字符索引

// 因从后向前比较, 所以i初始化为P的最后一位索引
i := len(f.pattern) - 1
for i < len(text) {
// 每次比较时都从p的最后一位开始比较
j := len(f.pattern) - 1
for j >= 0 && text[i] == f.pattern[j] {
i--
j--
}
// j为负数,说明匹配成功, 则直接返回 i+ 1
if j < 0 {
return i + 1
}
// j为非负, 表明text[i] != f.pattern[j], 则从坏字符表和好后缀表中获取分别获取i需要移动的步数, 取最大值并使移动到新位置
i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
}
return -1
}

免费可以测试的vps服务器资源?

xiaodu2017 回复了问题 • 4 人关注 • 5 个回复 • 505 次浏览 • 2 天前 • 来自相关话题

链表以及golang介入式链表的实现

sheepbao 发表了文章 • 4 个评论 • 211 次浏览 • 4 天前 • 来自相关话题

链表以及golang介入式链表的实现

今天看tcp/ip协议栈的代码时看到一个双向链表,链表吗?听过它的顶顶大名,知道它是由节点构成的,每个节点还有个指针指向下一个节点,但是从来没自己实现过一个,没有实践就不能深刻理解,遂有此文。查看全部

链表以及golang介入式链表的实现


今天看tcp/ip协议栈的代码时看到一个双向链表,链表吗?听过它的顶顶大名,知道它是由节点构成的,每个节点还有个指针指向下一个节点,但是从来没自己实现过一个,没有实践就不能深刻理解,遂有此文。

以下所有观点都是个人愚见,有不同建议或补充的的欢迎emial我aboutme


何为链表?


链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

简单的说链表是一个具有逻辑顺序的线性表,每一个节点里存到下一个节点的指针。


图示


单链表


list1


双向链表


list2


链表有啥用?


因为链表插入很快,而且具有动态性,想添加几个元素就添加几个(内存空间足够),不像数组一样那么死板,正因为链表的灵活性,所有链表的用处是大大的有啊。

链表最适合用于频繁更新变化的数据,比如一个需要异步执行并且不可丢失的命令序列、一个需要进行实时加载与卸载的驱动,无序且数量未知,这个时候就需要链表结构来协助完成数据的管理。如果不需要过度关注数据的顺序,还可以用链表方便快捷地在任意一个地方插入或删除一个元素,并且不会影响到其它的元素。

又或者我在今天看tcp/ip源码中,链表用来构造队列,作为数据段的队列。我想链表用于队列应该是最多的。如果你看过linux内核源码,应该会发现linux内核中多处使用链表这种结构。


go标准库的双向链表


golang的标准库中实现了一个双向链表,该链表可以存储任何数据,先看看使用标准库链表的例子:


package list_test

import (
"container/list"
"fmt"
"testing"
)

func TestList(t *testing.T) {
// Create a new list and put some numbers in it.
l := list.New()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)

// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
// output
// 1
// 2
// 3
// 4

该链表实现了链表所有的功能,链表的增删查改。


实现该链表的数据结构


// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}

// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element

// The list to which this element belongs.
list *List

// The value stored with this element.
Value interface{}
}

可以看到Element结构体看到了链表的结构,next,prev分别指向下一个和前一个元素的指针。Value就是链表中的数据段,可以理解为上图中的object。


介入式链表(intrusive list)


前面的链表都是普通链表,记得<<c语言程序设计>>上讲的链表也是一样,就是链表的节点指针和数据段是放在同一个struct,每实现一个不同的struct就得重新实现一遍链表的功能,这对于“懒惰”的程序员来说是不可忍受的,所以就出来了介入式链表,将数据段和链表的功能区别开来。最经典的例子莫过于linux内核的list_head,详情请看链接klist or Linked List in Linux Kernel,linux中是用c实现的,我想用go实现一个介入式链表。


实现代码


package list

type Intrusive interface {
Next() Intrusive
Prev() Intrusive
AddNext(Intrusive)
AddPrev(Intrusive)
}

// List provides the implementation of intrusive linked lists
type List struct {
prev Intrusive
next Intrusive
}

func (l *List) Next() Intrusive {
return l.next
}

func (l *List) Prev() Intrusive {
return l.prev
}

func (l *List) AddNext(i Intrusive) {
l.next = i
}

func (l *List) AddPrev(i Intrusive) {
l.prev = i
}

func (l *List) Reset() {
l.prev = nil
l.next = nil
}

func (l *List) Empty() bool {
return l.prev == nil
}

// Front returns the first element of list l or nil.
func (l *List) Front() Intrusive {
return l.prev
}

// Back returns the last element of list l or nil.
func (l *List) Back() Intrusive {
return l.next
}

// PushFront inserts the element e at the front of list l.
func (l *List) PushFront(e Intrusive) {
e.AddPrev(nil)
e.AddNext(l.prev)

if l.prev != nil {
l.prev.AddPrev(e)
} else {
l.next = e
}
l.prev = e
}

// PushBack inserts the element e at the back of list l.
func (l *List) PushBack(e Intrusive) {
e.AddNext(nil)
e.AddPrev(l.next)

if l.next != nil {
l.next.AddNext(e)
} else {
l.prev = e
}
l.next = e
}

// InsertAfter inserts e after b.
func (l *List) InsertAfter(e, b Intrusive) {
a := b.Next()
e.AddNext(a)
e.AddPrev(b)
b.AddNext(e)

if a != nil {
a.AddPrev(e)
} else {
l.next = e
}
}

// InsertBefore inserts e before a.
func (l *List) InsertBefore(e, a Intrusive) {
b := a.Prev()
e.AddNext(a)
e.AddPrev(b)
a.AddPrev(e)

if b != nil {
b.AddNext(e)
} else {
l.prev = e
}
}

// Remove removes e from l.
func (l *List) Remove(e Intrusive) {
prev := e.Prev()
next := e.Next()

if prev != nil {
prev.AddNext(next)
} else {
l.prev = next
}

if next != nil {
next.AddPrev(prev)
} else {
l.next = prev
}
}

我们这里用List表示实现了Intrusive接口,也实现了链表的基本功能,所以任何实现了Intrusive接口的对象都是可以作为链表的节点,利用这个介入式链表就很简单了,只要在现有的struct嵌入List这个结构体即可,在举个例子:


package list

import (
"container/list"
"fmt"
"testing"
)

func TestIntrusiveList(t *testing.T) {
type E struct {
List
data int
}
// Create a new list and put some numbers in it.
l := List{}
e4 := &E{data: 4}
e1 := &E{data: 1}
l.PushBack(e4)
l.PushFront(e1)
l.InsertBefore(&E{data: 3}, e4)
l.InsertAfter(&E{data: 2}, e1)

for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("e: %#v\n", e)
fmt.Printf("data: %#v\n", e.(*E).data)
}
}

E里嵌入List即可作为链表的节点,是不是很方便,其实当我写完介入式链表的栗子后,发现其实标准库的链表更方便,哈哈。。因为golang有interface{}


参考


https://blog.goquxiao.com/posts/2013/07/06/intrusive-list/

http://blog.nlogn.cn/linked-list-in-linux-kernel/

【翻译】使用 sync.ErrGroup 实现并发搜索文件

crazyvv 回复了问题 • 6 人关注 • 2 个回复 • 1529 次浏览 • 2017-10-11 15:11 • 来自相关话题

Go并发机制

simple 发表了文章 • 0 个评论 • 377 次浏览 • 2017-10-08 22:31 • 来自相关话题

不知道为什么有三张图在这里无法显示,有点郁闷!!! ->查看全部

不知道为什么有三张图在这里无法显示,有点郁闷!!! ->原文链接


1. C/C++ 与 Go语言的“价值观”对照


之前看过 白明老师 在GopherChina2017的一篇演讲文章《Go coding in go way》,里面提到C/C++/Go三门语言价值观,感觉很有意思,分享给大家感受一下:


C的价值观摘录



  • 相信程序员:提供指针和指针运算,让C程序员天马行空的发挥

  • 自己动手,丰衣足食:提供一个很小的标准库,其余的让程序员自造

  • 保持语言的短小和简单

  • 性能优先


C++价值观摘录



  • 支持多范式,不强迫程序员使用某个特定的范式

  • 不求完美,但求实用(并且立即可用)


Go价值观



  • Overall Simplicity 全面的简单

  • Orthogonal Composition 正交组合

  • Preference in Concurrency 偏好并发


用一句话概括Go的价值观:
Go is about orthogonal composition of simple concepts with preference in concurrency(Go是在偏好并发的环境下的简单概念/事物的正交组合).


从Go的价值观介绍可以看出 Go很适合并发编程,可以说其是为并发而生的一门语言,那它的并发机制如何?这正是这篇文章想要介绍的。


2. 从线程实现模型说起


线程的实现模型主要有3种:内核级线程模型、用户级线程模型和混合型线程模型。它们之间最大的区别在于线程与内核调度实体KSE(Kernel Scheduling Entity)之间的对应关系上。所谓的内核调度实体KSE 就是指可以被操作系统内核调度器调度的对象实体,有些地方也称其为内核级线程,是操作系统内核的最小调度单元。


2.1 内核级线程模型


用户线程与KSE是1对1关系(1:1)。大部分编程语言的线程库(如linux的pthread,Java的java.lang.Thread,C++11的std::thread等等)都是对操作系统的线程(内核级线程)的一层封装,创建出来的每个线程与一个不同的KSE静态关联,因此其调度完全由OS调度器来做。这种方式实现简单,直接借助OS提供的线程能力,并且不同用户线程之间一般也不会相互影响。但其创建,销毁以及多个线程之间的上下文切换等操作都是直接由OS层面亲自来做,在需要使用大量线程的场景下对OS的性能影响会很大。


2.2 用户级线程模型


用户线程与KSE是多对1关系(M:1),这种线程的创建,销毁以及多个线程之间的协调等操作都是由用户自己实现的线程库来负责,对OS内核透明,一个进程中所有创建的线程都与同一个KSE在运行时动态关联。现在有许多语言实现的 协程 基本上都属于这种方式。这种实现方式相比内核级线程可以做的很轻量级,对系统资源的消耗会小很多,因此可以创建的数量与上下文切换所花费的代价也会小得多。但该模型有个致命的缺点,如果我们在某个用户线程上调用阻塞式系统调用(如用阻塞方式read网络IO),那么一旦KSE因阻塞被内核调度出CPU的话,剩下的所有对应的用户线程全都会变为阻塞状态(整个进程挂起)。

所以这些语言的协程库会把自己一些阻塞的操作重新封装为完全的非阻塞形式,然后在以前要阻塞的点上,主动让出自己,并通过某种方式通知或唤醒其他待执行的用户线程在该KSE上运行,从而避免了内核调度器由于KSE阻塞而做上下文切换,这样整个进程也不会被阻塞了。


2.3 混合型线程模型


用户线程与KSE是多对多关系(M:N), 这种实现综合了前两种模型的优点,为一个进程中创建多个KSE,并且线程可以与不同的KSE在运行时进行动态关联,当某个KSE由于其上工作的线程的阻塞操作被内核调度出CPU时,当前与其关联的其余用户线程可以重新与其他KSE建立关联关系。当然这种动态关联机制的实现很复杂,也需要用户自己去实现,这算是它的一个缺点吧。Go语言中的并发就是使用的这种实现方式,Go为了实现该模型自己实现了一个运行时调度器来负责Go中的"线程"与KSE的动态关联。此模型有时也被称为 两级线程模型即用户调度器实现用户线程到KSE的“调度”,内核调度器实现KSE到CPU上的调度


三种模型的示意图如下:
图片1


3. Go并发调度: G-P-M模型


3.1 G-P-M模型


有了上面的认识,我们可以开始真正的介绍Go的并发机制了,先用一段代码展示一下在Go语言中新建一个“线程”(Go语言中称为Goroutine)的样子:


// 用go关键字加上一个函数(这里用了匿名函数)
// 调用就做到了在一个新的“线程”并发执行任务
go func() {
// do something in one new goroutine
}()

功能上等价于Java8的代码:


new java.lang.Thread(() -> { 
// do something in one new thread
}).start();

可以看到Go的并发用起来非常简单,用了一个语法糖将内部复杂的实现结结实实的包装了起来。其内部可以用下面这张图来概述:
图片2
其图中的G, P和M都是Go语言运行时系统(其中包括内存分配器,并发调度器,垃圾收集器等组件,可以想象为Java中的JVM)抽象出来概念和数据结构对象:

G:Goroutine的简称,上面用go关键字加函数调用的代码就是创建了一个G对象,是对一个要并发执行的任务的封装,也可以称作用户态线程。属于用户级资源,对OS透明,具备轻量级,可以大量创建,上下文切换成本低等特点。

M:Machine的简称,在linux平台上是用clone系统调用创建的,其与用linux pthread库创建出来的线程本质上是一样的,都是利用系统调用创建出来的OS线程实体。M的作用就是执行G中包装的并发任务。Go运行时系统中的调度器的主要职责就是将G公平合理的安排到多个M上去执行。其属于OS资源,可创建的数量上也受限了OS,通常情况下G的数量都多于活跃的M的。

P:Processor的简称,逻辑处理器,主要作用是管理G对象(每个P都有一个G队列),并为G在M上的运行提供本地化资源。

从2.3节介绍的两级线程模型来看,似乎并不需要P的参与,有G和M就可以了,那为什么要加入P这个东东呢?

其实Go语言运行时系统早期(Go1.0)的实现中并没有P的概念,Go中的调度器直接将G分配到合适的M上运行。但这样带来了很多问题,例如,不同的G在不同的M上并发运行时可能都需向系统申请资源(如堆内存),由于资源是全局的,将会由于资源竞争造成很多系统性能损耗,为了解决类似的问题,后面的Go(Go1.1)运行时系统加入了P,让P去管理G对象,M要想运行G必须先与一个P绑定,然后才能运行该P管理的G。这样带来的好处是,我们可以在P对象中预先申请一些系统资源(本地资源),G需要的时候先向自己的本地P申请(无需锁保护),如果不够用或没有再向全局申请,而且从全局拿的时候会多拿一部分,以供后面高效的使用。就像现在我们去政府办事情一样,先去本地政府看能搞定不,如果搞不定再去中央,从而提供办事效率。

而且由于P解耦了G和M对象,这样即使M由于被其上正在运行的G阻塞住,其余与该M关联的G也可以随着P一起迁移到别的活跃的M上继续运行,从而让G总能及时找到M并运行自己,从而提高系统的并发能力。

Go运行时系统通过构造G-P-M对象模型实现了一套用户态的并发调度系统,可以自己管理和调度自己的并发任务,所以可以说Go语言原生支持并发自己实现的调度器负责将并发任务分配到不同的内核线程上运行,然后内核调度器接管内核线程在CPU上的执行与调度。


3.2 调度过程


Go运行时完整的调度系统是很复杂,很难用一篇文章描述的清楚,这里只能从宏观上介绍一下,让大家有个整体的认识。


// Goroutine1
func task1() {
go task2()
go task3()
}

假如我们有一个G(Goroutine1)已经通过P被安排到了一个M上正在执行,在Goroutine1执行的过程中我们又创建两个G,这两个G会被马上放入与Goroutine1相同的P的本地G任务队列中,排队等待与该P绑定的M的执行,这是最基本的结构,很好理解。 关键问题是:

a.如何在一个多核心系统上尽量合理分配G到多个M上运行,充分利用多核,提高并发能力呢?
如果我们在一个Goroutine中通过go关键字创建了大量G,这些G虽然暂时会被放在同一个队列, 但如果这时还有空闲P(系统内P的数量默认等于系统cpu核心数),Go运行时系统始终能保证至少有一个(通常也只有一个)活跃的M与空闲P绑定去各种G队列去寻找可运行的G任务,该种M称为自旋的M。一般寻找顺序为:自己绑定的P的队列,全局队列,然后其他P队列。如果自己P队列找到就拿出来开始运行,否则去全局队列看看,由于全局队列需要锁保护,如果里面有很多任务,会转移一批到本地P队列中,避免每次都去竞争锁。如果全局队列还是没有,就要开始玩狠的了,直接从其他P队列偷任务了(偷一半任务回来)。这样就保证了在还有可运行的G任务的情况下,总有与CPU核心数相等的M+P组合 在执行G任务或在执行G的路上(寻找G任务)。

b. 如果某个M在执行G的过程中被G中的系统调用阻塞了,怎么办?

在这种情况下,这个M将会被内核调度器调度出CPU并处于阻塞状态,与该M关联的其他G就没有办法继续执行了,但Go运行时系统的一个监控线程(sysmon线程)能探测到这样的M,并把与该M绑定的P剥离,寻找其他空闲或新建M接管该P,然后继续运行其中的G,大致过程如下图所示。然后等到该M从阻塞状态恢复,需要重新找一个空闲P来继续执行原来的G,如果这时系统正好没有空闲的P,就把原来的G放到全局队列当中,等待其他M+P组合发掘并执行。

图片3

c. 如果某一个G在M运行时间过长,有没有办法做抢占式调度,让该M上的其他G获得一定的运行时间,以保证调度系统的公平性?

我们知道linux的内核调度器主要是基于时间片和优先级做调度的。对于相同优先级的线程,内核调度器会尽量保证每个线程都能获得一定的执行时间。为了防止有些线程"饿死"的情况,内核调度器会发起抢占式调度将长期运行的线程中断并让出CPU资源,让其他线程获得执行机会。当然在Go的运行时调度器中也有类似的抢占机制,但并不能保证抢占能成功,因为Go运行时系统并没有内核调度器的中断能力,它只能通过向运行时间过长的G中设置抢占flag的方法温柔的让运行的G自己主动让出M的执行权。

说到这里就不得不提一下Goroutine在运行过程中可以动态扩展自己线程栈的能力,可以从初始的2KB大小扩展到最大1G(64bit系统上),因此在每次调用函数之前需要先计算该函数调用需要的栈空间大小,然后按需扩展(超过最大值将导致运行时异常)。Go抢占式调度的机制就是利用在判断要不要扩栈的时候顺便查看以下自己的抢占flag,决定是否继续执行,还是让出自己。

运行时系统的监控线程会计时并设置抢占flag到运行时间过长的G,然后G在有函数调用的时候会检查该抢占flag,如果已设置就将自己放入全局队列,这样该M上关联的其他G就有机会执行了。但如果正在执行的G是个很耗时的操作且没有任何函数调用(如只是for循环中的计算操作),即使抢占flag已经被设置,该G还是将一直霸占着当前M直到执行完自己的任务。


4. Goroutine与Channel: 锁之外的另一种同步机制


在主流的编程语言中为了保证多线程之间共享数据安全性和一致性,都会提供一套基本的同步工具集,如锁,条件变量,原子操作等等。Go语言标准库也毫不意外的提供了这些同步机制,使用方式也和其他语言也差不多。

除了这些基本的同步手段,Go语言还提供了一种新的同步机制: Channel,它在Go语言中是一个像int, float32等的基本类型,一个channel可以认为是一个能够在多个Goroutine之间传递某一类型的数据的管道。Go中的channel无论是实现机制还是使用场景都和Java中的BlockingQueue很接近。


使用方式


// 声明channel变量
var syncChan = make(chan int) // 无缓冲channel,主要用于两个Goroutine之间建立同步点
var cacheChan = make(chan int, 10) // 缓冲channel
// 向channel中写入数据
syncChan <- 1
cacheChan <- 1
// 从channel读取数据
var i = <-syncChan
var j = <-cacheChan

几乎等价于的Java中的操作:


TransferQueue<Integer> syncQueue = new LinkedTransferQueue<Integer>();
BlockingQueue<Integer> cacheQueue = new ArrayBlockingQueue<Integer>(10);

syncQueue.transfer(1);
cacheQueue.put(1);

int i = syncQueue.take();
int j = cacheQueu.take();

使用场景

a. 与Java的BlockingQueue一样用在需要生产者消费者模型的并发环境中。

b. 锁同步场景下一种替代方案。在Go的并发编程中有一句很经典的话:不要以共享内存的方式去通信,而要以通信的方式去共享内存。在Go语言中并不鼓励用锁保护共享状态的方式在不同的Goroutine中分享信息(以共享内存的方式去通信)。而是鼓励通过channel将共享状态或共享状态的变化在各个Goroutine之间传递(以通信的方式去共享内存),这样同样能像用锁一样保证在同一的时间只有一个Goroutine访问共享状态。但这的确需要转换以前用锁做并发同步的思维方式,大家觉得那种适合自己和自己的使用场景就用哪种好了,并不能很简单、绝对地说哪种方式更好,更高效。


5. Go语言对网络IO的优化


在谈论高性能网络IO编程时,我们几乎都离不开epoll/kqueue/iocp等技术术语了,如Java最新的的NIO,Node等等的高性能网络IO模型都是基于这些技术实现的。诞生于21世纪,有互联网时代的C语言之称的Go语言,这么重视高并发,当然不会放过对网络的优化。且Go语言中对网络IO的优化很巧妙,让你可以用和以前一样的(同步的)思维方式去编程的同时(而不是反人类的异步方式),还能享受到与异步方式几乎同等高效的运行性能。那Go语言中是如何做的呢?主要是从两方面下手的:

a. 将标准库中的网络库全部封装为非阻塞形式,防止其阻塞底层的M并导致内核调度器切换上下文带来的系统开销。

b. 运行时系统加入epoll机制(针对Linux系统),当某一个Goroutine在进行网络IO操作时,如果网络IO未就绪,就将其该Goroutine封装一下,放入epoll的等待队列中,当前G挂起,与其关联的M可以继续运行其他G。当相应的网络IO就绪后,Go运行时系统会将等待网络IO就绪的G从epoll就绪队列中取出(主要在两个地方从epoll中获取已网络IO就绪的G列表,一是sysmon监控线程中,二是自旋的M中),再由调度器将它们像普通的G一样分配给各个M去执行。

Go语言将高性能网络IO的实现方式直接集成到了Go本身的运行时系统中,与Go的并发调度系统协同高效的工作,让开发人员可以简单,高效地进行网络编程。


6. 总结


Go语言并不完美,它是以软件工程为目的的语言设计。其实现的并发机制也并不是什么革新的技术,只是将这些经典的理论和技术以一种简洁高效的方式组合了起来,并用简单抽象的API或语法糖开放给开发人员,着实减轻了开发人员编程的心智负担。而且其通过引入channel机制,将另一种并发编程模型(CSP: 通信顺序进程)带给了我们,给我们提供了使用其他并发编程思维方式的机会(有关CSP模型建议大家看看《七周七并发模型》这本书的第六章),Goroutine与Channel的组合是一对很有powerful的并发工具,相信其可以给你带了更好的并发编程体验。


7. 参考


《Go并发编程实战》 第2版

《Go语言学习笔记》

也谈goroutine调度器

Go coding in go way

golang string和[]byte的对比

sheepbao 发表了文章 • 0 个评论 • 302 次浏览 • 2017-09-30 16:42 • 来自相关话题

golang string和[]byte的对比

为啥string和[]byte类型转换需要一定的代价?
为啥内置函数copy会有一种特殊情况copy(dst []byte, src string) int查看全部

golang string和[]byte的对比


为啥string和[]byte类型转换需要一定的代价?

为啥内置函数copy会有一种特殊情况copy(dst []byte, src string) int?

string和[]byte,底层都是数组,但为什么[]byte比string灵活,拼接性能也更高(动态字符串拼接性能对比)?

今天看了源码探究了一下。

以下所有观点都是个人愚见,有不同建议或补充的的欢迎emial我aboutme


何为string?


什么是字符串?标准库builtin的解释:


type string

string is the set of all strings of 8-bit bytes, conventionally but not necessarily representing UTF-8-encoded text. A string may be empty, but not nil. Values of string type are immutable.

简单的来说字符串是一系列8位字节的集合,通常但不一定代表UTF-8编码的文本。字符串可以为空,但不能为nil。而且字符串的值是不能改变的。

不同的语言字符串有不同的实现,在go的源码中src/runtime/string.go,string的定义如下:


type stringStruct struct {
str unsafe.Pointer
len int
}

可以看到str其实是个指针,指向某个数组的首地址,另一个字段是len长度。那到这个数组是什么呢?
在实例化这个stringStruct的时候:


func gostringnocopy(str *byte) string {
ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
s := *(*string)(unsafe.Pointer(&ss))
return s
}

哈哈,其实就是byte数组,而且要注意string其实就是个struct。


何为[]byte?


首先在go里面,byte是uint8的别名。而slice结构在go的源码中src/runtime/slice.go定义:


type slice struct {
array unsafe.Pointer
len int
cap int
}

array是数组的指针,len表示长度,cap表示容量。除了cap,其他看起来和string的结构很像。

但其实他们差别真的很大。


区别


字符串的值是不能改变


在前面说到了字符串的值是不能改变的,这句话其实不完整,应该说字符串的值不能被更改,但可以被替换。 还是以string的结构体来解释吧,所有的string在底层都是这样的一个结构体stringStruct{str: str_point, len: str_len},string结构体的str指针指向的是一个字符常量的地址,
这个地址里面的内容是不可以被改变的,因为它是只读的,但是这个指针可以指向不同的地址,我们来对比一下string、[]byte类型重新赋值的区别:


s := "A1" // 分配存储"A1"的内存空间,s结构体里的str指针指向这快内存
s = "A2" // 重新给"A2"的分配内存空间,s结构体里的str指针指向这快内存

其实[]byte和string的差别是更改变量的时候array的内容可以被更改。


s := []byte{1} // 分配存储1数组的内存空间,s结构体的array指针指向这个数组。
s = []byte{2} // 将array的内容改为2

因为string的指针指向的内容是不可以更改的,所以每更改一次字符串,就得重新分配一次内存,之前分配空间的还得由gc回收,这是导致string操作低效的根本原因。


string和[]byte的相互转换


将string转为[]byte,语法[]byte(string)源码如下:


func stringtoslicebyte(buf *tmpBuf, s string) []byte {
var b []byte
if buf != nil && len(s) <= len(buf) {
*buf = tmpBuf{}
b = buf[:len(s)]
} else {
b = rawbyteslice(len(s))
}
copy(b, s)
return b
}

func rawstring(size int) (s string, b []byte) {
p := mallocgc(uintptr(size), nil, false)

stringStructOf(&s).str = p
stringStructOf(&s).len = size

*(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}

return
}

可以看到b是新分配的,然后再将s复制给b,至于为啥copy函数可以直接把string复制给[]byte,那是因为go源码单独实现了一个slicestringcopy函数来实现,具体可以看src/runtime/slice.go


将[]byte转为string,语法string([]byte)源码如下:


func slicebytetostring(buf *tmpBuf, b []byte) string {
l := len(b)
if l == 0 {
// Turns out to be a relatively common case.
// Consider that you want to parse out data between parens in "foo()bar",
// you find the indices and convert the subslice to string.
return ""
}
if raceenabled && l > 0 {
racereadrangepc(unsafe.Pointer(&b[0]),
uintptr(l),
getcallerpc(unsafe.Pointer(&buf)),
funcPC(slicebytetostring))
}
if msanenabled && l > 0 {
msanread(unsafe.Pointer(&b[0]), uintptr(l))
}
s, c := rawstringtmp(buf, l)
copy(c, b)
return s
}

func rawstringtmp(buf *tmpBuf, l int) (s string, b []byte) {
if buf != nil && l <= len(buf) {
b = buf[:l]
s = slicebytetostringtmp(b)
} else {
s, b = rawstring(l)
}
return
}

依然可以看到s是新分配的,然后再将b复制给s。

正因为string和[]byte相互转换都会有新的内存分配,才导致其代价不小,但读者千万不要误会,对于现在的机器来说这些代价其实不值一提。
但如果想要频繁string和[]byte相互转换(仅假设),又不会有新的内存分配,能有办法吗?答案是有的。


package string_slicebyte_test

import (
"log"
"reflect"
"testing"
"unsafe"
)

func stringtoslicebyte(s string) []byte {
sh := (*reflect.StringHeader)(unsafe.Pointer(&s))
bh := reflect.SliceHeader{
Data: sh.Data,
Len: sh.Len,
Cap: sh.Len,
}
return *(*[]byte)(unsafe.Pointer(&bh))
}

func slicebytetostring(b []byte) string {
bh := (*reflect.SliceHeader)(unsafe.Pointer(&b))
sh := reflect.StringHeader{
Data: bh.Data,
Len: bh.Len,
}
return *(*string)(unsafe.Pointer(&sh))
}

func TestStringSliceByte(t *testing.T) {
s1 := "abc"
b1 := []byte("def")
copy(b1, s1)
log.Println(s1, b1)

s := "hello"
b2 := stringtoslicebyte(s)
log.Println(b2)
// b2[0] = byte(99) unexpected fault address

b3 := []byte("test")
s3 := slicebytetostring(b3)
log.Println(s3)
}

答案虽然有,但强烈推荐不要使用这种方法来转换类型,因为如果通过stringtoslicebyte将string转为[]byte的时候,共用的时同一块内存,原先的string内存区域是只读的,一但更改将会导致整个进程down掉,而且这个错误是runtime没法恢复的。


如何取舍?


既然string就是一系列字节,而[]byte也可以表达一系列字节,那么实际运用中应当如何取舍?



  • string可以直接比较,而[]byte不可以,所以[]byte不可以当map的key值。

  • 因为无法修改string中的某个字符,需要粒度小到操作一个字符时,用[]byte。

  • string值不可为nil,所以如果你想要通过返回nil表达额外的含义,就用[]byte。

  • []byte切片这么灵活,想要用切片的特性就用[]byte。

  • 需要大量字符串处理的时候用[]byte,性能好很多。


最后脱离场景谈性能都是耍流氓,需要根据实际场景来抉择。

為什麼我用 Drone 取代 Jenkins 及 GitLab CI

appleboy 回复了问题 • 4 人关注 • 4 个回复 • 464 次浏览 • 2017-09-27 10:38 • 来自相关话题

分享下一点创业小心得以及创业项目运营情况

qixinghaitang 发表了文章 • 3 个评论 • 309 次浏览 • 2017-09-22 13:16 • 来自相关话题

之前发过一个文章介绍我的创业小项目,但是可能还是有部分同学没有看到,所以在分享运营情况之前还是重新介绍下我的创业项目:

小专栏:一个专业人士的创作知识社区,旨在为一些在某个领域有深度研究的小伙伴提供的写作平台。后续小专栏会推出新功能,我们愿... 查看全部

之前发过一个文章介绍我的创业小项目,但是可能还是有部分同学没有看到,所以在分享运营情况之前还是重新介绍下我的创业项目:


小专栏:一个专业人士的创作知识社区,旨在为一些在某个领域有深度研究的小伙伴提供的写作平台。后续小专栏会推出新功能,我们愿景就是要改变技术人购买实体技术书的传统方式。


小专栏地址:https://xiaozhuanlan.com/


小专栏从8月1号开始内测到现在一共50天:


1、截止今天通过申请的专栏有将近130个,大多数专栏作者都是来自小米、腾讯、华为、阿里巴巴、百度、亚马逊、今日头条、欢聚时代、网易的技术产品设计牛人,也有如网易UEDC设计团队、又拍云技术团队、Ucloud 技术团队开设的团队专栏。


2、截止今天一共有1717次付费订阅共33691元,付费订阅次数最高的专栏如下:



还有剩下几十个两三百块钱订阅的专栏不一一罗列......


3、通过微信、Github、微博授权登录的用户是11067人,小专栏平台公众号也获得了超过7000人的订阅,希望大家可以多多支持,微信搜索“小专栏平台”关注支持一下哈。


4、成本:小专栏是我在今年四月份辞职之后全职做的,主要成本除了注册公司、各种认证花费将近一万元之外,其余都是人力成本,比如我接近6个月没有工资,薪资损失大概就18万了,还有一些设计费用等等加起来大约在二十六七万吧。


创业心得:


1、之前总结的一句话,那就是“如果看到一个平时还蛮骄傲的人哪怕再忙都跟每一个人/每一个群很有耐心聊天说话,那这个人肯定刚刚创业”。像小专栏这样的平台需要很多优秀的作者,需要不断邀请各类大牛加入平台,经常会遭受到各种拒绝,被拒绝其实也是需要一颗强大内心承受的。


2、每天想着如何能够让小专栏这个项目坚持20-24个月;在我钱少人少如何做到最好;后续的一些产品规划;等等。


3、在50天内测期间,我对小专栏付费率还是满意的吧,但是也时常会想做小专栏我怎么赚钱啊?万一20个月过去之后,我无法做到维持盈亏的话怎么办呢?


最后对自己说一句话:


坚持吧,少年!加油吧,少年!


也欢迎大家给建议、提意见,么么哒

使用bcc分析函数耗时

lrita 发表了文章 • 1 个评论 • 146 次浏览 • 2017-09-22 13:15 • 来自相关话题

golang自带的pprof工具只能分析定性分析哪些代码时最热(最占用CPU)的代码,通常低调用次数+高耗时的方法会被高调用次数的方法淹没掉。因此我们需要一些方法能够比较准确的... 查看全部

golang自带的pprof工具只能分析定性分析哪些代码时最热(最占用CPU)的代码,通常低调用次数+高耗时的方法会被高调用次数的方法淹没掉。因此我们需要一些方法能够比较准确的获知某个函数具体消耗的多少时间。
https://lrita.github.io/2017/09/16/get-function-elapse/

看到一个用Go语言编程的众筹机器人项目

Comdex 发表了文章 • 2 个评论 • 343 次浏览 • 2017-09-20 21:39 • 来自相关话题

https://z.jd.com/project/details/89271.html

好像还不错,大家怎么看

https://z.jd.com/project/details/89271.html


好像还不错,大家怎么看

一个多功能心跳发送包——yapool

千手扉间 发表了文章 • 0 个评论 • 223 次浏览 • 2017-09-14 19:42 • 来自相关话题

自己实现了一个多功能心跳包

传送门 https://github.com/CrocdileChan/yapool

因为之... 查看全部

自己实现了一个多功能心跳包


传送门 https://github.com/CrocdileChan/yapool


因为之前的项目需要,我将一部分功能逻辑抽象出来,这个包可以供给做分布式的小伙伴用来造轮子。


基于这个包,可以轻易的实现服务发现、健康监测以及集群数据采集功能,心跳可以分为多个等级,开发者可以在里面定义自己需要传送到center(或者叫master)的讯息,center端可以对该信息进行处理。

go 语言操作数据库 CRUD

leyafo 发表了文章 • 2 个评论 • 455 次浏览 • 2017-09-07 18:38 • 来自相关话题

文章原链:http://www.leyafo.com/post/2017-09-07-go-db-crud/


go 语言标准库已经提供数据库访问通用接口,不同数据库需搭配相应连接 Driver。标准库里面 database/sql 实现基本数据类型 Scan, 基本的 Transaction 以及 sql 参数化。用这些东西去操作数据库完全够用,只是随着项目代码增长,sql string 会蔓延到项目的各个角落。若要修改数据库表结构,这些 sql string 就是噩梦一般存在。流行做法是使用 ORM(Object Relational Mapping) 去解决这个问题。ORM 封装好一些 CRUD 基本操作,可以避免大量手写 sql string.


go 编译型语言,无法做到像 Ruby 里面的 Method Missing 这样动态特性,可以为一个复合类型的 struct 随时添加一个 field. go 社区使用的 ORM 还是需要事先手动添加好 Field. 这样做需要对数据库和 struct 的成员做很多约定,写好对应的访问 tag。这些仍然无法避免修改数据库表时要一齐修改 go 代码。


我们可以仔细想想 ORM 真的是唯一的选择吗?ORM 实际上无法完美操作数据库,它做的事情无非就是这些事情:



  1. 参数化 sql string。

  2. 封装一些简单的 CRUD 操作。

  3. 序列化 sql 查询结果。


对于一些复杂的数据库查询语句,任何强大的 ORM 库,灵活的动态语言特性都无法解决。况且 ORM 也未必是好东西,它简化了操作,却间接隐藏了数据库的一些功能。如果不脱离 ORM 依赖我们无法去更好的操作数据库,去自己优化查询语句。以 go 语言目前的特性来看,这个社区永远也不可能会做出能像动态语言那样灵活的 ORM。关于 ORM 与 go 语言更详细的吐槽请见这里


如果不用 ORM 我们碰到的无非是上面提到的 3 个问题而已。把这个三个问题掰开处理,第一个问题是不存在的。参数化 sql string 这件事情我们只需要小心的处理就能防止 sql 注入这样的安全问题。剩下的就是 2 和 3 的问题,而第二个问题我们暂时也不需要解决,我们一开始就去写一些重复代码好了。而问题 3 我们可以手动自己去序列化,也可以用社区的一些库去解决这个问题。社区已经有了不错的解决方案,我用的就是 sqlx 去解决的这个问题。


当初项目开始时我考察不少 ORM 库后,果断抛弃使用 ORM。项目经过一段时间迭代后,不用 ORM 没有特别明显的不便。唯一的问题就是我需要手动为每一张表做好 table 到 go struct 之间的映射。需要写非常多重复性的 CRUD 操作代码。这些代码很难使用统一方法减少重复,只好任其膨胀。直到有一天我看到这篇文章,原来 go 语言需要写重复代码这个问题在其他问题领域也存在,而社区老司机们解决这个问题的方式是使用机器生成代码。社区大范围这么做的原因是 go 语言的语法非常简单,很容易用 go 生成 go 代码。


写 CRUD 生成器思路很简单,只需要去数据库里查询 table 的详细信息,为不同的 column 数据类型映射 go 数据类型。最后用 go 的 template 实现一些简单的 CRUD 方法。对于一般的 select 查询语句我这里没有去做实现,因为不同的表查询条件是不一样的,这种差异用函数传参解决会更好。生成器做 column 映射和拼接查询语句是极好的。


最后在项目里面把生成器生成的代码和手写的数据库相关代码分离开来,以方便数据库表结构变动后可以让生成器重新生成代码。这里是我写的这个简单的生成器,参照了一部分 xo 项目的代码,由于我只支持 Postgresql, 没有去支持 join 和 has_many 这样的操作,代码相对他们要简单很多。


事情到这里并没有完,我们还需要序列化后的查询结果做一些反序列化的工作,go 语言的 struct tag 对这方面有很好的支持。可是我们用机器生成的代码是无法控制外界需要的各种反序列化的字段。下面以序列化 json 为例,我们并不想把数据库的 ID 字段暴露给外界。如果用生成器去控制这些配置,生成器需要做更多的配置,数据库表字段需要更多约定,这无疑会增加生成器的难度。我们必须要为每一张表手动单独做一个 Export 的结构体与方法,以满足各种其他序列化的要求。


type UserExport struct {
Name string `json:"name"`
Email string `json:"email"`
UpdatedAt string `json:"updated_at"`
}

func (u User) Export() UserExport {
return UserExport{
Name: u.Name,
Email: u.Email,
UpdatedAt: u.UpdatedAt,
}
}

func (u User) MarshalJSON() ([]byte, error) {
return json.Marshal(u.Export())
}

如上所示,我们可以为 User 表配置不同 field 和 tag。可以单独为不同的序列化数据类型写一个 Marshal 方法,这些都是手动可以控制。为了灵活我们还可以把 Export 这个结构体直接嵌入到其他结构体中,不用担心 Marshal 会继承式覆盖后面 Marshal 方法。

Jetbrains 家族利器之 Gogland 简明教程

bingohuang 发表了文章 • 8 个评论 • 872 次浏览 • 2017-09-05 10:03 • 来自相关话题

gogland.png

喜欢用 IDE 做开发的同... 查看全部

gogland.png


喜欢用 IDE 做开发的同学必定不能错过 Jetbrains 家族的 IDE,款款精品,可谓都是 IDE 中的神兵利器。


这里介绍该家族 又一款新的 IDE —— 用于开发 Go 语言 的 Gogland,喜欢折腾 Go 语言 IDE 的同学一定要试试看。


一、下载 Gogland


该步骤非常简单,访问 Gogland 的下载页面,下载相应平台的安装包即可,三大平台(Mac、Linux、Windows)都有支持。


注:当前 Gogland 还是预发布版,想了解更多 Gogland 信息,请参考附录二


二、安装 Go 环境


接下来需要安装相应的 Go 环境,才能在 Gogland 中开发 Go 程序。


安装方法多样,首先可参考官网安装指南,但如果你有 Go 多版本的需求(比如新老版本共存),你想简化 Go 配置过程(省去GOPATH、GOROOT等的配置),你还希望它支持跨平台(支持Mac和Linux),那么我特别推荐这款 Go 环境安装工具:GVM —— 详情可参考我的写的这篇文章《Go 语言多版本安装及管理利器 - GVM》


二、设置工作空间


用过 Eclipse 的同学必不陌生 Workspace (工作空间),Go 也有自己的工作空间,建议将 Go 的代码放在一个单独的空间,类似布局如下:


- workspace
- bin
- pkg
- src
- github.com
- user_name
- project1
- project2

然后将该工作空间(workspace 所在目录)设置到 GOPATH 当中。GOPATH 可用于 Go 导入、安装、构建和更新,还会被 Gogland 自动识别(见第四节)。


注:如果你采用上述说的 GVM 的安装方式,将自动创建一个 Workspace,并配置好 GOPATH 等相关环境变量,这也是 GVM 方便的地方。


三、设置 Gogland 的 GOROOT


在 Gogland 中,需要配置当前项目的 GOROOT,用来编译运行 Go 代码。配置起来也非常方便,打开 Settings → Go → GOROOT 设置即可:


gogland-goroot.png


如果你本地安装了多个版本的 Go,也可以在右侧下拉选择相应的版本,这依赖于你本地有多个版本的 Go 环境了。


四、设置 Gogland 的 GOPATH


Gogland 中的 GOPATH 设置功能非常实用和强大,你既可以配置多个全局的 GOPATH (IDE 会自动识别环境变量中的 GOPATH,可不勾选),也可以配置多个项目级别的 GOPATH,甚至还可以配置多个模块级别的 GOPATH。打开 Settings → Go → GOPATH 设置如下:
gogland-gopath.png


五、建立新的 Go 项目


这个很简单,在主菜单选择 File → New → Project, 继而弹出 New Project 设置向导:
gogland-new-project.png


此处就需要选择你在上面配置好的 GOROOT,新建的项目会自动关联全局 GOPATH,你还可以参照第四节说是设置你项目的 GOPATH


五、导入已有 Go 项目


如果你本地已有 Go 项目代码,只需在主菜单选择 File → Open,打开你的项目目录即可。


最新版的 Gogland有一个非常体贴的小功能,会自动匹配你当前设置好的全局 GOROOT。当然,你也可以在设置中更换。


接下来会开始建立索引(index),第一次建立的时候可能会比较慢,CPU消耗比较大,耗时长短依赖于你工作空间的代码量,但后续用起来就非常快捷了,索引的建立也是增量的。


注: 但也有一个问题,每次升级 gogland 或者安装更新插件,也会重新建立索引,这个确实不友好,希望 Jetbrains 后续能改善这点。


七、运行/调试/测试程序


当你有了一个 Go 项目工程,二话不说,先跑跑看(前提是你要有一个可执行入口,在 main package 下的 main 函数)。


为了在 Gogland 运行一个 Go 程序,你需要用到 Run Configuration。使用方法如下:



  • 在主菜单栏或工具栏打开:Run → Edit Configurations

  • 点击 Edit Configurations,打开 Run/Debug Configuration 对话框

  • 点击 + 号按钮,选择你需要的运行配置,Go 用到的配置类型如下(按使用频率解释):
    gogland-run-config.png

    1. Go Application:相当于执行 go build 和运行可执行文件命令,该配置会生成可执行文件,也可执行debug

    2. Go Single File:相当于 go run 命令,该配置不会生成可执行文件,不能执行 debug

    3. Go Test:用于运行测试代码,相当于 go test,有三种测试框架可供选择:gotest,gocheck 和 gobench

    4. Go Remote:提供了 Go 的远程调试支持,你只需要设置要远程连接的 Host 和 Port,并且保证你要调试的程序是通过 Delve 启动的

    5. Go App Engine:允许你将程序部署到 Google AppEngine,前提是你有使用 Google 云,并且你的程序模块加载了 Go AppEngine SDK



以上就是 Go 工程在运行/调试/测试过程中会用到的配置类型,特别是前三项,最为常用。


如果你要运行程序,推荐使用1和2。而 Gogland 智能的地方在于,你可以通过鼠标右击这样快捷的方式来运行和配置,如下,在有 main 函数的地方右击即可:
gogland-run.png


如果你要调试程序,本地调试可用1,远程调试请使用4。


如果你要测试程序,请使用第3种方式。


同时,在测试程序的基础上,你还可以执行调试和代码覆盖率统计,功能十分强大!


gogland-run-coverage.png


总的来说,Gogland 继承了 Jetbrains 家族的基因,完全可以作为 Go 语言编程的神兵利器,还不赶紧来试试看


注:提供两个附录,让大家更全面的了解 Gogland。


附录一:常用辅助快捷方式:以 Mac 为例



  1. 查看提示帮助:默认快捷键是 ⌥⏎。最常用的快捷键之一,从 Eclipse 转过来的同学对该快捷键肯定不陌生,很多地方都可以用上该快捷键,特别是有错误的时候,有时还会有意想不到的好效果哦。

  2. 查看声明:按住 Cmd 健(Windows 下是 Ctrl键),鼠标左键点击相关标识。最常用的快捷键之一,跳转声明、查看源码必不可少。

  3. 查看函数参数:⌘P。直接在当前函数下查看,当然你也可以用上面的查看声明方式跳转过去查看。

  4. 代码重构:在你需要重构的地方,右击选择 Refactor 即可。

  5. 查看使用率:在你需要查看使用率的地方,右击选择 Find Usages 即可。

  6. 还有一个非常赞的功能,就是设置 live template,使用方式就是:缩写 + Tab 键。配置方式在 Settings → Editor → Live Templates 中,Go 也内置了不少快捷模板哦。


以上快捷键你都可以在 Settings → Editor 中查找或重置,更多 Intellij IDE 的使用小技巧可以查看:Discover IntelliJ IDEA


附录二:常见问题


1、Gogland 代表什么?


Gogland 是一个代号,并不是最终的产品名称。灵感来自于芬兰湾的一座小岛,离芬兰湾另一座小岛 Kotlin(也是 Jetbrains 推出的一门语言) 不远。


2、Gogland 是否会开源?


当前没计划开源。


3、Gogland 是否免费?


当前预览版免费,正式版还是要收费的。


4、Gogland 中的 Go 插件是否能用于其他基于 IntelliJ 的 IDE?


可以的,这个 Go 官方插件 和 Gogland 所带的 Go 相关功能是一致的,可用于 IntellIJ IDEA 极限版和其它付费 IDE,不过还不能用于社区版。


5、Gogland 绑定了哪些其他 IntelliJ 插件?


Git, Terminal, Textmate, JavaScript, CSS, HTML, Database Tools 和 Coverage 等。


6、Gogland 什么时候正式发布?


还没有确切时间,预计每个月会发布一个 EAP build 版本。欢迎多多给我们反馈


7、我在哪里可以提交 issues 和功能需求?


请使用 Gogland 的 issue 跟踪:https://youtrack.jetbrains.com/issues/GO

Node.js 之父 Ryan 推薦大家使用 Go 語言,而不是 Node.js

appleboy 发表了文章 • 4 个评论 • 1076 次浏览 • 2017-09-05 09:34 • 来自相关话题

『Node.js 之父 Ryan 目前在 Google Brain 一手建立 Node.js 世界,但是在訪談中,竟然推薦大家使用 Go 語言,而不要使用 Node.js 當作後端 (假如您想要建構一個龐大的系統)。內文中提到 Node.js Callb... 查看全部

『Node.js 之父 Ryan 目前在 Google Brain 一手建立 Node.js 世界,但是在訪談中,竟然推薦大家使用 Go 語言,而不要使用 Node.js 當作後端 (假如您想要建構一個龐大的系統)。內文中提到 Node.js Callback 的缺陷在 Node.js 出現了 async 了有效了解決大量使用 Callback。Ryan 也非常驚訝地說,他沒想到在 Node.js Client 端竟然如此熱門。要建立小量的開發系統,他非常推薦使用 Node.js,但是如果您要建立龐大的分散式 DNS 系統,我覺得不會推薦你使用 Node。』


說到 Client Side 工具,在 Node.js 世界的確在 Web 領域佔有一席之地,就像我現在在寫 Go,也是大量使用 Node.js 工具 (像是 Webpack, Gulp, Imagemin 等圖片壓縮工具) 來幫助建置 Web 網站。


詳細原文可以參考: https://www.mappingthejourney.com/single-post/2017/08/31/episode-8-interview-with-ryan-dahl-creator-of-nodejs/

这个就是我做了三四个月的产品啦,欢迎提意见哦

qixinghaitang 发表了文章 • 2 个评论 • 449 次浏览 • 2017-09-01 12:48 • 来自相关话题

小专栏 :https://xiaozhuanlan.com/

主打付费专栏,如果你非常喜欢写作,且拥有重多粉丝读者,欢迎开开设付费专栏哟。如果你觉得不好意思收费... 查看全部

小专栏 :https://xiaozhuanlan.com/


主打付费专栏,如果你非常喜欢写作,且拥有重多粉丝读者,欢迎开开设付费专栏哟。如果你觉得不好意思收费,但是感觉自己写的东西很棒,那么你也可以来开设免费专栏。


但是小专栏最看重的还是您专业的分享,无论关于技术、产品或者运营方面。


推荐一些目前比较不错的专栏


iOS


1、iOS 成长之路 目前已经收获了超过5500元啦
面向读者:笼统的说就是面向初中级 iOS 开发者。你可能是一个刚刚入门能够熟练使用 UITableView 的新手,也可能是做了一两年对于 UIKit 和 Foudation 的 API 都已经很熟悉了,想要提高自己的开发者。或者是能实现工作中的业务需求,但是对如何提升自己还有些迷茫的开发者们。


2、iOS成长之路3期·WWDC17内参也已经有超过2800元的订阅了
本书的内容主要介绍 WWDC 17 上提到的和 iOS 开发相关的开发技术。


Android:


0、解读Android系统架构



  • 从源码角度,带领大家一睹Android系统架构;

  • 从App到framework,native,乃至Linux内核;

  • 从上至下地深度解读Android架构设计。


在过去的一年,对于Android从底层一路到上层有不少自己的理解和沉淀,把知识进行归档整理与再学习,从而加深对Android架构的理解。通过前面对系统启动的介绍,相信大家对Android系统有了一个整体观,接下来需要抓核心、理思路,争取各个击破。


关于作者:Gityuan,Android系统工程师,曾就职于IBM、Lenovo,目前就职于小米MIUI系统组


文章总数:接近110篇深度技术解析,出版成书大概是两本500页左右的书籍厚度。


专栏定位: 基于Android 6.0的源码,专注于分享Android系统原理、架构分析的原创文章。


建议阅读群体: 适合于正从事或者有兴趣研究Android系统的工程师或者爱好者,也适合Android App高级工程师; 对于尚未入门或者刚入门的App程序员阅读可能会困难些,可能不是很适合。


1、《Android 开源库的源码导读》
包含 Retrofit 、 Okio、OkHttp、RxJava 原理剖析。作者 Piasy 清华大学计算机系,目前就职于 YOLO,带领安卓团队。同时作者还有免费专栏《Android 架构系列》《Piasy 的 WebRTC 专栏》


2、《轻松在 VPS 搭建 Shadowsocks 科学上网》 作者键盘男,悦跑圈Android 开发工程师。本文收录于《键盘男的 Android 开发心得》


3、《Android 插件化原理解析》 作者田维术,前360,现蚂蚁金服Android工程师。以下为专栏内容。


4、《安卓自定义 View 教程》作者GcsSloop, 一名生活在2.5次元的魔法师,我一直在致力于研究基础魔法,并且始终坚信利用这些基础魔法,可以创造出华丽而又强大的高级魔法。以下为专栏内容简介。


5、《Kotlin Primer》 Kotlin 开发入门指南,专栏还将不断更新下去。作者张涛,沪江网 Android 开发工程师,知名博主。


6、《Android 开发实战》 开发过程中的一些实战经验,饱含各种进阶的技巧和知识,作者 D_clock爱吃葱花 ,欢聚时代Android 开发工程师,知名博主。


产品:


WinsonL的产品技能树
魅族产品经理的专栏,用实例干货分享产品技能树,完全可操作,不刻意抽象深奥化。


设计:


Google对话式交互规范指南,作者资深UX设计师、猫奴,曾就职于淘宝UED、腾讯ISUX设计中心、猎豹UX设计中心。
语音交互(voice interaction)和人工智能(AI)是目前互联网行业非常热门的话题,对于体验设计师来说,这是一个比较新的领域,行业与设计标准还未完全成型。Google作为行业先驱,针对对话UI体验提供了一系列设计原则、流程与方法的具体建议和归纳,本专栏文字翻译自Google官方对话式交互规范指南,为相关领域的开发者和设计师提供了比较基础的指导和框架。


欢迎大家体验和提建议哦