Что такое чередующийся массив?

Ответ 1

Чтобы сделать шаг, выполните "длинные шаги"

thefreedictionary.com/stride

Для массива это означало бы, что присутствуют только некоторые из элементов, как и каждый 10-й элемент. Затем вы можете сэкономить место, не сохраняя пустые элементы между ними.

Плотный массив будет таким, где присутствуют многие, если не все, элементы, поэтому между элементами нет пустого пространства.

Ответ 2

Скажите, что у вас есть структура

struct SomeStruct {
    int someField;
    int someUselessField;
    int anotherUselessField;
};

и массив

struct SomeStruct array[10];

Затем, если вы посмотрите на все someField в этом массиве, их можно считать самим массивом, но они не занимают последующих ячеек памяти, поэтому этот массив является strided. Шаг здесь sizeof(SomeStruct), т.е. Расстояние между двумя последующими элементами перечеркнутой решетки.

Редкий массив, упомянутый здесь, является более общим понятием и фактически другим: чередующийся массив не содержит нулей в пропущенных ячейках памяти, они просто не являются частью массива.

Strided array - это обобщение обычных (плотных) массивов, когда stride != sizeof(element).

Ответ 3

Если вы хотите работать с подмножеством 2D-массива, вам нужно знать "шаг" массива. Предположим, что у вас есть:

int array[4][5];

и вы хотите работать с подмножеством элементов, начиная с массива [1] [1], до массива [2,3]. Это, по существу, ядро ​​диаграммы ниже:

+-----+-----+-----+-----+-----+
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
+-----+=====+=====+=====+-----+
| 1,0 [ 1,1 | 1,2 | 1,3 ] 1,4 |
+-----+=====+=====+=====+-----+
| 2,0 [ 2,1 | 2,2 | 2,3 ] 2,4 |
+-----+=====+=====+=====+-----+
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |
+-----+-----+-----+-----+-----+

Чтобы получить доступ к подмножеству массива в функции точно, вам нужно указать вызываемой функции шаг массива:

int summer(int *array, int rows, int cols, int stride)
{
    int sum = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            sum += array[i * stride + j];
    return(sum);
}

и вызов:

int sum = summer(&array[1][1], 2, 3, 5);

Ответ 4

Я добавляю еще один ответ здесь, так как я не нашел ни одного из существующих удовлетворительным.

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

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

Направленные массивы

Компиляция APL для JavaScript объясняет чередующиеся массивы как способ представления многомерных массивов с данными и шагами, в отличие от типичного "прямоугольного" представления массивы, которые предполагают неявный шаг 1. Он допускает как положительный, отрицательный, так и нулевой шаг. Зачем? Это позволяет многим операциям изменять только шаг и форму, а не базовые данные, что позволяет эффективно манипулировать большими массивами.

Преимущество этого чередующегося представления становится очевидным при работе с большими объемами данных. Функции, такие как transpose (⍉⍵), reverse (⌽⍵) или drop (⍺↓⍵), могут повторно использовать массив данных и только заботиться о том, чтобы придать их новую форму, шаг и смещение. Реконструированный скаляр, например. 1000000⍴0, может занимать только постоянный объем памяти, используя тот факт, что шагами могут быть 0.

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

Ответ 5

В высокооптимизированном коде одна разумная технология coomon заключается в вставке дополнений в массивы. Это означает, что N-й логический элемент больше не находится в смещении N*sizeof(T). Причиной этого может быть оптимизация, так это то, что некоторые кеши ограничены ассоциативностью. Это означает, что они не могут кэшировать оба массива [i] и array [j] для некоторых пар i, j. Если алгоритм, работающий на плотном массиве, будет использовать многие из таких пар, добавление некоторых дополнений может уменьшить это.

Обычный случай, когда это происходит, заключается в обработке изображений. Изображение часто имеет ширину линии 512 байтов или другое "двоичное число раундов", а многие подпрограммы обработки изображений используют 3x3 окрестности пикселя. В результате вы можете получить довольно много выходов из кэша на некоторых архитектурах кэшей. Вставляя "странное" количество поддельных пикселей (например, 3) в конце каждой строки, вы изменяете "шаг" и там меньше помех кэша между соседними строками.

Это очень специфично для процессора, поэтому здесь нет общих советов.

Ответ 6

Возможность 1: Stride описывает буферный массив для чтения оптимизированного массива

Когда вы используете метод хранить многомерные массивы в линейном хранилище. Шаг описывает размер в каждом измерении буфера, который поможет вам прочитать этот массив. Изображение взято из Nd4j (дополнительная информация о Stride)

Возможность 2 (нижний уровень): Stride - это расстояние между смежными элементами массива

Это означает, что адреса элементов с индексами 0 и 1 не будут непрерывными в памяти, если вы не используете блок Stride. Большее значение будет иметь более отдаленные объекты в памяти.

Это полезно на низком уровне (оптимизация длины слова, перекрывающиеся массивы, оптимизация кеша). См. wikipedia.