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

Question

Существует также аналог, который называется массивом плотности.Что это значит?Я провел некоторый поиск, но не получил точную информацию.

Answer 1

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

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

и массив

struct SomeStruct array[10];

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

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

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

Answer 2

Ходить - значит «делать длинные шаги»

thefreedictionary.com / шаг

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

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

Answer 3

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

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

Answer 4

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

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

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

расширенные массивы

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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