前言

所有編程語(yǔ)言都在增加函數(shù)特性，因?yàn)檫\(yùn)行時(shí)已變得強(qiáng)大到足夠適應(yīng)性能或內(nèi)存開(kāi)銷。函數(shù)式編程的許多收益之一是，您可將麻煩或容易出錯(cuò)的任務(wù)卸載到運(yùn)行時(shí)。另一個(gè)收益是將函數(shù)特性簡(jiǎn)潔地組合到您代碼中的能力。

在本期文章中，我將探討 Java 下一代語(yǔ)言中的內(nèi)存化。然后，通過(guò)利用 Clojure 示例，我將展示通過(guò)利用函數(shù)特性之間的協(xié)調(diào)作用，如何實(shí)現(xiàn)常見(jiàn)問(wèn)題的一般解決方案。

內(nèi)存化

內(nèi)存化 這個(gè)詞是 Donald Michie（一位英國(guó)人工智能研究人員）發(fā)明的，用于表示重復(fù)的值的函數(shù)級(jí)緩存。如今，內(nèi)存化在函數(shù)式編程語(yǔ)言中很常見(jiàn)，它要么被用作一個(gè)內(nèi)置特性，要么被用作一個(gè)相對(duì)容易實(shí)現(xiàn)的特性。

內(nèi)存化在以下場(chǎng)景中很有幫助。假設(shè)您必須反復(fù)調(diào)用一個(gè)注重性能的函數(shù)。一個(gè)常見(jiàn)解決方案是構(gòu)建內(nèi)部緩存。每次計(jì)算某個(gè)參數(shù)集的值時(shí)，您都會(huì)將該值放入緩存中，作為參數(shù)值的線索。在未來(lái)，如果該函數(shù)使用以前的參數(shù)調(diào)用，那么它將會(huì)從緩存返回值，而不是重新計(jì)算它。函數(shù)緩存是一種經(jīng)典的計(jì)算機(jī)科學(xué)權(quán)衡：它使用更多內(nèi)存（我們常常擁有豐富的內(nèi)存）來(lái)不斷實(shí)現(xiàn)更高的性能。

函數(shù)必須是純粹的，緩存技術(shù)才能發(fā)揮其作用。純函數(shù) 是沒(méi)有副作用的函數(shù)：它沒(méi)有引用任何其他易變的類字段，沒(méi)有設(shè)置除返回值以外的任何值，而且僅依賴于參數(shù)作為輸入。java.lang.Math 類中的所有方法都是純函數(shù)的良好示例。顯然，只有在函數(shù)可靠地為一組給定的參數(shù)返回相同值時(shí)，您才能成功地重用緩存的結(jié)果。

Groovy 中的內(nèi)存化

內(nèi)存化在 Groovy 中很簡(jiǎn)單，Groovy 在 Closure 類上包含一系列 memoize() 函數(shù)。例如，假設(shè)您有一個(gè)昂貴的哈希算法，以至于您需要緩存結(jié)果來(lái)提高效率。為此，您可以使用閉包塊語(yǔ)法來(lái)定義方法，在返回時(shí)調(diào)用 memoize() 函數(shù)，如清單 1 所示。我并不是暗示清單 1 中使用的 ROT13 算法（即凱撒密碼 的一個(gè)版本）的性能面臨挑戰(zhàn)，只是假設(shè)緩存在這個(gè)示例中很重要。

清單 1. Groovy 中的內(nèi)存化

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 函數(shù)定義看起來(lái)像清單 1 中的 rot13()，方法主體位于參數(shù)列表之后。hash() 函數(shù)定義使用了稍微不同的語(yǔ)法，將代碼塊分配給 hash 變量。該定義的最后一部分是對(duì) memoize() 的調(diào)用，它自動(dòng)為重復(fù)的值創(chuàng)建一個(gè)內(nèi)部緩存，與該參數(shù)建立聯(lián)系。

memoize() 方法實(shí)際上是一個(gè)方法系列，為您提供了對(duì)緩存特征的一定控制，如表 1 所示。

表 1. Groovy 的 memoize() 系列

表 1 中的方法為您提供了對(duì)緩存特征粗粒度的控制，這不是直接調(diào)優(yōu)緩存特征的細(xì)粒度方式。內(nèi)存化應(yīng)是一種通用機(jī)制，您可以用它來(lái)輕松優(yōu)化常見(jiàn)的緩存情形。

Clojure 中的內(nèi)存化

內(nèi)置于 Clojure 中的內(nèi)存化。您可以使用 (memoize ) 函數(shù)內(nèi)存化任何函數(shù)。例如，如果您已經(jīng)擁有一個(gè) (hash "homer") 函數(shù)，那么您可以通過(guò) (memoize (hash "homer")) 針對(duì)一個(gè)緩存版本而對(duì)其進(jìn)行內(nèi)存化。清單 2 在 Clojure 中實(shí)現(xiàn)了 清單 1 中的名稱哈希示例。

清單 2. Clojure 內(nèi)存化

(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")))))

請(qǐng)注意，在 清單 1 中，調(diào)用內(nèi)存化的函數(shù)需要調(diào)用 call() 方法。在 Clojure 版本中，內(nèi)存化的方法調(diào)用在表面上完全相同，但增加了對(duì)方法用戶不可見(jiàn)的間接性和緩存。

Scala 中的內(nèi)存化

Scala 沒(méi)有直接實(shí)現(xiàn)內(nèi)存化，但有一個(gè)名為 getOrElseUpdate() 的集合方法來(lái)處理實(shí)現(xiàn)它的大部分工作，如清單 3 所示。

清單 3. Scala 內(nèi)存化

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() 函數(shù)是建立緩存的完美的運(yùn)算符。它檢索匹配的值，或者在沒(méi)有匹配值時(shí)創(chuàng)建一個(gè)新條目。

組合函數(shù)特性

通過(guò)復(fù)合 (composition) 來(lái)組合

復(fù)合 在軟件開(kāi)發(fā)中有許多含義。函數(shù)復(fù)合 指組合函數(shù)來(lái)獲得復(fù)合結(jié)果的能力。在數(shù)學(xué)術(shù)語(yǔ)中，如果您有一個(gè) f(x) 函數(shù)和一個(gè) g(x) 函數(shù)，那么您應(yīng)能夠執(zhí)行 f(g(x))。在軟件術(shù)語(yǔ)中，如果您有一個(gè)將字符串轉(zhuǎn)換為大寫(xiě)的 a() 函數(shù)和一個(gè)刪除過(guò)量空格的 b() 函數(shù)，那么復(fù)合函數(shù)將執(zhí)行這兩項(xiàng)任務(wù)。

在上一節(jié)和前幾期 Java 下一代 文章中，我介紹了函數(shù)式編程的許多細(xì)節(jié)，尤其是與 Java 下一代語(yǔ)言相關(guān)的細(xì)節(jié)。但是，函數(shù)式編程的真正強(qiáng)大之處在于各種特性與解決方案的執(zhí)行方式的組合。

面向?qū)ο蟮某绦騿T傾向于不斷創(chuàng)建新數(shù)據(jù)結(jié)構(gòu)和附帶的運(yùn)算。畢竟，構(gòu)建新類和在它們之間傳遞的消息是主要的語(yǔ)言模式。但是構(gòu)建如此多的定制結(jié)構(gòu)，會(huì)使在最低層級(jí)上構(gòu)建可重用代碼變得很困難。函數(shù)式編程語(yǔ)言引用一些核心代碼結(jié)構(gòu)并構(gòu)建優(yōu)化的機(jī)制來(lái)理解它們。

以下是一個(gè)示例。清單 4 給出了來(lái)自 Apache Commons 框架的 indexOfAny() 方法，該框架為 Java 編程提供了大量幫助器。

清單 4. 來(lái)自 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 的代碼負(fù)責(zé)邊緣檢查和實(shí)現(xiàn)嵌套迭代所需的變量的初始化。我將逐步將此代碼轉(zhuǎn)換為 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 會(huì)智能地處理 null 和 empty 情形，擁有 (when ...) 等智能函數(shù)，該函數(shù)僅在字符存在時(shí)返回 true。Clojure 具有動(dòng)態(tài)（且強(qiáng)）類型，消除了在使用前聲明變量類型的需求。因此，我可以刪除類型聲明，獲得清單 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 循環(huán) （命令式語(yǔ)言的主要元素）允許依次訪問(wèn)每個(gè)元素。函數(shù)式語(yǔ)言傾向于更多地依靠集合方法，這些方法已理解（或避免）了邊角情形，所以我可刪除 isHighSurrogate()（它檢查字符編碼）等方法和索引指針的操作。此轉(zhuǎn)換的結(jié)果如清單 7 所示。

清單 7. 一個(gè)用于替換最里面的 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 中，我將代碼折疊到一個(gè)方法中，該方法會(huì)檢查受歡迎的字符是否存在，在找到這些字符時(shí)，它會(huì)返回其索引。盡管我既未使用 Java 也未使用 Clojure，而是提供了一段陌生的偽代碼，但這個(gè) when 方法并不總是存在。但 Clojure 中還有 (when ) 方法，此代碼會(huì)慢慢變成該方法。

接下來(lái)，我將最頂層的 for 循環(huán)替換為一種更加簡(jiǎn)潔的代碼，使用 for comprehension： 一個(gè)結(jié)合了集合的訪問(wèn)和過(guò)濾（等）的宏。演變后的代碼如清單 8 所示。

清單 8. 添加一個(gè) comprehension

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

要理解清單 8 中的 for comprehension，首先您必須理解一些部件。Clojure 中的 (indexed ...) 函數(shù)接受一個(gè) Sequence

并返回一個(gè)包含編號(hào)的元素的序列。例如，如果我調(diào)用 (indexed '(a b c))，返回值為 ([0 a] [1 b] [2 c])。（單個(gè)撇號(hào)告訴 Clojure，我想要一個(gè)字符的文字序列，但并不希望執(zhí)行一個(gè)包含兩個(gè)參數(shù)的 (a )。）for comprehension 在我的搜索字符上創(chuàng)建這個(gè)序列，然后應(yīng)用內(nèi)部的 when 來(lái)查找匹配字符的索引。

此轉(zhuǎn)換的最后一步是將代碼轉(zhuǎn)換為合適的 Clojure 語(yǔ)法，還原真實(shí)函數(shù)和語(yǔ)法的外觀，如清單 9 所示。

清單 9. Clojure 化的代碼

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

在清單 9 中的最終的 Clojure 版本中，我將語(yǔ)法轉(zhuǎn)換為合適的 Clojure 并添加一次升級(jí)：此函數(shù)的調(diào)用方現(xiàn)在可傳遞任何判定函數(shù)（一個(gè)返回布爾值結(jié)果的函數(shù)），而不只是檢查一個(gè)空字符串。Clojure 的一個(gè)目標(biāo)是實(shí)現(xiàn)創(chuàng)建可讀的代碼的能力（在您理解圓括號(hào)之后），而且這個(gè)函數(shù)證實(shí)了這種能力：對(duì)于帶索引的集合，在您的判定與元素匹配時(shí)，將會(huì)返回索引。

Clojure 的另一個(gè)目標(biāo)是使用最少量的字符來(lái)表達(dá)清楚目的；在這方面，Java 與 Clojure 相差甚遠(yuǎn)。表 2 比較了 清單 4 中的 “移動(dòng)部件” 和 清單 9 中的相應(yīng)部件。

表 2.比較 “移動(dòng)部件”

復(fù)雜性上的差異一目了然。盡管 Clojure 代碼更簡(jiǎn)單，但它也更加通用。這里，我對(duì)一個(gè)硬幣翻轉(zhuǎn)序列建立了索引，建模為 Clojure :h（頭）和 :t（尾）關(guān)鍵字：

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

請(qǐng)注意，返回值是所有匹配的索引位置的序列，而不只是第一個(gè)。Clojure 中的列表操作盡可能是 惰性的，包括這一個(gè)操作。如果我僅想要第一個(gè)值，那么我可以通過(guò) (take 1 ) 從結(jié)果中獲得該值，或者我可以全部打印它們，就像我在這里所做的那樣。

我的 (index-filter ) 函數(shù)是通用的，所以我可在數(shù)字上使用它。例如，我可確定其斐波納契值超過(guò) 1,000 的第一個(gè)數(shù)字：

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

(fibo) 函數(shù)返回一個(gè)沒(méi)有限制但惰性的斐波納契數(shù)字序列；(index-filter ) 找到第一個(gè)超過(guò) 1,000 的值。（事實(shí)證明，18 的斐波納契值為 1,597。）函數(shù)結(jié)構(gòu)、動(dòng)態(tài)類型、惰性和簡(jiǎn)潔語(yǔ)法相結(jié)合，得到的是更強(qiáng)大的功能。

惰性

惰性 — 盡可能延遲表達(dá)式計(jì)算 — 是函數(shù)式語(yǔ)言在不需要或只需很少開(kāi)發(fā)人員成本的情況下添加功能的另一個(gè)優(yōu)秀示例。請(qǐng)參閱 “函數(shù)式思維：探索 Java 中的惰性計(jì)算” 和 “函數(shù)式思維：深入剖析惰性計(jì)算”，了解 Java 下一代語(yǔ)言中的惰性討論和示例。

結(jié)束語(yǔ)

函數(shù)式編程結(jié)構(gòu)在零散使用時(shí)可帶來(lái)優(yōu)勢(shì)，在結(jié)合使用它們時(shí)會(huì)帶來(lái)更多的優(yōu)勢(shì)。所有 Java 下一代語(yǔ)言在一定程度上都是函數(shù)式的，支持增加這種開(kāi)發(fā)風(fēng)格的使用。

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

最新評(píng)論