Stride of an array - Stride of an array
W programowania The kroku z układu (określany również jako przyrost , smoła lub wielkość kroku ) jest liczba miejsc w pamięci pomiędzy początkami kolejnych tablicy elementów, mierzona w bajtach lub w jednostki wielkości elementów tablicowych. Krok nie może być mniejszy niż rozmiar elementu, ale może być większy, wskazując na dodatkową przestrzeń między elementami.
Tablica z krokiem o dokładnie takim samym rozmiarze jak rozmiar każdego z jej elementów jest ciągła w pamięci. Czasami mówi się, że takie tablice mają krok jednostkowy . Jednostkowe tablice krokowe są czasami bardziej wydajne niż niejednostkowe tablice krokowe, ale niejednostkowe tablice krokowe mogą być bardziej wydajne w przypadku tablic 2D lub wielowymiarowych , w zależności od efektów buforowania i używanych wzorców dostępu . Można to przypisać zasadzie lokalności , w szczególności lokalności przestrzennej .
Przyczyny kroku bez jednostek
Tablice mogą mieć krok większy niż szerokość ich elementów w bajtach w co najmniej trzech przypadkach:
Wyściółka
Wiele języków (w tym C i C ++ ) pozwala na wypełnienie struktur, aby lepiej wykorzystać długość słowa i / lub rozmiar linii pamięci podręcznej maszyny. Na przykład:
struct A {
int a;
char b;
};
struct A myArray[100];
W powyższym fragmencie kodu myArray
może się okazać, że ma krok ośmiu bajtów zamiast pięciu (4 bajty dla int plus jeden dla znaku), jeśli kod C zostałby skompilowany dla architektury 32-bitowej , a kompilator został zoptymalizowany (jak to zwykle bywa) pod kątem minimalnego czasu przetwarzania, a nie minimalnego użycia pamięci.
Nakładające się tablice równoległe
W niektórych językach tablice struktur mogą być traktowane jako nakładające się tablice równoległe z niejednostkowym krokiem:
#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;
}
Ten idiom jest formą gry słów .
Przekrój tablicy
Niektóre języki, takie jak PL / I, pozwalają na tak zwany przekrój tablicy , który wybiera określone kolumny lub wiersze z większej tablicy. Na przykład, jeśli dwuwymiarowa tablica jest zadeklarowana jako
declare some_array (12,2)fixed;
tablica o jednym wymiarze składająca się tylko z drugiej kolumny może być określana jako
some_array(*,2)
Przykład wielowymiarowej tablicy z niejednostkowym krokiem
Krok bez jednostek jest szczególnie przydatny w przypadku obrazów. Pozwala na tworzenie podobrazów bez kopiowania danych pikseli. Przykład w Javie:
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];
}
}