简单探索 Java 中的惰性计算

前言

惰性计算（尽可能延迟表达式求值）是许多函数式编程语言的特性。惰性集合在需要时提供其元素，无需预先计算它们，这带来了一些好处。

首先，您可以将耗时的计算推迟到绝对需要的时候。其次，您可以创造无限个集合，只要它们继续收到请求，就会继续提供元素。第三，map 和 filter 等函数的惰性使用让您能够得到更高效的代码（请参阅 参考资料 中的链接，加入由 brian goetz 组织的相关讨论）。java 并没有为惰性提供原生支持，但一些框架和后继语言支持这种惰性。

假定使用此伪代码片段来打印列表的长度：

print length([2+1, 3*2, 1/0, 5-4])

如果您尝试执行此代码，结果会因为代码的编程语言类型的不同而有所不同：严格或不严格（也被称为惰性）。在严格的编程语言中，执行（或编译）此代码产生一个 divbyzero 异常，原因是列表的第三个元素。在不严格的语言中，其结果是 4，它准确地报告了列表中的项目数。

毕竟，我调用的方法是 length()，而不是 lengthandthrowexceptionwhendivbyzero()！haskell 是为数不多的仍在使用的不严格语言。可惜的是，java 不支持不严格的计算，但您仍然可以在 java 中使用惰性的概念。

在 java 中的惰性迭代器

java 缺乏对惰性集合的原生支持，但这并不意味着您不能使用 iterator 模拟一个惰性集合。在本系列的前几篇文章中，我使用了一个简单的素数算法来说明函数式概念。我会在 上期文章 中介绍的优化类的基础上展开本文的讨论，同时提供清单 1 中展示的增强：

清单 1. 确定素数的简单算法

import java.util.hashset;
import java.util.set;
import static java.lang.math.sqrt;
public class prime {
public static boolean isfactor(int potential, int number) {
return number % potential == 0;
}
public static set<integer> getfactors(int number) {
set<integer> factors = new hashset<integer>();
factors.add(1);
factors.add(number);
for (int i = 2; i < sqrt(number) + 1; i++)
if (isfactor(i, number)) {
factors.add(i);
factors.add(number / i);
}
return factors;
}
public static int sumfactors(int number) {
int sum = 0;
for (int i : getfactors(number))
sum += i;
return sum;
}
public static boolean isprime(int number) {
return number == 2 || sumfactors(number) == number + 1;
}
public static integer nextprimefrom(int lastprime) {
lastprime++;
while (! isprime(lastprime)) lastprime++;
return lastprime;
}
}

前面的一期文章 详细讨论了这个类是如何确定某个整数是否是素数的细节。在 清单 1 中，我添加了 nextprimefrom() 方法，根据输入的参数生成下一个素数。该方法在本文即将出现的示例中发挥了重要的作用。

一般情况下，开发人员认为迭代器会使用集合作为后备存储，但是支持 iterator 接口的任何集合都符合这个条件。因此，我可以创建一个素数的无限迭代器，如清单 2 所示：

清单 2. 创建一个惰性迭代器

public class primeiterator implements iterator<integer> {
private int lastprime = 1;
public boolean hasnext() {
return true;
}
public integer next() {
return lastprime = prime.nextprimefrom(lastprime);
}
public void remove() {
throw new runtimeexception("can't change the fundamental nature of the universe!");
}
}

在 清单 2 中，hasnext() 方法始终返回 true，因为就我们目前所掌握的知识，素数的数量是无限的。remove() 方法在此处不适用，所以在意外调用情况下，会抛出一个异常。沉稳的做法是使用 next() 方法，它用一行代码处理两件事。第一，它调用我在 清单 1 中添加的 nextprimefrom() 方法，根据上一个素数生成下一个素数。第二，它利用了 java 在单个语句中完成赋值与返回结果的能力，更新内部的 lastprime 字段。我在清单 3 中执行惰性迭代器：

清单 3. 测试惰性迭代器

public class primetest {
private arraylist<integer> primes_below_50 = new arraylist<integer>() {{
add(2); add(3); add(5); add(7); add(11); add(13);
add(17); add(19); add(23); add(29); add(31); add(37);
add(41); add(43); add(47);
}};
@test
public void prime_iterator() {
iterator<integer> it = new primeiterator();
for (int i : primes_below_50) {
asserttrue(i == it.next());
}
}
}

在 清单 3中，我创建了一个 primeiterator，并验证它会报告前 50 个素数。虽然这不是迭代器的典型用法，但它模仿一些惰性集合的有用行为。

使用 lazylist

jakarta commons 包括一个 lazylist 类，它结合使用了装饰设计模式和工厂。如果要使用 commons lazylist，则必须包装一个现有列表，使其具有惰性，并为新值创建一个工厂。请考虑使用清单 4 中的 lazylist：

清单 4. 测试 commons lazylist

public class primetest {
private arraylist<integer> primes_below_50 = new arraylist<integer>() {{
add(2); add(3); add(5); add(7); add(11); add(13);
add(17); add(19); add(23); add(29); add(31); add(37);
add(41); add(43); add(47);
}};
@test
public void prime_factory() {
list<integer> primes = new arraylist<integer>();
list<integer> lazyprimes = lazylist.decorate(primes, new primefactory());
for (int i = 0; i < primes_below_50.size(); i++)
assertequals(primes_below_50.get(i), lazyprimes.get(i));
}
}

在 清单 4 中，我创建一个新的空白 arraylist 并将它包装在 commons lazylist.decorate() 方法中，还有一个primefactory 用于生成新值。commons lazylist 使用列表中已存在的值，不论该值是什么，当对一个尚未赋值的索引调用 get() 方法时，lazylist 会使用工厂（在本例中为 primefactory()）生成和填充值。primefactory 出现在清单 5 中：

清单 5. lazylist 使用的 primefactory

public class primefactory implements factory {
private int index = 0;
@override
public object create() {
return prime.indexedprime(index++);
}
}

所有惰性列表都需要使用某种方法来生成后续的值。在 清单 2 中，我使用了 next() 方法和 prime 的 nextprimefrom() 方法的组合。对于 清单 4 中的 commons lazylist，我使用了 primefactory 实例。

commons lazylist 实现有一个特点，就是在请求新值时，没有信息传递给工厂方法。根据设计，它甚至没有传递所请求元素的索引，强制在 primefactory 类上维护当前状态。这产生了对返回列表的不必要的依赖（因为它必须初始化为空，以便让索引和 primefactory 的内部状态保持同步）。commons lazylist 是最好的基础实现，但还有更好的开源替代方案，如 totally lazy。

totally lazy

totally lazy 是一个框架，它将一流的惰性添加到 java。在 前面的一期文章 中，我介绍过 totally lazy，但介绍得并不详细。该框架的目标之一是使用静态导入集合来创建一个高度可读的 java 代码。清单 6 中简单的素数查找程序在编写时充分利用了这个 totally lazy 特性：

清单 6. totally lazy，充分利用静态导入

import com.googlecode.totallylazy.predicate;
import com.googlecode.totallylazy.sequence;
import static com.googlecode.totallylazy.predicates.is;
import static com.googlecode.totallylazy.numbers.numbers.equalto;
import static com.googlecode.totallylazy.numbers.numbers.increment;
import static com.googlecode.totallylazy.numbers.numbers.range;
import static com.googlecode.totallylazy.numbers.numbers.remainder;
import static com.googlecode.totallylazy.numbers.numbers.sum;
import static com.googlecode.totallylazy.numbers.numbers.zero;
import static com.googlecode.totallylazy.predicates.wherepredicate.where;
public class prime {
public static predicate<number> isfactor(number n) {
return where(remainder(n), is(zero));
}
public static sequence<number> factors(number n){
return range(1, n).filter(isfactor(n));
}
public static number sumfactors(number n){
return factors(n).reduce(sum);
}
public static boolean isprime(number n){
return equalto(increment(n), sumfactors(n));
}
}

在 清单 6 中，在完成静态导入后，代码是非典型的 java，但有很强的可读性。totally lazy 的部分灵感来自 junit 的 hamcrest 测试扩展的接口。它还使用了 hamcrest 的一些类。isfactor() 方法变成了对 where() 的调用，结合使用了 totally lazy 的 remainder() 与 hamcrest is() 方法。

同样，factors() 方法变成了针对 range() 对象调用 filter()，我使用现已熟悉的 reduce() 方法来确定总和。最后，isprime() 方法使用 hamcrest 的 equalto() 方法来确定因数的总和是否等于递增的数字。

细心的读者会注意到，清单 6 中的实现的确优化了我在前面的一期文章 中所提及的实现，使用了更高效的算法来确定因数。优化后的版本如清单 7 所示：

清单 7. 优化的素数查找程序的 totally lazy 实现

public class primefast {
public static predicate<number> isfactor(number n) {
return where(remainder(n), is(zero));
}
public static sequence<number> getfactors(final number n){
sequence<number> lowerrange = range(1, squareroot(n)).filter(isfactor(n));
return lowerrange.join(lowerrange.map(divide().apply(n)));
}
public static sequence<number> factors(final number n) {
return getfactors(n).memorise();
}
public static number sumfactors(number n){
return factors(n).reduce(sum);
}
public static boolean isprime(number n){
return equalto(increment(n), sumfactors(n));
}
}

清单 7 中有两个主要变化。首先，我改进了 getfactors() 算法，以获得平方根下的因数，然后生成平方根之上的对称因数。在 totally lazy 中，即使像 divide() 这样的操作也可以使用连贯接口样式来表达。第二个变化涉及内存，它会自动缓存使用相同参数的函数调用，我已经修改了 sumfactors() 方法，以便使用 getfactors() 方法，它是内存化的 getfactors() 方法。totally lazy 将内存实现为框架的一部分，因此，实现此优化并不需要更多的代码，但框架的作者将其拼写为 memorise()，而不是更传统的（如在 groovy 中）memoize()。

像 totally lazy 这个名称所声明的那样，totally lazy 试图​​在整个框架中尽可能使用惰性。事实上，totally lazy 框架本身就包含了一个 primes() 生成程序，它使用框架的构建块实现素数的无限序列。请考虑 numbers 类的节选代码，如清单 8 所示：

清单 8. 实现无限素数的 totally lazy 节选代码

public static function1<number, number> nextprime = new function1<number, number>() {
@override
public number call(number number) throws exception {
return nextprime(number);
}
};
public static computation<number> primes = computation(2, computation(3, nextprime));
public static sequence<number> primes() {
return primes;
}
public static logicalpredicate<number> prime = new logicalpredicate<number>() {
public final boolean matches(final number candidate) {
return isprime(candidate);
}
};
public static number nextprime(number number) {
return iterate(add(2), number).filter(prime).second();
}

nextprime() 方法创建了一个新的 function1，它是一个伪高阶函数的 totally lazy 实现，该方法旨在接受单一 number 参数，并产生一个 number 结果。在本例中，它返回 nextprime() 方法的结果。primes 变量已创建，用于存储素数的状态，使用 2（第一个素数）作为种子值执行计算，并使用一个新的计算来产生下一个素数。这是惰性实现中的典型模式：保存下一个元素，加上用于产生随后的值的方法。prime() 方法仅仅是一个包装程序，围绕之前执行的 prime 计算。

为了确定 清单 8 中的 nextprime()，totally lazy 创建了一个新的 logicalpredicate，以封装已确定的素数，然后创建 nextprime() 方法，它在 totally lazy 中使用良好的接口来确定下一个素数。

在 java 中使用低层的静态导入，以促进可读代码的使用，totally lazy 在这方面表现得很出色。许多开发人员认为 java 对于内部的域特定语言是较差的主机，但 totally lazy 消除了这种态度。它积极地采用惰性，延缓所有可能的操作。

结束语

在这一期文章中，我探索了惰性计算，首先在 java 中使用迭代器创建一个模拟惰性集合，然后使用了来自 jakarta commons collections 的基本 lazylist 类。最后，我利用了 totally lazy 来实现示例代码，在内部与素数的惰性无限集合中，使用惰性集合来确定素数。totally lazy 也说明了良好接口表示，并使用静态导入来提高代码的可读性。

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