️This article has been over 2 years since the last update.

本文主要来自如下章节的心得，文章很短

• 《Groovy程序设计》- 使用记忆化改善性能

什么是动态规划？

动态规划(DynamicProgramming)是一个看起来高大上的概念，不过然并卵，它并不是一种算法，也不是一种规划，而是一种对无状态的【纯函数】的一种缓存优化。动态规划通过(状态机+空间 )换时间保存旧的计算结果实现加速运算。大部分情况下，状态机通过Map<hash(args),retVal>实现缓存(memoize)，在实际后端业务中，用于

• 最短路径(也就是爬楼梯之类的题目)
• 规则引擎(避免反复计算费用，折扣)
• 分布式定时任务/负载均衡实现(匈牙利算法)
• JIT Hot Method

本文只介绍“动态规划”的实质，不讲算法。

Groovy中的动态规划

举个例子，下面是某个耗时的无状态函数

1
2
3
4
5

//模拟耗时3s的函数
def longFunc = {i->
    TimeUnit.SECONDS.sleep(3)
    return i
}

执行函数运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//用于计算函数执行耗时
def calcTimeMS = {Closure closure->
    def start = System.currentTimeMillis()
    closure.call()
    def end = System.currentTimeMillis()
    def delta = end-start
    println "take = $delta ms"
}
calcTimeMS({
    longFunc(1)
    longFunc(1)
    longFunc(1)
})
=> 9005ms

函数共耗时了9秒，由于longFunc是无状态的【纯函数】，那么意味着后面两次计算就算之前已经算过了，却还是白白浪费了时间与CPU。

Groovy对此类问题提供了一个无侵入式解决方法memoize()

1
2
3
4
5
6
7
8
9
10
11
12

//加入了memoize
def longFunc = {i->
    TimeUnit.SECONDS.sleep(3)
    return i
}.memoize()
// 再次执行函数
calcTimeMS({
    longFunc(1)
    longFunc(1)
    longFunc(1)
})
=> 3005ms

通过memoize就可以缓存之前的计算结果，以加快总体计算速度，这就是动态规划。

对memoize源码进行分析，可以发现为Closure包装了一个Map<args,retVal>的缓存，Closure本身没有状态，而外部包装却是有状态的。

由于源码太简单了，本文不分析。

总结

总结如下

• Groovy自带源码非常直观，通过无侵入式的memoize构造Map实现状态保存，远离了某些算法书上的各种数学公式
• 动态规划仅仅适用于耗时的【纯函数】，有状态的函数不能使用，后期可以配合FAAS进行微服务调用
• 平时说动态规划难，是指使用动态规划的算法难，比如最短路径问题，动态规划本身只是一个缓存。本博后续会对定时任务、负载均衡的算法进行进一步分析。

参考文献

• [美]Venkat Subramaniam. Groovy程序设计 (图灵程序设计丛书) (Kindle Location 2319). 人民邮电出版社. Kindle Edition.
• 组合数学的一些介绍