Что такое пошаговый массив?

Шагать — значит «делать большие шаги».

thefreedictionary.com/stride

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

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

Скажем, у вас есть структура

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

и массив

struct SomeStruct array[10];

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

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

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

Если вы хотите работать с подмножеством двумерного массива, вам нужно знать «шаг» массива. Предположим, у вас есть:

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);

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

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

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

Шаговые массивы

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

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

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

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

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

Вариант 2 (нижний уровень): Шаг — это расстояние между смежными элементами массива.

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

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

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

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

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