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

好多人都在刷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

从基准测试的数据来看,数组越大,每次操作耗费的时间越长,但是暴力法的耗时增长太大,导致性能低下。

从数据中也可以看出,哈希法是空间换时间的方式,内存占用和分配都比较大。

小结

从这测试和性能分析来看,不存在最优的算法,只存在最合适的。

如果你的数组元素比较少,那么暴力算法是更适合你的。 如果数组元素非常多,那么采用哈希算法就是一个比较好的选择了。

所以,根据我们自己系统的实际情况,来选择合适的算法,比如动态判断数组的大小,采用不同的算法,达到最大的性能。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Web行业观察

0.30000000000000004

0.30000000000000004问题是计算机科学领域的经典BUG, 由比尔盖茨那一代人标准化的浮点数表示法造福了一代人也祸害了一代人, 由...

4173
来自专栏数据结构与算法

P1044 栈

题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一...

3056
来自专栏阿凯的Excel

八种方式实现多条件匹配

之前在Excel内部的分享交流群和别的讲师探讨了多条件匹配有哪些实现方式。 围观的市民刘先生表示:我活了二十多年,看见斗图的比较多,这么无聊斗Excel使用技巧...

3414
来自专栏偏前端工程师的驿站

JS魔法堂:彻底理解0.1 + 0.2 === 0.30000000000000004的背后

Brief                                 一天有个朋友问我“JS中计算0.7 * 180怎么会等于125.9999999999...

3046
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

3144
来自专栏Python小屋

Python中else关键字的常见用法

Python中的else常见用法有三:选择结构、循环结构和异常处理结构。 (1)选择结构 这应该是最常见的用法,与关键字if和elif组合来使用,用来说明条件不...

29710
来自专栏章鱼的慢慢技术路

Luhn算法检验和验证

2256
来自专栏数据处理

mat(矩阵)与array(数组)区别

2483
来自专栏小红豆的数据分析

小蛇学python(16)numpy高阶用法

如果只是从事简单的数据分析,其实numpy的用处并不是很大。简单了解一下numpy,学好pandas已经够用,尤其是对于结构化或表格化数据。但是精通面向数组的编...

1482
来自专栏Crossin的编程教室

【编程课堂】震惊!小 bug 引发大灾难,0.1 + 0.2 的结果竟然是……

各位观众点进标题看文章的时候,我已经准备打包行李去UC报道啦~ 冷笑话结束,嗯,说正事。 请大家思考一下在 python 控制台输入 0.1 + 0.2 ==...

2859

扫码关注云+社区

领取腾讯云代金券