003
07.04.2003, 23:02 Uhr
virtual
Sexiest Bit alive
(Operator)
|
3. Lösungsansatz (Statische Variablen, aber dynamisch!)
Das im 1. Lösungansatz genannte KO-Kriterium, nämlich daß der Speicher nach Verlassen der Routine einfach futsch ist, kann man im Prinzip einfach dadurch umgehen, daß man die Variable buf in der Routine vokal_doppler static deklariert:
| C++: |
...
char* vokal_doppler(const char* str)
{
[b]static[/b] char buf[1024];
char* ptr = buf;
...
|
Nun wollen wir aber auch direkt dem anderen Nachteil (der Längenbegrenzung aus dem 1. und 2. Lösungansatz) begegnen und den Speicher je nach Bedarf neu allozieren. Zunächst mal der Source:
| C++: |
/* vokdop.c 3.0 */
#include <stdio.h>
#include <stdlib.h>
inline int istVokal(char zeichen)
{
...
}
/*
* Zur Kritik der Routine siehe text unten.
*/
char* vokal_doppler(char* str)
{
/*
* buf is initial NULL, ihm wird aber im Verlauf der Routine mit realloc
* Speicher zugewiesen. size Enthält die Länge des Speichers, auf den
* buf zeigt. Zu beachten ist, daß beide Variablen static sind; dh die
* Werte der Variablen gehen zwischen den Functionsaufrufen nicht verloren
*/
static char* buf = NULL;
static int size = 0;
/*
* Einige weitere "normale" Variablen für versch. Zwecke.
*/
char* ptr;
int str_laenge;
/*
* Wie bereits gesagt, behalten staic Variablen über Funktionsaufrufe
* hinweg ihre Werte. Natürlich bleibt auch der Speicher belegt, den
* wir weiter unten mittels realloc belegen. Um diesen Speicher auch
* freigeben zu können (in der Regel bei Programmende, "missbrauchen"
* wir den Fall, wenn ein NULL Pointer für str übergeben wird: wir
* geben den Speicher dann frei. Die Anwendung muß daher am Ende,
* bevor sie terminiert, einmal [i]vokal_doppler(NULL)[/i] aufrufen,
* um Memory leaks zu beseitigen. In professioneller software könnte
* man einen entsprechenden atexit-Handler installieren, was wir aber
* hier mal nicht machen.
*/
if (NULL == str)
{
if (NULL != buf)
{
free(buf);
buf = NULL;
size = 0;
}
return NULL;
}
/*
* Unsere Routine soll diesmal mit unbegrenzt langen Strings klar kommen.
* Vom 1. Lösungsansatz her wissen wir, daß der Resulatstring als maximale
* die doppelte Länge von [i]str[/i] hat. Wir prüfen im folgenden also
* ob [i]buf[/i] bereits genug Speicher enthält, um den Ergebnisstring
* aufzunehmen.
*/
str_laenge = strlen(str);
if (size<2*str_laenge+1) /* +1 wegen terminierender Null */
{
/*
* Der bisher belegte Platz is nicht doppelt so groß wie der String,
* folglich müssen wir ggf. etwas mehr Speicher belegen. Aber im Speicher
* zu sparen, berechenen wir, wie lang der String tatsächlich werden
* wird (wir zählen also die Vokale). Mit ein wenig Glück reicht
* der bisher belegte Speicher ja doch... ;)
*/
int i;
int vokal_anzahl = 0;
for(i=0; i<str_laenge; ++i)
{
if (istVokal(str[ i ])) ++vokal_anzahl;
}
/*
* Wenn die vokalanzahl == 0 ist, brauchen wir eigentlich garnichts
* zu tun und können [i]str[/i] zurückgeben.
*/
if (0 == vokal_anzahl)
{
return str;
}
/*
* Ansonsten ist sicherzustellen, daß der Speicher ausreicht:
*/
if (size<str_laenge+vokal_anzahl+1)
{
/*
* Oh - wir müssen den Speicher vergrößern. Das geht mit realloc:
* Wir speichern zunächst in tmp den neuen Speicher. Bei realloc
* ist es so, daß tmp==NULL ist, wenn kein Speicher da ist. Dann
* Zeigt [i]buf[/i] aber immer noch auf den alten Speicher.
* Funktioniert realloc hingegen, ist der Speicher, auf den [i]buf[/i]
* zeigt ungültig, die neue Address steht dann in [i]tmp[/i].
*/
char* tmp = realloc(buf, str_laenge+vokal_anzahl+1);
if (NULL == tmp)
{
/* Mist: kein Speicher */
return NULL;
}
else
{
/* Okay: neuen Speicher merken; auch dessen Länge */
size = str_laenge+vokal_anzahl+1;
buf = tmp;
}
}
}
ptr = buf;
/*
* Um es kurz zu machen, habe ich hier mal die Kommentare entfernt, es ist das gleiche
* wie im ersten Lösungsansatz...
*/
while (*str)
{
*ptr = *str++;
if (istVokal(*ptr))
{
*(ptr+1) = *ptr;
ptr++;
}
ptr++;
}
*ptr = 0;
return buf;
}
int main(int argc, char**argv)
{
int k;
int j;
if (argc<2)
{
fprintf(stderr, "%s: Zuwenig Argumente.\nBenutzung: %s Text...\n", argv[0], argv[0]);
exit(1);
}
for(k=1; k<argc; ++k)
{
char* vokdop = vokal_doppler(argv[k]);
/*
* Wir arbeiten ja neuerdings mit dynamischen Speicher. Da kann einiges
* schief gehen, zB kein Speicher mehr da. In diesem Fall gibt [i]vokal_doppler[/i]
* einen NULL Pointer zurück. Dies müssen wir prüfen:
*/
if (NULL == vokdop)
{
fprintf(stderr, "Mist: Kein Speicher!\n");
}
else
{
printf("%s => %s\n", argv[k], vokdop);
}
}
/*
* Wie bereits in der BEschreibung zu [i]vokal_doppler[/i] erwähnt, müssen
* wir am ende den Speicher aus den static Vairablen freigeben:
*/
vokal_doppler(NULL);
}
|
Die Lösung hat durchaus ihre Vorteile: Zum einen ist sie korrekt und kommt auch mit beliebig langen Strings klar. Und tatsächlich wird auch der Trick mit den static Variablen in manchen Systembibliotheken angewendet. Auch die Überprüfung, ob der Rückgabewert NULL ist (also ob die Funktion fehlschlug), ist nicht wirklich eine tragische Sache; damit hat man eigentlich immer zu tun, wenn man mit dynamischen Speicher zu tun hat. Ärgerlich ist sicherlich das vokal_doppler(NULL), welches wohl ganz gerne mal vergessen werden. Hinterlistiger sind da aber zwei Dinge die aus der Verwendung von static Variablen resultieren:
static Varaiblen sind hinsichtlich ihrere Eigenschaften globalen Varaiblen sehr ähnlich. Der einzige Unterschied besteht eigentlich nur darin, daß ihr Name nur innerhalb der umgebenden Funktion bekannt ist. Aber ihr Inhalt ist eben doch global. So kommt es, daß zwei aufeinanderfolgende Aufrufe von vokal_doppler die alten resultate überschreibt. Die Rückgabewerte bleiben also nur solange gültig, bis die Funktion erneut aufgerufen wird. Will man das Ergebnis länger aufbeahren, muß man eine Kopie anlegen.
Ein weiterer Nachteil ist, daß Funktionen, die static Variablen verwenden, ohne weitere Vorkehrungen generell nicht reentrant sind. Das beduetet konkret, daß man sie nicht in einer Multithreaded Application benutzen kann, weil zwei Threads sich gegenseitig den Speicher überschreiben.
Stören diese Beiden Minuspunkte nicht, ist die Lösung mit den static Variablen aber durachaus elegant und hat auch - bei guter Implementierung - performance Vorteiel gegenüber Versionen von vokal_doppler, die jedesmal neue Speicherbereiche anlegen.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
Dieser Post wurde am 09.04.2003 um 21:53 Uhr von virtual editiert. |
. Auch wenn dies die flexibelste Lösung ist, ist sie unter Garantie die langsamste, weil immer neuer Speicher belegt wird und freigegeben wird. Speicheroperationen sind im Vergleich zu dem Zeitaufwand, den die eigentlich Routine benötigt, sehr hoch.