深入学习java内存化和函数式协同

前言

所有编程语言都在增加函数特性，因为运行时已变得强大到足够适应性能或内存开销。函数式编程的许多收益之一是，您可将麻烦或容易出错的任务卸载到运行时。另一个收益是将函数特性简洁地组合到您代码中的能力。

在本期文章中，我将探讨 java 下一代语言中的内存化。然后，通过利用 clojure 示例，我将展示通过利用函数特性之间的协调作用，如何实现常见问题的一般解决方案。

内存化

内存化 这个词是 donald michie（一位英国人工智能研究人员）发明的，用于表示重复的值的函数级缓存。如今，内存化在函数式编程语言中很常见，它要么被用作一个内置特性，要么被用作一个相对容易实现的特性。

内存化在以下场景中很有帮助。假设您必须反复调用一个注重性能的函数。一个常见解决方案是构建内部缓存。每次计算某个参数集的值时，您都会将该值放入缓存中，作为参数值的线索。在未来，如果该函数使用以前的参数调用，那么它将会从缓存返回值，而不是重新计算它。函数缓存是一种经典的计算机科学权衡：它使用更多内存（我们常常拥有丰富的内存）来不断实现更高的性能。

函数必须是纯粹的，缓存技术才能发挥其作用。纯函数 是没有副作用的函数：它没有引用任何其他易变的类字段，没有设置除返回值以外的任何值，而且仅依赖于参数作为输入。java.lang.math 类中的所有方法都是纯函数的良好示例。显然，只有在函数可靠地为一组给定的参数返回相同值时，您才能成功地重用缓存的结果。

groovy 中的内存化

内存化在 groovy 中很简单，groovy 在 closure 类上包含一系列 memoize() 函数。例如，假设您有一个昂贵的哈希算法，以至于您需要缓存结果来提高效率。为此，您可以使用闭包块语法来定义方法，在返回时调用 memoize() 函数，如清单 1 所示。我并不是暗示清单 1 中使用的 rot13 算法（即凯撒密码 的一个版本）的性能面临挑战，只是假设缓存在这个示例中很重要。

清单 1. groovy 中的内存化

class namehash {
def static hash = {name ->
name.collect{rot13(it)}.join()
}.memoize()
public static char rot13(s) {
char c = s
switch (c) {
case 'a'..'m':
case 'a'..'m': return c + 13
case 'n'..'z':
case 'n'..'z': return c - 13
default: return c
}
}
}
class namehashtest extends groovytestcase {
void testhash() {
assertequals("ubzre", namehash.hash.call("homer")) }
}

正常情况下，groovy 函数定义看起来像清单 1 中的 rot13()，方法主体位于参数列表之后。hash() 函数定义使用了稍微不同的语法，将代码块分配给 hash 变量。该定义的最后一部分是对 memoize() 的调用，它自动为重复的值创建一个内部缓存，与该参数建立联系。

memoize() 方法实际上是一个方法系列，为您提供了对缓存特征的一定控制，如表 1 所示。

表 1. groovy 的 memoize() 系列

方法	用途
memoize()	返回闭包的一个包含缓存的实例
memoizeatmost()	为缓存元素的数量设置一个上限
memoizeatleast(int protectedcachesize)	为缓存元素的数量设置一个下限，保护一定数量的元素免遭垃圾收集
memoizebetween(int protectedcachesize, int maxcachesize)	为缓存元素的数量设置一个下限和上限

表 1 中的方法为您提供了对缓存特征粗粒度的控制，这不是直接调优缓存特征的细粒度方式。内存化应是一种通用机制，您可以用它来轻松优化常见的缓存情形。

clojure 中的内存化

内置于 clojure 中的内存化。您可以使用 (memoize ) 函数内存化任何函数。例如，如果您已经拥有一个 (hash "homer") 函数，那么您可以通过 (memoize (hash "homer")) 针对一个缓存版本而对其进行内存化。清单 2 在 clojure 中实现了 清单 1 中的名称哈希示例。

清单 2. clojure 内存化

(defn name-hash [name]
(apply str (map #(rot13 %) (split name #"\d"))))
(def name-hash-m (memoize name-hash))
(testing "name hash"
(is (= "ubzre" (name-hash "homer"))))
(testing "memoized name hash"
(is (= "ubzre" (name-hash-m "homer")))))

请注意，在 清单 1 中，调用内存化的函数需要调用 call() 方法。在 clojure 版本中，内存化的方法调用在表面上完全相同，但增加了对方法用户不可见的间接性和缓存。

scala 中的内存化

scala 没有直接实现内存化，但有一个名为 getorelseupdate() 的集合方法来处理实现它的大部分工作，如清单 3 所示。

清单 3. scala 内存化

def memoize[a, b](f: a => b) = new (a => b) {
val cache = scala.collection.mutable.map[a, b]()
def apply(x: a): b = cache.getorelseupdate(x, f(x))
}
def namehash = memoize(hash)

清单 3 中的 getorelseupdate() 函数是建立缓存的完美的运算符。它检索匹配的值，或者在没有匹配值时创建一个新条目。

组合函数特性

通过复合 (composition) 来组合

复合 在软件开发中有许多含义。函数复合 指组合函数来获得复合结果的能力。在数学术语中，如果您有一个 f(x) 函数和一个 g(x) 函数，那么您应能够执行 f(g(x))。在软件术语中，如果您有一个将字符串转换为大写的 a() 函数和一个删除过量空格的 b() 函数，那么复合函数将执行这两项任务。

在上一节和前几期 java 下一代 文章中，我介绍了函数式编程的许多细节，尤其是与 java 下一代语言相关的细节。但是，函数式编程的真正强大之处在于各种特性与解决方案的执行方式的组合。

面向对象的程序员倾向于不断创建新数据结构和附带的运算。毕竟，构建新类和在它们之间传递的消息是主要的语言模式。但是构建如此多的定制结构，会使在最低层级上构建可重用代码变得很困难。函数式编程语言引用一些核心代码结构并构建优化的机制来理解它们。

以下是一个示例。清单 4 给出了来自 apache commons 框架的 indexofany() 方法，该框架为 java 编程提供了大量帮助器。

清单 4. 来自 apache commons 的 indexofany()

// from apache commons lang, http://commons.apache.org/lang/
public static int indexofany(string str, char[] searchchars) {
if (isempty(str) || arrayutils.isempty(searchchars)) { 
return index_not_found;
}
int cslen = str.length();
int cslast = cslen - 1;
int searchlen = searchchars.length;
int searchlast = searchlen - 1;
for (int i = 0; i < cslen; i++) {
char ch = str.charat(i);
for (int j = 0; j < searchlen; j++) { 
if (searchchars[j] == ch) {
if (i < cslast && j < searchlast && charutils.ishighsurrogate(ch)) {
if (searchchars[j + 1] == str.charat(i + 1)) {
return i;
}
} else {
return i;
}
}
}
}
return index_not_found;
}

清单 4 中 1/3 的代码负责边缘检查和实现嵌套迭代所需的变量的初始化。我将逐步将此代码转换为 clojure。作为第一步，我将删除边角情形，如清单 5 所示。

清单 5. 删除边角情形

public static int indexofany(string str, char[] searchchars) {
when(searchchars) {
int cslen = str.length();
int cslast = cslen - 1;
int searchlen = searchchars.length;
int searchlast = searchlen - 1;
for (int i = 0; i < cslen; i++) {
char ch = str.charat(i);
for (int j = 0; j < searchlen; j++) {
if (searchchars[j] == ch) {
if (i < cslast && j < searchlast && charutils.ishighsurrogate(ch)) {
if (searchchars[j + 1] == str.charat(i + 1)) {
return i;
}
} else {
return i;
}
}
}
}
return index_not_found;
}
}

clojure 会智能地处理 null 和 empty 情形，拥有 (when ...) 等智能函数，该函数仅在字符存在时返回 true。clojure 具有动态（且强）类型，消除了在使用前声明变量类型的需求。因此，我可以删除类型声明，获得清单 6 中所示的代码。

清单 6. 删除类型声明

indexofany(str, searchchars) {
when(searchchars) {
cslen = str.length();
cslast = cslen - 1;
searchlen = searchchars.length;
searchlast = searchlen - 1;
for (i = 0; i < cslen; i++) {
ch = str.charat(i);
for (j = 0; j < searchlen; j++) {
if (searchchars[j] == ch) { 
if (i < cslast && j < searchlast && charutils.ishighsurrogate(ch)) {
if (searchchars[j + 1] == str.charat(i + 1)) {
return i;
}
} else {
return i;
}
}
}
}
return index_not_found;
}
}

for 循环 （命令式语言的主要元素）允许依次访问每个元素。函数式语言倾向于更多地依靠集合方法，这些方法已理解（或避免）了边角情形，所以我可删除 ishighsurrogate()（它检查字符编码）等方法和索引指针的操作。此转换的结果如清单 7 所示。

清单 7. 一个用于替换最里面的 for 的 when 子句

// when clause for innermost for
indexofany(str, searchchars) {
when(searchchars) {
cslen = str.length(); 
for (i = 0; i < cslen; i++) { 
ch = str.charat(i);
when (searchchars(ch)) i;
}
}
}

在清单 7 中，我将代码折叠到一个方法中，该方法会检查受欢迎的字符是否存在，在找到这些字符时，它会返回其索引。尽管我既未使用 java 也未使用 clojure，而是提供了一段陌生的伪代码，但这个 when 方法并不总是存在。但 clojure 中还有 (when ) 方法，此代码会慢慢变成该方法。

接下来，我将最顶层的 for 循环替换为一种更加简洁的代码，使用 for comprehension： 一个结合了集合的访问和过滤（等）的宏。演变后的代码如清单 8 所示。

清单 8. 添加一个 comprehension

// add comprehension
indexofany(str, searchchars) {
when(searchchars) {
for ([i, ch] in indexed(str)) { 
when (searchchars(ch)) i;
}
}
}

要理解清单 8 中的 for comprehension，首先您必须理解一些部件。clojure 中的 (indexed ...) 函数接受一个 sequence

并返回一个包含编号的元素的序列。例如，如果我调用 (indexed '(a b c))，返回值为 ([0 a] [1 b] [2 c])。（单个撇号告诉 clojure，我想要一个字符的文字序列，但并不希望执行一个包含两个参数的 (a )。）for comprehension 在我的搜索字符上创建这个序列，然后应用内部的 when 来查找匹配字符的索引。

此转换的最后一步是将代码转换为合适的 clojure 语法，还原真实函数和语法的外观，如清单 9 所示。

清单 9. clojure 化的代码

// clojure-ify
(defn index-filter [pred coll] 
(when pred 
(for [[index element] (indexed coll) :when (pred element)] index)))

在清单 9 中的最终的 clojure 版本中，我将语法转换为合适的 clojure 并添加一次升级：此函数的调用方现在可传递任何判定函数（一个返回布尔值结果的函数），而不只是检查一个空字符串。clojure 的一个目标是实现创建可读的代码的能力（在您理解圆括号之后），而且这个函数证实了这种能力：对于带索引的集合，在您的判定与元素匹配时，将会返回索引。

clojure 的另一个目标是使用最少量的字符来表达清楚目的；在这方面，java 与 clojure 相差甚远。表 2 比较了 清单 4 中的 “移动部件” 和 清单 9 中的相应部件。

表 2.比较 “移动部件”

	要求	函数
函数	1	1
类	1	0
内部退出点	2	0
变量	3	0
分支	4	0
布尔运算符	1	0
函数调用	6	3
总计	18	4

复杂性上的差异一目了然。尽管 clojure 代码更简单，但它也更加通用。这里，我对一个硬币翻转序列建立了索引，建模为 clojure :h（头）和 :t（尾）关键字：

(index-filter #{:h} [:t :t :h :t :h :t :t :t :h :h]) 
-> (2 4 8 9)

请注意，返回值是所有匹配的索引位置的序列，而不只是第一个。clojure 中的列表操作尽可能是 惰性的，包括这一个操作。如果我仅想要第一个值，那么我可以通过 (take 1 ) 从结果中获得该值，或者我可以全部打印它们，就像我在这里所做的那样。

我的 (index-filter ) 函数是通用的，所以我可在数字上使用它。例如，我可确定其斐波纳契值超过 1,000 的第一个数字：

(first 
(index-filter #(> % 1000) (fibo)))
-> 17

(fibo) 函数返回一个没有限制但惰性的斐波纳契数字序列；(index-filter ) 找到第一个超过 1,000 的值。（事实证明，18 的斐波纳契值为 1,597。）函数结构、动态类型、惰性和简洁语法相结合，得到的是更强大的功能。

惰性

惰性 — 尽可能延迟表达式计算 — 是函数式语言在不需要或只需很少开发人员成本的情况下添加功能的另一个优秀示例。请参阅 “函数式思维：探索 java 中的惰性计算” 和 “函数式思维：深入剖析惰性计算”，了解 java 下一代语言中的惰性讨论和示例。

结束语

函数式编程结构在零散使用时可带来优势，在结合使用它们时会带来更多的优势。所有 java 下一代语言在一定程度上都是函数式的，支持增加这种开发风格的使用。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。