3

假设我想要一个 Scala 数据结构，它实现了一个可以随时间变化的二维计数表（即，表中的单个单元格可以递增或递减）。我应该用什么来做到这一点？

我可以使用二维数组：

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

但是数组是可变的，我想我应该稍微喜欢不可变的数据结构。

所以我想到了使用二维向量：

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

但我不确定如何获得一个只改变一个元素的新向量。

最好的方法是什么？

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))

更快的是使用嵌套的 s——Vector大约是 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 倍）是只有一个您索引的向量：

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

对此没有内置方法，可能是因为它需要 Vector 知道它包含 Vectors 或 Vectors 或 Vectors 等，而大多数方法都是通用的，并且对于每个维数都需要一个单独的方法，因为您需要为每个维度指定一个坐标 arg。

但是，您可以自己添加这些；以下将带您进入 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 中，您不需要隐式定义，只需将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 回答