Go语言性能优化-两数之和算法性能研究

栏目: Go · 发布时间: 6年前

内容简介:好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,让我们看看今天在里面我尝试的第一道题,有点意思, 不只是单纯的算法,还有数据和是否适合的问题。点开题库,看了第一题,我们看看这道题:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,让我们看看今天在里面我尝试的第一道题,有点意思, 不只是单纯的算法,还有数据和是否适合的问题。

承题

点开题库,看了第一题,我们看看这道题:

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

用了这么多文字描述,其实总结起来就是:数组里那两个数想加等于目标值,找出来这两个数的索引。

题是不难,leetcode给出了两种算法:

  1. 暴力法,循环迭代找出来,时间复杂度O(n^2),空间复杂度是O(1)
  2. 一遍哈希表,时间和空间复杂度都是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语言性能优化-两数之和算法性能研究


以上所述就是小编给大家介绍的《Go语言性能优化-两数之和算法性能研究》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Tales from Facebook

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》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

随机密码生成器
随机密码生成器

多种字符组合密码

SHA 加密
SHA 加密

SHA 加密工具