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

92

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.

Eddy
quelle

Antworten:

177
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).

James McNellis
quelle
1
Es scheint nicht zu funktionieren. Ich erhalte 'Code zurückgegeben -1073741819' für Codeblöcke, was ein Seg-Fehler ist, oder?
Eddy
8
@Eddy: Zeigen Sie uns die Deklaration des Arrays.
GManNickG
1
Ich wette, es stürzt in anderen Zeilen ab, nicht in der memset, weil Sie erwähnt haben, dass Sie nur eine Zeile auf Null gesetzt haben.
Blindy
3
Huh. Ich habe gerade versucht, ein Array zu testen, das als deklariert int d0=10, d1=20; int arr[d0][d1]wurde und memset(arr, 0, sizeof arr);wie erwartet funktioniert hat (gcc 3.4.6, kompiliert mit -std=c99 -WallFlags). Mir ist klar, dass "es funktioniert auf meiner Maschine" bedeutet, in die Hocke zu gehen, aber memset(arr, 0, sizeof arr); es hätte funktionieren sollen. sizeof arr sollte die Anzahl der vom gesamten Array verwendeten Bytes zurückgeben (d0 * d1 * sizeof (int)). sizeof array[0] * m * ngibt Ihnen nicht die richtige Größe des Arrays.
John Bode
4
@ John Bode: Stimmt, aber es hängt davon ab, wie das Array erhalten wird. Wenn Sie eine Funktion haben, die einen Parameter akzeptiert int array[][10], sizeof(array) == sizeof(int*)ist die Größe der ersten Dimension nicht bekannt. Das OP hat nicht angegeben, wie das Array erhalten wurde.
James McNellis
77

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.

Alok Singhal
quelle
memset(array, 0, n*n*sizeof array[0][0]);Ich denke du meinst m*nnicht n*nrichtig?
Tagc
Seltsamerweise scheint dies nicht mit Werten wie 1 und 2 statt mit 0 zu funktionieren.
Ashish Ahuja
memsetfunktioniert auf Byte-Ebene (char). Da die zugrunde liegende Darstellung dieselben Bytes enthält 1oder 2nicht, können Sie dies nicht tun memset.
Alok Singhal
@AlokSinghal Vielleicht weisen Sie darauf hin, dass " intauf Ihrem System 4 Bytes sind" irgendwo vor dem minimalen Arbeitsbeispiel, damit der Leser die Summen leicht berechnen kann.
71GA
9

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.

Skizz
quelle
Interessante alternative Sichtweise auf das Problem.
Beska
1
Ich bin nicht sicher, ob das Hinzufügen eines zusätzlichen Vergleichs / Zweigs für jeden einzelnen Lesevorgang es wert ist, die Initialisierung des Arrays in diesem Fall zu verschieben (obwohl dies möglicherweise Ihre ist). Wenn das Array wirklich so groß ist, dass die Initialisierungszeit ein ernstes Problem darstellt, kann er stattdessen einen Hash verwenden.
Tixxit
8

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

Jarrod Smith
quelle
5

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.)

Ben Zotto
quelle
Ist dies schneller als Memset, wenn ich mein Array wiederholt auf Null setzen möchte?
Eddy
calloc setzt es zur Initialisierungszeit einmal auf Null und ist wahrscheinlich nicht schneller als das Aufrufen von malloc gefolgt von memset. Danach sind Sie alleine und können Memset nur verwenden, wenn Sie es wieder auf Null setzen möchten. Wenn Ihr Array nicht wirklich riesig ist, spielt Perf hier auf keiner vernünftigen Maschine eine Rolle.
Ben Zotto
3

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

... zumindest in GCC 4.8.

Ingenieur
quelle
2

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);
Pablo Santa Cruz
quelle
Ich habe ein char [10] [10] Array verwendet. Aber ich habe einen Fehler bekommen: Zu wenige Argumente, um 'memset' zu funktionieren, und das memset(a, 0, sizeof(char)*10*10);funktioniert gut für mich. , wie kommt es?
Noufal
1

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

DUDE_MXP
quelle
0

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

mack369
quelle
Ihr Code ist höchstwahrscheinlich langsamer als memsetbei Zeichentypen.
Tofro
0
memset(array, 0, sizeof(int [n][n]));
swestrup
quelle
1
Array [n] [n] ist die Größe von 1 Element des Arrays, daher würde nur das erste Element des Arrays initialisiert.
EvilTeach
Hoppla. Du hast Recht. Ich wollte eine Typensignatur in die Parens einfügen, keine Array-Suche. Behoben.
Swestrup
0

Sie können dies versuchen

int array[20,30] = {{0}};
Călin Calin
quelle
Bitte fügen Sie weitere Details hinzu
Marko Popovic
-2

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);
VoidPointer
quelle
Der erste Teil ist falsch. Für sizeofOperator arrayist kein Zeiger (wenn er als Array deklariert wurde). Siehe meine Antwort für ein Beispiel.
Alok Singhal