Krok pole - Stride of an array

V počítačovém programování je krok pole (označovaný také jako přírůstek , výška tónu nebo velikost kroku ) počet míst v paměti mezi počátky po sobě následujících prvků pole , měřeno v bajtech nebo v jednotkách velikosti prvků pole. Krok nemůže být menší než velikost prvku, ale může být větší, což naznačuje další mezeru mezi prvky.

Pole s krokem přesně stejné velikosti jako velikost každého z jeho prvků je v paměti souvislé. O takových polích se někdy říká, že mají jednotkový krok . Jednotková pole pole jsou někdy efektivnější než pole jednotky bez jednotky, ale pole jiné než jednotky mohou být efektivnější pro 2D nebo vícerozměrná pole v závislosti na účincích ukládání do mezipaměti a použitých přístupových vzorcích . To lze připsat principu lokality , konkrétně prostorové lokalitě .

Důvody pro nejednotný krok

Pole mohou mít krok větší než šířka jejich prvků v bajtech alespoň ve třech případech:

Polstrování

Mnoho jazyků (včetně C a C ++ ) umožňují struktury být polstrované , aby lépe využívaly buď o délce slova a / nebo velikost vyrovnávací vedení stroje. Například:

struct A {
    int a;
    char b;
};

struct A myArray[100];

Ve výše uvedeném fragmentu kódu myArray by se mohlo ukázat, že má krok osm bajtů, spíše než pět (4 bajty pro int plus jeden pro char), pokud byl kód C kompilován pro 32bitovou architekturu a kompilátor byl optimalizován (jak je tomu obvykle) pro minimální dobu zpracování, spíše než minimální využití paměti.

Překrývající se paralelní pole

Některé jazyky umožňují, aby pole struktur byly považovány za překrývající se paralelní pole s nejednotkovým krokem:

#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;
}

Tento idiom je formou punningu typu .

Průřez pole

Některé jazyky, jako je PL / I, umožňují takzvaný průřez pole , který vybírá určité sloupce nebo řádky z většího pole. Například pokud je dvourozměrné pole deklarováno jako

declare some_array (12,2)fixed;

na pole jedné dimenze skládající se pouze z druhého sloupce lze odkazovat jako

some_array(*,2)

Příklad vícerozměrného pole s nejednotkovým krokem

Nejednotkový krok je zvláště užitečný pro obrázky. Umožňuje vytvářet podobrazy bez kopírování dat obrazových bodů. Příklad 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];
    }
}

Reference