010
28.08.2003, 20:16 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Falls Du realloc richtig anwendest, gibt es vielleicht noch den Punkt, daß es rein von der Performance her ziemlich ungünstig ist, das Array jedesmal nur um 1 zu vergößern. Übliche Alternativen sind entweder exponentielles Wachstum oder lineare in großen Schritten. So oder so kommt man dann ziemlich schnell zum Punkt, daß man nicht mehr einfach mit einem Pointer auf den Speicher arbeitet, sondern gleich mit einer Struktur. Nehmen wir an, du willst ein Array dynamisch wachsen/schrumpfen lassen, welches aus lauter Zeilen der Länge 256 Zeichen (inkl 0 Byte besteht:
| C++: |
typedef char zeile_t[256]; /* Typ für eine Zeile */
|
Dann würde man sich Anstelle eines simplen Arrays sowas vorstellen können:
| C++: |
typedef struct
{
unsigned aktuell; /* Aktuelle anzahl der Zeilen */
unsigned maximal; /* maximale Anzahl der Zeilen */
zeile_t* zeilen; /* Das eigentliche Array */
} inhalt_t;
|
Man würde sich eine Routine schreiben, die in der lage ist, eine solche Struktur zu initialisieren:
| C++: |
void InitialisiereInhalt(inhalt_t* inhalt)
{
memset(inhalt, 0, sizeof(*inhalt));
}
|
Natürlich eine, um eine solche Struktur wieder freizugeben:
| C++: |
void LoescheInhalt(inhalt_t* inhalt)
{
unsigned i;
for(i=0; i<inhalt->aktuell; ++i)
{
if (NULL != inhalt->zeilen[i]) free (inhalt->zeilen[i]);
}
if (NULL != inhalt->zeilen) free(inhalt->zeilen);
memset(inhalt, 0, sizeof(*inhalt));
}
|
Tja, nun der interessante Teil: nämlich Zeilen anfügen. Deine Originalmethod sähe so aus:
| C++: |
int FuegeZeileHinzu(inhalt_t* inhalt, zeile_t zeile)
{
if (inhalt->aktuell==inhalt->maximal)
{
zeile_t* temp = realloc(inhalt->zeilen, (inhalt->maximal+1)*sizeof(zeile_t*));
if (NULL == temp)
{
/* fehler */
return -1;
}
++inhalt->maximal;
inhalt->zeilen = temp;
}
inhalt->zeilen[inhalt->aktuell] = malloc(sizeof(zeile_t));
if (NULL == inhalt->zeilen[inhalt->aktuell])
{
/* fehler */
return -1;
}
memcpy(inhalt->zeilen[inhalt->aktuell++], zeile, sizeof(zeile));
return 0;
}
|
In diesem Beispiel zahlt sich natürlich die Struktur nicht so dolle aus: maximal und aktuell haben immer den gleichen Wert, wenn nicht grade was schief gegangen ist. Aber Sobald man nicht immer um 1 vergrößert, sondern eben zB um 10, wird ein Schuh draus:
| C++: |
#define INCSIZE 10
int FuegeZeileHinzu(inhalt_t* inhalt, zeile_t zeile)
{
if (inhalt->aktuell==inhalt->maximal)
{
zeile_t* temp = realloc(inhalt->zeilen, (inhalt->maximal+INCSIZE)*sizeof(zeile_t*));
if (NULL == temp)
{
/* fehler */
return -1;
}
inhalt->maximal += INCSIZE;
inhalt->zeilen = temp;
}
inhalt->zeilen[inhalt->aktuell] = malloc(sizeof(zeile_t));
if (NULL == inhalt->zeilen[inhalt->aktuell])
{
/* fehler */
return -1;
}
memcpy(inhalt->zeilen[inhalt->aktuell++], zeile, sizeof(zeile));
return 0;
}
|
Man sieht schnell ein, daß bei gleichem Programm ds realloc wesentlich weniger aufgerufen wird. Wenn Du Die Routinen zB einsetzt, um große Dateien einzulesen, ist der Effekt deutlich messbar. Noch extremer ist es natürlich, enn du jedesmal den Speicher verdoppelst:
| C++: |
int FuegeZeileHinzu(inhalt_t* inhalt, zeile_t zeile)
{
if (inhalt->aktuell==inhalt->maximal)
{
zeile_t* temp;
if (inhalt->zeilen)
temp = realloc(inhalt->zeilen, (inhalt->maximal*2)*sizeof(zeile_t*));
else
temp = malloc(sizeof(zeile_t*));
if (NULL == temp)
{
/* fehler */
return -1;
}
if (inhalt->zeilen)
inhalt->maximal *= 2;
else
inhalt->maximal = 1;
inhalt->zeilen = temp;
}
inhalt->zeilen[inhalt->aktuell] = malloc(sizeof(zeile_t));
if (NULL == inhalt->zeilen[inhalt->aktuell])
{
/* fehler */
return -1;
}
memcpy(inhalt->zeilen[inhalt->aktuell++], zeile, sizeof(zeile));
return 0;
}
|
Allerdings ist hier daß problem, daß uU ziemlich viel Speicher brach liegt. Man bedenke den Fall, daß man eine Zeile mit 65537 Zeilen Einliest: 4*65535 Bytes einfach für die Katz!
Vor allem macht das Beispiel aber deutlich, daß es sinnvoll ist, auch in C für scheinbar einfache Dinge schnell Strukturen und eindeutig zugeordnete Methoden, äh nat. Funktionen zu schreiben.
Beispielcode ungetestet.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
