将身份函数映射到 Scala 集合的复杂性？

Question

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

Answer 1

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

测量代码执行时间的函数，来自this link：

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

Answer 2

很容易检查是否不是这种情况。首先制作一个可能优化形式的测试文件，然后使用 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？

Answer 3

Rex Kerr 的 handy Thyme utility 证实了 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

Answer 4

When I apply the Scala predefined identity function to a collection using the map method the original collection is returned unchanged.

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

However, is the compiler smart enough to simply return the unchanged collection as an O(1) operation? Or will the identity function still be applied to each element in the original collection yielding a O(n) operation?

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

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

将身份函数映射到 Scala 集合的复杂性？

Complexity of mapping identity function to a Scala collection?

scala

scala-collections

scala-compiler