Как я могу написать эффективную массивоподобную структуру с настраиваемым индексным диапазоном в Scala? - PullRequest
Новая
       26

Как я могу написать эффективную массивоподобную структуру с настраиваемым индексным диапазоном в Scala?

0 голосов
/ 26 мая 2018

Я хочу что-то вроде массивов переменных-индексов Pascal, где пользователь указывает допустимый диапазон индекса.Вместо выбора по умолчанию для индексации его содержимого от 0 до длины-1 я хочу, чтобы первый индекс был, скажем, 10 000, а последний - 20 000.

Scala настолько гибок, что это то, что я хочу, выполнимо.Тем не менее, дисциплина потребуется для создания структуры данных, которая гармонизируется с остальными коллекциями.

Одним из «очевидных» решений может быть простое указание размера, равного 20 000, и потеря первой половины памяти, но это бесполезно.Кроме того, структура карты может быть сделана работать в один миг.Но накладные расходы, связанные с HashMap, на порядок выше, чем у массивоподобной структуры, которую я описываю.

В идеале, он не должен повторять или заново изобретать уже существующий код, и при этом он не должен быть чрезмерно сложным, даже внутренне.

В качестве примера того, что я хочу, рассмотрим массив с допустимыми индексами от 500 до 999. Я назову свой класс IndexedArray, чтобы отличить его от стандартного массива, используемого в Scala.Также я буду использовать традиционный диапазон из Scala для указания диапазона индекса в объявлении.

Чтобы не усложнять ситуацию, мне не нужна структура данных, чтобы отличаться от структуры.Все индексы будут смежными.

var histogram = new IndexedArray[Int](500 to 999)
histogram(500) = 10  // "first" entry has value 10
histogram(999) += 1  // "last" entry has value 1

Конечно, проблему можно решить, просто используя стандартный массив Scala и переназначая индекс при каждом доступе.Но разве это не рецепт для ошибок?Я хочу, чтобы структура данных скрывала эту маленькую деталь от моих глаз.

Моя структура данных, конечно, будет изменчивой, поскольку стандартные массивы в Scala являются изменяемыми;и единственная разница в поведении заключается в том, что индекс будет автоматически переназначаться при каждом доступе.

1 Ответ

0 голосов
/ 30 мая 2018

Оказывается, не так сложно найти хотя бы элементарную структуру, которая теперь работает так, как рекламируется.Я действительно предпочел бы, чтобы мой класс расширял соответствующую структуру уже в коллекциях Scala, чтобы незаметно сливаться с остальной частью API изменяемой коллекции.Тем не менее, я не смог сделать это до сих пор.

Однако мое простейшее решение показывает некоторую удивительности Scala, имея тот же синтаксис для доступа к элементам, что и стандартный массив Scala.

class IndexedArray[T: ClassTag](val range: Range)  {

  val size: Int = range.end - range.start + 1
  val start: Int = range.start
  val array = new Array[T](size)

  def apply(index: Int): T = array(index - start).asInstanceOf[T]

  lazy val elemTag: ClassTag[T] = ClassTag[T](array.getClass.getComponentType)

  def length: Int = array.length

  def update(index: Int, elem: T): Unit = array.update( index - start, elem )

}

Теперь можно создать экземпляр структуры данных, используя вышеупомянутый синтаксис, и использовать структуру данных следующим образом.(Для новичков в Scala следующие две строки эквивалентны и выполняют одно и то же.) 

var pascalLike = IndexedArray[Int](500 until 1000)

или 

var pascalLike = IndexedArray[Int](500 to 999)

Затем мы можем использовать структуру. 

pascalLike(500) = 100          // Sets the first element to 100
pascalLike(500) += 1           // Adds 1 to the first element
pascalLike(501) -= 2           // Subtracts 2 from the second element
println(pascalLike(501))       // Prints "-2"

Чего я не знаю, так это как заставить эту структуру «течь» вместе с остальным API коллекций Scala.Например, я хотел бы, чтобы индексный метод zipWithIndex работал так, как можно ожидать для такой структуры данных, используя индексы, соответствующие этой структуре.

Прямо сейчас, единственный способ объединить этого парня - это захватить базовый член array и надеяться, что компилятор Scala позволяет неявное преобразование, которое согласуется с тем, что хочет сделать пользователь, что не совсем соответствуетмои первоначальные цели.

...