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

terry 2年前 (2023-09-27) 阅读数 63 #数据结构与算法

题后

点击打开题库，阅读第一题。我们来看这道题：

对于一个整数数组和一个目标值，在数组中找到两个数字，其和为目标值。
您可以假设每个输入仅对应一个答案，并且相同的元素不能再次使用。
示例：
给定数字 = [2, 7, 11, 15]，目标 = 9
因为 nums[0] + nums[1] = 2 + 7 = 90 , 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）可以看Go语言实用笔记（22）| 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
复制代码

从基准测试数据来看，数组越大，每次操作花费的时间就越长，但暴力破解方法的时间消耗增加太多，导致性能较差。

从数据中也可以看出，哈希法用空间换时间，内存占用和分配相当大。