scala視圖篩選器不是懶惰？

在試圖理解流，迭代器和集合視圖之間的差異時，我偶然發現了以下奇怪的行爲。scala視圖篩選器不是懶惰？

下面的代碼（映射和過濾器只需打印他們的意見，並將它轉發不變）：

object ArrayViewTest { 
    def main(args: Array[String]) { 
    val array = Array.range(1,10) 

    print("stream-map-head: ") 
    array.toStream.map(x => {print(x); x}).head 

    print("\nstream-filter-head: ") 
    array.toStream.filter(x => {print(x); true}).head 

    print("\niterator-map-head: ") 
    array.iterator.map(x => {print(x); x}).take(1).toArray 

    print("\niterator-filter-head: ") 
    array.iterator.filter(x => {print(x); true}).take(1).toArray 

    print("\nview-map-head: ") 
    array.view.map(x => {print(x); x}).head 

    print("\nview-filter-head: ") 
    array.view.filter(x => {print(x); true}).head 
    } 
}

，其輸出：

stream-map-head: 1 
stream-filter-head: 1 
iterator-map-head: 1 
iterator-filter-head: 1 
view-map-head: 1 
view-filter-head: 123456789 // <------ WHY ?

爲什麼過濾呼籲，全陣列的圖過程？我希望過濾器的評估只能通過調用head來驅動一次，就像在所有其他情況下一樣，特別是在使用地圖時。

我缺少哪些洞察力？

（上發表評論迷你側的問題，爲什麼沒有腦袋上的迭代器？）

編輯： 同樣奇怪的行爲（如這裏scala.Array.range(1,10)）由scala.collection.mutable.ArraySeq.range(1,10)，scala.collection.mutable.ArrayBuffer.range(1,10)實現，和scala.collection.mutable.StringBuilder.newBuilder.append("123456789")。 但是，對於所有其他可變集合以及所有不可變集合，視圖上的過濾器按預期工作，並輸出1。

來源

2016-03-01 cubic lettuce

（微型側回答）時，如果你想獲得迭代器的第一個元素使用filter而不是當情況發生時，Filtered特點是隻用你將不得不提前使用'next'並調用它兩次會有問題。 –

看來head使用isEmpty

trait IndexedSeqOptimized[+A, +Repr] extends Any with IndexedSeqLike[A, Repr] { self => 
... 
override /*IterableLike*/ 
def head: A = if (isEmpty) super.head else this(0)

而且isEmpty使用length

trait IndexedSeqOptimized[+A, +Repr] extends Any with IndexedSeqLike[A, Repr] { self => 
    ... 
    override /*IterableLike*/ 
    def isEmpty: Boolean = { length == 0 }

的length實現從Filtered使用它通過全陣列式循環

trait Filtered extends super.Filtered with Transformed[A] { 
    protected[this] lazy val index = { 
    var len = 0 
    val arr = new Array[Int](self.length) 
    for (i <- 0 until self.length) 
     if (pred(self(i))) { 
     arr(len) = i 
     len += 1 
     } 
    arr take len 
    } 
    def length = index.length 
    def apply(idx: Int) = self(index(idx)) 
}

調用filter

protected override def newFiltered(p: A => Boolean): Transformed[A] = 
new { val pred = p } with AbstractTransformed[A] with Filtered

這就是爲什麼使用map

來源

2016-03-01 12:38:25

感謝您的這一痕跡！事實上，這個問題似乎只發生在'IndexedSeq'特性上（請參閱我編輯的文章）。你是否同意這種方式如何實現是一個愚蠢的性能浪費，可能被稱爲一個錯誤？忽略任何內部的必要性：對我來說，通過單獨計算其元素來計算數組的長度是絕對沒有必要的 - 實際上，O（1）對數組長度的訪問是數組的一個重要屬性，事實上，數組長度*是*那裏 - 它根本不被過濾器讀取。 –

我同意性能未針對您的情況進行優化。我不知道這是一種權衡還是可以預防的。也許你可以問一下https://gitter.im/scala/contributors –

澄清：Scala並沒有通過計算它的元素來計算數組的長度。它通過計算其元素來計算視圖的長度，但數組視圖不是數組。 –

我認爲它必須這樣做Array是一個可變的索引序列。它的視圖也是一個可變的集合:)所以當它創建一個視圖時，它會創建一個索引來映射原始集合和過濾後的集合。並且懶惰地創建這個索引並沒有什麼意義，因爲有人會請求第i個元素而不是整個源數組可能會被遍歷。從某種意義上說，這個索引仍然是懶惰的，只有在您撥打head之後才能創建該索引。儘管這在scala文檔中沒有明確說明，並且它看起來像是一見鍾情。

對於微型問題，我認爲迭代器上的head問題是人們期望head是純函數，即你應該能夠調用它n次，它應該每次都返回相同的結果。而迭代器本質上是可變數據結構，它通過契約只能遍歷一次。這可以通過緩存迭代器的第一個元素來克服，但是我覺得這很混亂。

來源

2016-03-01 12:27:00 vitalii

實際上array'view'在'map'函數中是懶惰的。爲什麼 – Rumoku

因爲您不需要在映射視圖和源視圖之間重建索引。此外，我不知道如果映射視圖不是副本...非常令人困惑 – vitalii

scala視圖篩選器不是懶惰？

回答

相關問題