“Go 试图将静态类型语言的安全性和性能与动态类型解释语言的方便性和趣味性结合起来。”
-罗布派克
你喜欢去吗?若然,原因为何?会更好吗?你今天能把代码写得更好吗?
对因为 Go 简单而有力;走不会让我等待;其编译速度快,跨平台;Go 使并发编程变得容易;Go 还提供了有用的工具,它有一个很棒的开发社区。可能是的,这就是本书的内容:使用函数式编程(FP风格的编码。
在本章中,我将通过使用斐波那契序列代码示例来分享纯 FP 的好处及其对性能的影响。从一个简单的命令式实现开始,您将探索功能性实现,并在此过程中学习一些测试驱动的开发和基准测试技术。
本章的目标是:
- 以 FP 理论为基础
- 了解如何实施功能解决方案
- 确定哪种类型的 FP 最适合您的业务需求
FP 风格的编程可以帮助您以更简洁、更具表现力的方式编写更少的代码,并且错误更少。这怎么可能?FP 将计算视为对数学函数的求值。FP 利用这个计算模型(以及一些杰出的数学家和逻辑学家的工作)来实现优化和性能提升,而这是使用传统命令式编码技术无法实现的。
开发软件并不容易。您必须首先处理大量的非功能性需求(NFR),例如:
- 复杂性
- 扩展性
- 维修性
- 可靠性
- 并发性
- 可伸缩性
软件变得越来越复杂。典型应用程序中第三方依赖项的平均数量是多少?5 年前那是什么样子?我们的应用程序通常必须与公司内部、合作伙伴以及外部客户的其他服务集成。我们如何管理这种日益增长的复杂性?
应用程序过去常常在有宠物名字的服务器上运行,如 Apollo、Gemini 等。似乎每个客户端都有不同的命名方案。如今,大多数应用程序都部署到云环境中,例如 AWS 或 Google 云平台。您是否有很多在很多服务器上运行的软件应用程序?如果是这样,你应该像对待牛一样对待你的服务器;他们太多了。此外,由于您已经实现了自动扩展,重要的不是单个服务器,而是集群。只要集群中至少有一台服务器为会计部门运行,这才是真正重要的。
数字带来复杂性。你能像乐高积木一样组合你的应用程序吗?你发现编写运行非常快的有用测试很容易吗。或者,您是否觉得代码中有太多的 scaffolding/for
循环?你喜欢如此频繁地处理err != nil
情况吗?你想看一个更简单、更干净的方法来做同样的事情吗?你的应用程序有全局变量吗?您是否有代码始终正确管理其状态并防止所有可能的副作用?比赛条件曾经是个问题吗?
您是否知道应用程序中所有可能的错误情况,并且您是否有适当的代码来处理它们?你能看到代码中任何函数的函数签名,并立即对它的作用有一个直觉吗?
您是否有兴趣了解实现 NFR 的更好方法,并比现在更喜欢开发 Go 软件?寻找银弹?如果是,请继续阅读。(请注意,本书其余部分将以第一人称复数形式书写,因为我们将一起学习。)
本书源代码的 GitHub 存储库是https://github.com/l3x/fp-go 。
如果您将 Go 项目存储在~/myprojects
目录中,则运行cd ~/myprojects; git clone https://github.com/l3x/fp-go.git
。
接下来,在第一个项目目录cd ~/myprojects/fp-go/1-functional-fundamentals/ch01-pure-fp/01_oop
中运行cd
命令。
目录对应于本书的单元和章节:
每一章都按其在书中出现的顺序划分为顺序编号的目录。
首先,让我们确保安装了 Go,正确设置了GOPATH
,并且可以运行 Go 应用程序。
如果您使用的是 macOS,请查看附录中关于如何使用brew
命令安装 Go 的说明;否则,要安装 Go,请访问:http://golang.org/doc/install 。要设置您的GOPATH
,请访问:https://github.com/golang/go/wiki/Setting-GOPATH 。
许多人使用全局GOPATH
存储他们所有 Go 应用程序的源代码,或者经常手动重置其GOPATH
。我发现在为多个客户机处理多个 Go 项目时,这种做法很麻烦,每个客户机都有不同的 Go 版本和第三方依赖关系。
我们将在本章中使用的示例 Go 应用程序没有依赖关系;也就是说,我们不必导入任何第三方软件包。因此,我们需要做的就是运行我们的第一个app--cars.go--is
来验证 Go 是否已安装,设置我们的GOPATH
并键入go run cars.go
:
对于超级简单的项目,使用全局GOPATH
很容易,如本章中的示例。
在第 2 章操作集合中,我们的 Go 应用程序将开始变得更加复杂,我们将学习一种简单、更一致的方法来管理我们的 Go 开发环境。
让我们来看看为什么函数式编程比命令式编程更有效率。
“我们不是历史的创造者。我们是由历史创造的。”
-马丁·路德·金。
几乎所有的计算机硬件都是为执行机器代码而设计的,机器代码是计算机固有的,是以命令式风格编写的。程序状态由内存内容定义,语句是机器语言中的指令,其中每个语句将计算状态向前推进,直至最终结果。命令式程序会随着时间一步一步地改变其状态。高级命令式语言,如 C 和 Go,使用变量和更复杂的语句,但它们仍然遵循相同的范式。由于命令式编程的基本思想在概念上都类似于直接在计算机硬件上运行的低级代码,因此大多数计算机语言——如 Go,也被称为 21 世纪的C——在很大程度上都是命令式的。
命令式编程是一种编程范式,它使用语句来改变程序的状态。它着重于程序如何运行的逐步机制。
该术语通常与声明性编程形成对比。在声明式编程中,我们声明我们想要的结果。我们描述我们想要什么,而不是如何得到它的详细说明。
这里有一个典型的,必须的方法来发现Blazer
在一片汽车中:
var found bool
carToLookFor := "Blazer"
cars := []string{"Accord", "IS250", "Blazer" }
for _, car := range cars {
if car == carToLookFor {
found = true; // set flag
}
}
fmt.Printf("Found? %v", found)
以下是完成相同任务的一种实用方法:
cars := []string{"Accord", "IS250", "Blazer" }
fmt.Printf("Found? %v", cars.contains("Blazer"))
这是九行命令式代码,而在函数式编程(FP风格)中只有两行。
在这种情况下,函数构造通常比循环更清楚地表达我们的意图,当我们想要过滤、转换或聚合数据集中的元素时,函数构造尤其有用。
在命令式示例中,我们必须对*how 进行编码。*我们必须:
- 声明布尔标志
- 声明并设置一个变量值
- 创建一个循环结构
- 比较每个迭代值
- 立旗
在函数示例中,我们声明我们想要做什么。我们能够专注于我们想要完成的事情,而不是用循环结构、设置变量值等机制使代码膨胀。
在 FP 中,迭代由库函数contains()
实现。利用库函数意味着我们的代码更少,并允许库开发人员专注于高效的实现,这些实现通常都经过经验丰富的专业人员的审查和性能增强。我们不必为重复的逻辑编写、调试或测试这样高质量的代码。
现在,让我们看看如何使用面向对象编程范式寻找Blazer
:
type Car struct {
Model string
}
accord := &Car{"Accord"}; is250 := &Car{"IS250"}; blazer := &Car{"Blazer"}
cars := []*Car{is250, accord, blazer}
var found bool
carToLookFor := is250
for _, car := range cars {
if car == carToLookFor {
found = true;
}
}
fmt.Printf("Found? %v", found)
首先,我们声明对象类型:
type Car struct {
Model string
}
type Cars []Car
接下来,我们添加我们的方法:
func (cars *Cars) Add(car Car) {
myCars = append(myCars, car)
}
func (cars *Cars) Find(model string) (*Car, error) {
for _, car := range *cars {
if car.Model == model {
return &car, nil
}
}
return nil, errors.New("car not found")
}
在这里,我们声明了一个全局变量,即myCars
,我们将在其中保持状态,即我们将建造的汽车列表:
var myCars Cars
将三辆车添加到列表中。Car
对象封装了每个对象的数据,cars
对象封装了我们的汽车列表:
func main() {
myCars.Add(Car{"IS250"})
myCars.Add(Car{"Blazer"})
myCars.Add(Car{"Highlander"})
查找Highlander
并打印结果:
car, err := myCars.Find("Highlander")
if err != nil {
fmt.Printf("ERROR: %v", car)
} else {
fmt.Printf("Found %v", car)
}
}
我们使用的是car
对象,但我们基本上执行的操作与简单命令式代码示例中相同。我们确实有具有状态的对象,并且可以向其中添加方法,但底层机制是相同的。我们将状态分配给对象属性,通过调用方法修改内部状态,并推进执行状态,直到达到所需的结果。这是命令式编程。
“精神错乱就是一次又一次地做同样的事情,期望得到不同的结果。”
-爱因斯坦
我们可以用这个疯狂的原则来利用纯函数。
在命令函数执行期间为变量赋值可能会导致在其运行的环境中修改变量。如果我们使用相同的输入再次运行相同的命令函数,结果可能会有所不同。
给定命令函数的结果和相同的输入,每次运行时可能返回不同的结果。这不是疯了吗?
纯功能:
- 将职能部门视为一流公民
- 对于相同的输入,始终返回相同的结果
- 在它们运行的环境中没有副作用
- 不允许外部状态影响其结果
- 不允许变量值随时间变化
纯函数的两个特征包括引用透明性和幂等性:
- 引用透明性:这是在不改变程序行为的情况下,可以用相应的值替换函数调用的地方
- 幂等性:函数调用可以重复调用,每次都产生相同的结果
参考透明的程序更容易优化。让我们看看是否可以使用缓存技术和 Go 的并发特性执行优化。
斐波那契序列是一个数字序列,其中每个数字等于前两个数字相加。下面是一个例子:
1 1 2 3 5 8 13 21 34
1 加 1 等于 2,2 加 3 等于 5,5 加 8 等于 13,依此类推。
让我们使用斐波那契序列来帮助说明一些概念。
递归函数是一个调用自身以将复杂输入分解为简单输入的函数。对于每个递归调用,输入问题必须以最终必须达到基本情况的方式进行简化。
斐波那契序列可以很容易地实现为递归函数:
func Fibonacci(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return Fibonacci(x-2) + Fibonacci(x-1)
}
}
在前面的递归函数(Fibonacci
中,如果输入是0
的简单情况,则返回0。同样,如果输入为1
或2
,则返回1。
输入 0、1 或 2 称为基本情况或停止条件;否则,fib
将调用自身两次,将序列中的前一个值与前一个值相加:
斐波那契(5)计算图
在上图Fibonacci(5)计算图中,我们可以直观地看到 Fibonacci 序列中的第五个元素是如何计算的。我们看到f(3)计算了两次,f(2)计算了三次。仅将1的最终叶节点相加计算8的总和:
func main() {
fib := Fibonacci
fmt.Printf("%vn", fib(5))
}
运行该代码,您将得到8
。递归函数反复执行相同的计算;**f(3)**计算两次,**f(2)**计算三次。图形越深,执行的冗余计算越多。这是非常低效的。你自己试试看。将大于 50 的值传递给fib
并查看等待最终结果的时间。
Go 提供了许多方法来提高这种性能。我们将研究两个选项:记忆和并发。
记忆是一种优化技术,用于存储昂贵函数调用的结果,并在再次出现相同输入时返回缓存结果,从而提高性能。
由于纯函数具有以下两个特性,因此记忆效果良好:
- 对于相同的输入,它们总是返回相同的结果
- 它们在运行环境中没有副作用
让我们利用记忆技术来加速斐波那契计算。
首先,让我们创建一个名为Memoized()
的函数类型,并将斐波那契变量定义为该类型:
type Memoized func(int) int
var fibMem Memoized
接下来,让我们实现Memoize()
函数。这里要实现的关键是,只要我们的应用程序启动,甚至在我们的main()
函数被执行之前,我们的fibMem
变量就会被连接起来。如果我们单步执行代码,我们会看到我们的Memoize
函数被调用。缓存变量被分配,匿名函数被返回并分配给fibMem
函数文字变量。
func Memoize(mf Memoized) Memoized {
cache := make(map[int]int)
return func(key int) int {
if val, found := cache[key]; found {
return val
}
temp := mf(key)
cache[key] = temp
return temp
}
}
Memoize 将一个Memoized()
函数类型作为其输入,并返回一个Memoized()
函数。
在 Memoize 的第一行中,我们创建了一个类型为map
的变量作为缓存,以保存计算得出的斐波那契计算。
接下来,我们创建一个类型为Memoized()
的闭包,它是由Memoize()
函数生成的返回。请注意,闭包是一个内部函数,可以关闭或访问其外部范围内的变量。
在闭包内部,如果我们找到传递的整数的计算,我们将从缓存返回其值;否则我们调用递归斐波那契函数*(*mf
)和整数参数(key
),其返回值将存储在cache[key]
中。下次,当请求相同的键时,它的值将直接从缓存返回。
匿名函数是一个没有名字的函数。当匿名函数包含可以访问其作用域中定义的变量的逻辑时,例如,cache
,如果该匿名函数可以作为参数传递或作为函数调用的值返回(在本例中为 true),那么我们可以将该匿名函数称为 lambda 表达式。
我们将在名为fib
的函数中实现斐波那契序列的逻辑:
func fib(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return fib(x-2) + fib(x-1)
}
}
我们在memoize.go
文件中做的最后一件事是创建以下函数:
func FibMemoized(n int) int {
return fibMem(n)
}
现在,是时候看看我们的线路是否正常工作了。在我们的main()
函数中,当我们执行println
语句时,我们得到了正确的输出。
println(fibonacci.FibMemoized(5))
以下是输出:
5
我们可以通过回顾本章前面显示的Fibonacci(5)
计算图来验证 5 是正确答案。
如果我们使用调试器逐步完成代码,我们会看到fibonacci.FibMemoized(5)
调用以下命令
func FibMemoized(n int) int {
return fibMem(n)
}
n
变量的值为 5。由于fibMem
是预连线的,我们开始在 return 语句中执行(并且我们可以访问已经初始化的cache
变量)。因此,我们开始执行以下代码中显示的return
语句(来自Memoize
函数):
return func(key int) int {
if val, found := cache[key]; found {
return val
}
temp := mf(key)
cache[key] = temp
return temp
}
由于这是第一次通过,缓存中没有条目,我们跳过 if 块的主体并运行temp := mf(key)
调用fib
函数的:
func fib(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return fib(x-2) + fib(x-1)
}
}
由于x
大于 2,我们运行最后一个 else 语句,递归调用fib
两次。对fib
的递归调用将继续,直到达到基本条件并计算并返回最终结果。
让我们看几个简单的代码示例,以了解匿名函数和闭包之间的区别。
下面是一个典型的命名函数:
func namedGreeting(name string) {
fmt.Printf("Hey %s!n", name)
}
以下是匿名函数的示例:
func anonymousGreeting() func(string) {
return func(name string) {
fmt.Printf("Hey %s!n", name)
}
}
现在,让我们同时调用它们,并调用一个匿名内联函数,对 Cindy 说Hey
:
func main() {
namedGreeting("Alice")
greet := anonymousGreeting()
greet("Bob")
func(name string) {
fmt.Printf("Hello %s!n", name)
}("Cindy")
}
输出结果如下:
Hello Alice!
Hello Bob!
Hello Cindy!
现在,让我们看看名为greeting
的闭包,看看它与anonymousGreeting()
函数之间的区别。
由于闭包函数与msg
变量在同一范围内声明,因此闭包可以访问它。msg
变量与闭包处于相同的环境中;稍后,我们将看到闭包的环境变量和数据可以在程序执行期间的稍后时间传递和引用:
func greeting(name string) {
msg := name + fmt.Sprintf(" (at %v)", time.Now().String())
closure := func() {
fmt.Printf("Hey %s!n", msg)
}
closure()
}
func main() {
greeting("alice")
}
输出结果如下:
Hey alice (at 2017-01-29 12:29:30.164830641 -0500 EST)!
在下一个示例中,我们将返回它并将其返回值赋给main
函数中的hey
变量,而不是在greeting()
函数中执行闭包:
func greeting(name string) func() {
msg := name + fmt.Sprintf(" (at %v)", time.Now().String())
closure := func() {
fmt.Printf("Hey %s!n", msg)
}
return closure
}
func main() {
fmt.Println(time.Now())
hey := greeting("bob")
time.Sleep(time.Second * 10)
hey()
}
输出结果如下:
2017-01-29 12:42:09.767187225 -0500 EST
Hey bob (at 2017-01-29 12:42:09.767323847 -0500 EST)!
请注意,时间戳是在msg
变量初始化时,在greeting("bob")
值分配给hey
变量时计算的。
因此,10 秒后,当调用greeting
并执行闭包时,它将引用 10 秒前创建的消息。
此示例显示闭包如何保持状态。闭包允许创建、传递和随后引用状态,而不是在外部环境中操纵状态。
对于函数式编程,您仍然有一个状态,但它只是通过每个函数传递,即使外部作用域(它们的起源地)已经退出,也可以访问它。
在本书的后面,我们将看到一个更现实的例子,说明如何利用闭包来维护 API 所需的应用程序资源的上下文。
另一种加速递归斐波那契函数的方法是使用 Go 的并发结构。
给定表达式result := function1() + function2()
,并行化意味着我们可以在不同的 CPU 内核上运行每个函数,总时间大约是最昂贵的函数返回其结果所需的时间。考虑并行化和并发性的以下解释:
- 并行化:同时执行多个功能(在不同的 CPU 内核中)
- 并发:将一个程序分解成可以独立执行的部分
我建议您查看 Rob Pike 在拍摄的视频并发性不是并行性https://player.vimeo.com/video/49718712 。在这里,他将并发性解释为将复杂问题分解为更小的组件,其中单个组件可以同时运行,从而提高性能,前提是它们之间的通信得到了管理。
Go 通过使用通道的同步和消息传递增强了 Goroutine 的并发执行,并通过Select
语句提供了多路并发控制。
以下语言构造为并行软件构造提供了一个易于理解、使用和推理的模型:
- Goroutine:由 Go 运行时管理的轻量级线程。
- Go 语句s:在与调用代码相同的地址空间中,作为独立的并发控制线程或 Goroutine 启动函数调用执行的
go
指令。 - 通道:一种类型化的管道,通过该管道,您可以使用通道操作符发送和接收值,即
<-
。
在下面的代码中,data
被发送到第一行的channel
。在第二行中,data
被分配了从channel
接收到的值:
channel <- data
data := <-channel
由于 Go 通道的行为类似于 FIFO 队列,其中第一个输入的项目是第一个输出的项目,并且由于 Fibonacci 序列中下一个数字的计算是一个小组件,因此我们的 Fibonacci 序列函数计算似乎是并发实现的一个很好的候选者。
让我们试一试。首先,让我们定义一个Channel
函数,该函数使用通道执行斐波那契计算:
func Channel(ch chan int, counter int) {
n1, n2 := 0, 1
for i := 0; i < counter; i++ {
ch <- n1
n1, n2 = n2, n1 + n2
}
close(ch)
}
首先,我们声明变量n1
和n2
来保存初始序列值0
和1
。
然后,我们为给定的总次数创建一个循环。在每个循环中,我们将下一个序列号发送到通道并计算序列中的下一个数字,直到达到计数器值,这是序列中的最后一个序列号。
以下FibChanneled
函数使用make()
函数创建一个通道,即ch
,并将其定义为包含整数的通道:
func FibChanneled(n int) int {
n += 2
ch := make(chan int)
go Channel(ch, n)
i := 0; var result int
for num := range ch {
result = num
i++
}
return result
}
我们将Channel
(斐波那契)函数作为一个 Goroutine 运行,并将ch
通道和8
编号传递给它,告诉Channel
从斐波那契序列生成前八个编号。
下一步,我们在通道上设置范围,并打印通道在未关闭的情况下产生的任何值。
现在,让我们休息一下,用 Fibonacci 序列例子来检查我们已经完成了什么。
让我们编写一些测试来验证每种技术(简单的递归、记忆和通道化)是否正常工作。我们将使用 TDD 来帮助我们设计和编写更好的代码。
TDD,一种软件开发方法,开发人员从需求开始,首先编写一个简单的测试,该测试将失败。然后,它只编写足够的代码使其通过。它重复地继续这个单元测试模式,直到没有更合理的测试来验证代码是否满足需求。概念是现在就开始工作,以后再完善。在每次测试之后,执行重构以实现更多的特性需求。
再次执行相同或类似的测试,并引入新的测试代码来测试下一个功能部件。该过程根据需要重复多次,直到每个单元按照所需规范运行:
TDD 工作流程图
我们可以开始使用输入值表及其相应的结果值来验证被测函数是否正常工作:
// File: chapter1/_01_fib/ex1_test.go
package fib
import "testing"
var fibTests = []struct {
a int
expected int
}{
{1, 1},
{2, 2},
{3, 3},
{4, 5},
{20, 10946},
{42, 433494437},
}
func TestSimple(t *testing.T) {
for _, ft := range fibTests {
if v := FibSimple(ft.a); v != ft.expected {
t.Errorf("FibSimple(%d) returned %d, expected %d", ft.a, v, ft.expected)
}
}
}
回想一下斐波那契序列是这样的:1 1 2 3 5 8 13 21 34
。这里,第一个元素是1 {1, 1}
,第二个元素是2 {2, 2}
,依此类推。
我们使用 range 语句逐行遍历该表,并根据该行的预期值(ft.expected
检查每个计算结果(v := FibSimple(ft.a)
)。
只有当存在不匹配时,我们才会报告错误。
稍后在ex1_test.go
文件中,我们找到了运行中的基准测试设施,它允许我们检查 Go 代码的性能:
func BenchmarkFibSimple(b *testing.B) {
fn := FibSimple
for i := 0; i < b.N; i++ {
_ = fn(8)
}
}
让我们打开一个终端窗口,将cd
命令写入第一组 Go 代码,这是本书的源代码存储库。对我来说,那个目录是~/clients/packt/dev/fp-go/1-functional-fundamentals/ch01-pure-fp/01_fib
。
在第一个示例中,我使用了~/myprojects/fp-go
路径。我在这本书中实际用来创建代码的路径是~/clients/packt/dev/fp-go
。所以,请不要被这些路径所迷惑。它们是一样的。
另外,在本书后面,当我们开始使用 KISS Glide 时,屏幕截图可能会引用~/dev
目录。它来自于 init 脚本,即MY_DEV_DIR=~/dev
。
以下是该目录中的几个链接:
01_duck@ -> /Users/lex/clients/packt/dev/fp-go/2-design-patterns/ch04-solid/01_duck
01_hof@ -> /Users/lex/clients/packt/dev/fp-go/1-functional-fundamentals/ch03-hof/01_hof
04_onion@ -> /Users/lex/clients/packt/dev/fp-go/2-design-patterns/ch07-onion-arch/04_onion
有关 KISS Glide 的更多信息,请参见附录。
在第一个基准测试中,我们检查了计算斐波那契序列中第八个数字的性能。注意,我们通过了-bench=.
参数,这意味着运行所有基准测试。./...
参数意味着运行此目录中的所有测试以及所有子目录:
当我们请求序列中的第八个数字时,与1302 ns/op
和2224 ns/op
相比,简单的递归实现分别比记忆和通道(优化)版本213 ns/op
运行得更快。
事实上,当简单版本执行一次时,只需要3.94 ns/op
。
Go 的基准测试工具的一个非常酷的特性是,它足够聪明,可以计算出执行被测函数的次数。b.N
的值将每次增加,直到基准跑步者对基准的稳定性感到满意为止。函数在测试下运行得越快,基准设施运行它的次数就越多。基准设施运行函数的次数越多,性能指标就越准确,例如,3.94 ns/op
。
以FibSimple
测试为例。当以1
传递时,表示只需执行一次。因为它只需要3.94 ns/op
,所以我们看到它执行了 10000000 次。然而,当FibSimple
通过40
时,我们看到完成一次操作需要 2509110502 纳秒,并且基准设施足够智能,只能运行一次。通过这种方式,我们可以确保运行基准测试是尽可能准确的,并且它们在合理的时间内运行。那有多好?
由于FibSimple
实现是递归的,并且没有经过优化,因此我们可以测试我们的假设,即计算序列中每个连续数字所需的时间将呈指数增长。我们可以通过调用私有函数benchmarkFibSimple
使用通用测试技术来实现这一点,这样可以避免直接调用测试驱动程序:
func benchmarkFibSimple(i int, b *testing.B) {
for n := 0; n < b.N; n++ {
FibSimple(i)
}
}
func BenchmarkFibSimple1(b *testing.B) { benchmarkFibSimple(1, b) }
func BenchmarkFibSimple2(b *testing.B) { benchmarkFibSimple(2, b) }
func BenchmarkFibSimple3(b *testing.B) { benchmarkFibSimple(3, b) }
func BenchmarkFibSimple10(b *testing.B) { benchmarkFibSimple(4, b) }
func BenchmarkFibSimple20(b *testing.B) { benchmarkFibSimple(20, b) }
func BenchmarkFibSimple40(b *testing.B) { benchmarkFibSimple(42, b) }
我们测试序列中的前四个数字,20
,然后是42
。由于我的计算机计算序列中的第 42 个数字大约需要 3 秒钟,所以我决定不再计算更高的数字。当我们可以很容易地看到指数增长模式时,无需等待更长的时间,而无需等待一分钟以上才能得到结果。
我们的基准测试已经证明,我们对斐波那契序列的简单递归实现的性能与预期一致。这种行为等同于性能差。
让我们看看提高性能的几种方法。
我们已经观察到,我们的FibSimple
实现在给定相同输入的情况下总是返回相同的结果,并且在它运行的环境中没有副作用。例如,如果我们传递FibSimple
一个8
值,我们知道每次结果都是13
。我们利用这一事实利用一种称为 memoization 的缓存技术来创建FibMemoized
函数。
现在,让我们编写一些测试,看看MemoizeFcn
有多有效。
由于我们的fibTests
结构已经在包中的另一个测试中定义,在chapter1/_01_fib/ex1_test.go
中,我们不需要再次定义它。通过这种方式,我们只定义一次测试表,并且我们能够在后续的斐波那契函数实现中重用它,以便对每个解决方案进行合理的逐项比较。
以下是FibMemoized
功能的基本单元测试:
func TestMemoized(t *testing.T) {
for _, ft := range fibTests {
if v := FibMemoized(ft.a); v != ft.expected {
t.Errorf("FibMemoized(%d) returned %d, expected %d", ft.a, v, ft.expected)
}
}
}
除非代码中有 bug,否则它不会返回错误。
这是运行单元测试的一大好处。除非有什么东西坏了,否则你不会听说他们。
我们应该编写单元测试,以便:
- 确保您实现的内容满足您的功能需求
- 利用测试帮助您思考如何最好地实施您的解决方案
- 生成可用于持续集成过程的质量测试
- 验证您的实现是否满足与应用程序其他部分的接口要求
- 使开发集成测试更容易
- 保护您的工作不受其他开发人员的影响,他们可能会实现一个组件,从而在生产中破坏您的代码
以下是基准测试:
func BenchmarkFibMemoized(b *testing.B) {
fn := FibMemoized
for i := 0; i < b.N; i++ {
_ = fn(8)
}
}
与前面一样,在FibSimple
示例中,我们检查了计算斐波那契序列中第八个数字的性能:
func BenchmarkFibMemoized(b *testing.B) {
fn := FibMemoized
for i := 0; i < b.N; i++ {
_ = fn(8)
}
}
func benchmarkFibMemoized(i int, b *testing.B) {
for n := 0; n < b.N; n++ {
FibMemoized(i)
}
}
func BenchmarkFibMemoized1(b *testing.B) {
benchmarkFibMemoized(1, b) }
func BenchmarkFibMemoized2(b *testing.B) {
benchmarkFibMemoized(2, b) }
func BenchmarkFibMemoized3(b *testing.B) {
benchmarkFibMemoized(3, b) }
func BenchmarkFibMemoized10(b *testing.B) {
benchmarkFibMemoized(4, b) }
func BenchmarkFibMemoized20(b *testing.B) {
benchmarkFibMemoized(20, b) }
func BenchmarkFibMemoized40(b *testing.B) {
benchmarkFibMemoized(42, b) }
和前面一样,我们使用1
、2
、3
、4
、20
和42
作为输入,执行一个调用FibMemoized
的测试。
以下是FibChanelled
函数的完整列表:
package fib
import "testing"
func TestChanneled(t *testing.T) {
for _, ft := range fibTests {
if v := FibChanneled(ft.a); v != ft.expected {
t.Errorf("FibChanneled(%d) returned %d, expected %d", ft.a, v, ft.expected)
}
}
}
func BenchmarkFibChanneled(b *testing.B) {
fn := FibChanneled
for i := 0; i < b.N; i++ {
_ = fn(8)
}
}
func benchmarkFibChanneled(i int, b *testing.B) {
for n := 0; n < b.N; n++ {
FibChanneled(i)
}
}
func BenchmarkFibChanneled1(b *testing.B) {
benchmarkFibChanneled(1, b) }
func BenchmarkFibChanneled2(b *testing.B) {
benchmarkFibChanneled(2, b) }
func BenchmarkFibChanneled3(b *testing.B) {
benchmarkFibChanneled(3, b) }
func BenchmarkFibChanneled10(b *testing.B) {
benchmarkFibChanneled(4, b) }
func BenchmarkFibChanneled20(b *testing.B) {
benchmarkFibChanneled(20, b) }
func BenchmarkFibChanneled40(b *testing.B) {
benchmarkFibChanneled(42, b) }
我们使用缓存技术和 Go 的并发特性对原始 Fibonacci 序列逻辑进行了两次优化。我们编写了两个优化实现。更多的优化是可能的。在某些情况下,可以结合优化技术来生成更快的代码。
如果我们所要做的就是编写一个简单的递归版本,然后当我们编译 Go 代码时,Go 编译器会自动生成具有性能优化的目标代码,那该怎么办?
Lazy evaluation: An evaluation strategy that delays the evaluation of an expression until its value is needed, which improves performance by avoiding needless calculations.
让我们从一个命令行到一个纯函数的编程方法。首先,让我们看看命令式sum
函数:
func SumLoop(nums []int) int {
sum := 0
for _, num := range nums {
sum += num
}
return sum
}
整数变量sum
随时间变化或变异;sum
不是一成不变的。纯 FP 中没有 for 循环或变异变量。
那么,我们如何使用纯 FP 迭代一系列元素呢?我们可以使用递归来实现这一点。
Immutable variable: A variable whose value is assigned during runtime and cannot be modified.
请注意,Go 确实有常量,但它们与不可变变量的不同之处在于,值是在编译时分配给常量的,而不是在运行时分配给常量的:
func SumRecursive(nums []int) int {
if len(nums) == 0 {
return 0
}
return nums[0] + SumRecursive(nums[1:])
}
请注意,前面的SumRecursive
函数的最后一行调用自身:SumRecursive(nums[1:])
。这就是递归。
我们听说 Go 中的递归可能很慢。所以,让我们编写一些基准测试来检验它。首先,让我们测试一下基本命令函数SumLoop
的性能:
func benchmarkSumLoop(s []int, b *testing.B) {
for n := 0; n < b.N; n++ {
SumLoop(s)
}
}
func BenchmarkSumLoop40(b *testing.B) { benchmarkSumLoop([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }
结果:花费46.1 ns/op
时间。
现在我们知道了命令式函数SumLoop
需要多长时间,让我们编写一个基准测试,看看递归版本SumRecursive
需要多长时间:
func benchmarkSumRecursive(s []int, b *testing.B) {
for n := 0; n < b.N; n++ {
SumRecursive(s)
}
}
func BenchmarkSumRecursive40(b *testing.B) { benchmarkSumRecursive([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }
结果:花费178 ns/op
时间。
在 Prolog、Scheme、Lua 和 Elixir 等语言中,尾部调用递归速度更快,符合 ECMAScript 6.0 的 JavaScript 引擎采用纯函数式编程。那么,让我们试一试:
func SumTailCall(vs []int) int {
if len(vs) == 0 {
return 0
}
return vs[0] + SumTailCall(vs[1:])
}
基准测试结果:取192 ns/op
。
TCO: A tail call is where the last statement of a function is a function call. An optimized tail call has been effectively replaced with a GoTo
statement, which eliminates the work required to set up the call stack before the function call and restore it afterward.
我们甚至可以使用GoTo
语句来进一步加速尾部调用递归,但它仍然比命令式版本慢三倍。
为什么?这是因为 Go 不提供纯 FP 支持。例如,Go 不执行 TCO,也不提供不变的变量。
我们为什么要在 Go 中使用纯 FP?如果编写富有表现力、易于维护且有洞察力的代码比性能更重要,那么也许。
我们的替代方案是什么?稍后,我们将介绍一些纯 FP 库,它们为我们完成了繁重的工作,并朝着更高的性能迈进。
这就是 Go 中函数编程的全部内容吗?不,不远。Go 编译器目前不支持 TCO,这部分限制了我们在 Go 中使用 FP 的能力;然而,这种情况可能很快就会改变。详见附录如何提出 Go 变更部分。
函数编程的另一个方面是 Go 完全支持的:函数文本。事实证明,这是一种语言必须具备的支持 FP 的最重要的特性。
函数文字:这些函数被视为一种语言的一级公民,例如,任何变量类型,如 int 和 string。在 Go 中,函数可以声明为类型,分配给结构的变量和字段,作为参数传递给其他函数,并作为值从其他函数返回。函数文字是闭包,允许它们访问声明它们的范围。当函数文本在运行时分配给变量时,例如,val := func(x int) int { return x + 2}(5)
,我们可以将该匿名函数称为函数表达式。在 lambda 表达式中,函数文字与 curry 一起使用。(有关 lambda 表达式的详细信息,请参见第 10 章、函子、单群和泛型
请看,{ret = n + 2}
是我们的匿名函数/function literal/closure/lambda 表达式。
我们的函数文字:
- 像函数声明一样编写,但在
func
关键字后面没有函数名 - 这是一个表达
- 可以访问其词法范围内的所有可用变量(在本例中为
n
)
package main
func curryAddTwo(n int) (ret int) {
defer func(){ret = n + 2}()
return n
}
func main() {
println(curryAddTwo(1))
}
结果如下:
3
请注意,我们使用了defer
语句来延迟函数文本的执行,直到返回其周围的函数(curryAddTwo
)。由于我们的匿名函数可以访问其作用域(n
中的所有变量,因此它可以修改n
。修改后的值就是打印的值。
在测试纯函数时,我们只需传递输入参数并验证结果。没有要设置的环境或上下文。不需要存根或模拟。没有副作用。测试再简单不过了。
纯函数可以在水平扩展的多 CPU 环境中并行化以提高性能。然而,考虑到 Go 尚未优化以支持纯函数式编程,Go 中的纯 FP 实现可能无法满足我们的性能要求。我们不会让它妨碍我们利用 Go 的许多有效的非纯函数编程技术。我们已经了解了如何通过添加缓存逻辑和利用 Go 的并发特性来提高性能。我们可以使用许多功能模式,我们很快就会看到如何使用它们。我们还将了解如何利用它们来满足严格的性能要求。
在下一章中,当我们探索使用 FP 编程技术操作集合的不同方法时,您将了解高阶函数。