Какие структуры использовать для создания неизменяемой таблицы с постоянным временем доступа в 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, 0 <= j <n (начиная с 1 будет тоже хорошо) общая карта может быть не лучшим выбором. Тем более, если таблица заполнена, то есть все (i, j) имеют значения. Тогда что-то на основе Array, либо Array [Array [_]], либо даже отдельный массив, может быть намного лучше. Если вы хотите что-то специализированное, возможно, вы не захотите реализовывать полный интерфейс Map. </p>

Answer 2

HashMap почти делает это. Эта страница производительности Scala может быть очень полезна.

Answer 3

Для максимальной производительности вы, вероятно, захотите максимально избегать сборщика мусора (GC). Это означает, что нельзя создавать объекты кортежей (i, j) и не создавать примитивы бокса. Если ваша таблица будет полностью заполнена (а не разрежена), то ваша идея Array of Arrays разумна. Однако для лучшей производительности я бы пошел с идеей Дидьера и собрал все в единый массив с аксессорами. Вот возможная реализация:

// 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 (почти постоянные), они все же немного медленнее, чем доступ к массиву (в основном из-за давления на ГХ; Map не специализирован, оба ключа и значения должны быть выделены в куче).