调用函数或外部滤波器

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的集合，需要垃圾收集等等。