Шаг массива

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

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

Причины неединичного шага

Массивы могут иметь шаг, превышающий ширину их элементов в байтах как минимум в трех случаях:

Заполнение

Многие языки (включая C и C++ ) позволяют дополнять структуры , чтобы лучше использовать длину слова и/или размер строки кэша машины. Например:

struct A {
    int a;
    char b;
};

struct A myArray[100];

В приведенном выше фрагменте кода myArray вполне может оказаться, что размер шага составит восемь байт, а не пять (4 байта для int плюс один для char), если код C был скомпилирован для 32-битной архитектуры и компилятор оптимизировал (как это обычно бывает) В данном случае) для минимального времени обработки, а не минимального использования памяти.

Перекрывающиеся параллельные массивы

Некоторые языки позволяют массивы структур рассматривать как перекрывающиеся параллельные массивы с неединичным шагом:

#include <stdio.h>

struct MyRecord {
    int value;
    char *text;
};

/** Print the contents of an array of ints with the given stride.
    Note that size_t is the correct type, as int can overflow. */
void print_some_ints(const int *arr, int length, size_t stride)
{
    int i;
    printf("Address\t\tValue\n");
    for (i=0; i < length; ++i) {
        printf("%p\t%d\n", arr, arr[0]);
        arr = (int *)((unsigned char *)arr + stride);
    }
}

int main(void)
{
    int ints[100] = {0};
    struct MyRecord records[100] = {0};

    print_some_ints(&ints[0], 100, sizeof ints[0]);
    print_some_ints(&records[0].value, 100, sizeof records[0]);
    return 0;
}

Эта идиома является разновидностью каламбура .

Сечение массива

Некоторые языки, такие как PL/I или Fortran, допускают так называемое поперечное сечение массива , которое выбирает определенные столбцы или строки из большего массива. Например, если двумерный массив объявлен как

declare some_array (12,2)fixed;

массив одного измерения, состоящий только из второго столбца, может называться как

some_array(*,2)

Пример многомерного массива с неединичным шагом

Неединичный шаг особенно полезен для изображений. Это позволяет создавать фрагменты изображений без копирования данных пикселей. Пример Java:

public class GrayscaleImage {
    private final int width, height, widthStride;
    /** Pixel data. Pixel in single row are always considered contiguous in this example. */
    private final byte[] pixels;
    /** Offset of the first pixel within pixels */
    private final int offset;

    /** Constructor for contiguous data */
    public Image(int width, int height, byte[] pixels) {
        this.width = width;
        this.height = height;
        this.pixels = pixels;
        this.offset = 0;
        this.widthStride = width;
    }

    /** Subsection constructor */
    public Image(int width, int height, byte[] pixels, int offset, int widthStride) {
        this.width = width;
        this.height = height;
        this.pixels = pixels;
        this.offset = offset;
        this.widthStride = widthStride;
    }

    /** Returns a subregion of this Image as a new Image. This and the new image share
        the pixels, so changes to the returned image will be reflected in this image. */
    public Image crop(int x1, int y1, int x2, int y2) {
        return new Image(x2 - x1, y2 - y1, pixels, offset + y1 * widthStride + x1, widthStride);
    }

    /** Returns pixel value at specified coordinate */
    public byte getPixelAt(int x, int y) {
        return pixels[offset + y * widthStride + x];
    }
}