Scala函數式編程（六） 懶載入與Stream
- 2020 年 4 月 15 日
- 筆記
- java/scala, scala, 函數式編程
前情提要
什麼時候效率複習最高，毫無疑問是考試前的最後一夜，同樣的道理還有寒暑假最後一天做作業最高效。學界有一個定理：deadline是第一生產力，說的就是這個事情。
同樣的，這個道理完全可以推廣到函數式編程中來，而懶載入（scala的lazy關鍵字）就是這樣的東西。
在函數式編程中，因為要維持不變性，故而需要更多的存儲空間，這一點在函數式數據結構中有說到。懶載入可以說會在一定程度上解決這個問題，同時通過快取數據還能提高一些運行效率，以及通過面向表達式編程提高系統的模組化。
這一節先介紹lazy的具體內容，及其好處，然後通過Stream這一數據結構討論懶載入更多應用場景以及懶載入是如何實現性能優化的。
1.scala懶載入lazy
1.1 什麼是懶載入
懶載入，顧名思義就是一個字懶。就像老闆讓你去幹活，剛叫的時候你不會去干，只有等到著急的時候，催你的時候你才會去干。懶載入就是這樣的東西。
我們直接用命令行測試下：
//右邊是一個表達式，這裡不是懶載入，直接求值
scala> val x = { println("x"); 15 }
x
x: Int = 15
//使用了懶載入，這裡和上面的右側是類似的，不過不會立即求值
scala> lazy val y = { println("y"); 13 }
y: Int = <lazy>
//x的值變成15，也就是表達式的結果
scala> x
res2: Int = 15
//懶載入在真正調用的時候，才運行表達式的內容，列印y，並返回值
scala> y
y
res3: Int = 13
//lazy已經快取的表達式的內容，所以不會再運行表達式裡面的東西，也就是表達式內容只運行一次
scala> y
res4: Int = 13
看上面程式碼就明白了，懶載入就是讓表達式裡面的計算延遲，並且只計算一次，然後就會快取結果。
值得一提的是，懶載入只對表達式和函數生效，如果直接定義變數，那是沒什麼用的。因為懶載入就是讓延遲計算，你直接定義變數那計算啥啊。。。
說完lazy這個東西，那就來說說它究竟有什麼用。
1.2 懶載入的好處
初次看到這個東西，會疑惑，懶載入有什麼用？其實它的用處可不小。
lazy的一個作用，是將推遲複雜的計算，直到需要計算的時候才計算，而如果不使用，則完全不會進行計算。這無疑會提高效率。
而在大量數據的情況下，如果一個計算過程相互依賴，就算後面的計算依賴前面的結果，那麼懶載入也可以和快取計算結合起來，進一步提高計算效率。嗯，有點類似於spark中快取計算的思想。
除了延遲計算，懶載入也可以用於構建相互依賴或循環的數據結構。我這邊再舉個從stackOverFlow看到的例子：
這種情況會出現棧溢出，因為無限遞歸，最終會導致堆棧溢出。
trait Foo { val foo: Foo }
case class Fee extends Foo { val foo = Faa() }
case class Faa extends Foo { val foo = Fee() }
println(Fee().foo)
//StackOverflowException
而使用了lazy關鍵字就不會了，因為經過lazy關鍵字修飾，變數裡面的內容壓根就不會去調用。
trait Foo { val foo: Foo }
case class Fee extends Foo { lazy val foo = Faa() }
case class Faa extends Foo { lazy val foo = Fee() }
println(Fee().foo)
//Faa()
當然上面這種方法也可以讓它全部求值，在後面stream的時候再介紹。
1.3 其他語言的懶載入
看起來懶載入是很神奇的東西，但其實這個玩意也不是什麼新鮮東西。一說你可能就會意識到了，其實懶載入就是單例模式中的懶漢構造法。
以下是scala中的懶載入：
class LazyTest {
//懶載入定義一個變數
lazy val msg = "Lazy"
}
如果轉成同樣功能的java程式碼：
class LazyTest {
public int bitmap$0;
private String msg;
public String msg() {
if ((bitmap$0 & 1) == 0) {
synchronized (this) {
if ((bitmap$0 & 1) == 0) {
synchronized (this) {
msg = "Lazy";
}
}
bitmap$0 = bitmap$0 | 1;
}
}
return msg;
}
}
其實說白了，就是考慮多執行緒情況下，運用懶漢模式創建一個單例的程式碼。只不過在scala中，提供了語法級別的支援，所以懶載入使用起來更加方便。
OK，介紹完懶載入，我們再說說一個息息相關的數據結構，Stream（流）。
2.Stream數據結構
Stream數據結構，根據名字判斷，就知道這是一個流。直觀得說，Stream可以看作一個特殊點的List，特殊在於Stream天然就是「懶」的（java8也新增了叫Stream的數據結構，但和scala的還是有點區別的，這一點要區分好）。
直接看程式碼吧：
//新建List
scala> val li = List(1,2,3,4,5)
li: List[Int] = List(1, 2, 3, 4, 5)
//新建Stream
scala> val stream = Stream(1,2,3,4,5)
stream: scala.collection.immutable.Stream[Int] = Stream(1, ?)
//每個Stream有兩個元素，一個head表示當前元素，tail表示除當前元素後面的其他元素，也可能為空
//就跟鏈表一樣
scala> stream.head
res21: Int = 1
//後一個元素，類似鏈表
scala> stream.tail
res20: scala.collection.immutable.Stream[Int] = Stream(2, ?)
List可以直接轉成Stream，也可以新生成，一個Stream和鏈表是類似的，有一個當前元素，和一個指向下一個元素的句柄。
但是！Stream不會計算，或者說獲取下一個元素的狀態和內容。也就是說，在真正調用前，當前是Stream是不知道它指向下一個元素究竟是什麼，是不是空的？
那麼問題來了，為嘛要大費周章搞這麼個Stream？
其實Stream可以做很多事情，這裡簡單介紹一下。首先說明，無論是懶載入還是Stream，使用它們很大程度是為了提高運行效率或節省空間。
獲取數據
Stream特別適合在不確定量級的數據中，獲取滿足條件的數據。這裡給出一個大佬的例子：
Scala中Stream的應用場景及事實上現原理
這個例子講的是在50個隨機數中，獲取前3個能被整除的數字。當然直接寫個while很簡單，但如果要用函數式的方式就不容易了。
而如果要沒有一絲一毫的空間浪費，那就只有使用Stream了。
再舉個例子，如果要讀取一個非常大的文件，要讀取第一個’a’字元前面的所有數據。
如果使用getLine或其他iterator的api，那要用循環或遞歸迭代去獲取，而如果用Stream，只需一行程式碼。
Source.fromFile("path").toStream.takeWhile(_ != 'a')
道理和隨機數的那個例子是一樣的。
消除中間結果
這是《scala函數式編程》書裡面的例子，這裡拿來說一說。
有這樣一行程式碼：
List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
如果讓它執行，那麼會先執行map方法，生成一個中間結果，再執行filter，返回一個中間結果，再執行map得到最終結果，流程大概如下：
List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3) =>
//生成中間結果
List(11,12,13,14).filter(_ % 2 == 0).map(_ * 3) => //又生成中間結果
List(12,14).map(_ * 3) =>
//得到最終結果
List(36,42)
看，上面例子中，會生成多個中間的List，但其實這些是沒必要的，我們完全能重寫一個While，直接在一個程式碼塊中實現map(_ + 10).filter(_ % 2 == 0).map(_ * 3)這三個函數的功能，但卻不夠優雅。而Stream能夠無縫做到這點。
可以在idea中用程式碼調試功能追蹤一下，因為Stream天生懶的原因，它會讓一個元素直接執行全部函數，第一個元素產生結果後，再執行下一個元素，避免中間臨時數據產生。看流程：
Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).toList =>
//對第一個元素應用map
Stream(11,Stream(2,3,4)).map(_ + 10).filter(_ % 2 == 0).toList =>
//對第一個元素應用filter
Stream(2,3,4).map(_ + 10).filter(_ % 2 == 0).toList =>
//對第二個元素應用map
Stream(12,Stream(3,4)).map(_ + 10).filter(_ % 2 == 0).toList
//對第二個元素應用filter生成結果
12 :: Stream(3,4).map(_ + 10).filter(_ % 2 == 0).toList =>
......以此類推
通過Stream數據結構，可以優雅得去掉臨時數據所產生的負面影響。
小結
總而言之，懶載入主要是為了能夠在一定程度上提升函數式編程的效率，無論是空間效率還是時間效率。這一點看Stream的各個例子就明白了，Stream這種數據結構天然就是懶的。
同時懶載入更重要的一點是通過分離表達式和值，提升了模組化。這句話聽起來比較抽象，還是得看回1.2 懶載入的好處這一節的例子。所謂值和表達式分離，在這個例子中，就是當調用Fee().foo的時候，不會立刻要求得它的值，而只是獲得了一個表達式，表達式的值暫時並不關心。這樣就將表達式和值分離開來，並且模組化特性更加明顯！從這個角度來看，這一點和Scala函數式編程（五） 函數式的錯誤處理介紹的Try()錯誤處理有些類似，都是關注表達式而不關注具體的值，其核心歸根結底就是為了提升模組化。
以上~
