LeetCode刷题Day2:两数相加

LeetCodezkbhj 发表了文章 • 0 个评论 • 75 次浏览 • 2020-09-22 20:57 • 来自相关话题

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 
输出:7 -> 0 -> 8
原因:342 + 465 = 807LeetCode

 首先发一下我的思路已经给出的最初答案(大部分情况是正确的,但是超出数字范围就会和预期结果不一致),总之先把分析思路分享出来。


思路一:常规思路

分别循环两个链表,因为高位是个位,所以不断乘以10的n次方,n代表循环次数,从0开始,直到循环结束,就得到了两个无符号整数。所以,这就要求对输入数字有范围限制的要求,否则数字太大,超出整数的最大范围,得到的结果会因为发生溢出而不符合预期。

然后将两个整数进行加法运算,得到最终结果对应的int数字。

然后再将这个整数转化成字符串,循环字符串,得到字符对应的ASCII码点,然后减去48即可“间接“得到对应的数字。并按序生成链表。
 
func myPow(a,n int) int {
result := int(1)
for i:= n; i >0 ; i >>= 1 {
if i&1 != 0 {
result *=a
}
a *=a
}
return result
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var a,b,c,i,j int
p1 := l1
for p1!= nil {
a = a + p1.Val * myPow(10,i)
i++
p1 = p1.Next
}
p2 := l2
for p2!= nil {
b = b + p2.Val * myPow(10,j)
j++
p2 = p2.Next
}
c = a + b

str := strconv.Itoa(c)
headNode := new(ListNode)
current := headNode
current.Next = nil
for _,one := range str {
preNode := current
current.Val = int(one-48)
current = new(ListNode)
current.Next = preNode

}

return current.Next
}
思路一:高级思路(学习)
对应位置的数字相加,跟10取模,即可得到该位置上十进制数相加之后的数字,然后和10进行整除,如果两个数相加小于10,则整除之后是0,否则是1,即要进位的1,所以直到两个链表都循环完,或者最后没有进位时,停止循环,最终返回。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
headList := new(ListNode)
head := headList
num := 0

for (l1 != nil || l2 != nil || num > 0) {
headList.Next = new(ListNode)
headList = headList.Next
if l1 != nil {
num = num + l1.Val
l1 = l1.Next
}
if l2 != nil {
num = num + l2.Val
l2 = l2.Next
}
headList.Val = (num) % 10
num = num / 10
}

return head.Next
}
  查看全部


两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 
输出:7 -> 0 -> 8
原因:342 + 465 = 807LeetCode


 首先发一下我的思路已经给出的最初答案(大部分情况是正确的,但是超出数字范围就会和预期结果不一致),总之先把分析思路分享出来。


思路一:常规思路

分别循环两个链表,因为高位是个位,所以不断乘以10的n次方,n代表循环次数,从0开始,直到循环结束,就得到了两个无符号整数。所以,这就要求对输入数字有范围限制的要求,否则数字太大,超出整数的最大范围,得到的结果会因为发生溢出而不符合预期。

然后将两个整数进行加法运算,得到最终结果对应的int数字。

然后再将这个整数转化成字符串,循环字符串,得到字符对应的ASCII码点,然后减去48即可“间接“得到对应的数字。并按序生成链表。
 
func myPow(a,n int) int {
result := int(1)
for i:= n; i >0 ; i >>= 1 {
if i&1 != 0 {
result *=a
}
a *=a
}
return result
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var a,b,c,i,j int
p1 := l1
for p1!= nil {
a = a + p1.Val * myPow(10,i)
i++
p1 = p1.Next
}
p2 := l2
for p2!= nil {
b = b + p2.Val * myPow(10,j)
j++
p2 = p2.Next
}
c = a + b

str := strconv.Itoa(c)
headNode := new(ListNode)
current := headNode
current.Next = nil
for _,one := range str {
preNode := current
current.Val = int(one-48)
current = new(ListNode)
current.Next = preNode

}

return current.Next
}

思路一:高级思路(学习)
对应位置的数字相加,跟10取模,即可得到该位置上十进制数相加之后的数字,然后和10进行整除,如果两个数相加小于10,则整除之后是0,否则是1,即要进位的1,所以直到两个链表都循环完,或者最后没有进位时,停止循环,最终返回。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
headList := new(ListNode)
head := headList
num := 0

for (l1 != nil || l2 != nil || num > 0) {
headList.Next = new(ListNode)
headList = headList.Next
if l1 != nil {
num = num + l1.Val
l1 = l1.Next
}
if l2 != nil {
num = num + l2.Val
l2 = l2.Next
}
headList.Val = (num) % 10
num = num / 10
}

return head.Next
}

 

LeetCode刷题Day1:两数之和

LeetCodezkbhj 发表了文章 • 0 个评论 • 64 次浏览 • 2020-09-22 20:55 • 来自相关话题

从今天开始,把LeetCode刷题作为每天日常计划的一项。尽早做准备,同时也每天对算法和相关的技能知识通过刷题的形式进行潜移默化的提升和加深理解。其实身边已经有很多程序猿朋友都在LeetCode刷题了,再不参与进来,都要出圈儿了呀。

今天是Day1,从第一道题目开始:
 

两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 

示例: 

给定 nums = [2, 7, 11, 15], target = 9 

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]LeetCode
 

 
思路一:暴力遍历

也是最简单最原始的未经优化的方案思路。

首先明确题目要求,可以假设每种输入只会对应一个答案,即一定会有且只有一对符合要求的数据。

所以得到数组的长度,然后从第一个开始进行循环,将目标值target减去当前被循环的值,得到与之可以配对的值,然后在数组中进行寻找,如果找到,就返回2个符合要求的值的索引,否则继续下一次寻找,直到找到。

最外层循环的条件中 x&y异或之后如果为1,说明已经找到对应的结果,就不再循环。时间复杂度是O(n²),空间复杂度是O(1)。
func twoSum(nums []int, target int) []int {
len := len(nums)
var x,y int

for i:=0; i < len && x|y == 0; i++ {
findNum := target - nums[i]
for j:=0; j < len; j++ {
if findNum == nums[j] {
x = i;
y = j;
}
}

}

return []int{x,y}
}
思路二:进一步提升效率,可以利用哈希表
从第一个思路中,可以看到其实在判断一个值在一个“表”中是否存在的时候,我们采用了遍历的方式,这样的话时间复杂度就是O(n),但是大家肯定都知道,哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以,这样思路就很清晰了,我们需要先把传过来的数组生成对应的哈希结构,也就是Go里面的map字典,这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key,index作为map的value。代码实现如下。
 
func twoSum(nums []int, target int) []int {
var hashMap map[int]int
len := len(nums)
var x,y,found int

//初始化字典
hashMap = make(map[int]int)
for i:=0; i < len; i++ {
hashMap[nums[i]] = i
}

for j:=0; j < len && found == 0; j++ {
findNum := target - nums[j]
v, ok := hashMap[findNum]
if ok && v != j {
found = 1
x = j
y = v
}

}

return []int{x,y}
}
今天这道题的难度级别是简单,但是带我回顾了Go语言的数组、map的相关知识和用法,以及哈希表这一知识点。 查看全部
从今天开始,把LeetCode刷题作为每天日常计划的一项。尽早做准备,同时也每天对算法和相关的技能知识通过刷题的形式进行潜移默化的提升和加深理解。其实身边已经有很多程序猿朋友都在LeetCode刷题了,再不参与进来,都要出圈儿了呀。

今天是Day1,从第一道题目开始:
 


两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 

示例: 

给定 nums = [2, 7, 11, 15], target = 9 

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]LeetCode
 


 
思路一:暴力遍历

也是最简单最原始的未经优化的方案思路。

首先明确题目要求,可以假设每种输入只会对应一个答案,即一定会有且只有一对符合要求的数据。

所以得到数组的长度,然后从第一个开始进行循环,将目标值target减去当前被循环的值,得到与之可以配对的值,然后在数组中进行寻找,如果找到,就返回2个符合要求的值的索引,否则继续下一次寻找,直到找到。

最外层循环的条件中 x&y异或之后如果为1,说明已经找到对应的结果,就不再循环。时间复杂度是O(n²),空间复杂度是O(1)。

func twoSum(nums []int, target int) []int {
len := len(nums)
var x,y int

for i:=0; i < len && x|y == 0; i++ {
findNum := target - nums[i]
for j:=0; j < len; j++ {
if findNum == nums[j] {
x = i;
y = j;
}
}

}

return []int{x,y}
}

思路二:进一步提升效率,可以利用哈希表
从第一个思路中,可以看到其实在判断一个值在一个“表”中是否存在的时候,我们采用了遍历的方式,这样的话时间复杂度就是O(n),但是大家肯定都知道,哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以,这样思路就很清晰了,我们需要先把传过来的数组生成对应的哈希结构,也就是Go里面的map字典,这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key,index作为map的value。代码实现如下。
 

func twoSum(nums []int, target int) []int {
var hashMap map[int]int
len := len(nums)
var x,y,found int

//初始化字典
hashMap = make(map[int]int)
for i:=0; i < len; i++ {
hashMap[nums[i]] = i
}

for j:=0; j < len && found == 0; j++ {
findNum := target - nums[j]
v, ok := hashMap[findNum]
if ok && v != j {
found = 1
x = j
y = v
}

}

return []int{x,y}
}

今天这道题的难度级别是简单,但是带我回顾了Go语言的数组、map的相关知识和用法,以及哈希表这一知识点。

使用了Go mod管理的项目里如何添加新的第三方包?

回复

GoLangzkbhj 回复了问题 • 1 人关注 • 1 个回复 • 192 次浏览 • 2020-09-17 11:32 • 来自相关话题

如何快速提升Go程序性能?

GoLangzkbhj 发表了文章 • 0 个评论 • 97 次浏览 • 2020-09-15 18:39 • 来自相关话题

这篇文章中列出了一些不需要太多精力就能显著提高性能的技巧,并不包含那些需要太多精力或需要大幅度修改程序结构的技巧。
 
开始优化之前
 
开始优化之前,首先应该花些时间找出一个合适的基准线,以便稍后比较。如果没有基准,那就等于摸着石头过河,根本不知道自己的优化有没有效果。首先要编写性能测试程序,然后生成能用于pprof的profile文件。最好可以编写Go的性能测试脚本(https://dave.cheney.net/2013/0 ... in-go),这样可以很容易地使用pprof,还可以评测内存分配情况。还可以使用benchcmp,这个工具可以帮助比较两次性能测试之间的性能差异。

如果代码很难做性能测试,那就从你能测量时间的部分开始。可以利用runtime/pprof手工测量代码。

现在开始吧!
 
使用sync.Pool重用之前分配过的对象
 
sync.Pool实现了一个空闲列表(free-list)。这样可以重新使用之前分配过的对象。这样做可以将对象分配的代价平摊到多次使用上,减少垃圾回收器的工作。API非常简单:只需实现一个函数,用来分配新的对象即可。它会返回指针类型。
 
var bufpool = sync.Pool{
New: func() interface{} {
buf := make([]byte, 512)
return &buf
}}之后,可以用Get()从池中获取对象,用完之后用Put()将对象放回。

不过要注意一些陷阱。在Go 1.13之前,每次发生垃圾回收时该池都会被清空。对于需要分配大量对象的程序来说,这可能会造成性能的影响。在1.13版本中似乎GC后能保留更多对象了(https://go-review.googlesource.com/c/go/+/162919/)。

你可能需要在将对象放回池中之前将其结构的字段清空。

如果不这样做,就可能从池中获得一个“脏”的对象,它包含之前使用过的数据。这可能会造成严重的安全问题!
 
安全的做法就是明确清空内存:// reset resets all fields of the AuthenticationResponse before pooling it.
func (a* AuthenticationResponse) reset() {
a.Token = ""
a.UserID = ""
}

rsp := authPool.Get().(*AuthenticationResponse)
defer func() {
rsp.reset()
authPool.Put(rsp)
}()
在大map中避免使用包含指针的结构作为map的键
 
关于Go中大型堆的性能问题已经有很多人讨论过了。在垃圾回收过程中,运行时会扫描包含指针的对象并遍历其指针。如果你有非常大的map[string]int,那么垃圾回收器就不得不在每次垃圾回收过程中检查map中的每个字符串,因为字符串包含指针。

这个例子中我们向一个map[string]int中写入了一千万个元素,然后测量垃圾回收的时间。map是在包的作用域中分配的,以保证它被分配到堆上。
import (
"fmt"
"runtime"
"strconv"
"time"
)

const (
numElements = 10000000
)

var foo = map[string]int{}

func timeGC() {
t := time.Now()
runtime.GC()
fmt.Printf("gc took: %s\n", time.Since(t))
}

func main() {
for i := 0; i < numElements; i++ {
foo[strconv.Itoa(i)] = i
}

for {
timeGC()
time.Sleep(1 * time.Second)
}
}运行后可以得到以下结果:gc took: 98.726321ms
gc took: 105.524633ms
gc took: 102.829451ms
gc took: 102.71908ms
gc took: 103.084104ms
gc took: 104.821989ms对于计算机来说这花得时间太多了!

怎样可以改进呢?最好是能尽量去掉指针,这样能减少垃圾回收器需要遍历的指针数量。由于字符串包含指针,因此我们可以用map[int]int来实现:
 
import (
"fmt"
"runtime"
"time"
)

const (
numElements = 10000000
)

var foo = map[int]int{}

func timeGC() {
t := time.Now()
runtime.GC()
fmt.Printf("gc took: %s\n", time.Since(t))
}

func main() {
for i := 0; i < numElements; i++ {
foo[i] = i
}

for {
timeGC()
time.Sleep(1 * time.Second)
}
}重新运行程序,结果如下:
 
gc took: 3.608993ms
gc took: 3.926913ms
gc took: 3.955706ms
gc took: 4.063795ms
gc took: 3.91519ms
gc took: 3.75226ms好多了。垃圾回收的时间减少了97%。在生产环境下,字符串需要进行hash之后再插入到map中。
 
生成marshalling代码以避免运行时反射
 
将数据结构marshalh或unmarshal成JSON等各种序列化格式是个很常见的操作,特别是在构建微服务的时候。实际上,大部分微服务做的唯一工作就是序列化。像json.Marshal和json.Unmarshal需要依赖运行时反射才能将结构体的字段序列化成字节,反之亦然。这个操作很慢,反射的性能完全无法与显式的代码相比。

但我们不必这么做。marshalling JSON的原理大致如下:
package json

// Marshal take an object and returns its representation in JSON.
func Marshal(obj interface{}) ([]byte, error) {
// Check if this object knows how to marshal itself to JSON
// by satisfying the Marshaller interface.
if m, is := obj.(json.Marshaller); is {
return m.MarshalJSON()
}

// It doesn't know how to marshal itself. Do default reflection based marshallling.
return marshal(obj)
}如果我们知道怎样将对象marshal成JSON,就应该避免运行时反射。但我们不想手工marshal所有代码,怎么办呢?可以让计算机替我们写程序!像easyjson等代码生成器会检查结构体,然后生成高度优化且与json.Marshaller等接口完全兼容的代码。

下载这个包,然后在包含结构体的$file.go上运行下面的命令:
easyjson -all $file.go$file.go
这个命令会生成$file_easyjson.go。由于easyjson为我们实现了json.Marshaller接口,因此序列化时不会调用默认的反射,而是会使用生成的函数。祝贺你!你已经将JSON marshalling的代码的速度提高了三倍。还有许多其他技巧可以进一步提升性能。
 
使用strings.Builder来构建字符串
 
Go语言的字符串是不可修改的,可以认为它们是只读的字节切片。这就是说,每次创建字符串都要分配新的内存,可能还会给垃圾回收器造成更多工作。

Go 1.10引入了strings.Builder作为高效率构建字符串的方式。它内部会将字符串写入到字节缓冲区。只有在builder上调用String()时才会真正生成字符串。它依赖一些unsafe的技巧将底层的字节作为字符串返回,而不实际进行内存非配。这篇文章(https://syslog.ravelin.com/byt ... ca7ff)介绍了更多其工作原理。pkg: github.com/sjwhitworth/perfblog/strbuild
BenchmarkStringBuildNaive-8 5000000 255 ns/op 216 B/op 8 allocs/op
BenchmarkStringBuildBuilder-8 20000000 54.9 ns/op 64 B/op 1 allocs/op可见,strings.Builder要快4.7倍,它的内存分配次只有前者的1/8,内存使用只有前者的1/4。

所以,在性能重要的时候应该使用strings.Builder。一般来说,除非是非常不重要的情况,否则我建议永远使用strings.Builder来构建字符串。
 
使用strconv代替fmt

fmt是Go中最著名的包之一。估计你从第一个Go程序——输出“hello, world”——的时候就开始用它了。但是,如果需要将整数和浮点数转换成字符串,它就不如更底层的strconv有效率了。strconv只需要在API中进行很小改动,就能带来不错的性能提升。

大多数情况下fmt会接受一个interface{}作为参数。这样做有两个弊端:

失去了类型安全。对于我来说这是个很大的问题。

会增加内存分配次数。将非指针类型作为interface{}传递通常会导致堆分配的问题。进一步的内容可以阅读这篇文章(https://www.darkcoding.net/sof ... face/)。
BenchmarkStrconv-8 30000000 39.5 ns/op 32 B/op 1 allocs/op
BenchmarkFmt-8 10000000 143 ns/op 72 B/op 3 allocs/op可以看到,strconv版本要快3.5倍,内存分配次数是1/3,内存分配量是1/2。

在make中指定分配的容量来避免重新分配

在讨论性能改善之前,我们先来迅速看一下切片。切片是Go语言中一个非常有用的概念。它提供了可改变大小的数组,还可以用不同的方式表示同一片底层内存区域,而不需要重新进行内存分配。slice的内部结构由三个元素组成:

data:切片中指向底层数据的指针
len:切片中的当前元素数目
cap:在不重新分配内存的前提下,切片能够增长到的元素数目

我经常看到类似于下面的代码,尽管在切片容量可以预先得知的情况下依然生成一个容量为零的切片:var userIDs []string
for _, bar := range rsp.Users {
userIDs = append(userIDs, bar.ID)
}这段代码中,切片的初始长度和容量都为零。在收到响应后,我们将用户添加到切片。这样做就会达到切片的容量上限,从而导致底层分配两倍容量的新数组,然后将旧切片中的数据拷贝过来。如果有8个用户,就会造成5次内存分配。

更有效的方式是这样:
userIDs := make([]string, 0, len(rsp.Users)
for _, bar := range rsp.Users {
userIDs = append(userIDs, bar.ID)
}使用make显式声明切片的容量。接下来可以向切片添加元素,而不会触发内存重新分配和拷贝。
 
这条建议也适用于map:适用make(map[string]string, len(foo))可以分配足够的底层内存以避免内存重新分配。
 
使用可以接受字节切片的方法
 
在使用包时,寻找那些接受字节切片作为参数的方法,这些方法通常给你更多控制内存分配的自由。

一个很好的例子就是time.Format和time.AppendFormat。time.Format返回字符串。内部会分配一个新的字节切片,然后在其上调用time.AppendFormat。而time.AppendFormat接受一个字节缓冲区,将格式化后的时间写入缓冲区,然后返回扩展后的字节切片。标准库中这种做法非常常见,如strconv.AppendFloat或bytes.NewBuffer。

为什么这样能提高性能?因为你可以传递从sync.Poolh获得的字节切片,而不需要每次都分配新的缓冲区。或者可以初始化一个足够大的缓冲区,来减少切片拷贝。
 
这些建议只是某些具体情况下的建议,而不是真理。一定要自己测量性能。

要知道何时该停止优化。提高系统性能会让工程师感觉非常满足:问题本身很有趣,也有立竿见影的效果。但是,提高性能带来的效果非常依赖于具体情况。如果服务的响应时间只有10毫秒,而网络访问需要90毫秒,那么将10毫秒优化到5毫秒就完全不值得,因为你依然需要95毫秒。就算你将响应时间优化到1毫秒,最后结果还是91毫秒。你应该去做其他更有价值的事情。
 
原文:
https://stephen.sh/posts/quick-go-performance-improvements
译文:
https://blog.csdn.net/csdnnews/article/details/93987866
  查看全部
这篇文章中列出了一些不需要太多精力就能显著提高性能的技巧,并不包含那些需要太多精力或需要大幅度修改程序结构的技巧。
 
开始优化之前
 
开始优化之前,首先应该花些时间找出一个合适的基准线,以便稍后比较。如果没有基准,那就等于摸着石头过河,根本不知道自己的优化有没有效果。首先要编写性能测试程序,然后生成能用于pprof的profile文件。最好可以编写Go的性能测试脚本(https://dave.cheney.net/2013/0 ... in-go),这样可以很容易地使用pprof,还可以评测内存分配情况。还可以使用benchcmp,这个工具可以帮助比较两次性能测试之间的性能差异。

如果代码很难做性能测试,那就从你能测量时间的部分开始。可以利用runtime/pprof手工测量代码。

现在开始吧!
 
使用sync.Pool重用之前分配过的对象
 
sync.Pool实现了一个空闲列表(free-list)。这样可以重新使用之前分配过的对象。这样做可以将对象分配的代价平摊到多次使用上,减少垃圾回收器的工作。API非常简单:只需实现一个函数,用来分配新的对象即可。它会返回指针类型。
 
var bufpool = sync.Pool{
New: func() interface{} {
buf := make([]byte, 512)
return &buf
}}
之后,可以用Get()从池中获取对象,用完之后用Put()将对象放回。

不过要注意一些陷阱。在Go 1.13之前,每次发生垃圾回收时该池都会被清空。对于需要分配大量对象的程序来说,这可能会造成性能的影响。在1.13版本中似乎GC后能保留更多对象了(https://go-review.googlesource.com/c/go/+/162919/)。

你可能需要在将对象放回池中之前将其结构的字段清空。

如果不这样做,就可能从池中获得一个“脏”的对象,它包含之前使用过的数据。这可能会造成严重的安全问题!
 
安全的做法就是明确清空内存:
// reset resets all fields of the AuthenticationResponse before pooling it.
func (a* AuthenticationResponse) reset() {
a.Token = ""
a.UserID = ""
}

rsp := authPool.Get().(*AuthenticationResponse)
defer func() {
rsp.reset()
authPool.Put(rsp)
}()

在大map中避免使用包含指针的结构作为map的键
 
关于Go中大型堆的性能问题已经有很多人讨论过了。在垃圾回收过程中,运行时会扫描包含指针的对象并遍历其指针。如果你有非常大的map[string]int,那么垃圾回收器就不得不在每次垃圾回收过程中检查map中的每个字符串,因为字符串包含指针。

这个例子中我们向一个map[string]int中写入了一千万个元素,然后测量垃圾回收的时间。map是在包的作用域中分配的,以保证它被分配到堆上。
import (
"fmt"
"runtime"
"strconv"
"time"
)

const (
numElements = 10000000
)

var foo = map[string]int{}

func timeGC() {
t := time.Now()
runtime.GC()
fmt.Printf("gc took: %s\n", time.Since(t))
}

func main() {
for i := 0; i < numElements; i++ {
foo[strconv.Itoa(i)] = i
}

for {
timeGC()
time.Sleep(1 * time.Second)
}
}
运行后可以得到以下结果:
gc took: 98.726321ms
gc took: 105.524633ms
gc took: 102.829451ms
gc took: 102.71908ms
gc took: 103.084104ms
gc took: 104.821989ms
对于计算机来说这花得时间太多了!

怎样可以改进呢?最好是能尽量去掉指针,这样能减少垃圾回收器需要遍历的指针数量。由于字符串包含指针,因此我们可以用map[int]int来实现:
 
import (
"fmt"
"runtime"
"time"
)

const (
numElements = 10000000
)

var foo = map[int]int{}

func timeGC() {
t := time.Now()
runtime.GC()
fmt.Printf("gc took: %s\n", time.Since(t))
}

func main() {
for i := 0; i < numElements; i++ {
foo[i] = i
}

for {
timeGC()
time.Sleep(1 * time.Second)
}
}
重新运行程序,结果如下:
 
gc took: 3.608993ms
gc took: 3.926913ms
gc took: 3.955706ms
gc took: 4.063795ms
gc took: 3.91519ms
gc took: 3.75226ms
好多了。垃圾回收的时间减少了97%。在生产环境下,字符串需要进行hash之后再插入到map中。
 
生成marshalling代码以避免运行时反射
 
将数据结构marshalh或unmarshal成JSON等各种序列化格式是个很常见的操作,特别是在构建微服务的时候。实际上,大部分微服务做的唯一工作就是序列化。像json.Marshal和json.Unmarshal需要依赖运行时反射才能将结构体的字段序列化成字节,反之亦然。这个操作很慢,反射的性能完全无法与显式的代码相比。

但我们不必这么做。marshalling JSON的原理大致如下:
package json

// Marshal take an object and returns its representation in JSON.
func Marshal(obj interface{}) ([]byte, error) {
// Check if this object knows how to marshal itself to JSON
// by satisfying the Marshaller interface.
if m, is := obj.(json.Marshaller); is {
return m.MarshalJSON()
}

// It doesn't know how to marshal itself. Do default reflection based marshallling.
return marshal(obj)
}
如果我们知道怎样将对象marshal成JSON,就应该避免运行时反射。但我们不想手工marshal所有代码,怎么办呢?可以让计算机替我们写程序!像easyjson等代码生成器会检查结构体,然后生成高度优化且与json.Marshaller等接口完全兼容的代码。

下载这个包,然后在包含结构体的$file.go上运行下面的命令:
easyjson -all $file.go$file.go

这个命令会生成$file_easyjson.go。由于easyjson为我们实现了json.Marshaller接口,因此序列化时不会调用默认的反射,而是会使用生成的函数。祝贺你!你已经将JSON marshalling的代码的速度提高了三倍。还有许多其他技巧可以进一步提升性能。
 
使用strings.Builder来构建字符串
 
Go语言的字符串是不可修改的,可以认为它们是只读的字节切片。这就是说,每次创建字符串都要分配新的内存,可能还会给垃圾回收器造成更多工作。

Go 1.10引入了strings.Builder作为高效率构建字符串的方式。它内部会将字符串写入到字节缓冲区。只有在builder上调用String()时才会真正生成字符串。它依赖一些unsafe的技巧将底层的字节作为字符串返回,而不实际进行内存非配。这篇文章(https://syslog.ravelin.com/byt ... ca7ff)介绍了更多其工作原理。
pkg: github.com/sjwhitworth/perfblog/strbuild
BenchmarkStringBuildNaive-8 5000000 255 ns/op 216 B/op 8 allocs/op
BenchmarkStringBuildBuilder-8 20000000 54.9 ns/op 64 B/op 1 allocs/op
可见,strings.Builder要快4.7倍,它的内存分配次只有前者的1/8,内存使用只有前者的1/4。

所以,在性能重要的时候应该使用strings.Builder。一般来说,除非是非常不重要的情况,否则我建议永远使用strings.Builder来构建字符串。
 
使用strconv代替fmt

fmt是Go中最著名的包之一。估计你从第一个Go程序——输出“hello, world”——的时候就开始用它了。但是,如果需要将整数和浮点数转换成字符串,它就不如更底层的strconv有效率了。strconv只需要在API中进行很小改动,就能带来不错的性能提升。

大多数情况下fmt会接受一个interface{}作为参数。这样做有两个弊端:

失去了类型安全。对于我来说这是个很大的问题。

会增加内存分配次数。将非指针类型作为interface{}传递通常会导致堆分配的问题。进一步的内容可以阅读这篇文章(https://www.darkcoding.net/sof ... face/)。
BenchmarkStrconv-8      30000000            39.5 ns/op        32 B/op          1 allocs/op
BenchmarkFmt-8 10000000 143 ns/op 72 B/op 3 allocs/op
可以看到,strconv版本要快3.5倍,内存分配次数是1/3,内存分配量是1/2。

在make中指定分配的容量来避免重新分配

在讨论性能改善之前,我们先来迅速看一下切片。切片是Go语言中一个非常有用的概念。它提供了可改变大小的数组,还可以用不同的方式表示同一片底层内存区域,而不需要重新进行内存分配。slice的内部结构由三个元素组成:


data:切片中指向底层数据的指针
len:切片中的当前元素数目
cap:在不重新分配内存的前提下,切片能够增长到的元素数目


我经常看到类似于下面的代码,尽管在切片容量可以预先得知的情况下依然生成一个容量为零的切片:
var userIDs []string
for _, bar := range rsp.Users {
userIDs = append(userIDs, bar.ID)
}
这段代码中,切片的初始长度和容量都为零。在收到响应后,我们将用户添加到切片。这样做就会达到切片的容量上限,从而导致底层分配两倍容量的新数组,然后将旧切片中的数据拷贝过来。如果有8个用户,就会造成5次内存分配。

更有效的方式是这样:
userIDs := make([]string, 0, len(rsp.Users)
for _, bar := range rsp.Users {
userIDs = append(userIDs, bar.ID)
}
使用make显式声明切片的容量。接下来可以向切片添加元素,而不会触发内存重新分配和拷贝。
 
这条建议也适用于map:适用make(map[string]string, len(foo))可以分配足够的底层内存以避免内存重新分配。
 
使用可以接受字节切片的方法
 
在使用包时,寻找那些接受字节切片作为参数的方法,这些方法通常给你更多控制内存分配的自由。

一个很好的例子就是time.Format和time.AppendFormat。time.Format返回字符串。内部会分配一个新的字节切片,然后在其上调用time.AppendFormat。而time.AppendFormat接受一个字节缓冲区,将格式化后的时间写入缓冲区,然后返回扩展后的字节切片。标准库中这种做法非常常见,如strconv.AppendFloat或bytes.NewBuffer。

为什么这样能提高性能?因为你可以传递从sync.Poolh获得的字节切片,而不需要每次都分配新的缓冲区。或者可以初始化一个足够大的缓冲区,来减少切片拷贝。
 
这些建议只是某些具体情况下的建议,而不是真理。一定要自己测量性能。

要知道何时该停止优化。提高系统性能会让工程师感觉非常满足:问题本身很有趣,也有立竿见影的效果。但是,提高性能带来的效果非常依赖于具体情况。如果服务的响应时间只有10毫秒,而网络访问需要90毫秒,那么将10毫秒优化到5毫秒就完全不值得,因为你依然需要95毫秒。就算你将响应时间优化到1毫秒,最后结果还是91毫秒。你应该去做其他更有价值的事情。
 
原文:
https://stephen.sh/posts/quick-go-performance-improvements
译文:
https://blog.csdn.net/csdnnews/article/details/93987866
 

中文分词及结巴分词原理概述

搜索推荐zkbhj 发表了文章 • 0 个评论 • 131 次浏览 • 2020-08-01 17:08 • 来自相关话题

中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 

基于词典的分词方法;
基于统计的分词方法。


基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:

基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法。


下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
  查看全部
中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 


基于词典的分词方法;
基于统计的分词方法。



基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:


基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法



下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
 

美团点评《O2O搜索场景下的查询理解系统》总结

搜索推荐zkbhj 发表了文章 • 0 个评论 • 155 次浏览 • 2020-07-28 20:57 • 来自相关话题

查询理解简介
 
QU(Query Understanding),对用户输入的Query进行一系列的分析(分词、归一化、纠错、实体识别、实体链接、异地识别、意图识别等),进而产生一系列的基础信号(POI、城市词、品牌词、类别词、经纬度、异地等)。
 
然后用这些基础信号去做更精准的召回,以及对最后排序可能会产生影响。
 
从QU到DQU,是美团NLP的平台化方向和过程。
 
NLP核心模块介绍
 
实体识别
 
对比通用搜索(百度等),电商/O2O搜索是结构化召回NER是指导召回关键信号
 

命名实体识别(Named Entity Recognition,简称NER),又称作“专名识别”,是指识别文本中具有特定意义的实体,主要包括人名、地名、机构名、专有名词等。NER是信息提取、问答系统、句法分析、机器翻译、面向Semantic Web的元数据标注等应用领域的重要基础工具,在自然语言处理技术走向实用化的过程中占有重要的地位。在美团搜索场景下,NER是深度查询理解(Deep Query Understanding,简称 DQU)的底层基础信号,主要应用于搜索召回、用户意图识别、实体链接等环节,NER信号的质量,直接影响到用户的搜索体验。


实体识别模型迭代引入BERT模型
 
查询改写
 
基于知识库(精度高,召回少)->基于用户行为(整串匹配,召回一般) -> 基于翻译模型(召回高,容易语义漂移) -> 基于语义(召回高,解决语义漂移)
 翻译改写主模型:SMT
 
意图识别
 
识别用户需求,决定多业务&多形态召回
 
更多扩展阅读:
BERT在美团搜索核心排序的探索和实践
https://tech.meituan.com/2020/07/09/bert-in-meituan-search.html
美团搜索中NER技术的探索与实践
https://tech.meituan.com/2020/07/23/ner-in-meituan-nlp.html
视频地址:
https://appukvkryx45804.h5.xiaoeknow.com/v1/course/column/p_5f0eeb5ae4b04349896c0dd5?type=3&share_user_id=u_5f190d7aa0047_eBn4XWgyvu&share_type=5&scene=%E9%82%80%E8%AF%B7%E9%93%BE%E6%8E%A5&entry=2&entry_type=2001&is_redirect=1
 
  查看全部
查询理解简介
 
QU(Query Understanding),对用户输入的Query进行一系列的分析(分词、归一化、纠错、实体识别、实体链接、异地识别、意图识别等),进而产生一系列的基础信号(POI、城市词、品牌词、类别词、经纬度、异地等)。
 
然后用这些基础信号去做更精准的召回,以及对最后排序可能会产生影响。
 
从QU到DQU,是美团NLP的平台化方向和过程。
 
NLP核心模块介绍
 
实体识别
 
  • 对比通用搜索(百度等),电商/O2O搜索是结构化召回
  • NER是指导召回关键信号

 


命名实体识别(Named Entity Recognition,简称NER),又称作“专名识别”,是指识别文本中具有特定意义的实体,主要包括人名、地名、机构名、专有名词等。NER是信息提取、问答系统、句法分析、机器翻译、面向Semantic Web的元数据标注等应用领域的重要基础工具,在自然语言处理技术走向实用化的过程中占有重要的地位。在美团搜索场景下,NER是深度查询理解(Deep Query Understanding,简称 DQU)的底层基础信号,主要应用于搜索召回、用户意图识别、实体链接等环节,NER信号的质量,直接影响到用户的搜索体验。



实体识别模型迭代引入BERT模型
 
查询改写
 
基于知识库(精度高,召回少)->基于用户行为(整串匹配,召回一般) -> 基于翻译模型(召回高,容易语义漂移) -> 基于语义(召回高,解决语义漂移)
 翻译改写主模型:SMT
 
意图识别
 
识别用户需求,决定多业务&多形态召回
 
更多扩展阅读:
BERT在美团搜索核心排序的探索和实践
https://tech.meituan.com/2020/07/09/bert-in-meituan-search.html
美团搜索中NER技术的探索与实践
https://tech.meituan.com/2020/07/23/ner-in-meituan-nlp.html
视频地址:
https://appukvkryx45804.h5.xiaoeknow.com/v1/course/column/p_5f0eeb5ae4b04349896c0dd5?type=3&share_user_id=u_5f190d7aa0047_eBn4XWgyvu&share_type=5&scene=%E9%82%80%E8%AF%B7%E9%93%BE%E6%8E%A5&entry=2&entry_type=2001&is_redirect=1
 
 

如何评估搜索的好坏?学习企查查搜索系统演进

搜索推荐zkbhj 发表了文章 • 0 个评论 • 128 次浏览 • 2020-07-27 11:43 • 来自相关话题

无论搜索怎么扩充信息,最终我们评估搜索的标准依然是回归到搜索的本身,即是否返回用户最想要的信息。怎么度量这个,如何评估搜索的好坏?如何确认搜索人员做到的精准,是否就是用户想要的?企查查对于搜索的评估主要基于如下4个指标Top3SuggestNullHitRate。我们持续关注上述这个指标的变化,并持续予以优化。

1. TOP3

我们的结果集常态的输入可能有数十条数百条,精准的搜索可能只有1条记录,最大的则能达到1万条。对于不同量级的结果集,我们关注前三条用户的点击比例,并把这个指标作为衡量整个搜索是否精度的最主要指标。

2. Suggest

用户每多输入一个字数,结果集都是在变化,他什么时候点击相当重要,如果持续不点击suggest意味着用户需要输入更多的字数,这时会判断推荐词是否是他想要的,如果该指标比例提高会有效减少用户的输入时间。这也是评估搜索是否精准的一个重要指标。

3. Null

无结果是搜索比较糟糕的体验,为了规避无结果的占比,我们除了分析用户的输入以推动纠错,兼容形近、音近等情况,还补全了诸如二次搜索等机制。

4. HitRate

整体的点击搜索比,宏观面的数据,既可以辅助分析用户的搜索行为,也可以反推当前的数据质量走势。

通过对上述指标的持续跟进,我们可以较为直观的知道整个搜索团队的工作是否在往更好的方向发展,同时也能分析到给用户的搜索习惯走势。
 
当然,关于搜索,我们除了上述各种预设的机制外,对于热门的搜索,我们也特别增加了人工干预,以规避新词更新不及时,热点事件排序不合理问题。
 
原文阅读:
https://developer.aliyun.com/article/720572
  查看全部
无论搜索怎么扩充信息,最终我们评估搜索的标准依然是回归到搜索的本身,即是否返回用户最想要的信息。怎么度量这个,如何评估搜索的好坏?如何确认搜索人员做到的精准,是否就是用户想要的?企查查对于搜索的评估主要基于如下4个指标Top3SuggestNullHitRate。我们持续关注上述这个指标的变化,并持续予以优化。

1. TOP3

我们的结果集常态的输入可能有数十条数百条,精准的搜索可能只有1条记录,最大的则能达到1万条。对于不同量级的结果集,我们关注前三条用户的点击比例,并把这个指标作为衡量整个搜索是否精度的最主要指标。

2. Suggest

用户每多输入一个字数,结果集都是在变化,他什么时候点击相当重要,如果持续不点击suggest意味着用户需要输入更多的字数,这时会判断推荐词是否是他想要的,如果该指标比例提高会有效减少用户的输入时间。这也是评估搜索是否精准的一个重要指标。

3. Null

无结果是搜索比较糟糕的体验,为了规避无结果的占比,我们除了分析用户的输入以推动纠错,兼容形近、音近等情况,还补全了诸如二次搜索等机制。

4. HitRate

整体的点击搜索比,宏观面的数据,既可以辅助分析用户的搜索行为,也可以反推当前的数据质量走势。

通过对上述指标的持续跟进,我们可以较为直观的知道整个搜索团队的工作是否在往更好的方向发展,同时也能分析到给用户的搜索习惯走势。
 
当然,关于搜索,我们除了上述各种预设的机制外,对于热门的搜索,我们也特别增加了人工干预,以规避新词更新不及时,热点事件排序不合理问题。
 
原文阅读:
https://developer.aliyun.com/article/720572
 

理解Golang中的函数、方法、闭包的本质

GoLangzkbhj 发表了文章 • 0 个评论 • 106 次浏览 • 2020-07-24 10:27 • 来自相关话题

函数的本质

在go的世界中,函数是一等公民,可以给变量赋值,可以作为参数传递,也可以直接赋值。
在go语言中将这样的变量、参数、返回值,即在堆空间和栈空间中绑定函数的值,称为function value。
函数的指令在编译期间生成,使用go tool compile -S main.go可以获取汇编代码, 以OSX 10.15.6,go 1.14为例,将看到下述汇编代码(下面只引用部分)...
"".B STEXT nosplit size=1 args=0x8 locals=0x0
0x0000 00000 (main.go:9) TEXT "".B(SB), NOSPLIT|ABIInternal, $0-8
0x0000 00000 (main.go:9) PCDATA $0, $-2
0x0000 00000 (main.go:9) PCDATA $1, $-2
0x0000 00000 (main.go:9) FUNCDATA $0, gclocals·2a5305abe05176240e61b8620e19a815(SB)
0x0000 00000 (main.go:9) FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x0000 00000 (main.go:9) FUNCDATA $2, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x0000 00000 (main.go:11) PCDATA $0, $-1
0x0000 00000 (main.go:11) PCDATA $1, $-1
0x0000 00000 (main.go:11) RET
0x0000 c3
...运行时将存放在__TEXT段中,也就是存放在代码段中,读写权限为rx/rwx, 通过vmmap [pid]可以获取运行时的内存分布

==== Non-writable regions for process 13443
REGION TYPE START - END [ VSIZE RSDNT DIRTY SWAP] PRT/MAX SHRMOD PURGE REGION DETAIL
__TEXT 0000000001000000-0000000001167000 [ 1436K 1436K 0K 0K] r-x/rwx SM=COW .../test

使用otool -v -l [file]可以看到下述内容(下面只引用了一部分)...
Load command 1
cmd LC_SEGMENT_64
cmdsize 632
segname __TEXT
vmaddr 0x0000000001000000
vmsize 0x0000000000167000
fileoff 0
filesize 1470464
maxprot rwx
initprot r-x
nsects 7
flags (none)
Section
sectname __text
segname __TEXT
addr 0x0000000001001000
size 0x000000000009c365
offset 4096
align 2^4 (16)
reloff 0
nreloc 0
type S_REGULAR
attributes PURE_INSTRUCTIONS SOME_INSTRUCTIONS
reserved1 0
reserved2 0
...所以如果要问函数在go语言里的本质是什么,那么其实就是指向__TEXT段内存地址的一个指针。
 
函数调用的过程

在go语言中,每一个goroutine持有一个连续栈,栈基础大小为2kb,当栈大小超过预分配大小后,会触发栈扩容,也就是分配一个大小为当前栈2倍的新栈,并且将原来的栈拷贝到新的栈上。使用连续栈而不是分段栈的目的是,利用局部性优势提升执行速度,原理是CPU读取地址时会将相邻的内存读取到访问速度比内存快的多级cache中,地址连续性越好,L1、L2、L3 cache命中率越高,速度也就越快。

在go中,和其他一些语言有所不同,函数的返回值、参数都是由被caller保存。每次函数调用时,会在caller的栈中压入函数返回值列表、参数列表、函数返回时的PC地址,然后更改bp和pc为新函数,执行新函数,执行完之后将变量存到caller的栈空间中,利用栈空间中保存的返回地址和caller的栈基地址,恢复pc和sp回到caller的执行过程。

对于栈变量的访问是通过bp+offset的方式来访问,而对于在堆上分配的变量来说,就是通过地址来访问。在go中,变量被分配到堆上还是被分配到栈上是由编译器在编译时根据逃逸分析决定的,不可以更改,只能利用规则尽量让变量被分配到栈上,因为局部性优势,栈空间的内存访问速度快于堆空间访问。
 方法的本质

go里面其实方法就是语法糖,请看下述代码,两个Println打印的结果是一样的,实际上Method就是将receiver作为函数的第一个参数输入的语法糖而已,本质上和函数没有区别。type T struct {
name string
}

func (t T) Name() string {
return "Hi! " + t.name
}

func main() {
t := T{name: "test"}
fmt.Println(t.Name()) // Hi! test
fmt.Println(T.Name(t)) // Hi! test
}
 闭包的本质

前面已经提到在go语言中将这在堆空间和栈空间中绑定函数的值,称为function value。这也就是闭包在go语言中的实体。一个最简单的funcval实际上是通过二级指针指向__TEXT代码段上函数的结构体。

那我们来看下面这个闭包,也就是main函数中的变量ffunc getFunc() func() int {
a := 0
return func() int {
a++
return a
}
}

func main() {
f := getFunc()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}上面这段代码执行完后会输出1~10,也就是说f在执行的时候所使用的a会累计,但是a并不是一个全局变量,为什么f就变成了一个有状态的函数呢?其实这也就是go里面的闭包了。那我们来看go是如何实现闭包的。

首先来解释一下闭包的含义,闭包在实现上是一个结构体,需要存储函数入口和关联环境,关联环境包含约束变量(函数内部变量)和自由变量(函数外部变量,在函数外被定义,但是在函数内被引用,如例子中的变量a),和函数不同的是,在捕获闭包时才能确定自由变量,当脱离了捕捉变量的上下文时,也能照常运行。基于闭包可以很容易的定义异步调用的回调函数。

在 go 语言中,闭包的状态是通过捕获列表实现的。具体来说,有自由变量的闭包funcval的分配都在堆上,(没有自由变量的funcval在__DATA数据段上,和常量一样),funcval中除了包含地址以外,还会包含所引用的自由变量,所有自由变量构成捕获列表。对于会被修改的值,捕获的是值的指针,对于不会被修改的值,捕获的是值拷贝。
 
https://mp.weixin.qq.com/s/96Df9YGykE6daDREli9W1A
  查看全部
函数的本质

在go的世界中,函数是一等公民,可以给变量赋值,可以作为参数传递,也可以直接赋值。
在go语言中将这样的变量、参数、返回值,即在堆空间和栈空间中绑定函数的值,称为function value。
函数的指令在编译期间生成,使用go tool compile -S main.go可以获取汇编代码, 以OSX 10.15.6,go 1.14为例,将看到下述汇编代码(下面只引用部分)
...
"".B STEXT nosplit size=1 args=0x8 locals=0x0
0x0000 00000 (main.go:9) TEXT "".B(SB), NOSPLIT|ABIInternal, $0-8
0x0000 00000 (main.go:9) PCDATA $0, $-2
0x0000 00000 (main.go:9) PCDATA $1, $-2
0x0000 00000 (main.go:9) FUNCDATA $0, gclocals·2a5305abe05176240e61b8620e19a815(SB)
0x0000 00000 (main.go:9) FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x0000 00000 (main.go:9) FUNCDATA $2, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x0000 00000 (main.go:11) PCDATA $0, $-1
0x0000 00000 (main.go:11) PCDATA $1, $-1
0x0000 00000 (main.go:11) RET
0x0000 c3
...
运行时将存放在__TEXT段中,也就是存放在代码段中,读写权限为rx/rwx, 通过vmmap [pid]可以获取运行时的内存分布

==== Non-writable regions for process 13443
REGION TYPE START - END [ VSIZE RSDNT DIRTY SWAP] PRT/MAX SHRMOD PURGE REGION DETAIL
__TEXT 0000000001000000-0000000001167000 [ 1436K 1436K 0K 0K] r-x/rwx SM=COW .../test

使用otool -v -l [file]可以看到下述内容(下面只引用了一部分)
...
Load command 1
cmd LC_SEGMENT_64
cmdsize 632
segname __TEXT
vmaddr 0x0000000001000000
vmsize 0x0000000000167000
fileoff 0
filesize 1470464
maxprot rwx
initprot r-x
nsects 7
flags (none)
Section
sectname __text
segname __TEXT
addr 0x0000000001001000
size 0x000000000009c365
offset 4096
align 2^4 (16)
reloff 0
nreloc 0
type S_REGULAR
attributes PURE_INSTRUCTIONS SOME_INSTRUCTIONS
reserved1 0
reserved2 0
...
所以如果要问函数在go语言里的本质是什么,那么其实就是指向__TEXT段内存地址的一个指针。
 
函数调用的过程

在go语言中,每一个goroutine持有一个连续栈,栈基础大小为2kb,当栈大小超过预分配大小后,会触发栈扩容,也就是分配一个大小为当前栈2倍的新栈,并且将原来的栈拷贝到新的栈上。使用连续栈而不是分段栈的目的是,利用局部性优势提升执行速度,原理是CPU读取地址时会将相邻的内存读取到访问速度比内存快的多级cache中,地址连续性越好,L1、L2、L3 cache命中率越高,速度也就越快。

在go中,和其他一些语言有所不同,函数的返回值、参数都是由被caller保存。每次函数调用时,会在caller的栈中压入函数返回值列表、参数列表、函数返回时的PC地址,然后更改bp和pc为新函数,执行新函数,执行完之后将变量存到caller的栈空间中,利用栈空间中保存的返回地址和caller的栈基地址,恢复pc和sp回到caller的执行过程。

对于栈变量的访问是通过bp+offset的方式来访问,而对于在堆上分配的变量来说,就是通过地址来访问。在go中,变量被分配到堆上还是被分配到栈上是由编译器在编译时根据逃逸分析决定的,不可以更改,只能利用规则尽量让变量被分配到栈上,因为局部性优势,栈空间的内存访问速度快于堆空间访问
 方法的本质

go里面其实方法就是语法糖,请看下述代码,两个Println打印的结果是一样的,实际上Method就是将receiver作为函数的第一个参数输入的语法糖而已,本质上和函数没有区别。
type T struct {
name string
}

func (t T) Name() string {
return "Hi! " + t.name
}

func main() {
t := T{name: "test"}
fmt.Println(t.Name()) // Hi! test
fmt.Println(T.Name(t)) // Hi! test
}

 闭包的本质

前面已经提到在go语言中将这在堆空间和栈空间中绑定函数的值,称为function value。这也就是闭包在go语言中的实体。一个最简单的funcval实际上是通过二级指针指向__TEXT代码段上函数的结构体。

那我们来看下面这个闭包,也就是main函数中的变量f
func getFunc() func() int {
a := 0
return func() int {
a++
return a
}
}

func main() {
f := getFunc()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}
上面这段代码执行完后会输出1~10,也就是说f在执行的时候所使用的a会累计,但是a并不是一个全局变量,为什么f就变成了一个有状态的函数呢?其实这也就是go里面的闭包了。那我们来看go是如何实现闭包的。

首先来解释一下闭包的含义,闭包在实现上是一个结构体,需要存储函数入口和关联环境,关联环境包含约束变量(函数内部变量)和自由变量(函数外部变量,在函数外被定义,但是在函数内被引用,如例子中的变量a),和函数不同的是,在捕获闭包时才能确定自由变量,当脱离了捕捉变量的上下文时,也能照常运行。基于闭包可以很容易的定义异步调用的回调函数。

在 go 语言中,闭包的状态是通过捕获列表实现的。具体来说,有自由变量的闭包funcval的分配都在堆上,(没有自由变量的funcval在__DATA数据段上,和常量一样),funcval中除了包含地址以外,还会包含所引用的自由变量,所有自由变量构成捕获列表。对于会被修改的值,捕获的是值的指针,对于不会被修改的值,捕获的是值拷贝
 
https://mp.weixin.qq.com/s/96Df9YGykE6daDREli9W1A
 

Golang中的并发安全

GoLangzkbhj 发表了文章 • 0 个评论 • 121 次浏览 • 2020-07-23 17:05 • 来自相关话题

并发安全

并发安全也叫线程安全,在并发中出现了数据的丢失,称为并发不安全。

map和slice都是并发不安全的。
 

slice在并发执行中不会报错,但是数据会丢失;
map在并发执行中会直接报错(fatal error: concurrent map writes)。

 
切片并发不安全

场景: 10000个协程同时添加切片
var s []int

func appendValue(i int) {
s = append(s, i)
}

func main() {
for i := 0; i < 10000; i++ { //10000个协程同时添加切片
go appendValue(i)
}

for i, v := range s { //同时打印索引和值
fmt.Println(i, ":", v)
}
}输出:

 
没有到9999,说明有数据丢失

解决方法: 加锁
var s []int
var lock sync.Mutex //互斥锁
func appendValue(i int) {
lock.Lock() //加锁
s = append(s, i)
lock.Unlock() //解锁
}

func main() {
for i := 0; i < 10000; i++ {
go appendValue(i)
}
//sort.Ints(s) //给切片排序,先排完序再打印,和下面一句效果相同
time.Sleep(time.Second) //间隔1s再打印,防止一边插入数据一边打印时数据乱序
for i, v := range s {
fmt.Println(i, ":", v)
}
}
总结: slice在并发执行中不会报错,但是数据会丢失

map并发不安全

场景: 2个协程同时读和写
func main() {
m := make(map[int]int)
go func() { //开一个协程写map
for i := 0; i < 10000; i++ {
m[i] = i
}
}()

go func() { //开一个协程读map
for i := 0; i < 10000; i++ {
fmt.Println(m[i])
}
}()

//time.Sleep(time.Second * 20)
for {
;
}
}输出:

 
解决方法:尽量不要做map的并发,如果用并发要加锁,保证map的操作要么读,要么写。
var lock sync.Mutex
func main() {
m:=make(map[int]int)
go func() { //开一个协程写map
for i:=0;i<10000 ;i++ {
lock.Lock() //加锁
m[i]=i
lock.Unlock() //解锁
}
}()
go func() { //开一个协程读map
for i:=0;i<10000 ;i++ {
lock.Lock() //加锁
fmt.Println(m[i])
lock.Unlock() //解锁
}
}()
time.Sleep(time.Second*20)
}

总结: map在并发执行中会直接报错

原文链接:https://blog.csdn.net/weixin_4 ... 97247 查看全部
并发安全

并发安全也叫线程安全,在并发中出现了数据的丢失,称为并发不安全。

map和slice都是并发不安全的。
 


slice在并发执行中不会报错,但是数据会丢失;
map在并发执行中会直接报错(fatal error: concurrent map writes)。


 
切片并发不安全

场景: 10000个协程同时添加切片
var s []int

func appendValue(i int) {
s = append(s, i)
}

func main() {
for i := 0; i < 10000; i++ { //10000个协程同时添加切片
go appendValue(i)
}

for i, v := range s { //同时打印索引和值
fmt.Println(i, ":", v)
}
}
输出:

 
没有到9999,说明有数据丢失

解决方法: 加锁
var s []int
var lock sync.Mutex //互斥锁
func appendValue(i int) {
lock.Lock() //加锁
s = append(s, i)
lock.Unlock() //解锁
}

func main() {
for i := 0; i < 10000; i++ {
go appendValue(i)
}
//sort.Ints(s) //给切片排序,先排完序再打印,和下面一句效果相同
time.Sleep(time.Second) //间隔1s再打印,防止一边插入数据一边打印时数据乱序
for i, v := range s {
fmt.Println(i, ":", v)
}
}
总结: slice在并发执行中不会报错,但是数据会丢失

map并发不安全

场景: 2个协程同时读和写
func main() {
m := make(map[int]int)
go func() { //开一个协程写map
for i := 0; i < 10000; i++ {
m[i] = i
}
}()

go func() { //开一个协程读map
for i := 0; i < 10000; i++ {
fmt.Println(m[i])
}
}()

//time.Sleep(time.Second * 20)
for {
;
}
}
输出:

 
解决方法:尽量不要做map的并发,如果用并发要加锁,保证map的操作要么读,要么写。
var lock sync.Mutex
func main() {
m:=make(map[int]int)
go func() { //开一个协程写map
for i:=0;i<10000 ;i++ {
lock.Lock() //加锁
m[i]=i
lock.Unlock() //解锁
}
}()
go func() { //开一个协程读map
for i:=0;i<10000 ;i++ {
lock.Lock() //加锁
fmt.Println(m[i])
lock.Unlock() //解锁
}
}()
time.Sleep(time.Second*20)
}

总结: map在并发执行中会直接报错

原文链接:https://blog.csdn.net/weixin_4 ... 97247

初识Embedding

机器学习zkbhj 发表了文章 • 0 个评论 • 141 次浏览 • 2020-07-23 11:36 • 来自相关话题

什么是embedding?为什么说embedding是深度学习的基本操作?
 

简单来说,embedding就是用一个低维的向量表示一个物体,可以是一个词,或是一个商品,或是一个电影等等。

 
这个embedding向量的性质是能使距离相近的向量对应的物体有相近的含义,比如 Embedding(复仇者联盟)和Embedding(钢铁侠)之间的距离就会很接近,但 Embedding(复仇者联盟)和Embedding(乱世佳人)的距离就会远一些。
 
Embedding在数学上表示一个maping:f:x->y, 也就是一个function。

其中该函数满足两个性质:

injective (单射的):就是我们所说的单射函数,每个X只有唯一的Y对应;
structure-preserving(结构保存):比如在X所属的空间上 x1<=x2,那么映射后在Y所属空间上同理 y1 <= y2 。


那么对于word embedding, 就是找到一个映射(函数)将单词(word)映射到另外一个空间(其中这个映射具有injective和structure-preserving的特点), 生成在一个新的空间上的表达,该表达就是word representation.

举个颜色的例子:

对于颜色,我们可以把它拆成三个特征维度,用这三个维度的组合理论上可以表示任意一种颜色。同理,对于词,我们也可以把它拆成指定数量的特征维度,词表中的每一个词都可以用这些维度组合成的向量来表示,这个就是Word Embedding的含义。

当然,词跟颜色还是有很大的差别的——我们已经知道表示颜色的三个维度有明确对应的物理意义(即RGB),直接使用物理原理就可以知道某一个颜色对应的RGB是多少。但是对于词,我们无法给出每个维度所具备的可解释的意义,也无法直接求出一个词的词向量的值应该是多少。所以我们需要使用语料和模型来训练词向量——把嵌入矩阵当成模型参数的一部分,通过词与词间的共现或上下文关系来优化模型参数,最后得到的矩阵就是词表中所有词的词向量。

这里需要说明的是,有的初学者可能没绕过一个弯,就是“最初的词向量是怎么来的”——其实你只要知道最初的词向量是瞎JB填的就行了。嵌入矩阵最初的参数跟模型参数一样是随机初始化的,然后前向传播计算损失函数,反向传播求嵌入矩阵里各个参数的导数,再梯度下降更新,这个跟一般的模型训练都是一样的。等训练得差不多的时候,嵌入矩阵就是比较准确的词向量矩阵了。

作者:到处挖坑蒋玉成
链接:https://www.zhihu.com/question ... 50109
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
 
https://www.jianshu.com/p/6c977a9a53de
https://www.zhihu.com/question/38002635
https://zhuanlan.zhihu.com/p/46016518
  查看全部
什么是embedding?为什么说embedding是深度学习的基本操作?
 


简单来说,embedding就是用一个低维的向量表示一个物体,可以是一个词,或是一个商品,或是一个电影等等。


 
这个embedding向量的性质是能使距离相近的向量对应的物体有相近的含义,比如 Embedding(复仇者联盟)和Embedding(钢铁侠)之间的距离就会很接近,但 Embedding(复仇者联盟)和Embedding(乱世佳人)的距离就会远一些。
 
Embedding在数学上表示一个maping:f:x->y, 也就是一个function。

其中该函数满足两个性质:


injective (单射的):就是我们所说的单射函数,每个X只有唯一的Y对应;
structure-preserving(结构保存):比如在X所属的空间上 x1<=x2,那么映射后在Y所属空间上同理 y1 <= y2 。



那么对于word embedding, 就是找到一个映射(函数)将单词(word)映射到另外一个空间(其中这个映射具有injective和structure-preserving的特点), 生成在一个新的空间上的表达,该表达就是word representation.

举个颜色的例子:

对于颜色,我们可以把它拆成三个特征维度,用这三个维度的组合理论上可以表示任意一种颜色。同理,对于词,我们也可以把它拆成指定数量的特征维度,词表中的每一个词都可以用这些维度组合成的向量来表示,这个就是Word Embedding的含义。

当然,词跟颜色还是有很大的差别的——我们已经知道表示颜色的三个维度有明确对应的物理意义(即RGB),直接使用物理原理就可以知道某一个颜色对应的RGB是多少。但是对于词,我们无法给出每个维度所具备的可解释的意义,也无法直接求出一个词的词向量的值应该是多少。所以我们需要使用语料和模型来训练词向量——把嵌入矩阵当成模型参数的一部分,通过词与词间的共现或上下文关系来优化模型参数,最后得到的矩阵就是词表中所有词的词向量。

这里需要说明的是,有的初学者可能没绕过一个弯,就是“最初的词向量是怎么来的”——其实你只要知道最初的词向量是瞎JB填的就行了。嵌入矩阵最初的参数跟模型参数一样是随机初始化的,然后前向传播计算损失函数,反向传播求嵌入矩阵里各个参数的导数,再梯度下降更新,这个跟一般的模型训练都是一样的。等训练得差不多的时候,嵌入矩阵就是比较准确的词向量矩阵了。

作者:到处挖坑蒋玉成
链接:https://www.zhihu.com/question ... 50109
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
 
https://www.jianshu.com/p/6c977a9a53de
https://www.zhihu.com/question/38002635
https://zhuanlan.zhihu.com/p/46016518