Der schnellste Weg, ein 2d-Array in C auf Null zu setzen?

Ich möchte ein großes 2D-Array in C wiederholt auf Null setzen. Dies ist, was ich im Moment mache:

// Array of size n * m, where n may not equal m
for(j = 0; j < n; j++)
{
    for(i = 0; i < m; i++)
    {  
        array[i][j] = 0;
    }
}

Ich habe versucht, memset zu verwenden:

memset(array, 0, sizeof(array))

Dies funktioniert jedoch nur für 1D-Arrays. Wenn ich den Inhalt des 2D-Arrays drucke, ist die erste Zeile Nullen, aber dann habe ich eine Menge zufälliger großer Zahlen und es stürzt ab.

memset(array, 0, sizeof(array[0][0]) * m * n);

Wo mund nsind die Breite und Höhe des zweidimensionalen Arrays (in Ihrem Beispiel haben Sie also ein quadratisches zweidimensionales Array m == n).

Wenn arrayes sich wirklich um ein Array handelt, können Sie es mit "nullen":

memset(array, 0, sizeof array);

Es gibt jedoch zwei Punkte, die Sie kennen sollten:

• Dies funktioniert nur, wenn arrayes sich tatsächlich um ein "Two-D-Array" handelt, dh T array[M][N];für einen Typ deklariert wurde T.
• es funktioniert nur in dem Bereich, in dem arraydeklariert wurde. Wenn Sie es an eine Funktion übergeben, wird der Name array zu einem Zeiger und sizeofgibt Ihnen nicht die Größe des Arrays.

Lassen Sie uns ein Experiment machen:

#include <stdio.h>

void f(int (*arr)[5])
{
    printf("f:    sizeof arr:       %zu\n", sizeof arr);
    printf("f:    sizeof arr[0]:    %zu\n", sizeof arr[0]);
    printf("f:    sizeof arr[0][0]: %zu\n", sizeof arr[0][0]);
}

int main(void)
{
    int arr[10][5];
    printf("main: sizeof arr:       %zu\n", sizeof arr);
    printf("main: sizeof arr[0]:    %zu\n", sizeof arr[0]);
    printf("main: sizeof arr[0][0]: %zu\n\n", sizeof arr[0][0]);
    f(arr);
    return 0;
}

Auf meinem Computer wird Folgendes gedruckt:

main: sizeof arr:       200
main: sizeof arr[0]:    20
main: sizeof arr[0][0]: 4

f:    sizeof arr:       8
f:    sizeof arr[0]:    20
f:    sizeof arr[0][0]: 4

Obwohl arres sich um ein Array handelt, zerfällt es bei Übergabe in einen Zeiger auf sein erstes Element f(), und daher sind die eingedruckten Größen f()"falsch". In f()der Größe von arr[0]ist auch die Größe des Arrays arr[0], das ein "Array [5] von int" ist. Es ist nicht die Größe von a int *, da das "Zerfallen" nur auf der ersten Ebene stattfindet, und deshalb müssen wir deklarieren f(), dass ein Zeiger auf ein Array mit der richtigen Größe verwendet wird.

Wie ich bereits sagte, funktioniert das, was Sie ursprünglich getan haben, nur, wenn die beiden oben genannten Bedingungen erfüllt sind. Wenn nicht, müssen Sie tun, was andere gesagt haben:

memset(array, 0, m*n*sizeof array[0][0]);

Schließlich memset()und die von forIhnen gepostete Schleife sind im engeren Sinne nicht gleichwertig. Es könnte (und gab) Compiler geben, bei denen "alle Bits Null" für bestimmte Typen, wie z. B. Zeiger und Gleitkommawerte, nicht gleich Null ist. Ich bezweifle, dass Sie sich darüber Sorgen machen müssen.

Nun, der schnellste Weg, dies zu tun, besteht darin, es überhaupt nicht zu tun.

Klingt seltsam, ich weiß, hier ist ein Pseudocode:

int array [][];
bool array_is_empty;


void ClearArray ()
{
   array_is_empty = true;
}

int ReadValue (int x, int y)
{
   return array_is_empty ? 0 : array [x][y];
}

void SetValue (int x, int y, int value)
{
   if (array_is_empty)
   {
      memset (array, 0, number of byte the array uses);
      array_is_empty = false;
   }
   array [x][y] = value;
}

Eigentlich wird das Array immer noch gelöscht, aber nur, wenn etwas in das Array geschrieben wird. Dies ist hier kein großer Vorteil. Wenn das 2D-Array beispielsweise mithilfe eines Quad-Baums (kein dynamischer Geist) oder einer Sammlung von Datenzeilen implementiert wurde, können Sie den Effekt des Booleschen Flags lokalisieren, benötigen jedoch mehr Flags. Setzen Sie im Quad-Baum einfach das leere Flag für den Wurzelknoten, im Array von Zeilen setzen Sie einfach das Flag für jede Zeile.

Was führt zu der Frage "Warum möchten Sie ein großes 2D-Array wiederholt auf Null setzen?" Wofür wird das Array verwendet? Gibt es eine Möglichkeit, den Code so zu ändern, dass das Array nicht auf Null gesetzt werden muss?

Zum Beispiel, wenn Sie hatten:

clear array
for each set of data
  for each element in data set
    array += element 

Verwenden Sie es also für einen Akkumulationspuffer. Wenn Sie es dann so ändern, wird die Leistung ohne Ende verbessert:

 for set 0 and set 1
   for each element in each set
     array = element1 + element2

 for remaining data sets
   for each element in data set
     array += element 

Dies erfordert nicht, dass das Array gelöscht wird, funktioniert aber trotzdem. Und das ist viel schneller als das Löschen des Arrays. Wie gesagt, der schnellste Weg ist, es überhaupt nicht zu tun.

Wenn Sie wirklich, wirklich von Geschwindigkeit besessen sind (und nicht so sehr von Portabilität), denke ich, wäre der absolut schnellste Weg, dies zu tun, die Verwendung von SIMD-Vektor-Intrinsics. Auf Intel-CPUs können Sie beispielsweise die folgenden SSE2-Anweisungen verwenden:

__m128i _mm_setzero_si128 ();                   // Create a quadword with a value of 0.
void _mm_storeu_si128 (__m128i *p, __m128i a);  // Write a quadword to the specified address.

Jeder Speicherbefehl setzt vier 32-Bit-Ints bei einem Treffer auf Null.

p muss 16-Byte-ausgerichtet sein, aber diese Einschränkung ist auch gut für die Geschwindigkeit, da sie dem Cache hilft. Die andere Einschränkung ist, dass p auf eine Zuordnungsgröße zeigen muss, die ein Vielfaches von 16 Bytes ist, aber dies ist auch cool, weil es uns ermöglicht, die Schleife einfach abzuwickeln.

Haben Sie dies in einer Schleife und rollen Sie die Schleife ein paar Mal ab, und Sie werden einen verrückten schnellen Initialisierer haben:

// Assumes int is 32-bits.
const int mr = roundUpToNearestMultiple(m, 4);      // This isn't the optimal modification of m and n, but done this way here for clarity.    
const int nr = roundUpToNearestMultiple(n, 4);    

int i = 0;
int array[mr][nr] __attribute__ ((aligned (16)));   // GCC directive.
__m128i* px = (__m128i*)array;
const int incr = s >> 2;                            // Unroll it 4 times.
const __m128i zero128 = _mm_setzero_si128();

for(i = 0; i < s; i += incr)
{
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
}

Es gibt auch eine Variante _mm_storeu, die den Cache umgeht (dh das Nullstellen des Arrays verschmutzt den Cache nicht), was unter bestimmten Umständen zu sekundären Leistungsvorteilen führen kann.

Eine SSE2-Referenz finden Sie hier: http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

Wenn Sie das Array mit initialisieren malloc, verwenden Sie callocstattdessen; Ihr Array wird kostenlos auf Null gesetzt. (Gleiche Leistung offensichtlich wie Memset, nur weniger Code für Sie.)

int array[N][M] = {0};

... zumindest in GCC 4.8.

Wie wurde Ihr 2D-Array deklariert?

Wenn es so etwas wie:

int arr[20][30];

Sie können es auf Null setzen, indem Sie Folgendes tun:

memset(arr, sizeof(int)*20*30);

Verwenden Sie calloc anstelle von malloc. calloc initiiert alle Felder auf 0.

int * a = (int *) calloc (n, Größe von (int));

// Alle Zellen von a wurden auf 0 initialisiert

Ich denke, dass der schnellste Weg, dies von Hand zu tun, darin besteht, dem Code zu folgen. Sie können die Geschwindigkeit mit der Memset-Funktion vergleichen, sie sollte jedoch nicht langsamer sein.

(Ändern Sie den Typ der ptr- und ptr1-Zeiger, wenn sich Ihr Array-Typ von int unterscheidet.)

#define SIZE_X 100
#define SIZE_Y 100

int *ptr, *ptr1;
ptr = &array[0][0];
ptr1 = ptr + SIZE_X*SIZE_Y*sizeof(array[0][0]);

while(ptr < ptr1)
{
    *ptr++ = 0;
}

memset(array, 0, sizeof(int [n][n]));

Sie können dies versuchen

int array[20,30] = {{0}};

Dies liegt daran, dass sizeof (Array) die Zuordnungsgröße des Objekts angibt, auf das das Array zeigt . ( Array ist nur ein Zeiger auf die erste Zeile Ihres mehrdimensionalen Arrays). Sie haben jedoch j Arrays der Größe i zugewiesen . Folglich müssen Sie die Größe einer Zeile, die von sizeof (Array) zurückgegeben wird, mit der Anzahl der von Ihnen zugewiesenen Zeilen multiplizieren, z.

bzero(array, sizeof(array) * j);

Beachten Sie auch, dass sizeof (Array) nur für statisch zugewiesene Arrays funktioniert. Für ein dynamisch zugewiesenes Array würden Sie schreiben

size_t arrayByteSize = sizeof(int) * i * j; 
int *array = malloc(array2dByteSite);
bzero(array, arrayByteSize);