前言

惰性計算（盡可能延遲表達式求值）是許多函數(shù)式編程語言的特性。惰性集合在需要時提供其元素，無需預(yù)先計算它們，這帶來了一些好處。

首先，您可以將耗時的計算推遲到絕對需要的時候。其次，您可以創(chuàng)造無限個集合，只要它們繼續(xù)收到請求，就會繼續(xù)提供元素。第三，map 和 filter 等函數(shù)的惰性使用讓您能夠得到更高效的代碼（請參閱 參考資料 中的鏈接，加入由 Brian Goetz 組織的相關(guān)討論）。Java 并沒有為惰性提供原生支持，但一些框架和后繼語言支持這種惰性。

假定使用此偽代碼片段來打印列表的長度：

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

如果您嘗試執(zhí)行此代碼，結(jié)果會因為代碼的編程語言類型的不同而有所不同：嚴格或不嚴格（也被稱為惰性）。在嚴格的編程語言中，執(zhí)行（或編譯）此代碼產(chǎn)生一個 DivByZero 異常，原因是列表的第三個元素。在不嚴格的語言中，其結(jié)果是 4，它準確地報告了列表中的項目數(shù)。

畢竟，我調(diào)用的方法是 length()，而不是 lengthAndThrowExceptionWhenDivByZero()！Haskell 是為數(shù)不多的仍在使用的不嚴格語言。可惜的是，Java 不支持不嚴格的計算，但您仍然可以在 Java 中使用惰性的概念。

在 Java 中的惰性迭代器

Java 缺乏對惰性集合的原生支持，但這并不意味著您不能使用 Iterator 模擬一個惰性集合。在本系列的前幾篇文章中，我使用了一個簡單的素數(shù)算法來說明函數(shù)式概念。我會在 上期文章 中介紹的優(yōu)化類的基礎(chǔ)上展開本文的討論，同時提供清單 1 中展示的增強：

清單 1. 確定素數(shù)的簡單算法

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;
}
}

前面的一期文章 詳細討論了這個類是如何確定某個整數(shù)是否是素數(shù)的細節(jié)。在 清單 1 中，我添加了 nextPrimeFrom() 方法，根據(jù)輸入的參數(shù)生成下一個素數(shù)。該方法在本文即將出現(xiàn)的示例中發(fā)揮了重要的作用。

一般情況下，開發(fā)人員認為迭代器會使用集合作為后備存儲，但是支持 Iterator 接口的任何集合都符合這個條件。因此，我可以創(chuàng)建一個素數(shù)的無限迭代器，如清單 2 所示：

清單 2. 創(chuàng)建一個惰性迭代器

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，因為就我們目前所掌握的知識，素數(shù)的數(shù)量是無限的。remove() 方法在此處不適用，所以在意外調(diào)用情況下，會拋出一個異常。沉穩(wěn)的做法是使用 next() 方法，它用一行代碼處理兩件事。第一，它調(diào)用我在 清單 1 中添加的 nextPrimeFrom() 方法，根據(jù)上一個素數(shù)生成下一個素數(shù)。第二，它利用了 Java 在單個語句中完成賦值與返回結(jié)果的能力，更新內(nèi)部的 lastPrime 字段。我在清單 3 中執(zhí)行惰性迭代器：

清單 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中，我創(chuàng)建了一個 PrimeIterator，并驗證它會報告前 50 個素數(shù)。雖然這不是迭代器的典型用法，但它模仿一些惰性集合的有用行為。

使用 LazyList

Jakarta Commons 包括一個 LazyList 類，它結(jié)合使用了裝飾設(shè)計模式和工廠。如果要使用 Commons LazyList，則必須包裝一個現(xiàn)有列表，使其具有惰性，并為新值創(chuàng)建一個工廠。請考慮使用清單 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 中，我創(chuàng)建一個新的空白 ArrayList 并將它包裝在 Commons LazyList.decorate() 方法中，還有一個PrimeFactory 用于生成新值。Commons LazyList 使用列表中已存在的值，不論該值是什么，當對一個尚未賦值的索引調(diào)用 get() 方法時，LazyList 會使用工廠（在本例中為 PrimeFactory()）生成和填充值。PrimeFactory 出現(xiàn)在清單 5 中：

清單 5. LazyList 使用的 PrimeFactory

public class PrimeFactory implements Factory {
private int index = 0;
@Override
public Object create() {
return Prime.indexedPrime(index++);
}
}

所有惰性列表都需要使用某種方法來生成后續(xù)的值。在 清單 2 中，我使用了 next() 方法和 Prime 的 nextPrimeFrom() 方法的組合。對于 清單 4 中的 Commons LazyList，我使用了 PrimeFactory 實例。

Commons LazyList 實現(xiàn)有一個特點，就是在請求新值時，沒有信息傳遞給工廠方法。根據(jù)設(shè)計，它甚至沒有傳遞所請求元素的索引，強制在 PrimeFactory 類上維護當前狀態(tài)。這產(chǎn)生了對返回列表的不必要的依賴（因為它必須初始化為空，以便讓索引和 PrimeFactory 的內(nèi)部狀態(tài)保持同步）。Commons LazyList 是最好的基礎(chǔ)實現(xiàn)，但還有更好的開源替代方案，如 Totally Lazy。

Totally Lazy

Totally Lazy 是一個框架，它將一流的惰性添加到 Java。在 前面的一期文章 中，我介紹過 Totally Lazy，但介紹得并不詳細。該框架的目標之一是使用靜態(tài)導(dǎo)入集合來創(chuàng)建一個高度可讀的 Java 代碼。清單 6 中簡單的素數(shù)查找程序在編寫時充分利用了這個 Totally Lazy 特性：

清單 6. Totally Lazy，充分利用靜態(tài)導(dǎo)入

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 中，在完成靜態(tài)導(dǎo)入后，代碼是非典型的 Java，但有很強的可讀性。Totally Lazy 的部分靈感來自 JUnit 的 Hamcrest 測試擴展的接口。它還使用了 Hamcrest 的一些類。isFactor() 方法變成了對 where() 的調(diào)用，結(jié)合使用了 Totally Lazy 的 remainder() 與 Hamcrest is() 方法。

同樣，factors() 方法變成了針對 range() 對象調(diào)用 filter()，我使用現(xiàn)已熟悉的 reduce() 方法來確定總和。最后，isPrime() 方法使用 Hamcrest 的 equalTo() 方法來確定因數(shù)的總和是否等于遞增的數(shù)字。

細心的讀者會注意到，清單 6 中的實現(xiàn)的確優(yōu)化了我在前面的一期文章 中所提及的實現(xiàn)，使用了更高效的算法來確定因數(shù)。優(yōu)化后的版本如清單 7 所示：

清單 7. 優(yōu)化的素數(shù)查找程序的 Totally Lazy 實現(xiàn)

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() 算法，以獲得平方根下的因數(shù)，然后生成平方根之上的對稱因數(shù)。在 Totally Lazy 中，即使像 divide() 這樣的操作也可以使用連貫接口樣式來表達。第二個變化涉及內(nèi)存，它會自動緩存使用相同參數(shù)的函數(shù)調(diào)用，我已經(jīng)修改了 sumFactors() 方法，以便使用 getFactors() 方法，它是內(nèi)存化的 getFactors() 方法。Totally Lazy 將內(nèi)存實現(xiàn)為框架的一部分，因此，實現(xiàn)此優(yōu)化并不需要更多的代碼，但框架的作者將其拼寫為 memorise()，而不是更傳統(tǒng)的（如在 Groovy 中）memoize()。

像 Totally Lazy 這個名稱所聲明的那樣，Totally Lazy 試圖​​在整個框架中盡可能使用惰性。事實上，Totally Lazy 框架本身就包含了一個 primes() 生成程序，它使用框架的構(gòu)建塊實現(xiàn)素數(shù)的無限序列。請考慮 Numbers 類的節(jié)選代碼，如清單 8 所示：

清單 8. 實現(xiàn)無限素數(shù)的 Totally Lazy 節(jié)選代碼

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() 方法創(chuàng)建了一個新的 Function1，它是一個偽高階函數(shù)的 Totally Lazy 實現(xiàn)，該方法旨在接受單一 Number 參數(shù)，并產(chǎn)生一個 Number 結(jié)果。在本例中，它返回 nextPrime() 方法的結(jié)果。primes 變量已創(chuàng)建，用于存儲素數(shù)的狀態(tài)，使用 2（第一個素數(shù)）作為種子值執(zhí)行計算，并使用一個新的計算來產(chǎn)生下一個素數(shù)。這是惰性實現(xiàn)中的典型模式：保存下一個元素，加上用于產(chǎn)生隨后的值的方法。prime() 方法僅僅是一個包裝程序，圍繞之前執(zhí)行的 prime 計算。

為了確定 清單 8 中的 nextPrime()，Totally Lazy 創(chuàng)建了一個新的 LogicalPredicate，以封裝已確定的素數(shù)，然后創(chuàng)建 nextPrime() 方法，它在 Totally Lazy 中使用良好的接口來確定下一個素數(shù)。

在 Java 中使用低層的靜態(tài)導(dǎo)入，以促進可讀代碼的使用，Totally Lazy 在這方面表現(xiàn)得很出色。許多開發(fā)人員認為 Java 對于內(nèi)部的域特定語言是較差的主機，但 Totally Lazy 消除了這種態(tài)度。它積極地采用惰性，延緩所有可能的操作。

結(jié)束語

在這一期文章中，我探索了惰性計算，首先在 Java 中使用迭代器創(chuàng)建一個模擬惰性集合，然后使用了來自 Jakarta Commons Collections 的基本 LazyList 類。最后，我利用了 Totally Lazy 來實現(xiàn)示例代碼，在內(nèi)部與素數(shù)的惰性無限集合中，使用惰性集合來確定素數(shù)。Totally Lazy 也說明了良好接口表示，并使用靜態(tài)導(dǎo)入來提高代碼的可讀性。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論