更新一个二维计数表 [英] Updating a 2d table of counts

问题描述

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

Suppose I want a Scala data structure that implements a 2-dimensional table of counts that can change over time (i.e., individual cells in the table can be incremented or decremented). What should I be using to do this?

我可以使用二维数组:

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

但是数组是可变的，我想我应该更喜欢不可变的数据结构.

But Arrays are mutable, and I guess I should slightly prefer immutable data structures.

所以我考虑使用二维向量:

So I thought about using a 2-dimensional Vector:

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

但我不知道如何获得一个只改变一个元素的新向量.

But I'm not sure how to get a new vector with only a single element changed.

最好的方法是什么?

推荐答案

最佳取决于您的标准是什么.最简单的不可变变体是使用从 (Int,Int) 到您的计数的映射:

Best depends on what your criteria are. The simplest immutable variant is to use a map from (Int,Int) to your count:

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)) 有点烦人，但还不错.

Then you access your values with c(i,j) and set them with c += ((i,j) -> n); c += ((i,j) -> (c(i,j)+1)) is a little bit annoying, but it's not too bad.

更快的是使用嵌套的 Vectors——大约是 2 到 3 倍，这取决于你是否倾向于一遍又一遍地重新设置相同的元素——但它有一个丑陋的更新方法:

Faster is to use nested Vectors--by about a factor of 2 to 3, depending on whether you tend to re-set the same element over and over or not--but it has an ugly update method:

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 倍)是只有一个向量可以索引:

Faster yet (by about 2x) is to have only one vector which you index into:

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

If you don't need immutability and your table size isn't going to change, just use an array as you've shown. It's ~200x faster than the fastest vector solution if all you're doing is incrementing and decrementing an integer.

这篇关于更新一个二维计数表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！