阿猫的博客

阿猫的博客

Go 函数式编程:从一个 for 循环讲起

Go
312
2024-02-17

背景

有一天,有一只刚毕业的猫去面试,面试官说:写一个函数,过滤一个切片里的所有奇数,留下所有的偶数。

这很简单,他马上写出了以下代码:

package main

func Filter(s []int) []int {
    result := []int{}
    for _, v := range s {
       if v%2 == 0 {
          result = append(result, v)
       }
    }
    return result
}

func main() {
	s := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

	result := Filter(s)

	for _, v := range result {
		println(v)
	}
}

需求变更:只要 3 的倍数

面试官似乎不满意,他说:现在来了一个产品经理,他希望在新的列表中只保留 3 的倍数。

猫心想,把原来的函数复制粘贴一下,把原来的 2 改成 3 不就行了?他再想,不对,一定没有这么简单,面试官一定是希望代码能复用起来。于是他写:

func Filter(s []int, keep int) []int {
	result := []int{}
    for _, v := range s {
       if v%keep == 0 {
          result = append(result, v)
       }
    }
    return result
}

技术调整:数字是 int64

面试官眉头开始皱起来了,但他还是继续说:现在技术做了点调整,这个切片里的数字都是 int64 类型的。

猫汗流浃背了,总不能把之前的函数再复制一份,然后把函数签名里的 int 改成 int64 吧?

见猫不出声,面试官提示了一下:要不看看泛型

泛型是 Go 1.18 新引入的特性,允许声明和使用能够作用在一系列由调用代码提供的类型上的函数或类型。

尽管比较生疏,猫还是写下了以下的代码:

func Filter[V int | int64](s []V, keep V) []V {
	result := []V{}
	for _, v := range s {
		if v%keep == 0 {
			result = append(result, v)
		}
	}
	return result
}

注:% 运算符仅在类int 类型上定义(如int64,uint等),Go 暂时没有提供一个类型名称给这些类型,因此在声明类型约束时,只能写 [V int | int64](可以根据需要加上其他类int类型)。

残酷现实:以不变应万变

面试官又继续说:那如果给你的切片里是一个结构体呢?如果过滤逻辑很长呢?如果过滤逻辑里需要查库、调接口呢?

猫听得晕头转向,只好尴尬的说不会了。

面试官今天心情看起来不错,他接着说:你看看你写的这些代码,有什么共通点?是不是都是一个 for 循环,中间包裹了业务逻辑?能不能把共同的部分抽象出来,把业务逻辑的函数当作参数传入?对于过滤这个场景,业务逻辑是不是能抽象成一个这样的函数:

func keepFunc[V any](item V) bool

在循环中不停执行这个函数,由这个函数决定是否保留对应的元素。于是代码能够改造成:

type keepFunc[V any] func(V) bool

func Filter[V any](s []V, f keepFunc[V]) []V {
	result := []V{}
	for _, v := range s {
		if f(v) {
			result = append(result, v)
		}
	}
	return result
}

至于是保留 2 的倍数还是 3 的倍数,可以在调用时通过匿名函数决定。

result := Filter(s, func(v int) bool {
		return v%2 == 0
	})

就算切片里是一个结构体,同样可以访问其某些成员变量来决定是否保留。如果有更加复杂的逻辑,也可以将逻辑抽取出来,将判断函数放在参数里传入,这就是函数式编程的特点之一——函数是“第一等公民”。

所谓"第一等公民"(first class),指的是函数与其他数据类型一样,处于平等地位,可以赋值给其他变量,也可以作为参数,传入另一个函数,或者作为别的函数的返回值。

func filterBy2(v int) bool {
	return v%2 == 0
}
...
result := Filter(s, filterBy2)

渐入佳境:使用并发优化性能

我们知道,对于大量 IO 的场景,并发能有效提升性能。而函数式编程还有以下这个特点:没有"副作用"——函数要保持独立,所有功能就是返回一个新的值,没有其他行为,尤其是不得修改外部变量的值。因此使用函数式编程的代码很适合实现并发编程。同时,由于业务逻辑独立在一个函数中,把过滤的逻辑改成并发甚至不需要去修改业务代码。

我们利用 Go 并发的知识,很容易就给前面的 Filter 加上了并发:

func FilterAsync[V any](s []V, f keepFunc[V]) []V {
	var wg sync.WaitGroup
	resultChan := make(chan V, len(s))

	for _, v := range s {
		wg.Add(1)
		go func(v V) {
			defer wg.Done()
			if f(v) {
				resultChan <- v
			}
		}(v)
	}

	go func() {
		wg.Wait()
		close(resultChan)
	}()

	result := []V{}
	for v := range resultChan {
		result = append(result, v)
	}

	return result
}

func FilterWithOrder[V any](collection []V, f keepFunc[V]) []V {
	var wg sync.WaitGroup
	resultChans := make([]chan V, len(collection))

	for i := range collection {
		resultChans[i] = make(chan V, 1)
		wg.Add(1)
		go func(i int, v V) {
			defer wg.Done()
			if f(v) {
				resultChans[i] <- v
			}
		}(i, collection[i])
	}

	go func() {
		wg.Wait()
		for i := range resultChans {
			close(resultChans[i])
		}
	}()

	result := []V{}
	for i := range resultChans {
		for v := range resultChans[i] {
			result = append(result, v)
		}
	}

	return result
}

注:由于 goroutine 的执行时间有随机性,因此 FilterAsync 返回的顺序不一定与原来一致,因此实现了一个FilterWithOrder ,通过多循环一遍来保持顺序,会有一定的性能损耗。

我们再写一个测试来验证一下这几个函数的性能。注意我们随机 sleep 了一下来模拟 IO 操作产生的影响。

func BenchmarkFilter(b *testing.B) {
	s := make([]int, 1e4)
	for i := range s {
		s[i] = i
	}
	f := func(v int) bool {
		time.Sleep(time.Duration(rand.Intn(100)) * time.Microsecond)
		return v%2 == 0
	}

	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		Filter(s, f)
	}
}

注:因篇幅限制,省略了一部分测试代码。

结果如下:

BenchmarkFilter-10                     2         605060292 ns/op          169248 B/op         17 allocs/op
BenchmarkFilterAsync-10              214           5585200 ns/op         1723336 B/op      29925 allocs/op
BenchmarkFilterWithOrder-10          196           6069507 ns/op         3083992 B/op      39932 allocs/op

可以看到,比起单纯的 for 循环,增加了 gouroutine 的两个方法快了约 100 倍

但是函数式编程的缺点也很明显:使用了更多的内存。而如果把 sleep 去掉,即使使用异步,使用函数式编程也比单纯使用 for 循环更慢。

最后

猫如梦初醒,摇头晃脑地坐上了回家的地铁。他在小本本上写:

函数式编程,代码简洁、可读性好,而且适合并发编程;但是有性能损耗,在 CPU 密集型场景优化不明显,但是能优化 IO 操作。

Reference