更新二维计数表

Question

假设我想要一个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

但是我不确定如何只更改一个元素就可以得到一个新的向量。

最好的方法是什么？

Answer 1

最好取决于您的标准。最简单的不可变形式是使用从（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的倍数，具体取决于您是否倾向于一遍又一遍地重置相同的元素-但它具有丑陋的update方法：

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倍。