Schritt eines Arrays - Stride of an array

Bei der Computerprogrammierung ist der Schritt eines Arrays (auch als Inkrement , Tonhöhe oder Schrittgröße bezeichnet ) die Anzahl der Speicherstellen zwischen den Anfängen aufeinanderfolgender Array- Elemente, gemessen in Bytes oder in Einheiten der Größe der Elemente des Arrays. Der Schritt kann nicht kleiner als die Elementgröße sein, kann jedoch größer sein, was auf zusätzlichen Abstand zwischen den Elementen hinweist.

Ein Array mit einem Schritt, der genau der Größe der einzelnen Elemente entspricht, ist im Speicher zusammenhängend. Solche Arrays werden manchmal als Einheitsschritte bezeichnet . Einheitsschritt-Arrays sind manchmal effizienter als Nicht-Einheitsschritt-Arrays, aber Nicht-Einheitsschritt-Arrays können für 2D- oder mehrdimensionale Arrays effizienter sein , abhängig von den Auswirkungen des Cachings und den verwendeten Zugriffsmustern . Dies ist auf das Prinzip der Lokalität zurückzuführen , insbesondere auf die räumliche Lokalität .

Gründe für einen Schritt ohne Einheit

Arrays können in mindestens drei Fällen einen Schritt haben, der größer als die Breite ihrer Elemente in Bytes ist:

Polsterung

In vielen Sprachen (einschließlich C und C ++ ) können Strukturen aufgefüllt werden , um die Wortlänge und / oder die Cache-Zeilengröße des Computers besser zu nutzen . Zum Beispiel:

struct A {
    int a;
    char b;
};

struct A myArray[100];

myArray Wenn sich der C-Code für eine 32-Bit- Architektur und der Compiler kompiliert hätte , könnte sich herausstellen, dass im obigen Code-Snippet ein Schritt von acht Bytes statt fünf (4 Bytes für das int plus eins für das char) vorliegt wurde (wie normalerweise) für eine minimale Verarbeitungszeit und nicht für eine minimale Speichernutzung optimiert.

Überlappende parallele Arrays

In einigen Sprachen können Arrays von Strukturen als überlappende parallele Arrays mit nicht einheitlichen Schritten behandelt werden:

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

Diese Redewendung ist eine Form der Typ-Punning .

Array-Querschnitt

Einige Sprachen wie PL / I erlauben einen sogenannten Array-Querschnitt , bei dem bestimmte Spalten oder Zeilen aus einem größeren Array ausgewählt werden. Zum Beispiel, wenn ein zweidimensionales Array als deklariert ist

declare some_array (12,2)fixed;

Ein Array mit einer Dimension, das nur aus der zweiten Spalte besteht, kann als bezeichnet werden

some_array(*,2)

Beispiel eines mehrdimensionalen Arrays mit nicht einheitlichem Schritt

Ein Schritt ohne Einheit ist besonders nützlich für Bilder. Es ermöglicht das Erstellen von Teilbildern, ohne die Pixeldaten zu kopieren. Java-Beispiel:

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

Verweise