集合有許多建立新集合的方法。例如 map
、filter
或 ++
。我們稱呼這些方法為轉換器,因為它們至少會將一個集合作為接收器物件,並產生另一個集合作為結果。
有兩種主要方法可以實作轉換器。一種是嚴格,也就是說,一個新的集合及其所有元素會建構為轉換器的結果。另一種是非嚴格或延遲,也就是說,只會建構結果集合的代理,而其元素只會在需要時建構。
以下是一個延遲映射運算的非嚴格轉換器實作範例
def lazyMap[T, U](iter: Iterable[T], f: T => U) = new Iterable[U] {
def iterator = iter.iterator.map(f)
}
def lazyMap[T, U](iter: Iterable[T], f: T => U) = new Iterable[U]:
def iterator = iter.iterator.map(f)
請注意,lazyMap
會建構一個新的 Iterable
,而不會逐一檢視給定集合 coll
的所有元素。相反地,給定的函數 f
會套用至新集合的 iterator
的元素,當這些元素被要求時。
Scala 集合在所有轉換器中預設為嚴格,除了 LazyList
,它會延遲實作其所有轉換器方法。不過,有一個系統化的方式可以將每個集合轉換成延遲集合,反之亦然,這取決於集合檢視。檢視是一種特殊類型的集合,它代表某個基本集合,但會延遲實作所有轉換器。
若要從集合轉換成其檢視,可以在集合上使用 view
方法。如果 xs
是某個集合,則 xs.view
是同一個集合,但所有轉換器都會延遲實作。若要從檢視轉回嚴格集合,可以使用 to
轉換運算,並將嚴格集合工廠設為參數 (例如 xs.view.to(List)
)。
讓我們來看一個範例。假設您有一個 Int 向量,您想要連續對其套用兩個函數
scala> val v = Vector(1 to 10: _*)
val v: scala.collection.immutable.Vector[Int] =
Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
scala> v.map(_ + 1).map(_ * 2)
val res5: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
scala> val v = Vector((1 to 10)*)
val v: scala.collection.immutable.Vector[Int] =
Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
scala> v.map(_ + 1).map(_ * 2)
val res5: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
在最後一個陳述式中,表達式 v map (_ + 1)
建構一個新的向量,然後透過第二次呼叫 map (_ * 2)
轉換成第三個向量。在許多情況下,從第一次呼叫 map 建構中間結果有點浪費。在上面的範例中,使用 (_ + 1)
和 (_ * 2)
這兩個函式的組合執行單一 map 會更快。如果您在同一個地方有這兩個函式,您可以手動執行此操作。但常常,資料結構的連續轉換會在不同的程式模組中執行。融合這些轉換會破壞模組化。避免中間結果的更一般方式是先將向量轉換成檢視,然後將所有轉換套用至檢視,最後強制檢視轉換成向量
scala> val w = v.view.map(_ + 1).map(_ * 2).to(Vector)
val w: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
讓我們再次逐一執行這段操作順序
scala> val vv = v.view
val vv: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
應用 v.view
會提供 IndexedSeqView[Int]
,也就是延遲評估的 IndexedSeq[Int]
。如同 LazyList
,檢視的 toString
操作不會強制檢視元素,這就是為什麼 vv
的內容顯示為 IndexedSeqView(<not computed>)
的原因。
將第一個 map
套用至檢視會產生
scala> vv.map(_ + 1)
val res13: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
map
的結果是另一個 IndexedSeqView[Int]
值。這基本上是一個包裝器,它記錄了對向量 v
應用具有函數 (_ + 1)
的 map
的事實。然而,它不會在檢視強制執行之前套用該映射。現在讓我們將第二個 map
套用到最後一個結果。
scala> res13.map(_ * 2)
val res14: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
最後,強制執行最後一個結果會產生
scala> res14.to(Vector)
val res15: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
在執行 to
操作時,兩個儲存的函數都會被套用,並且會建構一個新的向量。這樣就不需要中間資料結構了。
一般而言,套用於檢視的轉換操作絕不會建立新的資料結構,而存取檢視的元素實際上會盡可能地遍歷基礎資料結構的元素。因此,檢視具有以下屬性:(1) 轉換器的複雜度為 O(1)
,(2) 元素存取操作具有與基礎資料結構相同的複雜度(例如,在 IndexedSeqView
上的索引存取是常數,否則為線性)。
不過,這些規則有幾個例外。例如,sorted
操作無法滿足這兩個屬性。的確,必須遍歷整個基礎集合才能找到其最小元素。一方面,如果在呼叫 sorted
時發生該遍歷,則會違反第一個屬性(sorted
在檢視上不會是延遲的),另一方面,如果在存取結果檢視元素時發生該遍歷,則會違反第二個屬性。對於此類操作,我們決定違反第一個屬性。這些操作被記錄為「總是強制執行集合元素」。
使用檢視的主要原因是效能。您已經看到,透過將集合切換為檢視,可以避免建立中間結果。這些節省相當重要。作為另一個範例,考慮在字詞清單中尋找第一個迴文的難題。迴文是從前往後讀和從後往前讀都一樣的字詞。以下是必要的定義
def isPalindrome(x: String) = x == x.reverse
def findPalindrome(s: Seq[String]) = s.find(isPalindrome)
現在,假設您有一個非常長的序列 words,而且您要在該序列的前一百萬個字詞中尋找迴文。您可以重複使用 findPalindrome
的定義嗎?當然,您可以撰寫
val palindromes = findPalindrome(words.take(1000000))
這樣可以很好地將取得序列的前一百萬個字詞和在其中尋找迴文這兩個面向分開。但缺點是,它總是會建構一個由一百萬個字詞組成的中間序列,即使該序列的第一個字詞已經是迴文。因此,潛在有 999’999 個字詞會複製到中間結果中,而之後完全不會檢查這些字詞。許多程式設計師會在這裡放棄,並撰寫自己的專門版本,在引數序列的某個特定前置詞中尋找迴文。但使用檢視,您不必這麼做。只要撰寫
val palindromes = findPalindrome(words.view.take(1000000))
這具有相同的明確分工,但它只會建構一個單一的輕量級檢視物件,而不是一百萬個元素的序列。這樣,您就不需要在效能和模組化之間做選擇。
在看過檢視的所有這些巧妙用途後,您可能會好奇為什麼還要使用嚴格集合?一個原因是效能比較並不總是偏好延遲集合而非嚴格集合。對於較小的集合大小,在檢視中形成和套用封閉項目的額外開銷通常大於避免中間資料結構的收益。一個可能更重要的原因是,如果延遲操作有副作用,則在檢視中的評估可能會非常令人困惑。
以下是一個範例,它讓一些 Scala 2.8 之前版本的使用者感到困擾。在這些版本中,Range
類型是延遲的,因此它實際上就像檢視一樣。人們試圖建立許多像這樣的執行緒
val actors = for (i <- 1 to 10) yield actor { ... }
val actors = for i <- 1 to 10 yield actor { ... }
他們驚訝地發現,儘管演員方法應該建立並啟動一個演員,但沒有任何演員在之後執行。為了解釋為什麼沒有發生任何事情,請記住,上面的 for 表達式等同於應用 map
val actors = (1 to 10).map(i => actor { ... })
由於先前由 (1 to 10)
產生的範圍表現得像一個檢視,因此 map 的結果又是一個檢視。也就是說,沒有任何元素被計算,因此沒有建立任何演員!強制整個表達式的範圍可以建立演員,但這並非讓演員執行其工作的必要條件,這一點遠非顯而易見。
為了避免像這樣的驚訝,目前的 Scala 集合函式庫有更規則的規則。除了惰性清單和檢視外,所有集合都是嚴格的。從嚴格集合轉換為惰性集合的唯一方法是透過 view
方法。回轉的唯一方法是透過 to
。因此,上面的 actors
定義現在會如預期般建立並啟動 10 個演員。若要回復到令人驚訝的前一個行為,您必須新增一個明確的 view
方法呼叫
val actors = for (i <- (1 to 10).view) yield actor { ... }
val actors = for i <- (1 to 10).view yield actor { ... }
總而言之,檢視是一種強大的工具,可以調和效率和模組化的考量。但為了不糾纏於延遲評估的層面,你應該將檢視限制在純粹的功能程式碼,其中集合轉換沒有副作用。最好避免檢視和建立新集合的運算混合,同時也產生副作用。