调用函数或外部滤波器
问题描述:
比方说,我有以下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个片段。
如果后者是真的,请您向我推荐一些相关文献?
谢谢。
答
好吧,让我们把它放到测试(使用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的集合,需要垃圾收集等等。
您可以尝试scalac命令的-print选项来比较生成的Java代码。您也可以放入一些时间并运行代码几千次以实证检查。 – wwkudu