1

当我使用该方法将 Scala 预定义identity函数应用于集合时map，原始集合将原样返回。但是，编译器是否足够聪明，可以简单地将未更改的集合作为O(1)操作返回？还是将恒等函数仍应用于原始集合中的每个元素以产生O(n)操作？

4

4 回答 4

4

检查情况是否如此非常简单。首先使用可能优化的形式制作一个测试文件并使用scalac（有或没有-optimise）编译它

/// TestMap.scala
object TestMap {
  def mapOption[T](o: Option[T]): Option[T] = o.map(identity)
  def mapList[T](l: List[T]): List[T] = l.map(identity)
  def mapSeq[T](l: Seq[T]): Seq[T] = l.map(identity)
}

然后，检查javap -c TestMap.class您可以看到没有任何优化过去专门map针对mapSeq、mapList或mapOption：

Compiled from "TestMap.scala"
public final class TestMap {
  public static <T extends java/lang/Object> scala.collection.Seq<T> mapSeq(scala.collection.Seq<T>);
    Code:
       0: getstatic     #16                 // Field TestMap$.MODULE$:LTestMap$;
       3: aload_0       
       4: invokevirtual #18                 // Method TestMap$.mapSeq:(Lscala/collection/Seq;)Lscala/collection/Seq;
       7: areturn       

  public static <T extends java/lang/Object> scala.collection.immutable.List<T> mapList(scala.collection.immutable.List<T>);
    Code:
       0: getstatic     #16                 // Field TestMap$.MODULE$:LTestMap$;
       3: aload_0       
       4: invokevirtual #22                 // Method TestMap$.mapList:(Lscala/collection/immutable/List;)Lscala/collection/immutable/List;
       7: areturn       

  public static <T extends java/lang/Object> scala.Option<T> mapOption(scala.Option<T>);
    Code:
       0: getstatic     #16                 // Field TestMap$.MODULE$:LTestMap$;
       3: aload_0       
       4: invokevirtual #26                 // Method TestMap$.mapOption:(Lscala/Option;)Lscala/Option;
       7: areturn

更简单地说，这种优化在具有副作用的语言中不能很好地扩展（另一方面，在 Haskell 中，这种事情经常发生）。例如，编译器是否应该l.map(x => { println(x); x })优化l？

于 2016-09-18T03:42:37.750 回答
2

Rex Kerr方便的 Thyme 实用程序证实了 Alec 的发现。运行时间大致与identity集合大小成正比。

val smallC = Vector.tabulate(90)(_*2)
val bigC = Vector.tabulate(900)(_*2)

val th = ichi.bench.Thyme.warmed(verbose = print)
th.pbenchOffWarm("A vs. B")(th.Warm(smallC.map(identity)))(th.Warm(bigC.map(identity)))

Benchmark comparison (in 4.694 s): A vs. B
Significantly different (p ~= 0)
  Time ratio:    9.31267   95% CI 9.25599 - 9.36935   (n=20)
    First     1.492 us   95% CI 1.487 us - 1.496 us
    Second    13.89 us   95% CI 13.82 us - 13.96 us
于 2016-09-18T04:04:39.460 回答
2

当我使用该方法将 Scala 预定义identity函数应用于集合时map，原始集合将原样返回。

不，不是。返回具有相同内容的新集合。构建这个新集合通常需要 O(n)。

但是，编译器是否足够聪明，可以简单地将未更改的集合作为O(1)操作返回？还是将恒等函数仍应用于原始集合中的每个元素以产生O(n)操作？

为了执行这样的优化，编译器必须决定要应用的函数在扩展上等于恒等函数。这个问题被称为函数问题并且已知是不可判定的。（例如，可以使用停机问题来证明。）

当然，可以针对特定函数进行优化Predef.identity，而不仅仅是任何恒等函数。但是 Scala 编译器设计者不喜欢这种一次性的特殊情况优化，它只会帮助标准库代码。他们更喜欢有利于所有代码的一般优化。

于 2016-09-18T08:11:33.987 回答
0

测量执行时间似乎表明恒等函数为 O(n)：

用于测量代码执行时间的功能，来自此链接：

def time[R](block: => R): R = {  
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
    result
}

time {(1 to 100000000).map(identity)}  // Elapsed time: 8893077396ns

time {(1 to 10).map(identity)} // Elapsed time: 341129ns

// while only creation of range takes similar order of magnitude times. 

time {(1 to 10)}  // Elapsed time: 30250ns

time {(1 to 100000000)} // Elapsed time: 32351ns
于 2016-09-18T03:40:11.033 回答