3

時間とともに変化する (つまり、テーブル内の個々のセルをインクリメントまたはデクリメントできる) カウントの 2 次元テーブルを実装する Scala データ構造が必要だとします。これを行うには何を使用すればよいですか?

2 次元配列を使用できます。

val x = Array.fill[Int](1, 2) = 0
x(1)(2) += 1

しかし、配列は可変であり、不変のデータ構造を少し好むべきだと思います。

そこで、2 次元のベクターを使用することを考えました。

val x = Vector.fill[Int](1, 2) = 0
// how do I update this? I want to write something like val newX : Vector[Vector[Int]] = x.add((1, 2), 1)
// but I'm not sure how

しかし、要素が 1 つだけ変更された新しいベクターを取得する方法がわかりません。

最善のアプローチは何ですか？

4

3 に答える 3

6

最適は、基準が何であるかによって異なります。最も単純な不変のバリアントは、(Int,Int) からカウントへのマップを使用することです。

var c = (for (i <- 0 to 99; j <- 0 to 99) yield (i,j) -> 0).toMap

次に、で値にアクセスしc(i,j)、で設定しc += ((i,j) -> n)ます。c += ((i,j) -> (c(i,j)+1))少し面倒ですが、それほど悪くはありません。

ネストされたVectors を使用する方が高速ですが、同じ要素を何度もリセットする傾向があるかどうかに応じて、約 2 倍から 3 倍になりますが、更新方法が醜いです。

var v = Vector.fill(100,100)(0)
v(82)(49)     // Easy enough
v = v.updated(82, v(82).updated(49, v(82)(49)+1)    // Ouch!

さらに高速 (約 2 倍) は、インデックスを作成するベクトルを 1 つだけ持つことです。

var u = Vector.fill(100*100)(0)
u(82*100 + 49)    // Um, you think I can always remember to do this right?
u = u.updated(82*100 + 49, u(82*100 + 49)+1)       // Well, that's actually better

不変性が必要なく、テーブルのサイズが変わらない場合は、示したように配列を使用してください。整数のインクリメントとデクリメントだけを行っている場合、最速のベクトル ソリューションよりも最大 200 倍高速です。

于 2012-09-26T22:27:18.877 に答える
3

これを非常に一般的で機能的な (ただし必ずしもパフォーマンスが高いとは限らない) 方法で行いたい場合は、レンズを使用できます。Scalaz 7の実装をどのように使用できるかの例を次に示します。たとえば:

import scalaz._

def at[A](i: Int): Lens[Seq[A], A] = Lens.lensg(a => a.updated(i, _), (_(i)))
def at2d[A](i: Int, j: Int) = at[Seq[A]](i) andThen at(j)

そしてちょっとしたセットアップ：

val table = Vector.tabulate(3, 4)(_ + _)

def show[A](t: Seq[Seq[A]]) = t.map(_ mkString " ") mkString "\n"

これにより、次のことがわかります。

scala> show(table)
res0: String = 
0 1 2 3
1 2 3 4
2 3 4 5

レンズは次のように使用できます。

scala> show(at2d(1, 2).set(table, 9))
res1: String = 
0 1 2 3
1 2 9 4
2 3 4 5

または、特定のセルの値を取得できます。

scala> val v: Int = at2d(2, 3).get(table)
v: Int = 5

または、特定のセルに関数を適用するなど、より複雑なことを多数実行します。

scala> show(at2d(2, 2).mod(((_: Int) * 2), table))
res8: String = 
0 1 2 3
1 2 3 4
2 3 8 5

等々。

于 2012-09-27T00:04:02.997 に答える
1

これには組み込みのメソッドはありません。おそらく、ベクターがベクター、ベクター、ベクターなどを含むことをベクターが認識している必要があるためですが、ほとんどのメソッドは一般的であり、次元数ごとに個別のメソッドが必要になります。 、各次元の座標引数を指定する必要があるためです。

ただし、これらは自分で追加できます。以下では4Dまで使用できますが、必要なのが2Dのビットを追加するだけでもかまいませんが、次のようになります。

object UpdatableVector {
  implicit def vectorToUpdatableVector2[T](v: Vector[Vector[T]]) = new UpdatableVector2(v)
  implicit def vectorToUpdatableVector3[T](v: Vector[Vector[Vector[T]]]) = new UpdatableVector3(v)
  implicit def vectorToUpdatableVector4[T](v: Vector[Vector[Vector[Vector[T]]]]) = new UpdatableVector4(v)

  class UpdatableVector2[T](v: Vector[Vector[T]]) {
    def updated2(c1: Int, c2: Int)(newVal: T) =
      v.updated(c1, v(c1).updated(c2, newVal))
  }

  class UpdatableVector3[T](v: Vector[Vector[Vector[T]]]) {
    def updated3(c1: Int, c2: Int, c3: Int)(newVal: T) =
      v.updated(c1, v(c1).updated2(c2, c3)(newVal))
  }

  class UpdatableVector4[T](v: Vector[Vector[Vector[Vector[T]]]]) {
    def updated4(c1: Int, c2: Int, c3: Int, c4: Int)(newVal: T) =
      v.updated(c1, v(c1).updated3(c2, c3, c4)(newVal))
  }
}

Scala 2.10では、暗黙のdefは必要なくimplicit、クラス定義にキーワードを追加するだけです。

テスト：

  import UpdatableVector._

  val v2 = Vector.fill(2,2)(0)
  val r2 = v2.updated2(1,1)(42)
  println(r2) // Vector(Vector(0, 0), Vector(0, 42))

  val v3 = Vector.fill(2,2,2)(0)
  val r3 = v3.updated3(1,1,1)(42)
  println(r3) // etc

それがお役に立てば幸いです。

于 2012-09-27T01:43:16.330 に答える