19

私は現在、より機能的なプログラミングスタイルを低レベル（LWJGLベース）のGUI開発を含むプロジェクトに適用しようとしています。明らかに、そのような場合、現在のバージョンでは変更可能な多くの状態を持ち歩く必要があります。私の目標は、副作用としての状態変化を回避するために、最終的に完全に不変の状態になることです。私はしばらくの間scalazのレンズと状態モナドを研究しましたが、私の主な関心事は残っています：これらの技術はすべてコピーオンライトに依存しています。私の州にはたくさんのフィールドとかなりのサイズのフィールドの両方があるので、パフォーマンスが心配です。

私の知る限り、不変オブジェクトを変更するための最も一般的なアプローチは、aの生成されたcopyメソッドを使用することですcase class（これは、レンズが内部で行うことでもあります）。私の最初の質問は、このcopyメソッドが実際にどのように実装されているかということです。次のようなクラスでいくつかの実験を行いました。

case class State(
  innocentField: Int, 
  largeMap: Map[Int, Int], 
  largeArray: Array[Int]
)

ベンチマークとその出力を見ると、-Xprof更新は実際にディープコピーを実行しているように見え、とsomeState.copy(innocentField = 42)のサイズを大きくするとパフォーマンスが大幅に低下することがわかります。内部的には参照がコンストラクターに渡されるだけなので、新しく構築されたインスタンスが元の状態のオブジェクト参照を共有することをどういうわけか期待していました。デフォルトのこのディープコピー動作を強制または無効にすることはできますか？largeMaplargeArraycopy

コピーオンライトの問題について考えている間、不変データの変更を一種の増分的な方法で（「更新の収集」または「収集」の意味で）保存するFPで、この問題に対するより一般的な解決策があるかどうか疑問に思いました。変更」）。驚いたことに、何も見つからなかったので、次のことを試しました。

// example state with just two fields
trait State {
  def getName: String
  def getX: Int

  def setName(updated: String): State = new CachedState(this) {
    override def getName: String = updated
  }
  def setX(updated: Int): State = new CachedState(this) {
    override def getX: Int = updated
  }

  // convenient modifiers
  def modName(f: String => String) = setName(f(getName))
  def modX(f: Int => Int) = setX(f(getX))

  def build(): State = new BasicState(getName, getX)
}

// actual (full) implementation of State
class BasicState(
  val getName: String, 
  val getX: Int
) extends State


// CachedState delegates all getters to another state
class CachedState(oldState: State) extends State {
  def getName = oldState.getName
  def getX    = oldState.getX
}

これで、次のようなことができます。

var s: State = new BasicState("hello", 42)

// updating single fields does not copy
s = s.setName("world")
s = s.setX(0)

// after a certain number of "wrappings"
// we can extract (i.e. copy) a normal instance
val ns = s.setName("ok").setX(40).modX(_ + 2).build()

今の私の質問は、このデザインについてどう思いますか？これは私が気付いていないある種のFPデザインパターンですか（ビルダーパターンとの類似性は別として）？似たようなものは見つからなかったので、このアプローチに大きな問題があるのではないかと思います。または、不変性をあきらめることなく、コピーオンライトのボトルネックを解決するための標準的な方法はありますか？

get / set / mod関数を何らかの方法で統合する可能性さえありますか？

編集：

copyディープコピーを実行するという私の仮定は確かに間違っていました。

4

2 に答える 2

12

これは基本的にビューと同じであり、遅延評価の一種です。このタイプの戦略は、Haskellでは多かれ少なかれデフォルトであり、Scalaではかなり使用されています（たとえば、マップ上のmapValues、コレクションにグループ化された、別のIteratorまたはStreamを返すIteratorまたはStreamのほとんどすべてを参照）。適切な状況で余分な作業を回避することは、実証済みの戦略です。

しかし、あなたの前提は多少間違っていると思います。

case class Foo(bar: Int, baz: Map[String,Boolean]) {}
Foo(1,Map("fish"->true)).copy(bar = 2)

実際には、マップが深くコピーされることはありません。参照を設定するだけです。バイトコードでの証明：

62: astore_1
63: iconst_2   // This is bar = 2
64: istore_2
65: aload_1
66: invokevirtual   #72; //Method Foo.copy$default$2:()Lscala/collection/immutable/Map;
69: astore_3   // That was baz
70: aload_1
71: iload_2
72: aload_3
73: invokevirtual   #76; //Method Foo.copy:(ILscala/collection/immutable/Map;)LFoo;

そして、それが何をするのか見てみましょうcopy$default$2：

0:  aload_0
1:  invokevirtual   #50; //Method baz:()Lscala/collection/immutable/Map;
4:  areturn

マップを返すだけです。

そしてcopyそれ自体？

0:  new #2; //class Foo
3:  dup
4:  iload_1
5:  aload_2
6:  invokespecial   #44; //Method "<init>":(ILscala/collection/immutable/Map;)V
9:  areturn

通常のコンストラクターを呼び出すだけです。マップの複製はありません。

したがって、コピーするときは、コピーするオブジェクトの新しいコピーであるオブジェクトを1つだけ作成し、フィールドに入力します。フィールドの数が多い場合は、ビューが速くなります（新しいオブジェクトを1つ作成する必要があるため）。 （関数アプリケーションバージョンを使用する場合は2つ、関数オブジェクトも作成する必要があるため）が、フィールドは1つだけです）。それ以外はほぼ同じです。

したがって、はい、潜在的には良い考えですが、あなたのケースでそれが価値があることを確認するために慎重にベンチマークしてください-ケースクラスにすべてを任せるのではなく、手作業でかなりのコードを書く必要があります。

于 2012-11-06T22:24:34.463 に答える
3

copyケースクラスの操作でのタイミングパフォーマンスの（かなり大まかな）テストを書いてみました。

object CopyCase {

    def main(args: Array[String]) = {

        val testSizeLog = byTen(10 #:: Stream[Int]()).take(6).toList
        val testSizeLin = (100 until 1000 by 100) ++ (1000 until 10000 by 1000) ++ (10000 to 40000 by 10000)

        //warmUp
        runTest(testSizeLin)
        //test with logarithmic size increments 
        val times = runTest(testSizeLog)
        //test with linear size increments 
        val timesLin = runTest(testSizeLin)

        times.foreach(println)
        timesLin.foreach(println)
    }

    //The case class to test for copy
    case class State(
        innocentField: Int, 
        largeMap: Map[Int, Int], 
        largeArray: Array[Int]
    )

    //executes the test
    def runTest(sizes: Seq[Int]) = 
        for {
            s <- sizes
            st = State(s, largeMap(s), largeArray(s))
            //(time, state) = takeTime (st.copy(innocentField = 42)) //single run for each size
            (time, state) = mean(st.copy(innocentField = 42))(takeTime) //mean time on multiple runs for each size
        } yield (s, time)

    //Creates the stream of 10^n  with n = Naturals+{0}
    def byTen(s: Stream[Int]): Stream[Int] = s.head #:: byTen(s map (_ * 10))

    //append the execution time to the result
    def takeTime[A](thunk: => A): (Double, A) = {
        import System.{currentTimeMillis => millis, nanoTime => nanos}
        val t0:Double = nanos
        val res = thunk
        val time = ((nanos - t0) / 1000)
        (time, res)
    }

    //does a mean on multiple runs of the first element of the pair 
    def mean[A](thunk: => A)(fun: (=> A) => (Double, A)) = {
        val population = 50
        val mean = ((for (n <- 1 to population) yield fun(thunk)) map (_._1) ).sum / population
        (mean, fun(thunk)._2)
    }

    //Build collections for the requested size
    def largeMap(size: Int) = (for (i <- (1 to size)) yield (i, i)).toMap
    def largeArray(size: Int) = Array.fill(size)(1)
}

このマシンの場合：

  • CPU：64ビットデュアルコア-i5 3.10GHz
  • RAM：8GB RAM
  • OS：win7
  • Java：1.7
  • Scala：2.9.2

次の結果が得られましたが、これは私にはかなり規則的なように見えます。

(size, millisecs to copy)
(10,0.4347000000000001)
(100,0.4412600000000001)
(1000,0.3953200000000001)
(10000,0.42161999999999994)
(100000,0.4478600000000002)
(1000000,0.42816000000000015)
(100,0.4084399999999999)
(200,0.41494000000000014)
(300,0.42156000000000016)
(400,0.4281799999999999)
(500,0.42160000000000003)
(600,0.4347200000000001)
(700,0.43466000000000016)
(800,0.41498000000000007)
(900,0.40178000000000014)
(1000,0.44134000000000007)
(2000,0.42151999999999995)
(3000,0.42148)
(4000,0.40842)
(5000,0.38860000000000006)
(6000,0.4413600000000001)
(7000,0.4743200000000002)
(8000,0.44795999999999997)
(9000,0.45448000000000005)
(10000,0.45448)
(20000,0.4281600000000001)
(30000,0.46768)
(40000,0.4676200000000001)

おそらく、さまざまなパフォーマンス測定を念頭に置いています。

または、プロファイルされた時間が、 ？をコピーするのではなく、実際にMapとの生成に費やされている可能性があります。Arraycase class

于 2012-11-07T11:00:45.533 に答える