scala - ID 関数を Scala コレクションにマッピングするのは複雑ですか?

Question

メソッドを使用して Scala 定義済みidentity関数をコレクションに適用するmapと、元のコレクションが変更されずに返されます。しかし、コンパイラはO(1)操作として変更されていないコレクションを単純に返すほど賢いでしょうか? それとも、元のコレクションの各要素に同一性関数が適用され、O(n)操作が行われるのでしょうか?

Answer 1

これが当てはまらないことを確認するのは非常に簡単です。おそらく最適化されたフォームでテストファイルを作成することから始めて、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何も最適化されていないことを確認できます。mapmapSeqmapListmapOption

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 2

メソッドを使用して Scala 定義済みidentity関数をコレクションに適用するmapと、元のコレクションが変更されずに返されます。

いいえ、そうではありません。同じ内容の新しいコレクションが返されます。通常、この新しいコレクションの構築は O(n) になります。

しかし、コンパイラはO(1)操作として変更されていないコレクションを単純に返すほど賢いでしょうか? それとも、元のコレクションの各要素に同一性関数が適用され、O(n)操作が行われるのでしょうか?

このような最適化を実行するために、コンパイラは、適用される関数が恒等関数と拡張的に等しいことを決定する必要があります。この問題は関数問題と呼ばれ、決定不能であることが知られています。(たとえば、停止問題を使用して証明できます。)

もちろん、恒等関数だけでなく、特定の関数を最適化することも可能です。Predef.identityしかし、Scala コンパイラーの設計者は、標準ライブラリー・コードのみを支援するような 1 回限りの特殊なケースの最適化を好みません。彼らは、すべてのコードに利益をもたらす一般的な最適化を好みます。

Answer 3

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

Answer 4

実行時間を測定すると、恒等関数が 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