Оптимизированные «многомерные» массивы в Ruby

Question

С самого рождения меня всегда учили избегать вложенных массивов, таких как чума, по причинам производительности и внутренней структуры данных.Поэтому я пытаюсь найти хорошее решение для оптимизированных многомерных структур данных в Ruby.

Типичное решение может включать использование одномерного массива и доступ к каждому из них x*width + y.

Ruby.имеет возможность перегрузить оператор [], поэтому, возможно, хорошее решение будет включать в себя использование multi_dimensional_array[2,4] или даже использование сплата для поддержки произвольных величин измерений.(Но на самом деле мне нужны только два измерения)

Есть ли уже библиотека / гем для этого?Если нет, то какой будет лучший способ написать это?

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

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

Answer 1

narray

NArray - это класс числовых N-мерных массивов.Поддерживаемые типы элементов: 1/2/4-байтовое целое число, вещественная / сложная одинарная / двойная точность и объект Ruby.Эта библиотека расширений включает в себя быстрый расчет и простое манипулирование большими числовыми массивами в языке Ruby.NArray имеет функции, аналогичные NumPy, но NArray имеет векторные и матричные подклассы.

Answer 2

Вы можете наследовать от Array и создать свой собственный класс, который эмулировал многомерный массив (но внутренне был простым одномерным массивом).Вы можете увидеть некоторое ускорение, но трудно сказать, не написав код в обоих направлениях и не профилировав его.

Возможно, вы захотите поэкспериментировать с классом NArray .

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

array.each {|x|
    x.each {|y|
        y.each {|z|
            ...
        }
    }
}

Это позволяет вам выполнить один поиск в первом измерении, а затем получить доступ ко всему «позади», а затем один поиск во втором.измерение и т. д. и т. д. Это приведет к значительно меньшему количеству поисков, чем к случайному доступу к элементам.

Если вам нужен произвольный доступ к элементам, вы можете вместо этого попробовать использовать хеш.Вы можете взять индексы массива, объединить их вместе в виде строки и использовать их в качестве хэш-ключа (например, array[12][0][3] становится hash['0012_0000_0003']).Это может привести к более быстрому «произвольному доступу», но вы бы наверняка захотели его профилировать.

Есть ли шанс, что вы сможете опубликовать свой проблемный код?Знание кода проблемы поможет нам порекомендовать решение.

Answer 3

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

Большое правило: не прыгайте по вложенному массиву, попробуйте пройти его линейно от строки к строке.