An printList haben wir gesehen, dass das Iterieren über alle Elemente unserer Liste ziemlich langsam ist. Man könnte das beschleunigen, indem man Clients den Zugriff auf Nodes gestattet, würde damit aber die Abstraktion ruinieren.
Alternative: Iteratoren. Dabei besorgt man sich ein Objekt, das die Liste kennt und eine Methode hat, die das jeweils nächstes Objekt in der Liste zurückgibt.
Für unsere Liste muss der Iterator etwas von der internen Struktur der Liste wissen und muss deshalb ins gleiche Modul. Sein Interface:
Der Iterator ist übrigens ein klassisches Beispiel eines Patterns, einer immer wieder anwendbaren Softwaretechnik.
typedef struct Iterator_s {
List *list;
Node *current;
} Iterator;
Iterator *list_iteratorNew(List *l)
{
Iterator *it=malloc(sizeof(Iterator));
if (it) {
it->list = l;
it->current = l->first;
}
return it;
}
void list_iteratorFree(Iterator *i)
{
free(i);
}
char *list_iteratorNext(Iterator *it)
{
char *res=NULL;
if (it->current) {
res = it->current->cont;
it->current = it->current->next;
}
return res;
}
Damit lässt sich ein schnelleres printList so schreiben:
int printListFast(List *l)
{
Iterator *it=list_iteratorNew(l);
char *item;
if (!it) {
return -1;
}
while ((item=list_iteratorNext(it))) {
printf("%s\n", item);
}
list_iteratorFree(it);
return 0;
}
Das Problem ist jetzt, dass das Erzeugen des Iterators wegen des zusätzlichen Speicherbedarfs natürlich schief gehen kann, weshalb wir jetzt besser etwas zurückgeben, so dass aufrufende Funktionen ggf. prüfen können, ob auch alles geklappt hat. Es ist typisch, dass man einen tradeoff, einen Kompromiss also, zwischen Speicherbedarf und Geschwindigkeit machen muss – in diesem Fall allerdings ist der zusätzliche Speicher vernachlässigbar.
Das Ergebnis dieser Mühen ist folgendes Profile:
% cumulative self self total time seconds seconds calls Ts/call Ts/call name 0.00 0.00 0.00 6179 0.00 0.00 getNextWord 0.00 0.00 0.00 6179 0.00 0.00 list_iteratorNext 0.00 0.00 0.00 6178 0.00 0.00 getNodeFro... 0.00 0.00 0.00 6178 0.00 0.00 list_append 0.00 0.00 0.00 1 0.00 0.00 getNodeArr 0.00 0.00 0.00 1 0.00 0.00 list_iteratorFree 0.00 0.00 0.00 1 0.00 0.00 list_iteratorNew 0.00 0.00 0.00 1 0.00 0.00 list_len 0.00 0.00 0.00 1 0.00 0.00 list_new 0.00 0.00 0.00 1 0.00 0.00 list_quicksort 0.00 0.00 0.00 1 0.00 0.00 printListFast
– auf dem aktuellen Rechner braucht also kein Teil unseres Programms messbar Rechenzeit. Die von der csh gemessene Laufzeit des Programms ist nun 0.02 Sekunden, gegenüber 0.4 Sekunden mit dem alten printList und 1.2 Sekunden mit dem alten list_sort.
Optimierung kann also viel bringen, die großen Sprünge gehen aber im Allgemeinen nur durch Änderung des Algorithmus’. Genau das verlangt aber Nachdenken und kostet Zeit, so dass man eigentlich nur dort Optimieren möchte, wo es etwas bringt. Bei der Bestimmung dieses Ortes helfen Profiler.
Der Iterator hat übrigens das Problem, dass er von Veränderungen an der Liste nichts mitbekommt – es ist z.B. ohne weiteres möglich, die Liste freizugeben und den Iterator weiter zu verwenden, was wiederum zu Abstürzen führen würde. Eine Möglichkeit, das zu unterbinden, wäre ein Callback auf einen gesetzten Iterator in der Liste; die Liste könnte, wenn sie verändert wird, dem Iterator sagen, dass er nicht mehr gültig ist. Ob sich dieser Aufwand lohnt, ist allerdings fragwürdig – man könnte auch einfach sagen, dass BenutzerInnen, die eine Liste, auf der ein Iterator werkt, freigeben, nichts besseres als einen Absturz verdient haben.