likes
comments
collection
share

golang快速入门：函数式编程

作者站长头像
站长
· 阅读数 10

高阶函数

高阶函数，就是接收其他函数作为参数传入，或者把其他函数作为结果返回的函数。

1、 高阶函数实现装饰器模式

装饰器模式（Decorator）是一种软件设计模式，其应用场景是为某个已经存在的功能模块（类或者函数）添加一些「装饰」功能，而又不会侵入和修改原有的功能模块。

package main

import "fmt"

func add(a, b int) int {
    return a + b
}

func main() {
    a := 2
    b := 8
    c := add(a, b)
    fmt.Printf("%d + %d = %d\n", a, b, c)
}

假如在不修改现有 add 函数代码的前提下计算加法运算的执行时间，显然，这可以引入装饰器模式来实现。

package main
import (
    "fmt"
    "time"
)
// 为函数类型设置别名提高代码可读性
type addFunc func(int, int) int
// 加法运算函数
func add(a, b int) int {
    return a + b
}
// 通过高阶函数在不侵入原有函数实现的前提下计算加法函数执行时间
func execTime(f Func) Func {
    return func(a, b int) int {
        start := time.Now() // 起始时间
        c := f(a, b)  // 执行加法运算函数
        end := time.Since(start) // 函数执行完毕耗时
        fmt.Printf("--- 执行耗时: %v ---\n", end)
        return c  // 返回计算结果
    }
}
func main() {
    a := 2
    b := 8
    // 通过修饰器调用加法函数，返回的是一个匿名函数
    decorator := execTime(add)
    // 执行修饰器返回函数
    c := decorator(a, b)
    fmt.Printf("%d + %d = %d\n", a, b, c)
}

递归函数

递归函数指的是在函数内部调用函数自身的函数。

func recursion() {
    recursion() /* 函数调用自身 */
}

在实际开发过程中，某个问题满足以下条件就可以通过递归函数来解决：

  • 一个问题的解可以被拆分成多个子问题的解
  • 拆分前的原问题与拆分后的子问题除了数据规模不同，求解思路完全一样
  • 子问题存在递归终止条件

下面我们就以递归函数的经典示例 —— 斐波那契数列为例

func fibonacci(n int) int {
    if n == 1 {
        return 0
    }
    if n == 2 {
        return 1
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
    result := 0
    for i := 1; i <= 10; i++ {
        result = fibonacci(i)
        fmt.Printf("fibonacci(%d) is: %d\n", i, result)
    }
}

递归函数性能优化

首先我们看一下不同层级数量的调用耗时：

package main

import (
    "fmt"
    "time"
)

type FibonacciFunc func(int) int

// 通过递归函数实现斐波那契数列
func fibonacci(n int) int {
    // 终止条件
    if n == 1 {
        return 0
    }
    if n == 2 {
        return 1
    }
    // 递归公式
    return fibonacci(n-1) + fibonacci(n-2)
}

// 斐波那契函数执行耗时计算
func fibonacciExecTime(f FibonacciFunc) FibonacciFunc {
    return func(n int) int {
        start := time.Now() // 起始时间
        num := f(n)  // 执行斐波那契函数
        end := time.Since(start) // 函数执行完毕耗时
        fmt.Printf("--- 执行耗时: %v ---\n", end)
        return num  // 返回计算结果
    }
}

func main() {
    n1 := 5
    f := fibonacciExecTime(fibonacci)
    r1 := f(n1)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n1, r1)

    n2 := 50
    r2 := f(n2)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, r2)
}

打印结果

--- 执行耗时: 567ns ---
The 5th number of fibonacci sequence is 3
--- 执行耗时: 39.584574922s ---
The 50th number of fibonacci sequence is 7778742049

可以看到， 5 和 50 从序号上看只相差了 10 倍，但是最终体现在递归函数的执行时间上，却是不止十倍百倍的巨大差别（1s = 10亿ns）

通过内存缓存技术优化递归函数性能

通过缓存中间计算结果来避免重复计算，从而提升递归函数的性能。

const MAX = 50
var fibs [MAX]int

// 缓存中间结果的递归函数优化版
func fibonacci2(n int) int {
    if n == 1 {
        return 0
    }

    if n == 2 {
        return 1
    }

    index := n - 1
    if fibs[index] != 0 {
        return fibs[index]
    }

    num := fibonacci2(n-1) + fibonacci2(n-2)
    fibs[index] = num
    return num
}

func main() {
    n1 := 5
    f1 := fibonacciExecTime(fibonacci)
    r1 := f1(n1)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n1, r1)
    n2 := 50
    r2 := f1(n2)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, r2)
    f2 := fibonacciExecTime(fibonacci2)
    r3 := f2(n2)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, r3)
}

打印结果

--- 执行耗时: 500ns ---
The 5th number of fibonacci sequence is 3
--- 执行耗时: 39.90102197s ---
The 50th number of fibonacci sequence is 7778742049
--- 执行耗时: 749ns ---
The 50th number of fibonacci sequence is 7778742049

通过预定义数组 ​​fibs​​ 保存已经计算过的斐波那契序号对应的数值（序号 ​​n​​ 与对应数组索引的映射关系为 ​​n-1​​，因为数组索引从下标 ​​0​​ 开始，而这里的斐波那契序号从 ​​1​​ 开始），这样下次要获取对应序号的斐波那契值时会直接返回而不是调用一次递归函数进行计算。

通过打印结果耗时对比可以看出，执行时间上有了很大的提升。

通过尾递归优化递归函数性能

函数调用底层是通过栈来维护的，对于递归函数而言，如果层级太深，同时保存成百上千的调用记录，会导致这个栈越来越大，消耗大量内存空间，严重情况下会导致栈溢出，为了优化这个问题，可以引入尾递归优化技术来重用栈，降低对内存空间的消耗，提升递归函数性能。

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归。 以计算斐波那契数列的递归函数为例，递归调用 ​​​​fibonacci(n-1)​​​​​ 时，还有 ​​​​fibonacci(n-2)​​​ 没有执行，因此需要保存前面的中间状态，内存开销很大。我们可以这样实现尾递归函数就要重构​​​fibonacci​​​ 函数。

func fibonacciTail(n, first, second int) int {
    if n < 2 {
        return first
    }
    return fibonacciTail(n-1, second, first+second)
}

func fibonacci3(n int) int {
    return fibonacciTail(n, 0, 1) // F(1) = 0, F(2) = 1
}

func main() {
    n1 := 5
    f1 := fibonacciExecTime(fibonacci)
    r1 := f1(n1)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n1, r1)
    n2 := 50
    r2 := f1(n2)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, r2)
    f2 := fibonacciExecTime(fibonacci2)
    r3 := f2(n2)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, r3)
    f3 := fibonacciExecTime(fibonacci3)
    r4 := f3(n2)
    fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, r4)
}

打印结果
--- 执行耗时: 623ns ---
The 5th number of fibonacci sequence is 3
--- 执行耗时: 41.350406309s ---
The 50th number of fibonacci sequence is 7778742049
--- 执行耗时: 816ns ---
The 50th number of fibonacci sequence is 7778742049
--- 执行耗时: 194ns ---
The 50th number of fibonacci sequence is 7778742049

​​first​​ + ​​second​​ 的和赋值给下次调用的 ​​second​​ 参数，当前 ​​second​​ 值赋值给下次调用的 ​​first​​ 参数，就等同于实现了 ​​F(n) = F(n-1) + F(n-2)​​ 的效果，循环往复，不断累加，直到 ​​n​​ 值等于 1（F(1) = 0，无需继续迭代下去），则返回 ​​first​​ 的值，也就是最终的 ​​F(n)​​ 的值。把原来通过递归调用计算结果转化为通过外部传递参数初始化，再传递给下次尾递归调用不断累加，这样就可以保证 ​​fibonacciTail​​ 调用始终是线性结构的更新，不需要开辟新的堆栈保存中间函数调用。

通过打印结果可以看出，尾递归优化版递归函数性能要优于内存缓存技术优化版，并且不需要借助额外的内存空间保存中间结果。

Map-Reduce-Filter 模式

日常开发过程中，要处理数组、切片、字典等集合类型，常规做法都是循环迭代进行处理。

package main

import (
    "fmt"
    "strconv"
)

func salarySum(userMap []map[string]string) int {
    var sum int
    for _, user := range userMap {
        num, _ := strconv.Atoi(user["salary"])
        sum += num
    }
    return sum
}

func main() {
    var salaryMap = []map[string]string{
        {
            "name":   "杜小月",
            "salary": "2000",
        },
        {
            "name":   "和珅",
            "salary": "4000",
        },
        {
            "name":   "纪晓岚",
            "salary": "3500",
        },
    }
    fmt.Printf("用户工资累加结果: %d\n", salarySum(salaryMap))
}

代码几乎没有什么复用性可言：每次处理类似的问题都要重复的编写。

Map-Reduce

Map-Reduce 并不是一个整体，而是要分两步实现：Map 和 Reduce，针对上面的例子，可以通过该模式优化。

先将字典类型转化为一个字符串类型（Map 映射转化函数）

func mapToString(items []map[string]string, f func(map[string]string) string) []string {
    newSlice := make([]string, len(items))
    for _, item := range items {
        newSlice = append(newSlice, f(item))
    }
    return newSlice
}

转化后的切片元素转化为整型后累加起来（Reduce 求和函数）

func fieldSum(items []string, f func(string) int) int {
    var sum int
    for _, item := range items{
        sum += f(item)
    }
    return sum
}

上面例子可以直接调用Map 映射转化函数和Reduce 求和函数。

salarySlice := mapToString(salaryMap, func(user map[string]string) string {
    return user["salary"]
})
sum := fieldSum(salarySlice, func(salary string) int {
    intSalary, _ := strconv.Atoi(salary)
    return intSalary
})
fmt.Printf("用户工资累加结果: %d\n", sum)

这样明显代码复用性、可读性和后续可维护性更好。

Filter 函数

为了让 Map-Reduce 代码更加健壮（排除无效的字段值），或者只对指定范围的数据进行统计计算，还可以在 Map-Reduce 基础上引入 Filter（过滤器），对集合元素进行过滤。

在上面的代码中新增一个 Filter 函数：

func itemsFilter(items []map[string]string, f func(map[string]string) bool) []map[string]string {
    newSlice := make([]map[string]string, len(items))
    for _, item := range items {
        if f(item) {
            newSlice = append(newSlice, item)
        }
    }
    return newSlice
}

应用 Filter 函数对无效用户工资进行过滤，或者排除指定范围工资：

func main() {
    var salaryMap = []map[string]string{
        {
            "name": "杜小月",
            "salary": "1000",
        },
        {
            "name": "洪霞",
            "salary": "2000",
        },
        {
            "name": "纪晓岚",
            "salary": "3000",
        },
        {
            "name": "刘全",
            "salary": "0",
        },
        {
            "name": "和珅",
            "salary": "5000",
        },
        {
            "name": "杏儿",
            "salary": "1500",
        },
    }
    //fmt.Printf("用户工资累加结果: %d\n", salarySum(users))

    validUsers := itemsFilter(salaryMap, func(user map[string]string) bool {
        salary, ok := user["salary"]
        if !ok {
            return false
        }
        intSalary, err := strconv.Atoi(salary)
        if err != nil {
             return false
        }
        if intSalary < 1000 || intSalary > 3500 {
            return false
        }
        return true
    })
    salarySlice := mapToString(validUsers, func(user map[string]string) string {
        return user["salary"]
    })
    sum := fieldSum(salarySlice, func(salary string) int {
        intSalary, _ := strconv.Atoi(salary)
        return intSalary
    })
    fmt.Printf("用工资累加结果: %d\n", sum)
}