оптимальный способ хранения многомерного массива / тензора

Question

Я пытаюсь создать тензорный (можно представить как многомерный массив) пакет в scala. До сих пор я хранил данные в 1D Vector и делал индексную арифметику.

Но нарезка и подмассивы не так легко получить. Нужно сделать много арифметики, чтобы преобразовать многомерные индексы в одномерные индексы.

Есть ли оптимальный способ хранения многомерного массива? Если нет, то есть 1D массив - это лучшее решение, как можно оптимально нарезать массивы (какой-то конкретный код действительно помог бы мне)?

Answer 1

Ключ к ответу на этот вопрос: когда косвенное указание быстрее арифметического? Ответ почти никогда. Обходы по порядку могут быть примерно такими же быстрыми для 2D, и от этого дела идут хуже:

2D random access
  Array of Arrays - 600 M / second
  Multiplication - 1.1 G / second

3D in-order
  Array of Array of Arrays - 2.4G / second
  Multiplication - 2.8 G / second

(etc.)

Так что тебе лучше просто делать математику.

Теперь вопрос в том, как сделать нарезку. Первоначально, если у вас есть измерения n1, n2, n3, ... и индексы i1, i2, i3, ..., вы вычисляете смещение в массиве

i = i1 + n1*(i2 + n2*(i3 + ... ))

, где обычно i1 выбирается как последнее (самое внутреннее) измерение (но в целом это должно быть измерение чаще всего в самом внутреннем цикле). То есть, если бы это был массив массивов (...), вы бы указали в нем как a(...)(i3)(i2)(i1).

Теперь предположим, что вы хотите нарезать это. Во-первых, вы можете задать смещение o1, o2, o3 для каждого индекса:

i = (i1 + o1) + n1*((i2 + o2) + n2*((i3 + o3) + ...))

и тогда у вас будет более короткий диапазон для каждого (назовем это m1, m2, m3, ...).

Наконец, если вы полностью исключите измерение - скажем, например, что m2 == 1, то есть i2 == 0, вы просто упростите формулу:

i = (i1 + o1 + n1*o2) + (n1+n2)*((i3 + o3) + ... ))

Я оставлю это в качестве упражнения для читателя, чтобы выяснить, как это сделать в целом, но учтите, что мы можем хранить новые константы o1 + n1*o21 и n1+n2, поэтому нам не нужно продолжать делать эту математику ломтик.

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

Answer 2

Просто идея: как насчет карты с Int-кортежами в качестве ключей? Пример:

val twoDimMatrix = Map((1,1) -> -1, (1,2) -> 5, (2,1) -> 7.7, (2,2) -> 9)

и тогда вы могли бы

scala> twoDimMatrix.filterKeys{_._2 == 1}.values 
res1: Iterable[AnyVal] = MapLike(-1, 7.7)

или

twoDimMatrix.filterKeys{tuple => { val (dim1, dim2) = tuple; dim1 == dim2}} //diagonal

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

Answer 3

Из моего собственного общего опыта: если вам нужно написать класс многомерного (прямоугольного) массива самостоятельно, не ставьте целью хранить данные как Array[Array[Double]], но используйте одномерное хранилище и добавляйте вспомогательные методы для преобразования многомерного доступа кортежи с простым индексом и наоборот.

При использовании списков списков вам нужно много делать для того, чтобы все списки были одинакового размера, и вы должны быть осторожны при назначении подсписка другому подсписку (потому что это делает назначенный подсписку идентичным первому и вы удивляетесь, почему изменение предмета на (0,5) также меняет (3,5)).

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

Answer 4

Вы можете просто хранить информацию в многомерном массиве ( например, . `Array [Array [Double]]).

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

Для арифметики срезов.Это зависит от того, какой тип нарезки вам требуется.Я полагаю, у вас уже есть функция для извлечения элемента на основе индексов.Поэтому напишите основной цикл сплайсинга, основанный на итерации индексов, вставьте вручную выражение для извлечения элемента, а затем попытайтесь упростить весь цикл.Часто это проще, чем написать правильное выражение с нуля.

Answer 5

Как только номер измерения известен до проектирования, вы можете использовать коллекцию collection ... (n раз) collection. Если вы должны быть в состоянии построить редактор для любого числа измерений, то в Scala API нет ничего удобного для этого (насколько я знаю).