調用函數或外部濾波器

Question

比方說，我有以下2個功能等效的代碼段，返回有自己的逆轉也在列表字符串列表：

var a = Array("abc", "bca", "abc", "aba", "cba") 
a.filter(x => a.toSet(x.reverse)).distinct 

和

var a = Array("abc", "bca", "abc", "aba", "cba") 
var aSet = a.toSet // notice that toSet is called outside filter 
a.filter(x => aSet(x.reverse)).distinct 

我想知道這些片段之間的時間複雜程度是否有差異，因爲我在第一個片段中調用.toSet爲a中的每個元素，而在第二個片段中，我只在開始時調用它。然而，這就是說，有些東西告訴我編譯器可能會優化第一個調用，產生相當於時間複雜度的2個片段。

如果後者是真的，請您向我推薦一些相關文獻？

謝謝。

Answer 1

好吧，讓我們把它放到測試（使用Scalameter）：

import org.scalameter.{Gen, PerformanceTest} 
import org.scalatest._ 

import scala.collection.mutable 

class SOPerformance extends PerformanceTest.Quickbenchmark { 
    val gen = Gen.unit("unit") 
    @inline def fn = { 
     var a = Array("abc", "bca", "abc", "aba", "cba") 
    a.filter(x => a.toSet(x.reverse)).distinct 
    } 
    @inline def fn2 = { 
     var a = Array("abc", "bca", "abc", "aba", "cba") 
     var aSet = a.toSet // notice that toSet is called outside filter 
     a.filter(x => aSet(x.reverse)).distinct 
    } 

    performance of "Range" in { 
    measure method "fn" in { 
     using(gen) in { gen ⇒ 
     fn 
     } 
    } 
    measure method "fn2" in { 
     using(gen) in { gen ⇒ 
     fn2 
     } 
    } 
    } 
} 

這都說明fn平均在0.005674米利斯運行和fn2平均在0.003903米利斯運行。

現在我們讓這個數組有點大！

import org.scalameter.{Gen, PerformanceTest} 
import org.scalatest._ 

import scala.collection.mutable 

class SOPerformance extends PerformanceTest.Quickbenchmark { 
    var a = (1 to 1000).map(_.toString).toArray 

    val gen = Gen.unit("unit") 

    @inline def fn = { 
     a.filter(x => a.toSet(x.reverse)).distinct 
    } 
    @inline def fn2 = { 
     var aSet = a.toSet // notice that toSet is called outside filter 
     a.filter(x => aSet(x.reverse)).distinct 
    } 

    performance of "Range" in { 
    measure method "fn" in { 
     using(gen) in { gen ⇒ 
     fn 
     } 
    } 
    measure method "fn2" in { 
     using(gen) in { gen ⇒ 
     fn2 
     } 
    } 
    } 
} 

這顯示了真正的殺手。 fn平均需要158.241861毫秒，而fn2需要0.353472毫秒！爲什麼？因爲創建集合非常昂貴！特別是需要製作新HashSet的集合，需要垃圾收集等等。