LeetCode刷题Day2:两数相加

LeetCodezkbhj 发表了文章 • 0 个评论 • 85 次浏览 • 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 个评论 • 73 次浏览 • 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的相关知识和用法,以及哈希表这一知识点。

我的阅读分享:《名侦探的守则》

读后感zkbhj 发表了文章 • 0 个评论 • 71 次浏览 • 2020-09-22 17:22 • 来自相关话题

阅读书目:《名侦探的守则》
作者:[日]东野圭吾 著
书籍类型:侦探推理小说
页数:256页
阅读开始时间:2020年9月19日
阅读结束时间:2020年9月20日18:18:11
如何发现这本书:京东热销书单
阅读次数:第1次
阅读类型:精读
推荐等级:★★★★★
阅读建议:
这个周末2天的空闲时间,读完了《名侦探的守则》这本看似是“侦探推理”类型小说的小说,这也是我读了这么多东野圭吾作品里,最特别的一本。说它是“侦探推理小说”,它确实也是,因为里面全部都是围绕“名侦探”天下一大五郎展开的“本格推理”典型案件。
说它又不像是“侦探推理小说”,是因为它跟以前读过的所有侦探推理小说都不一样,无论从叙事方式,还是人物描写。太不一样了。
它用一种幽默讽刺的口吻,解构了本格推理小说的创作模式,把大家在侦探小说里能够见到的本格推理的各种诡计和作案手法都彻底进行了颠覆,让你感到完全不按“套路”出牌!
推荐一看!
所以到这里,有一个概念就要弄清楚,读了这么多侦探推理类型的小说,什么是“本格推理”?

本格推理,又称古典推理,指与注重写实的社会派推理小说相对,以推理解谜为主要走向,让读者和侦探拥有同样线索、站在同一平面的推理小说主流类型。常有密室杀人或孤岛杀人等诡计类型。
 
比如之前读过的阿加莎·克里斯蒂的经典之作《无人生还》,就是孤岛杀人的典型代表作,而东野圭吾的《放学后》、《嫌疑人X的献身》等都是密室杀人的典型代表作。

看了下这部作品还拍了10集的电视剧,有机会去看看。

豆瓣地址:https://book.douban.com/subject/26926528/
 






  查看全部


阅读书目:《名侦探的守则》
作者:[日]东野圭吾 著
书籍类型:侦探推理小说
页数:256页
阅读开始时间:2020年9月19日
阅读结束时间:2020年9月20日18:18:11
如何发现这本书:京东热销书单
阅读次数:第1次
阅读类型:精读
推荐等级:★★★★★
阅读建议:
这个周末2天的空闲时间,读完了《名侦探的守则》这本看似是“侦探推理”类型小说的小说,这也是我读了这么多东野圭吾作品里,最特别的一本。说它是“侦探推理小说”,它确实也是,因为里面全部都是围绕“名侦探”天下一大五郎展开的“本格推理”典型案件。
说它又不像是“侦探推理小说”,是因为它跟以前读过的所有侦探推理小说都不一样,无论从叙事方式,还是人物描写。太不一样了。
它用一种幽默讽刺的口吻,解构了本格推理小说的创作模式,把大家在侦探小说里能够见到的本格推理的各种诡计和作案手法都彻底进行了颠覆,让你感到完全不按“套路”出牌!
推荐一看!
所以到这里,有一个概念就要弄清楚,读了这么多侦探推理类型的小说,什么是“本格推理”?

本格推理,又称古典推理,指与注重写实的社会派推理小说相对,以推理解谜为主要走向,让读者和侦探拥有同样线索、站在同一平面的推理小说主流类型。常有密室杀人或孤岛杀人等诡计类型。
 
比如之前读过的阿加莎·克里斯蒂的经典之作《无人生还》,就是孤岛杀人的典型代表作,而东野圭吾的《放学后》、《嫌疑人X的献身》等都是密室杀人的典型代表作。

看了下这部作品还拍了10集的电视剧,有机会去看看。

豆瓣地址:https://book.douban.com/subject/26926528/
 



586b3518N17890c29.jpg

 

我的阅读分享:《祈念守护人》

读后感zkbhj 发表了文章 • 0 个评论 • 93 次浏览 • 2020-09-18 13:23 • 来自相关话题

阅读书目:《祈念守护人》
作者:[日]东野圭吾 著
书籍类型:人情温暖小说
页数:314页
阅读开始时间:2020年9月10日
阅读结束时间:2020年9月18日13:18:11
如何发现这本书:京东热销书单
阅读次数:第1次
阅读类型:精读
推荐等级:★★★★★
阅读建议:就算世界冷漠疏离,《祈念守护人》为你找回人情温暖。祈念,就跟字面要传达的含义一样,他不是简简单单的祈祷或者许愿,念,则包含很多东西,更多的则是一种真情,给人以温暖,给人以力量。很治愈的小说构思,可以一读。稍稍运用了一些简单的推理,整部作品算不上是推理小说。

豆瓣地址:https://book.douban.com/subject/35017604/






  查看全部


阅读书目:《祈念守护人》
作者:[日]东野圭吾 著
书籍类型:人情温暖小说
页数:314页
阅读开始时间:2020年9月10日
阅读结束时间:2020年9月18日13:18:11
如何发现这本书:京东热销书单
阅读次数:第1次
阅读类型:精读
推荐等级:★★★★★
阅读建议:就算世界冷漠疏离,《祈念守护人》为你找回人情温暖。祈念,就跟字面要传达的含义一样,他不是简简单单的祈祷或者许愿,念,则包含很多东西,更多的则是一种真情,给人以温暖,给人以力量。很治愈的小说构思,可以一读。稍稍运用了一些简单的推理,整部作品算不上是推理小说。

豆瓣地址:https://book.douban.com/subject/35017604/



529c6762c3d0544a.jpg

 

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

回复

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

#阅读2020#2020年第4季度读书计划

读书计划zkbhj 发表了文章 • 0 个评论 • 99 次浏览 • 2020-09-16 17:48 • 来自相关话题

2020年第4季度读书计划

时间跨度:10、11、12三个月

第4季度精读书目表(总)
《Flutter:从0到1构建大前端应用》何瑞君 (技术:技能提升)《Dart编程语言》[美]Gilad Bracha(技术:技能提升)《贫穷的本质》阿比吉特·巴纳吉 著(技能:经济&思维提升)《S. 忒修斯之船 (简体中文典藏复刻版)》[美] J·J·艾布拉姆斯,[美] 道格·道斯特 著,颜湘如 译(小说:悬疑推理)《从一到无穷大:科学中的事实与猜想》乔治·伽莫夫 著(科普经典)《次第花开》希阿荣博堪布著 著(文化:藏人精神保持愉悦的秘密)《我的前半生》爱新觉罗·溥仪 著(历史:历史人物)《红楼梦(上册)》曹雪芹(小说:四大名著、豆瓣读书第一名)《红楼梦(下册)》曹雪芹(小说:四大名著、豆瓣读书第一名)《一往无前》小米10周年创业故事《全球科技简史》吴军 著(科技历史)
 
 
第4季度粗读书目表(总) 

  查看全部
2020年第4季度读书计划

时间跨度:10、11、12三个月

第4季度精读书目表(总)
  1. 《Flutter:从0到1构建大前端应用》何瑞君 (技术:技能提升)
  2. 《Dart编程语言》[美]Gilad Bracha(技术:技能提升)
  3. 《贫穷的本质》阿比吉特·巴纳吉 著(技能:经济&思维提升)
  4. 《S. 忒修斯之船 (简体中文典藏复刻版)》[美] J·J·艾布拉姆斯,[美] 道格·道斯特 著,颜湘如 译(小说:悬疑推理)
  5. 《从一到无穷大:科学中的事实与猜想》乔治·伽莫夫 著(科普经典)
  6. 《次第花开》希阿荣博堪布著 著(文化:藏人精神保持愉悦的秘密)
  7. 《我的前半生》爱新觉罗·溥仪 著(历史:历史人物)
  8. 《红楼梦(上册)》曹雪芹(小说:四大名著、豆瓣读书第一名)
  9. 《红楼梦(下册)》曹雪芹(小说:四大名著、豆瓣读书第一名)
  10. 《一往无前》小米10周年创业故事
  11. 《全球科技简史》吴军 著(科技历史)

 
 
第4季度粗读书目表(总) 

 

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

GoLangzkbhj 发表了文章 • 0 个评论 • 106 次浏览 • 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 回复了问题 • 1 人关注 • 1 个回复 • 148 次浏览 • 2020-09-10 16:00 • 来自相关话题

MySQL如何通过sql查询数据的区间分布情况?

回复

数据库zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 185 次浏览 • 2020-09-07 10:42 • 来自相关话题

#阅读2020#周末书店阅读简记:2020年08月30日

读书笔记zkbhj 发表了文章 • 0 个评论 • 142 次浏览 • 2020-08-30 16:32 • 来自相关话题

# 北京西西弗书店蓝色港湾店
#2020年08月30日11:15:18~
 
《人生十二法则》
阅读感受:这本书简单看看就行了,不需要买回来看。
最好的规则并不会限制我们,反而会推动我们前进,让我们生活得更加充实和自由。
事实是,如果没有规则,我们很快就会称为自己情绪的奴隶,而这种情况是毫无自由而言的。当不受约束地用未经训练的本能做判断时,我们不仅会缺乏追去,还会崇拜那些不值得我们崇拜的品质。
 
最重要的法则是:你必须为自己的人生负责。
 
法则一:获胜的龙虾从不低头:笔直站立,昂首挺胸
Stand up straight with your shoulders back
 
法则二:像照顾生病的宠物一样关心自己:待己如助人
Treat yourself like someone you are responsible for helping
 
法则三:放弃损友:与真心希望你好的人做朋友
Make friends with people who want the best for you
 
法则四:战胜内心的批评家:和昨天的自己比,别和今天的别人比
compare yourself to who you were yesterday, not to who someone else is today
 
法则五:管教你家的小怪物:别让孩子做出令他讨厌的事
do not let your children no anything that makes you dislike them
 
法则六:当痛苦到想诅咒一切:批判世界之前先清理你的房间
set your house in perfect order before you criticize the world
 
法则七:苏格拉底的选择:追求意义,拒绝苟且
pursue What is meaningful(not What is expedient)
 
法则八:不买醉鬼卖的东西:说真话,或者至少别撒谎
tell the truth——or,at least,don't lie
 
法则九:别偷走来访者的问题:假设你聆听的人知道你不知道的事
assume that the person you are listening to might know something you don't
 
法则十:不要无视地毯下的龙:直面问题,言辞精确
be precise in you speech
 
法则十一:不要打扰玩滑板的孩子们:承认现实,反对偏见
do not bother children when they are skateboarding
 
法则十二:当你在街上遇见一只猫时,摸摸它:关注存在的善
pet a cat when you encounter one on the street
 
《你的格局注定你的解决》
阅读建议:这本书可以买实体书看一下,里面的内容还是很有意义的。加入精读书单。
人的格局是从远见、通透、专注度、内驱力和时间观五个维度体现的。
格局是认知力。认知力的高低取决于远见和通透。
远见是在利益面前保持冷静,在情绪失控前保持克制,在显示一片狼藉中看到光明的未来,在不如己意的苟且里看到诗意和远方,明白一切的有可能和不可能的假定,最终都有可能被打破。
活的通透是能够坦然面对生命的各种馈赠,也能张开双手迎接各种不幸,不逃避,不怨天尤人;是在看清人生不易之后,依然全心全意投入生活,认真而负责的活;是遵从自己的内心需求,按照自己的步伐活出完整的生命。
 
格局是专注度。是捂住耳朵做好眼前事。
格局是内驱力。当别人都在混日子的时候,你没有随波逐流。所有的机遇都是在你全力以赴的路上遇到的。
格局是时间观。在正确的时间做该做的事,减少遗憾。管理好自己的时间,也就是管理好自己的生活。
 
人若没有高度,看到的都是问题;人若没有格局,看到的都是鸡毛蒜皮。
格局不是成长的结果,而是成长的原因。
有格局的人不会和烂事纠缠。
有格局的人不会盲从、盲信,不会随波逐流,而是有清晰的自我定位。
有格局的人早早就为自己的人生布好了局,他们拥有更宽广和开放的心智。 查看全部
# 北京西西弗书店蓝色港湾店
#2020年08月30日11:15:18~
 
《人生十二法则》
阅读感受:这本书简单看看就行了,不需要买回来看。
最好的规则并不会限制我们,反而会推动我们前进,让我们生活得更加充实和自由。
事实是,如果没有规则,我们很快就会称为自己情绪的奴隶,而这种情况是毫无自由而言的。当不受约束地用未经训练的本能做判断时,我们不仅会缺乏追去,还会崇拜那些不值得我们崇拜的品质。
 
最重要的法则是:你必须为自己的人生负责。
 
法则一:获胜的龙虾从不低头:笔直站立,昂首挺胸
Stand up straight with your shoulders back
 
法则二:像照顾生病的宠物一样关心自己:待己如助人
Treat yourself like someone you are responsible for helping
 
法则三:放弃损友:与真心希望你好的人做朋友
Make friends with people who want the best for you
 
法则四:战胜内心的批评家:和昨天的自己比,别和今天的别人比
compare yourself to who you were yesterday, not to who someone else is today
 
法则五:管教你家的小怪物:别让孩子做出令他讨厌的事
do not let your children no anything that makes you dislike them
 
法则六:当痛苦到想诅咒一切:批判世界之前先清理你的房间
set your house in perfect order before you criticize the world
 
法则七:苏格拉底的选择:追求意义,拒绝苟且
pursue What is meaningful(not What is expedient)
 
法则八:不买醉鬼卖的东西:说真话,或者至少别撒谎
tell the truth——or,at least,don't lie
 
法则九:别偷走来访者的问题:假设你聆听的人知道你不知道的事
assume that the person you are listening to might know something you don't
 
法则十:不要无视地毯下的龙:直面问题,言辞精确
be precise in you speech
 
法则十一:不要打扰玩滑板的孩子们:承认现实,反对偏见
do not bother children when they are skateboarding
 
法则十二:当你在街上遇见一只猫时,摸摸它:关注存在的善
pet a cat when you encounter one on the street
 
《你的格局注定你的解决》
阅读建议:这本书可以买实体书看一下,里面的内容还是很有意义的。加入精读书单。
人的格局是从远见、通透、专注度、内驱力和时间观五个维度体现的。
格局是认知力。认知力的高低取决于远见和通透。
远见是在利益面前保持冷静,在情绪失控前保持克制,在显示一片狼藉中看到光明的未来,在不如己意的苟且里看到诗意和远方,明白一切的有可能和不可能的假定,最终都有可能被打破。
活的通透是能够坦然面对生命的各种馈赠,也能张开双手迎接各种不幸,不逃避,不怨天尤人;是在看清人生不易之后,依然全心全意投入生活,认真而负责的活;是遵从自己的内心需求,按照自己的步伐活出完整的生命。
 
格局是专注度。是捂住耳朵做好眼前事。
格局是内驱力。当别人都在混日子的时候,你没有随波逐流。所有的机遇都是在你全力以赴的路上遇到的。
格局是时间观。在正确的时间做该做的事,减少遗憾。管理好自己的时间,也就是管理好自己的生活。
 
人若没有高度,看到的都是问题;人若没有格局,看到的都是鸡毛蒜皮。
格局不是成长的结果,而是成长的原因。
有格局的人不会和烂事纠缠。
有格局的人不会盲从、盲信,不会随波逐流,而是有清晰的自我定位。
有格局的人早早就为自己的人生布好了局,他们拥有更宽广和开放的心智。