Лучший тип коллекции Scala для векторизованных числовых вычислений

Question

Ищете правильный тип данных (например, IndexedSeq[Double]) использовать при разработке предметной библиотеки числовых вычислений. Для этого вопроса я ограничиваю работу с 1-мерными массивами Double, Библиотека будет определять числовые функции, которые обычно применяются для каждого элемента в одномерном массиве.

Соображения:

• Предпочитают неизменные типы данных, такие как Vector или же IndexedSeq
• Хотите минимизировать преобразования данных
• Достаточно эффективный в пространстве и времени
• Дружественный для других людей, использующих библиотеку
• Элегантный и чистый API

Должен ли я использовать что-то выше по иерархии коллекций, таких как Seq?

Или лучше просто определить одноэлементные функции и оставить отображение / повторение для конечного пользователя?

Это кажется менее эффективным (поскольку некоторые вычисления могут выполняться один раз для набора вызовов), но в то же время более гибким API, поскольку он будет работать с любым типом коллекции.

Любые рекомендации?

Answer 1

Если ваши вычисления должны делать что-то удаленно вычислительное, используйте Arrayлибо в необработанном виде, либо в ваших собственных классах. Вы можете предоставить оболочку, совместимую с коллекцией, но сделать ее явной оболочкой только для взаимодействия. Все, кроме Array является общим и, следовательно, в штучной упаковке и, следовательно, сравнительно медленным и громоздким

Если вы не используете Arrayлюди будут вынуждены отказаться от всего, что у вас есть, и просто использовать Array вместо этого, когда производительность имеет значение. Может быть, все в порядке; может быть, вы хотите, чтобы вычисления были для удобства, а не эффективности. В этом случае я предлагаю использовать IndexedSeq для интерфейса, предполагая, что вы хотите, чтобы люди знали, что индексация не является чрезвычайно медленной (например, не List) и использовать Vector под капотом. Вы будете использовать примерно в 4 раза больше памяти, чем Array[Double]и быть в 3-10 раз медленнее для большинства операций с небольшим усилием (например, умножение).

Например, это:

val u = v.map(1.0 / _)   //  v is Vector[Double]

примерно в три раза медленнее, чем это:

val u = new Array[Double](v.length)
var j = 0
while (j<u.length) {
  u(j) = 1.0/v(j)      // v is Array[Double]
  j += 1
}

Если вы используете map метод на Arrayэто так же медленно, как Vector[Double] путь; операции на Array являются общими и, следовательно, в штучной упаковке. (И вот откуда большинство наказаний.)

Answer 2

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

Также обратите внимание, что текущей коллекцией по умолчанию для неизменяемых индексированных последовательностей является Vector, так что если вы напишите какой-нибудь код, подобный for (i <- 0 until n) yield {...}, это возвращает IndexedSeq[...] но тип времени выполнения - вектор. Таким образом, может быть хорошей идеей всегда использовать Векторы, поскольку некоторые двоичные операторы, которые принимают в качестве входных данных две последовательности, могут выиграть от того факта, что два аргумента имеют один и тот же тип реализации. (Сейчас это не совсем так, но кто-то указал, что конкатенация векторов может происходить в лог (N) времени, в отличие от текущего линейного времени, потому что второй параметр просто рассматривается как общая последовательность.)

Тем не менее, я считаю, что Seq[Double] уже должен предоставить большинство интерфейсов функций, которые вам нужны. А так как отображение результатов из Range не дает Vector напрямую я обычно ставлю Seq[Double] в качестве типа аргумента в качестве моего ввода, так что он имеет некоторую общность. Я ожидаю, что эффективность будет оптимизирована в базовой реализации.

Надеюсь, это поможет.