在执行geth --help命令时,提示错误:`GLIBC_2.14' not found

回复

区块链zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 216 次浏览 • 2021-08-12 21:37 • 来自相关话题

如何启动Geth区块链网络?

回复

区块链zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 243 次浏览 • 2021-08-12 18:24 • 来自相关话题

Elasticsearch如何查找两个圆形区域的差集中的文档?

回复

ElasticSearchzkbhj 回复了问题 • 1 人关注 • 1 个回复 • 1055 次浏览 • 2021-02-20 19:15 • 来自相关话题

#英文技术文章翻译# Nitro框架(原Go Micro)介绍文档

GoLangzkbhj 发表了文章 • 0 个评论 • 859 次浏览 • 2020-11-26 11:37 • 来自相关话题

原文地址:https://github.com/asim/nitro 






Nitro (formerly known as Go Micro) is a future framework for distributed app development, IoT, edge and p2p.
Nitro(原来以Go Micro为大家所熟知)是一个面向未来的适用于分布式应用、IoT(物联网)边缘计算和P2P的框架。
 
Overview 综述
 
Nitro will provide the core requirements for distributed app development, IoT, edge and p2p including RPC and Event driven communication. The Nitro mantra is in-memory defaults with a pluggable architecture. Blaze with pure in-memory development and swap out as needed to go multi-process or multi-host.
Nitro将会为分布式应用、IoT(物联网)边缘计算和P2P的应用开发提供核心所需要的功能包括RPC和事件驱动通信。Nitro是一个默认内存式的可插拔的架构。纯内存式编程并且可以随时根据需要切换到go 的多进程或多线程模式上。

Note: Nitro is currently undergoing a complete rewrite and is considered unstable for use.
提示:Nitro目前正在经历全面的重写并且在真正使用到正式项目中时需要深思熟虑它的安全性问题。
 
Features 特性
 
Now focusing on dapps, IoT, edge and p2p. Features include:
现在(框架)只专注于分布式应用、物联网、边缘计算和P2P。特性包括:
Lightweight RPC based communicationsEvent broadcasting and notificationsCRDT Data synchronisation and storageConsensus protocol and execution engineWebAssembly target compilation supportUnique randomized token generation aka BLSP2P gossip networking defined in user space
 
基于轻量级的RPC通信事件驱动和消息通知CRDT数据同步和存储(CRDT是Conflict-free Replicated Data Type的简称,也称为a passive synchronisation,即免冲突的可复制的数据类型)一致的协议和执行引擎实验性的编译器支持唯一token生成器BLS用户空间自定义P2P网络
 
Future 未来
 
In the future there's the potential to launch a live network based on Nitro. More on that soon.
在未来开启一个基于Nitro的在线网络服务是可能的。很快就会实现了。

FAQ QA环节

What happened to Go Micro?
Go Micro发生了什么?

Go Micro has now been renamed to Nitro. Go Micro moved back to being a personal project and no longer lives under the organisation github.com/micro. The company is now doubling down on Micro itself and has pulled in the needed interfaces to consolidate a Server, Framework and CLI into one tool. Go Micro is now no longer maintained by a company. Yet it continued to create confusion even as a personal repo. So for that reason, we're renaming to Nitro. Go Micro V2 has been archived at microhq/go-micro and the plugins at microhq/plugins.
Go Micro现在已经被重新命名为Nitro。Go Micro项目已经变成了一个个人项目并且不再是一个团队(github.com/micro.)负责的项目。公司正在加倍使用Micro并且引入了必要的接口使之成为一个服务、框架和CLI的工具(上云提供商业服务,见 m3o.com)。Go Micro现在已经不再被任何公司维护。但是使用Go Micro作为名字的话依然会产生困惑,即使作为一个个人回收的项目。基于上面的原因,我们考虑把它重新命名为Nitro。Go Micro V2版本已经被归档在 microhq/go-micro ,插件归档在microhq/plugins。What's the new direction of Nitro?Nitro新的方向是什么?

Nitro will now focus on distributed app development using the Go standard library. It will continue to define abstractions for distributed systems but will only do so without external dependencies. In this manner the hope is Nitro can be picked up with minimal overhead for all sorts of new applications that have a low memory or low resource footprint. The assumption is there are places which would like to use distributed apps just as embedded systems or web assembly, unikernels, and related targets that would benefit from a framework that defined these as primitives for such use.
Nitro从现在开始将聚焦在用Go标准库来开发分布式应用。框架会持续为分布式系统定义抽象但是仅限于在没有外部依赖的情况下。通过这种方式,我们希望Nitro可以以最小的开销为那些内存或资源占有率低的程序使用。假设有些场景下更喜欢用分布式应用,像是嵌入式系统或者实验性系统,unikernels,和其他目标系统,他们将会从这个被定义为专为这些应用而生的基础框架中受益。
 
How do Nitro and Micro now differ?
现在Nitro和Micro有什么不同?

Micro is a platform for cloud native development. A complete experience that includes a server, framework and multi-language clients. Beyond that it also include environments, multi-tenancy and many more features which push it towards being a hosted Micro as a Service offering. It is a complete platform.
Micro是一个为云原生应用开发的平台框架。是一个完整的经验包括服务端,框架和多种语言客户端。除了上面提到的它也包括环境,多客端和未来更多的特性,这些特性把它推向成为一个提供服务的Micro托管产品。它是一个完整的平台框架。

Nitro is more of a embeddable framework for distributed app development and now once again a purely personal project maintained by me and perhaps others who still find use for it commercially or noncommercially. It's of sentimental value and something I'd like to carry on for personal projects such as things related to edge, IoT, embedded systems, p2p, web assembly, etc.
Nitro是一个为分布式应用提供的可嵌入式的框架,并且再一次成为一个完全的个人项目被我维护,也许会有人会发现把它并把它用于商业用途或非商业用途。这个框架充满了感情色彩以及我可能希望和喜欢的一些东西带入到这个个人项目中,比如像是一些跟边缘计算、物联网、嵌入式系统、P2P和实验性的东西等等。
 
I used Go Micro to build microservices. What should I do now?
我曾经用Go Micro来构建微服务应用。我现在应该做些什么?

You should quite honestly go look at Micro and then consider the hosted offering at m3o.com which starts as a purely free dev environment in the cloud. Micro continues to address many of the concerns and requirements you had if not more. It is likely you managed metrics, tracing, logging and much other boilerplate that needed to be plugged in. Micro will now take this complete platform story approach and help you in that journey e.gyou're probably running managed kubernetes on a major cloud provider with many other things. We're doing that for you instead as a company and platform team.
你应该非常诚恳的看一看 Micro这个项目然后考虑m3o.com提供的托管产品,这个托管产品开始会在云上提供一个完全免费的开发环境。Micro将会继续设法解决你有的问题和需求如果不太多的话。就像你管理的应用性能,链路追踪,日志和许多其他的组件包被引入的。Micro会采用这种完整的平台托管方式来帮助你解决迁移过程中你可能遇到的问题,比如管理在一个核心的云服务提供上运行的项目或者其他一些事情。我们代替公司或者平台团队为你做这些事情。
 
I want to use Go Micro version 2.0 for my company. Can I still do that?
我想使用Go Micro 2.0版本为我们公司的项目。我可以一直这么做吗?

Yes. Go Micro 2.0 is still Apache 2.0 licensed which means you can still freely use it for everything you were using before. If you're a new user you can do the same. These things are using go modules so you're import path is simply github.com/micro/go-micro/v2 as it was before. Because GitHub handles redirects this should not break. Please continue to use it if you like, but my own support for 2.0 is now end of life.
当然。Go Micro 2.0 将一直是一个Apache 2.0 授权的,这意味着你可以一直免费使用它来做任何事情就像你以前用它一样。如果你是一个新用户,你也可以这么做。可以用go modules来做这些事,所以你可以通过import 这个路径  github.com/micro/go-micro/v2 就像以前一样。因为GitHub上面的链接不会被失效掉。如果你喜欢,请继续使用它。但是我从现在开始不会再继续支持和维护这个2.0版本了。
 
Why has the license changed from Apache 2.0 to Polyform Noncommercial?
为什么授权许可从Apache 2.0变成了Polyform Noncommercia?

Go Micro was largely a solo maintained effort for the entirety of its lifetime. It has enabled the creation of a company called Micro Services, Inc. which now focuses on Micro as a Service and has consolidated any interfaces here into a service library in that project. For the most part, Go Micro was underfunded and in some ways under appreciated. In version 3.0, going back to something of a personal project of more than 6 years I have made the hard decision to relicense as a noncommercial project.
Go Micro 很大程度上在它的整个生命周期中都是一个单独维护的项目。它使一家名为Micro Services的公司成立成为可能,这家公司目前主要聚焦在Micro作为一个服务来提供,然后把所有的接口都整合成一个服务库。在很大程度上,Go Micro项目资金不足且在一定程度上没有得到重视。在3.0版本中,追忆这个超过6年的个人项目的一些事情的情况下我做了一个艰难的决定就是重新作为一个非商业项目获得授权。
 
  查看全部
原文地址:https://github.com/asim/nitro 

73709577.png


Nitro (formerly known as Go Micro) is a future framework for distributed app development, IoT, edge and p2p.
Nitro(原来以Go Micro为大家所熟知)是一个面向未来的适用于分布式应用、IoT(物联网)边缘计算和P2P的框架。
 
Overview 综述
 
Nitro will provide the core requirements for distributed app development, IoT, edge and p2p including RPC and Event driven communication. The Nitro mantra is in-memory defaults with a pluggable architecture. Blaze with pure in-memory development and swap out as needed to go multi-process or multi-host.
Nitro将会为分布式应用、IoT(物联网)边缘计算和P2P的应用开发提供核心所需要的功能包括RPC和事件驱动通信。Nitro是一个默认内存式的可插拔的架构。纯内存式编程并且可以随时根据需要切换到go 的多进程或多线程模式上。

Note: Nitro is currently undergoing a complete rewrite and is considered unstable for use.
提示:Nitro目前正在经历全面的重写并且在真正使用到正式项目中时需要深思熟虑它的安全性问题。
 
Features 特性
 
Now focusing on dapps, IoT, edge and p2p. Features include:
现在(框架)只专注于分布式应用、物联网、边缘计算和P2P。特性包括:
  • Lightweight RPC based communications
  • Event broadcasting and notifications
  • CRDT Data synchronisation and storage
  • Consensus protocol and execution engine
  • WebAssembly target compilation support
  • Unique randomized token generation aka BLS
  • P2P gossip networking defined in user space

 
  • 基于轻量级的RPC通信
  • 事件驱动和消息通知
  • CRDT数据同步和存储(CRDT是Conflict-free Replicated Data Type的简称,也称为a passive synchronisation,即免冲突的可复制的数据类型)
  • 一致的协议和执行引擎
  • 实验性的编译器支持
  • 唯一token生成器BLS
  • 用户空间自定义P2P网络

 
Future 未来
 
In the future there's the potential to launch a live network based on Nitro. More on that soon.
在未来开启一个基于Nitro的在线网络服务是可能的。很快就会实现了。

FAQ QA环节

What happened to Go Micro?
Go Micro发生了什么?

Go Micro has now been renamed to Nitro. Go Micro moved back to being a personal project and no longer lives under the organisation github.com/micro. The company is now doubling down on Micro itself and has pulled in the needed interfaces to consolidate a Server, Framework and CLI into one tool. Go Micro is now no longer maintained by a company. Yet it continued to create confusion even as a personal repo. So for that reason, we're renaming to Nitro. Go Micro V2 has been archived at microhq/go-micro and the plugins at microhq/plugins.
Go Micro现在已经被重新命名为Nitro。Go Micro项目已经变成了一个个人项目并且不再是一个团队(github.com/micro.)负责的项目。公司正在加倍使用Micro并且引入了必要的接口使之成为一个服务、框架和CLI的工具(上云提供商业服务,见 m3o.com)。Go Micro现在已经不再被任何公司维护。但是使用Go Micro作为名字的话依然会产生困惑,即使作为一个个人回收的项目。基于上面的原因,我们考虑把它重新命名为Nitro。Go Micro V2版本已经被归档在 microhq/go-micro ,插件归档在microhq/plugins。What's the new direction of Nitro?Nitro新的方向是什么?

Nitro will now focus on distributed app development using the Go standard library. It will continue to define abstractions for distributed systems but will only do so without external dependencies. In this manner the hope is Nitro can be picked up with minimal overhead for all sorts of new applications that have a low memory or low resource footprint. The assumption is there are places which would like to use distributed apps just as embedded systems or web assembly, unikernels, and related targets that would benefit from a framework that defined these as primitives for such use.
Nitro从现在开始将聚焦在用Go标准库来开发分布式应用。框架会持续为分布式系统定义抽象但是仅限于在没有外部依赖的情况下。通过这种方式,我们希望Nitro可以以最小的开销为那些内存或资源占有率低的程序使用。假设有些场景下更喜欢用分布式应用,像是嵌入式系统或者实验性系统,unikernels,和其他目标系统,他们将会从这个被定义为专为这些应用而生的基础框架中受益。
 
How do Nitro and Micro now differ?
现在Nitro和Micro有什么不同?

Micro is a platform for cloud native development. A complete experience that includes a server, framework and multi-language clients. Beyond that it also include environments, multi-tenancy and many more features which push it towards being a hosted Micro as a Service offering. It is a complete platform.
Micro是一个为云原生应用开发的平台框架。是一个完整的经验包括服务端,框架和多种语言客户端。除了上面提到的它也包括环境,多客端和未来更多的特性,这些特性把它推向成为一个提供服务的Micro托管产品。它是一个完整的平台框架。

Nitro is more of a embeddable framework for distributed app development and now once again a purely personal project maintained by me and perhaps others who still find use for it commercially or noncommercially. It's of sentimental value and something I'd like to carry on for personal projects such as things related to edge, IoT, embedded systems, p2p, web assembly, etc.
Nitro是一个为分布式应用提供的可嵌入式的框架,并且再一次成为一个完全的个人项目被我维护,也许会有人会发现把它并把它用于商业用途或非商业用途。这个框架充满了感情色彩以及我可能希望和喜欢的一些东西带入到这个个人项目中,比如像是一些跟边缘计算、物联网、嵌入式系统、P2P和实验性的东西等等。
 
I used Go Micro to build microservices. What should I do now?
我曾经用Go Micro来构建微服务应用。我现在应该做些什么?

You should quite honestly go look at Micro and then consider the hosted offering at m3o.com which starts as a purely free dev environment in the cloud. Micro continues to address many of the concerns and requirements you had if not more. It is likely you managed metrics, tracing, logging and much other boilerplate that needed to be plugged in. Micro will now take this complete platform story approach and help you in that journey e.gyou're probably running managed kubernetes on a major cloud provider with many other things. We're doing that for you instead as a company and platform team.
你应该非常诚恳的看一看 Micro这个项目然后考虑m3o.com提供的托管产品,这个托管产品开始会在云上提供一个完全免费的开发环境。Micro将会继续设法解决你有的问题和需求如果不太多的话。就像你管理的应用性能,链路追踪,日志和许多其他的组件包被引入的。Micro会采用这种完整的平台托管方式来帮助你解决迁移过程中你可能遇到的问题,比如管理在一个核心的云服务提供上运行的项目或者其他一些事情。我们代替公司或者平台团队为你做这些事情。
 
I want to use Go Micro version 2.0 for my company. Can I still do that?
我想使用Go Micro 2.0版本为我们公司的项目。我可以一直这么做吗?

Yes. Go Micro 2.0 is still Apache 2.0 licensed which means you can still freely use it for everything you were using before. If you're a new user you can do the same. These things are using go modules so you're import path is simply github.com/micro/go-micro/v2 as it was before. Because GitHub handles redirects this should not break. Please continue to use it if you like, but my own support for 2.0 is now end of life.
当然。Go Micro 2.0 将一直是一个Apache 2.0 授权的,这意味着你可以一直免费使用它来做任何事情就像你以前用它一样。如果你是一个新用户,你也可以这么做。可以用go modules来做这些事,所以你可以通过import 这个路径  github.com/micro/go-micro/v2 就像以前一样。因为GitHub上面的链接不会被失效掉。如果你喜欢,请继续使用它。但是我从现在开始不会再继续支持和维护这个2.0版本了。
 
Why has the license changed from Apache 2.0 to Polyform Noncommercial?
为什么授权许可从Apache 2.0变成了Polyform Noncommercia?

Go Micro was largely a solo maintained effort for the entirety of its lifetime. It has enabled the creation of a company called Micro Services, Inc. which now focuses on Micro as a Service and has consolidated any interfaces here into a service library in that project. For the most part, Go Micro was underfunded and in some ways under appreciated. In version 3.0, going back to something of a personal project of more than 6 years I have made the hard decision to relicense as a noncommercial project.
Go Micro 很大程度上在它的整个生命周期中都是一个单独维护的项目。它使一家名为Micro Services的公司成立成为可能,这家公司目前主要聚焦在Micro作为一个服务来提供,然后把所有的接口都整合成一个服务库。在很大程度上,Go Micro项目资金不足且在一定程度上没有得到重视。在3.0版本中,追忆这个超过6年的个人项目的一些事情的情况下我做了一个艰难的决定就是重新作为一个非商业项目获得授权。
 
 

LeetCode刷题Day2:两数相加

LeetCodezkbhj 发表了文章 • 0 个评论 • 622 次浏览 • 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 个评论 • 632 次浏览 • 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 个回复 • 3734 次浏览 • 2020-09-17 11:32 • 来自相关话题

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

GoLangzkbhj 发表了文章 • 0 个评论 • 648 次浏览 • 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 个评论 • 991 次浏览 • 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 个评论 • 998 次浏览 • 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