内容简介:好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,让我们看看今天在里面我尝试的第一道题,有点意思, 不只是单纯的算法,还有数据和是否适合的问题。点开题库,看了第一题,我们看看这道题:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,让我们看看今天在里面我尝试的第一道题,有点意思, 不只是单纯的算法,还有数据和是否适合的问题。
承题
点开题库,看了第一题,我们看看这道题:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
用了这么多文字描述,其实总结起来就是:数组里那两个数想加等于目标值,找出来这两个数的索引。
题是不难,leetcode给出了两种算法:
- 暴力法,循环迭代找出来,时间复杂度O(n^2),空间复杂度是O(1)
- 一遍哈希表,时间和空间复杂度都是O(n)
暴力法
我用 Go 语言(golang)实现了暴力法,下面看看代码。
func TwoSum1(nums []int, target int) []int { n:=len(nums) for i,v:=range nums { for j:=i+1;j<n;j++ { if v+nums[j] == target { return []int{i,j} } } } return nil }
两层循环嵌套,很黄很暴力。这个算法是如果运气好了,循环两遍就出来结果了,如果运气不好,要找的元素正好在最后两位,那么真的是O(n^2)了。
哈希法
Go语言里有map类型,这个默认的Hash实现,基于这个我们用Golang实现哈希法。
func TwoSum2(nums []int, target int) []int { m:=make(map[int]int,len(nums)) for i,v:=range nums { sub:=target-v if j,ok:=m[sub];ok{ return []int{j,i} }else{ m[v]=i } } return nil }
这个算法中规中矩,时间和空间复杂度都是O(n),如果运气好,数组内重复的元素多,空间占用还会再少一些。
测试
写好了算法,还要测试一下,要保证结果是正确的,不能搞乌龙。
package main import ( "flysnow.org/hello/lib" "fmt" ) func main(){ r1:=lib.TwoSum1([]int{2, 7, 11, 15},9) fmt.Println(r1) r2:=lib.TwoSum2([]int{2, 7, 11, 15},9) fmt.Println(r2) }
运行输出:
[0 1] [0 1]
和期望的结果一样,说明我们的算法没有问题。
性能期望
这两种算法,leetcode也给了空间和时间复杂度,从我们自己的代码实现分析看,也是第二种哈希法要比暴力法好的多,真实的情况真的是这样吗?我们用Go语言的基准测试(Benchmark),测试一下。
func BenchmarkTwoSum1(b *testing.B) { b.ResetTimer() for i:=0;i<b.N;i++{ TwoSum1([]int{2, 7, 11, 15},9) } } func BenchmarkTwoSum2(b *testing.B) { b.ResetTimer() for i:=0;i<b.N;i++{ TwoSum2([]int{2, 7, 11, 15},9) } }
运行 ➜ lib go test -bench=. -benchmem -run=none
命令查看Golang Benchmark 测试的结果。
pkg: flysnow.org/hello/lib BenchmarkTwoSum1-8 50000000 26.9 ns/op 16 B/op 1 allocs/op BenchmarkTwoSum2-8 20000000 73.9 ns/op 16 B/op 1 allocs/op
我用的测试用例,直接用题中给的,我们发现在这种测试用例的情况下,我们不看好的暴力法,反而性能比哈希法高出2.5倍,好像和我们想的有点不一样。
数组位置调整
我们看测试的数组,答案就在数组的前两位,这对于暴力法来说,的确有优势,我们把这两个答案2、7调整到数组的末尾,也就是测试数组为 {11, 15, 2, 7}
,看看测试结果。
BenchmarkTwoSum1-8 50000000 29.1 ns/op 16 B/op 1 allocs/op BenchmarkTwoSum2-8 10000000 140 ns/op 16 B/op 1 allocs/op
好吧,这一调,暴力法还是一如既往的坚挺,但是哈希法的性能下降了1倍,把哈希法给调死了。
扩大数组个数
我们发现,数组个数少的时候,暴力法是占有优势的,性能是最好的。下面我们调整下数组的个数,再进行测试。
const N = 10 func BenchmarkTwoSum1(b *testing.B) { nums:=[]int{} for i:=0;i<N;i++{ nums=append(nums,rand.Int()) } nums=append( nums,7,2) b.ResetTimer() for i:=0;i<b.N;i++{ TwoSum1(nums,9) } } func BenchmarkTwoSum2(b *testing.B) { nums:=[]int{} for i:=0;i<N;i++{ nums=append(nums,rand.Int()) } nums=append( nums,7,2) b.ResetTimer() for i:=0;i<b.N;i++{ TwoSum2(nums,9) } }
仔细看上面的代码,我采用自动随机生成数组元素的方式,但是为了保证答案,数组的最后两位还是 7,2
。 先测试下数组大小为10个的情况。
BenchmarkTwoSum1-8 20000000 73.3 ns/op 16 B/op 1 allocs/op BenchmarkTwoSum2-8 2000000 660 ns/op 318 B/op 2 allocs/op
10个元素是,暴力法比哈希法的性能快10倍。
继续调整数组大小为50,直接修改常量 N
就好了,测试50个元素的情况。
BenchmarkTwoSum1-8 2000000 984 ns/op 16 B/op 1 allocs/op BenchmarkTwoSum2-8 500000 3200 ns/op 1451 B/op 6 allocs/op
随着数组大小的增加,哈希法的优势开始凸现,50个数组元素时,相差只有4倍。
从不断的增加数组的大小开始,在我的电脑上,当数组的大小为300时,两者打平,性能一样。
当数组大小为1000时,哈希法的性能已经是暴力法的4倍,反过来了。
当数组大小为10000时,哈希法的性能已经是暴力法的20倍,测试数据如下:
BenchmarkTwoSum1-8 100 21685955 ns/op 16 B/op 1 allocs/op BenchmarkTwoSum2-8 2000 641821 ns/op 322237 B/op 12 allocs/op
从基准测试的数据来看,数组越大,每次操作耗费的时间越长,但是暴力法的耗时增长太大,导致性能低下。
从数据中也可以看出,哈希法是空间换时间的方式,内存占用和分配都比较大。
小结
从这测试和性能分析来看,不存在最优的算法,只存在最合适的。
如果你的数组元素比较少,那么暴力算法是更适合你的。 如果数组元素非常多,那么采用哈希算法就是一个比较好的选择了。
所以,根据我们自己系统的实际情况,来选择合适的算法,比如动态判断数组的大小,采用不同的算法,达到最大的性能。
本文为原创文章,转载注明出处,「总有烂人抓取文章的时候还去掉我的原创说明」欢迎扫码关注公众号 flysnow_org
或者网站 http://www.flysnow.org/ ,第一时间看后续精彩文章。「防烂人备注**……&*¥」觉得好的话,顺手分享到朋友圈吧,感谢支持。
以上所述就是小编给大家介绍的《Go语言性能优化-两数之和算法性能研究》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法题:两数之和
- LeetCode-1-两数之和
- Leetcode 1:两数之和
- LeetCode题解 - 1. 两数之和
- LeetCode 第 1 号问题:两数之和
- LeetCode 1:两数之和 Two Sum
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Tales from Facebook
Daniel Miller / Polity Press / 2011-4-1 / GBP 55.00
Facebook is now used by nearly 500 million people throughout the world, many of whom spend several hours a day on this site. Once the preserve of youth, the largest increase in usage today is amongst ......一起来看看 《Tales from Facebook》 这本书的介绍吧!