22

友人がClojureでこのコードスニペットをくれました

(defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
(time (sum (range 1 9999999) 0))

そして、同様のScala実装に対してどのようにうまくいくのかと私に尋ねました。

私が書いたScalaコードは次のようになります。

def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))
val ints = from(1).take(9999998)

def add(a: Stream[Int], b: Long): Long = {
    if (a.isEmpty) b else add(a.tail, b + a.head)
}

val t1 = System.currentTimeMillis()
println(add(ints, 0))
val t2 = System.currentTimeMillis()
println((t2 - t1).asInstanceOf[Float] + " msecs")

つまり、Clojureのコードは私のマシンで約1.8秒で実行され、5 MB未満のヒープを使用し、Scalaのコードは約12秒で実行され、512 MBのヒープでは不十分です（ 1GBまでヒープ）。

では、なぜこの特定のケースでClojureがこれほど高速でスリムなのか、疑問に思っています。速度とメモリ使用量の点で同様の動作をするScala実装がありますか？

宗教的な発言は控えてください。私の興味は、主にこの場合のclojureの速度を上げる理由と、scalaでのalgoの実装が速いかどうかを調べることにあります。ありがとう。

4

4 に答える 4

37

まず、Scalaは、で呼び出す場合にのみ末尾呼び出しを最適化し-optimiseます。編集：Scalaは、可能であれば、末尾呼び出しの再帰を常に最適化するよう-optimiseです。

第二に、StreamそしてRange2つの非常に異なるものです。ARangeには始まりと終わりがあり、その投影にはカウンターと終わりだけがあります。AStreamはオンデマンドで計算されるリストです。全体を追加しているので、全体intsを計算し、したがって割り当てStreamます。

より近いコードは次のようになります。

import scala.annotation.tailrec

def add(r: Range) = {
  @tailrec 
  def f(i: Iterator[Int], acc: Long): Long = 
    if (i.hasNext) f(i, acc + i.next) else acc

  f(r iterator, 0)
}

def time(f: => Unit) {
  val t1 = System.currentTimeMillis()
  f
  val t2 = System.currentTimeMillis()
  println((t2 - t1).asInstanceOf[Float]+" msecs")
}

通常の実行：

scala> time(println(add(1 to 9999999)))
49999995000000
563.0 msecs

elementsScala 2.7では、「」の代わりに「」が必要であり、「 」アノテーションはiteratorありません。このアノテーションは、定義を末尾再帰で最適化できない場合に文句を言うためだけに使用されるため、「 」を削除する必要があります。コードからの「」も同様です。tailrec@tailrecimport scala.annotation.tailrec

また、代替実装に関するいくつかの考慮事項。もっとも単純な：

scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs

平均して、ここで複数の実行を行うと、速度が低下します。また、Intでのみ機能するため、正しくありません。正しいもの：

scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs

ここで実行すると、さらに遅くなります。正直なところ、実行速度が遅くなるとは思っていませんでしたが、各対話は渡される関数を呼び出します。それを考えれば、再帰バージョンと比較してかなり良い時期です。

于 2009-08-31T20:20:09.403 に答える
28

Clojureの範囲はメモ化されませんが、ScalaのStreamはメモ化されます。まったく異なるデータ構造とまったく異なる結果。Scalaにはメモ化されていない範囲構造がありますが、現在、この単純な再帰的な方法で作業するのは一種の厄介です。これが私の全体像です。

遅い古いボックスでClojure1.0を使用すると、3.6秒かかります

user=> (defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
#'user/sum
user=> (time (sum (range 1 9999999) 0))
"Elapsed time: 3651.751139 msecs"
49999985000001

Scalaへの直訳では、コードを書く必要があります

def time[T](x : => T) =  {
  val start = System.nanoTime : Double
  val result = x
  val duration = (System.nanoTime : Double) - start
  println("Elapsed time " + duration / 1000000.0 + " msecs")
  result
}

それが正しいことを確認するのは良いことです

scala> time (Thread sleep 1000)
Elapsed time 1000.277967 msecs

ここで、Clojureと同様のセマンティクスを持つ記憶されていない範囲が必要です

case class MyRange(start : Int, end : Int) {
  def isEmpty = start >= end
  def first = if (!isEmpty) start else error("empty range")
  def rest = new MyRange(start + 1, end)
}

その「追加」から直接続きます

def add(a: MyRange, b: Long): Long = {
    if (a.isEmpty) b else add(a.rest, b + a.first)
}

そして、同じボックスにあるClojureよりもはるかに高速です

scala> time(add(MyRange(1, 9999999), 0))
Elapsed time 252.526784 msecs
res1: Long = 49999985000001

Scalaの標準ライブラリRangeを使用して、フォールドを実行できます。単純な原始再帰ほど高速ではありませんが、コードが少なく、Clojure再帰バージョンよりも高速です（少なくとも私のボックスでは）。

scala> time((1 until 9999999 foldLeft 0L)(_ + _))
Elapsed time 1995.566127 msecs
res2: Long = 49999985000001

メモ化されたストリームの折り畳みと対比

time((Stream from 1 take 9999998 foldLeft 0L)(_ + _)) 
Elapsed time 3879.991318 msecs
res3: Long = 49999985000001
于 2009-08-31T20:53:46.560 に答える
5

Clojureがテールケイルの最適化を処理する方法が原因だと思います。JVMはこの最適化をネイティブに実行しないため（そしてClojureとScalaの両方がその上で実行されます）、Clojureはrecurキーワードを介して末尾再帰を最適化します。Clojureサイトから：

関数型言語では、ループと反復は再帰関数呼び出しを介して置き換え/実装されます。このような言語の多くは、テール位置で行われる関数呼び出しがスタックスペースを消費しないことを保証しているため、再帰ループは一定のスペースを利用します。ClojureはJava呼び出し規約を使用しているため、同じ末尾呼び出しの最適化を保証することはできません。代わりに、recur特殊演算子を提供します。この演算子は、最も近い囲んでいるループまたは関数フレームに再バインドしてジャンプすることにより、定数スペースの再帰ループを実行します。末尾呼び出しの最適化ほど一般的ではありませんが、同じエレガントな構造のほとんどが可能であり、繰り返しの呼び出しが末尾位置でのみ発生することを確認できるという利点があります。

編集： Scalaは、特定の形式である限り、末尾呼び出しも最適化します。ただし、前のリンクが示すように、Scalaは非常に単純な場合にのみこれを実行できます。

実際、これは末尾呼び出しの最適化と呼ばれるScalaコンパイラの機能です。再帰呼び出しを最適化します。ただし、この機能は上記のような単純な場合にのみ機能します。たとえば、再帰が間接的である場合、JVM命令セットが制限されているため、Scalaは末尾呼び出しを最適化できません。

実際にコードをコンパイルおよび逆コンパイルして、どのJVM命令が生成されるかを確認しなければ、それは単純なケースの1つではないと思います（Michaelが言ったように、a.tail再帰的な各ステップでフェッチする必要があるため）。したがって、Scalaはそれを最適化できません。 。

于 2009-08-31T19:07:52.920 に答える
5

あなたのこの例のプロファイルを作成しました。クラスStream（それに関連する匿名関数-visualvmがクラッシュしたため、名前を忘れました）がヒープの大部分を占めているようです。これは、Scalaのsがメモリをリークするという事実に関連しています-Scala Trac＃692を参照してください。修正はScala2.8で予定されています。Stream。編集： ダニエルのコメントは、それがこのバグとは関係がないことを正しく指摘しました。これは、「val intsストリームヘッドを指しているため、ガベージコレクターは何も収集できない」ためです[ダニエル]。この質問に関連して、このバグレポートのコメントを読むのは良いと思いました。

add関数では、への参照を保持しているa.headため、ガベージコレクターはヘッドを収集できず、最終的に9999998要素を保持するストリームになります。これはGC化できません。

[少し間奏]

また、通過し続ける尻尾のコピーを保持することもできますが、それをどのように処理するかはわかりませんStream。リストを使用する場合、テールはコピーされません。例えば：

val xs =  List(1,2,3)
val ys = 1 :: xs
val zs = 2 :: xs

ここで、とは両方とも、少なくともヒープごとに同じテールysを「共有」します（ 、別名参照等式は、を生成します）。zsys.tail eq zs.tailtrue

[この小さな間奏は、多くのテールを渡すことは原則として本当に悪いことではないことを指摘することでした:)、少なくともリストについては、それらはコピーされません]

別の実装（非常に高速に実行され、純粋な機能的な実装よりも明確だと思います）は、命令型のアプローチを使用することです。

def addTo(n: Int, init: Int): Long = {
  var sum = init.toLong
  for(i <- 1 to n) sum += i
  sum
}

scala> addTo(9999998, 0)

Scalaでは、パフォーマンスと明快さのために命令型アプローチを使用することはまったく問題ありません（少なくとも私にとって、このバージョンのバージョンはaddその意図に対してより明確です）。さらに簡潔にするために、次のように書くこともできます

(1 to 9999998).reduceLeft(_ + _)

（実行速度は少し遅くなりますが、それでも妥当であり、メモリを爆破しません）

Clojureは完全に機能するため、より高速である可能性があると思います。したがって、Scala（機能、OO、および命令をブレンドする）よりも多くの最適化が可能です。しかし、私はClojureにあまり精通していません。

お役に立てれば ：）

于 2009-08-31T20:00:44.217 に答える