在Scala中使用什么结构来创建常量访问时间不可变表

Question

Scala有任何类型的类可以处理这个吗?我正在考虑使用Array[Array[_]]，因为它非常适合我的需求。

我还有其他选择吗?我认为使用Map[(Int,Int),_]太慢了，因为它具有线性访问时间。

Answer 1

Map实现中的访问(除了ListMap)当然不是线性的(非常小的地图，少于4个元素，确实做线性搜索，但这是一个非常快的实现对于如此小的地图，这是O(N)与一个非常小的N，和一个非常小的k因子太。但是当表增长时，使用不同的算法，渐近地快得多，通常是O(log(N))或O(1)。

然而，如果你需要的是一个表/矩阵，在某种意义上，它包含键(i,j)满足0 <= i <M,><= j <N，(从1开始也可以)一般地图可能不是最佳选择。如果表是满的，那么所有(i,j)都有值。那么基于Array的东西，Array[Array[_]]或甚至单个数组可能会更好。如果你想要一些专门化的东西，也许你不想实现完整的Map接口。>

Answer 2

HashMap几乎做到了。这个Scala集合性能页面非常有用。

Answer 3

为了获得最佳性能，您可能希望尽可能避免垃圾收集器(GC)。这意味着不创建元组对象(i, j)和不装箱原语。如果您的表将被完全填充(而不是稀疏)，那么您的Array of Arrays的想法是合理的。但是，为了获得最佳性能，我将采用didierd的想法，并将所有内容打包到带有访问器的单个数组中。下面是一个可能的实现:

// specialize A to avoid boxing primitives such as Int, Double, ...
class Table[@specialized A: Manifest](numRows: Int, numCols: Int) {
  val data = new Array[A](numRows*numCols)
  def checkIndices(i: Int, j: Int) {
    require (i >= 0 && i < numRows && j >= 0 && j < numCols)
  }
  def apply(i: Int, j: Int): A = {
    checkIndices(i, j)
    data(i*numCols + j)
  } 
  def update(i: Int, j: Int, x: A) {
    checkIndices(i, j)
    data(i*numCols + j) = x
  } 
}

您可以像这样自然地使用它(注意您从特殊的apply和update方法中获得的良好语法):

scala> val table = new Table[Double](2, 2)
table: Table[Double] = Table$mcD$sp@4d22366e
scala> table(0, 0) = 3.0
scala> table(1, 1) = table(0, 0) + 2.0
scala> table(2, 1)
java.lang.IllegalArgumentException: requirement failed
...

另一方面，如果表是稀疏的，那么最好使用Map来为所有空条目节省内存。请注意，尽管Map有快速的update和apply方法(几乎不变)，但它们仍然比数组访问慢一些(主要是由于GC的压力;Map不是专门化的，键和值都必须是堆分配的)