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

Lesezeit: 9 Minuten

Eddys Benutzeravatar
Wirbel

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

// 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 bekomme ich eine Menge zufälliger großer Zahlen und es stürzt ab.

Benutzeravatar von James McNellis
James McNellis

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

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

  • Es scheint nicht zu funktionieren. Ich erhalte ‘Prozess zurückgegeben -1073741819’ auf Codeblöcken, was ein Seg-Fehler ist, oder?

    – Wirbel

    25. März 2010 um 14:09 Uhr

  • @Eddy: Zeigen Sie uns die Deklaration des Arrays.

    – GManNickG

    25. März 2010 um 14:13 Uhr

  • Ich wette, es stürzt auf anderen Linien ab, nicht auf der memsetweil Sie den Absturz erwähnt haben, weil Sie auch nur eine Zeile auf Null gesetzt haben.

    – Blind

    25. März 2010 um 14:15 Uhr

  • Hm. Habe gerade einen Test ausprobiert, als ein Array deklariert wurde int d0=10, d1=20; int arr[d0][d1]und memset(arr, 0, sizeof arr); funktionierte wie erwartet (gcc 3.4.6, kompiliert mit -std=c99 -Wall Flaggen). Mir ist klar, dass “es funktioniert auf meiner Maschine” ziemlich gedrungen bedeutet, aber memset(arr, 0, sizeof arr); sollte habe gearbeitet. sizeof arr sollte gibt die Anzahl der vom gesamten Array verwendeten Bytes zurück (d0 * d1 * sizeof(int)). sizeof array[0] * m * n gibt Ihnen nicht die richtige Größe des Arrays.

    – Johannes Bode

    25. März 2010 um 15:00 Uhr


  • @ John Bode: Stimmt, aber es hängt davon ab, wie das Array abgerufen wird. Wenn Sie eine Funktion haben, die einen Parameter akzeptiert int array[][10]dann sizeof(array) == sizeof(int*) da die Größe der ersten Dimension nicht bekannt ist. Das OP hat nicht angegeben, wie das Array erhalten wurde.

    – James McNellis

    25. März 2010 um 15:10 Uhr


Benutzeravatar von Alok Singhal
Alok Singhal

Wenn array ist wirklich ein Array, dann können Sie es “auf Null setzen” mit:

memset(array, 0, sizeof array);

Aber es gibt zwei Punkte, die Sie wissen sollten:

  • das geht nur wenn array ist wirklich ein “Zwei-D-Array”, dh deklariert wurde T array[M][N]; für irgendeinen Typ T.
  • es funktioniert nur in dem Bereich wo array wurde erklärt. Wenn Sie es an eine Funktion übergeben, dann den Namen array zerfällt zu einem Zeiger, und sizeof gibt Ihnen nicht die Größe des Arrays.

Machen wir ein Experiment:

#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 meiner Maschine druckt das obige:

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

Wenngleich arr ein Array ist, zerfällt es zu einem Zeiger auf sein erstes Element, wenn es übergeben wird f()und damit die eingedruckten Größen f() sind falsch”. Auch in f() die Größe von arr[0] ist die Größe des Arrays arr[0]das ist ein “Array [5] von int“. Es ist nicht die Größe eines int *weil das “Zerfallen” nur auf der ersten Ebene passiert, und deshalb müssen wir deklarieren f() wie einen Zeiger auf ein Array der richtigen Größe zu nehmen.

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

Endlich, memset() und die for Schleife, die Sie gepostet haben, 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 sind. Ich bezweifle aber, dass Sie sich darüber Sorgen machen müssen.

  • memset(array, 0, n*n*sizeof array[0][0]); Ich schätze du meinst m*n nicht n*n Rechts?

    – Tagc

    16. Februar 2018 um 8:29 Uhr

  • Seltsamerweise scheint dies nicht mit Werten wie 1 und 2 anstelle von 0 zu funktionieren.

    – Kiste Kiste Kiste Kiste

    4. Dezember 2018 um 6:51 Uhr

  • memset arbeitet auf Byte (char) Ebene. Seit 1 oder 2 nicht die gleichen Bytes in der zugrunde liegenden Darstellung haben, können Sie das nicht tun memset.

    – Alok Singhal

    4. Dezember 2018 um 15:13 Uhr

  • @AlokSinghal Vielleicht darauf hinweisen intauf Ihrem System ist 4 Byte” irgendwo vor dem minimalen Arbeitsbeispiel, damit der Leser die Summen leicht berechnen kann.

    – 71GA

    11. März 2020 um 18:03 Uhr


Nun, der schnellste Weg, es zu tun, ist, 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;
}

Tatsächlich wird das Array immer noch gelöscht, aber nur, wenn etwas in das Array geschrieben wird. Das ist hier kein großer Vorteil. Wenn das 2D-Array jedoch beispielsweise mit einem Quad-Tree (kein dynamischer Mind) oder einer Sammlung von Datenzeilen implementiert wurde, können Sie die Wirkung des booleschen Flags lokalisieren, benötigen jedoch mehr Flags. Setzen Sie im Quad-Tree einfach das leere Flag für den Wurzelknoten, im Array of Rows setzen Sie einfach das Flag für jede Zeile.

Was zu der Frage führt: “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?

Wenn Sie zum Beispiel Folgendes hatten:

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

das heißt, verwenden Sie es für einen Akkumulationspuffer, dann würde eine Änderung wie folgt die Leistung ohne Ende verbessern:

 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 kein Löschen des Arrays, funktioniert aber trotzdem. Und das geht viel schneller als das Löschen des Arrays. Wie gesagt, der schnellste Weg ist, es gar nicht erst zu tun.

  • Interessante alternative Sichtweise auf das Problem.

    – Beška

    25. März 2010 um 14:36 ​​Uhr

  • Ich bin mir 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 es sich möglicherweise um Ihren handelt). Wenn das Array wirklich so groß ist, dass die Initialisierungszeit ein ernsthaftes Problem darstellt, könnte er stattdessen einen Hash verwenden.

    – Tixxit

    26. März 2010 um 16:59 Uhr


Benutzeravatar von Jarrod Smith
Jarrod Smith

Wenn Sie wirklich, wirklich von Geschwindigkeit besessen sind (und nicht so sehr von Portabilität), denke ich, das Absolute am schnellsten Ein Weg, dies zu tun, wäre die Verwendung von SIMD-Vektor-Intrinsics. Auf Intel-CPUs könnten Sie beispielsweise diese 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-Ganzzahlen in 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 Zuweisungsgröße verweisen muss, die ein Vielfaches von 16 Bytes ist, aber das ist auch cool, weil es uns erlaubt, die Schleife einfach aufzurollen.

Haben Sie dies in einer Schleife und rollen Sie die Schleife ein paar Mal aus, 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 von _mm_storeu das den Cache umgeht (dh das Nullen des Arrays wird den Cache nicht verschmutzen), was Ihnen unter bestimmten Umständen einige sekundäre Leistungsvorteile bringen könnte.

Siehe hier für SSE2-Referenz: http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

Wenn Sie das Array mit initialisieren mallocverwenden calloc stattdessen; Es wird Ihr Array kostenlos auf Null setzen. (Offensichtlich die gleiche Leistung wie Memset, nur weniger Code für Sie.)

  • Ist dies schneller als memset, wenn ich mein Array wiederholt auf Null setzen möchte?

    – Wirbel

    25. März 2010 um 15:06 Uhr

  • calloc setzt es zur Initialisierungszeit einmal auf Null und ist wahrscheinlich nicht schneller als das Aufrufen von malloc gefolgt von memset. Danach sind Sie auf sich allein gestellt und können einfach memset verwenden, wenn Sie es wieder auf Null setzen möchten. Wenn Ihr Array nicht wirklich riesig ist, ist Leistung hier auf keinem vernünftigen Computer wirklich eine Überlegung.

    – Ben Zotto

    25. März 2010 um 15:35 Uhr

Benutzeravatar des Engineers
Techniker

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

…zumindest in GCC 4.8.

  • Ist dies schneller als memset, wenn ich mein Array wiederholt auf Null setzen möchte?

    – Wirbel

    25. März 2010 um 15:06 Uhr

  • calloc setzt es zur Initialisierungszeit einmal auf Null und ist wahrscheinlich nicht schneller als das Aufrufen von malloc gefolgt von memset. Danach sind Sie auf sich allein gestellt und können einfach memset verwenden, wenn Sie es wieder auf Null setzen möchten. Wenn Ihr Array nicht wirklich riesig ist, ist Leistung hier auf keinem vernünftigen Computer wirklich eine Überlegung.

    – Ben Zotto

    25. März 2010 um 15:35 Uhr

Benutzeravatar von Pablo Santa Cruz
Pablo Santa Cruz

Wie wurde Ihr 2D-Array deklariert?

Wenn es so etwas wie:

int arr[20][30];

Sie können es nullen, indem Sie Folgendes tun:

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

  • Ich habe ein Zeichen verwendet[10][10] Reihe. Aber ich habe einen Fehler bekommen: zu wenige Argumente, um ‘memset’ zu funktionieren, und memset(a, 0, sizeof(char)*10*10); funktioniert gut für mich. , wie geht das?

    – noufal

    18. Oktober 2013 um 7:02 Uhr

1421080cookie-checkDer schnellste Weg, um ein 2D-Array in C auf Null zu setzen?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy