 |
Allgemeines |
|---|
Inhalt: Allgemeines - Datentypen - Mathematische Operationen - Schleifenzähler richtig konstruieren - Operationen in Schleifen verringern - Übergabe von Argumenten - Logische Ausdrücke - Vergleiche umformen - Anzahl der Vergleiche reduzieren - Vorsicht bei Vergleichen - Aufgaben intelligenter verteilen - Zeitmessung
|
Auch wenn viele der hier vorgestellten Prinzipien und Beispiele zur Beschleunigung von Programmen dem PC-Normalanwender überzogen erscheinen (“Die Rechner sind ja heute soooo schnell”), gibt es überall gute Gründe, auf die Geschwindigkeit zu achten.
Weiterhin gibt es in der Steuerungs- und Regeltechnik noch genügend Prozessoren, die z.B. eine Werkzeugmaschine mit minimalen Mitteln unter Kontrolle halten müssen. Mathematische Co-Prozessoren und schnelle CPU’s werden hier nicht wie im SoHo-Bereich (Small-Office/Home-Office) nach dem Motto ‘Lieber ein wenig zu viel als viel zu wenig’ zugekauft, sondern nach dem Grundsatz ‘passend und billigst’ ausgewählt.
Die Wirkung eigener Optimierungsmaßnahmen hängt u.a. von der
verwendeten Programmiersprache ab. Bei diesen unterscheidet man u.a. zwischen
‘Interpretern’ und ‘Compilern’:
Aus diesen Gründen muß der Programmierer nach wie vor persönlich optimieren, wenn es darum geht, Algorithmen auf höchste Geschwindigkeit zu trimmen.
|
Schon mit der Auswahl des richtigen Datentyps läßt sich oft Zeit
sparen, ohne daß an der Funktionalität des Programmes Änderungen
vorzunehmen sind.
Die meisten Programmiersprachen und Datenbanken bieten einen regelrechten
Datentypen-Zoo an. Die folgende Liste beginnt mit einigen der einfachsten
Datentypen (nicht auf C beschränkt):
BYTE, SHORTINT, INT,
WORD, LONG)
CURRENCY, DATE)
FLOAT, SINGLE,
DOUBLE)
Innerhalb dieser Datentypen ist dann der Datentyp mit dem kleinsten
Speicherplatzverbrauch zu wählen, also wenn möglich
INTEGER statt LONG.
Berechnungen mit den Ganzzahl-Typen BYTE, INTEGER,
WORD oder LONG erledigt die CPU sehr schnell und
meist ohne zusätzliche Software.
CURRENCY wird für die Darstellung von
Währungsbeträgen verwendet. Bei der Rechnung mit Fließkommazahlen
sollte daher geprüft werden, ob der Datentyp CURRENCY anstelle
von SINGLE, FLOAT oder DOUBLE verwendet
werden kann, denn obwohl hier (eine feste Zahl) von Nachkommastellen gespeichert
wird, kann dieser Datentyp wie ein Ganzzahl-Datentyp verwendet werden.
FLOAT und DOUBLE benötigen entweder die FPU
(mathematischer Co-Prozessor) oder ein spezielles Programm und sind daher
langsam.
Die BCD-Darstellung von Zahlen wird wohl nur noch in Taschenrechnern benutzt.
Bei der Rechnung mit Dezimalzahlen im BCD-Format entstehen aber weniger
Rundungsfehler. Zahlen im BCD-Format sind im Vergleich zu
SINGLE, FLOAT oder DOUBLE noch aufwendiger
zu berechnen und werden i. allg. nicht als Funktionen der
Hardware verdrahtet.
Darüber hinaus gibt es in vielen Programmiersprachen ähnliche oder ganz andere, nicht-numerische Datentypen, z.B. Strings oder Objektdatentypen.
Fließkommazahlen sind nur im äußersten Notfall zu verwenden. Nicht alle Prozessortypen haben einen mathematischen Co-Prozessor und bei denen ist auch nicht garantiert, daß sie Berechnungen schnell oder gar genau erledigen.
Berechnungen mit Fließkommazahlen haben außerdem den Nachteil,
daß sie Rundungsfehler ‘magisch’ anziehen.
|
Der Zeitbedarf für mathematische Operationen kann sehr groß werden. Was auf dem Taschenrechner kaum zu bemerken ist, kostet in einer Schleife richtig Zeit. Schon in den Anfängen der numerischen Mathematik auf Großrechnern kostete die Rechenzeit bares Geld. Besonders die Multiplikationen wurden als ‘teuer’ bezeichnet, weil sie viel Zeit verschlangen. Zu einfachen mathematischen Verfahren, wie z.B. die Lösung linearer Gleichungssysteme, wurden zahlreiche Varianten entwickelt, die auf spezielle Daten eingingen und so die Berechnungen schneller machten. Für spezielle Berechnungen (z.B. Strömungstechnik) sind manchmal lineare Gleichungssysteme (allerdings dünn besetzt mit sog. ‘Bandmatritzen’) mit Millionen von Gleichungen aufzulösen.
Schneller bedeutet meist weniger ‘Punktoperationen’, weil Addition
und Subtraktion in der Rechenzeit kaum ins Gewicht fielen, wenn gleichzeitig
viele Multiplikationen erforderlich waren. Auch wenn es inzwischen Algorithmen
gibt, welche die Multiplikation fast so schnell wie die Addition erledigen,
kann man sich meist nicht aussuchen, in welcher Umgebung das Programm
später ausgeführt wird, daher gilt nach wie vor die
Hier die empfohlene Reihenfolge der mathematischen Operationen, wobei die einfachsten zuerst kommen:
±, CHS |
Vorzeichenwechsel |
», « |
Bits verschieben |
+, - |
Addition, Subtraktion |
×, ÷ |
Multiplikation, Division |
^ |
Potenzrechnung |
sin, ln |
höhere mathematische Funktionen |
Der Wechsel des Vorzeichens erfordert nur die Änderung eines einzelnen Bits.
Das Verschieben von Bits beherrschen Prozessoren selbst. Wegen der binären Zahlendarstellung entspricht das Verschieben je eines Bits nach links die Multiplikation mit 2, die Verschiebung eines Bits nach rechts bedeutet die Division durch 2, wobei der Divisionsrest (bei ungeraden Zahlen) einfach wegfällt. Dieses Bitschieben funktioniert nur bei ganzzahligen Datentypen !!!
Beispiel: Addition statt Multiplikation.
Langsam ...
R = 4 × A ;
Schneller ...
R = A + A ; R += R ;
oder (nicht sehr schön):
R += R = A + A ;
... weil zwei Additionen in der Regel schneller sind, als eine Multiplikation.
Noch schneller ...
R = A << 2 ;
... doch dieses ‘Bitschieben’ erfordert Ganzzahl-Typen und ist nur möglich, wenn mit Zweierpotenzen (2n = 2, 4, 8, 16, ...) multipliziert bzw. durch sie dividiert werden soll.
Beispiel aus der c’t 19/98, Artikel ‘Programmieren nach Plan’
Langsam ...
R ×= 5 ;
Schneller ...
R += R << 2 ;
... weil eine Multiplikation durch Bitschieben («) und
eine Addition (R += ... entspricht
R = R + ..., sinngemäß gilt dies auch
für R ×= ...) ersetzt wurde. Die c’t nimmt
dieses Beispiel allerdings zu Recht als Warnung vor einem Programmierstil,
der einer Wartung und Wiederverwertung des Codes völlig abträglich
ist.
Beispiel: Anwendung der 3. binomischen Formel
Langsam ...
R = A × A - B × B ;
Schnell ...
R = (A + B) × (A - B) ;
... weil ein × durch ein + ersetzt wurde. Diese Formel verursacht außerdem weniger Rundungsfehler.
Beispiel: Auch die Anwendung der höheren mathematischen Funktionen bietet einiges Potential zur Zeiteinsparung.
Langsam ...
R = log(1/A) ;
Schnell ...
R = -log(A) ;
... weil eine Division durch einen Vorzeichenwechsel ersetzt wurde. Diese Änderung reduziert ebenfalls die Rundungsfehler.
|
Was in einer Schleife ganz innen steht, wird auch am häufigsten ausgeführt. Daher sollte man so wenig wie möglich im Inneren einer Schleife arbeiten. Der erste Schritt ist die Optimierung der Schleifenzähler.
Im folgenden Beispiel wird aus den Zählern eine Zahl berechnet und an
eine Prozedur PixelSetzen übergeben.
Langsam ...
for (I = 0; I < 8; I++)
for (J = 0; J < 5; J++)
{ PixelSetzen(I × 10 + J, J + 8);
}
... weil in jeder Schleife zur Berechnung des Ausdrucks ist eine Multiplikation und eine Addition erforderlich ist.
Zur Beschleunigung des Programmabschnitts löst man zunächst die
Multiplikation I × 10 auf, denn sie wird in dieser
Schleifen-Konstruktion 40× ausgeführt, aber nur 8× ändert
sich der Wert, der an die Prozedur PixelSetzen übergeben
wird.
Zur Vereinfachung ersetzt man den Schleifenzähler I im
Argument für die Funktion PixelSetzen so, daß aus
I × 10 nur I wird. Dies gelingt,
indem man I in der gesamten Schleifen-Struktur
durch I/10 ersetzt:
Im Kopf der for-Schleife wird die Start-Bedingung
I = 0 zu I/10 = 0. Weil aber
hier eine Zuweisung stattfindet, muß die linke Seite der Gleichung
mit Hilfe einfacher mathematischer Umformungen in die Form
I = ... gebracht werden, so daß die Startbedingung
der for-Schleife diesem Falle unverändert bleibt:
I = 0.
Aus I < 8 in der Laufbedingung der
for-Schleife wird I/10 < 8, weil aber
nach einer später vorgestellten Regel (Vergleiche
umformen) konstante Ausdrücke zusammengefaßt werden sollen,
ergibt sich I < 80.
Der Ausdruck I++ entspricht der Gleichung/Zuweisung I
= I + 1, so daß eine Ersetzung des
Schleifen-Inkrements I/10 = I/10 + 1 und
damit I = I + 10 ergibt. In C läßt
sich dies als I += 10 schreiben.
Schneller:
for (I = 0; I < 80; I += 10)
for (J = 0; J < 5; J++)
{ PixelSetzen(I + J, J + 8); }
In einem zweiten Schritt könnte man nun versuchen, aus der Prozedur
PixelSetzen noch den Ausdruck J + 8 umzuformen.
Dazu ersetzt man an jeder Stelle J durch J - 8:
Aus J = 0 wird J = 8, aus
J < 5 wird J < 13 und
weil J++ die Zuweisung J = J + 1
darstellt, wird daraus J - 8
= J - 8 + 1, weshalb das Schleifen-Inkrement
unverändert bleibt.
for (I = 0; I < 80; I += 10)
for (J = 8; J < 13; J++)
{ PixelSetzen(I + J - 8, J); }
Diese Lösung ist allerdings nicht besonders befriedigend, weil sie
gegenüber der vorherigen Version keine Vorteile bringt. Jedoch kann
man die so gewonnene Form weiterentwickeln: Dazu nehmen wir einfach an, daß
die -8 im Argument der Prozedur PixelSetzen nicht
zu J, sondern zu I gehört, und versuchen es
dann in den Kopf der for-Schleife von I zu ziehen.
Dann ist überall I durch I + 8 zu
ersetzen.
Damit entsteht die abschließende Version der Schleife:
Noch schneller:
for (I = -8; I < 72; I += 10)
for (J = 8; J < 13; J++)
{ PixelSetzen(I + J, J); }
Die Bilanz der Operationen ergibt gegenüber der ersten Version eine Einsparung von 40 Multiplikationen und 40 Additionen.
|
Was in einer Schleife ganz innen steht, wird auch am häufigsten
ausgeführt. Der erste Schritt wurde im vorhergehenden Abschnitt behandelt.
Der zweite Schritt ist die Optimierung der übrigen Befehle.
Oft erfordert die Berücksichtigung dieser Regel eine Änderung des gesamtem Algorithmus.
Beispiel: Wert soll hier eine beliebige, positive Ganzzahl
sein.
Langsam ...
while (Wert < 100)
{
if (Wert % 2 == 0) { MachWas ; }
Wert++ ;
}
... weil in der Schleife eine Berechnung stattfindet und nur bei jedem zweiten Schleifendurchlauf etwas passiert.
[Anmerkung. In anderen Programmiersprachen entspricht %
dem Modulo-Operator (MOD).]
Zur Vereinfachung muß daher zunächst Wert um
1 erhöht werden, falls Wert ungerade ist, schließlich
muß sichergestellt werden, daß Wert nur gerade Zahlen
durchläuft.
Wert = Wert + Wert % 2 ;
oder:
Wert += Wert % 2 ;
Außerdem muß Wert immer um 2 erhöht
werden. Damit ergibt sich, daß die for-Schleife die
Anforderungen des Algorithmus besser erfüllt, als die
while-Schleife.
Schneller ...
for (Wert += Wert % 2; Wert < 100; Wert += 2)
{ MachWas; }
... weil die Berechnung aus der Schleife herausgezogen wurde.
Beispiel: Das Array Vektor hat AnzElem
Elemente. Diese sollen ‘rotieren’, d.h. wenn die ursprüngliche
Reihenfolge der Elemente 1-2-3-4 war, soll sie danach 2-3-4-1 lauten.
Langsam ...
for (Nr = 0; Nr < AnzElem - 1; Nr++)
{
Temp = Vektor[Nr];
Vektor[Nr] = Vektor[Nr+1];
Vektor[Nr+1] = Temp;
}
... weil bei jedem Schritt 3 × Umspeichern, 2 Additionen und eine
Subtraktion (Schleifensteuerung bei
Nr < AnzElem - 1) fällig sind.
Schnell ...
Temp = Vektor[0];
for (Nr = 1; Nr < AnzElem; Nr++)
{ Vektor[Nr-1] = Vektor[Nr]; }
Vektor[AnzElem-1] = Temp;
... weil nur noch eine Verschiebung und eine Subtraktion in der Schleife erforderlich sind und durch Indexverschiebung die Subtraktion in der Schleifensteuerung entfällt.
Beispiel: In einer Schleife wird ein Test ausgeführt und je nach Ergebnis des Tests die eine oder andere Anweisung ausgeführt. Jedoch ändert sich die Testbedingung innerhalb der Schleife nicht, so daß man den Test aus der Schleife herausziehen kann.
Langsam ...
for (Nr = 0; Nr < 10000; Nr++)
if (A % 2) { MachDies ; }
else { MachDas ; }
... weil bei jedem Schleifendurchlauf auch der Test ausgeführt wird.
Schnell ...
if (A % 2)
for (Nr = 0; Nr < 10000; Nr++) { MachDies ; }
else
for (Nr = 0; Nr < 10000; Nr++) { MachDas ; }
... weil der Test nur noch einmal ausgeführt wird.
|
Bei einfache Programmiersprachen benutzen Unterprogramme die gleichen Variablen wie das Hauptprogramm. Die höheren Programmiersprachen erlauben Funktionen und Unterprogrammen die Verwendung von Variablennamen, die unter gleichem Namen bereits im Hauptprogramm oder in anderen Funktionen / Unterprogrammen existieren.
Speziell bei der Übergabe von Variablen (Argumenten) an das Unterprogramm
werden im allgemeinen zwei Mechanismen angeboten:
Die Übergabe der Argumente ‘als Wert’ bietet viele Vorteile:
Aber: Bei der Übergabe von Variablen ‘als Wert’ muß
das Programm bei jeder Variablenübergabe an eine Funktion / Unterprogramm
erst einmal eine Kopie der Variablen erstellen – das kostet zusätzlich
Rechenzeit. Daher gilt die
Die Programmiersprachen bieten zur Übergabe eines Arguments ‘als
Referenz’ unterschiedliche Möglichkeiten und Alternativen:
|
Zusammengesetzte logische Ausdrücke lassen sich auf verschiede Arten optimieren. Das De-Morgansche Theorem läßt verschiedene Umformungen dieser Ausdrücke zu. Doch nicht alles, was in der booleschen Algebra geht, funktioniert auch in Programmen (siehe Abschnitt Vorsicht bei Vergleichen).
Die folgenden Regeln sind hilfreich, wenn die Programmiersprache logische
Ausdrücke nur solange auswertet, bis das Ergebnis eindeutig ist. So
kann die Auswertung der logischen UND-Verknüpfung
X AND Y AND Z beendet werden, sobald ein
Ausdruck den Wert false hat. Wenn also
X = false ist, ist das Ergebnis des ganzen Ausdrucks
false, egal welchen Wert Y und Z haben.
Bei logischen ODER-Verknüpfungen ist es gerade umgekehrt. Wenn nur ein
Wert in dem Ausdruck X OR Y OR Z den Wert
true annimmt, dann ist der ganze Ausdruck true.
Falls also die Programmiersprache diese verkürzte Auswertung
unterstützt, gilt folgende
Beispiel: Y-Reisen (Motto “Wir buchen, Sie fluchen”) hat die Datensätze aller Einwohner einer Großstadt erhalten. Nun soll für die wehrfähigen Männer zwischen 18...35 ein Musterungsbescheid gedruckt werden. Wie sollte die Abfrage zur Selektion der potentiellen Wehrpflichtigen am Besten erstellen ?
Langsam ...
if ((Bürger->Alter >= 18) &&
(Bürger->Alter <= 35) &&
(Bürger->Geschlecht == "m"))
{ DruckeMusterungsBescheid(Bürger);
}
... denn der Anteil der Frauen an der deutschen Wohnbevölkerung liegt bei 52% – bei der Zahl der Geburten haben Männer zwar einen leichten Vorteil, weil Damen aber ‘haltbarer’ sind, erscheinen sie in der Bevölkerungsstatistik einige Jahre länger als die Herren, daher die 52%.
Weil in dem gezeigten Vergleich das Geschlecht zuletzt getestet wird, werden die Damen also unnötiger- und unhöflicherweise erst zwei Alters-Tests unterzogen, obwohl sie aufgrund ihres Geschlechts ohnehin keinen Musterungsbescheid erhalten würden.
Schneller ...
if ((Bürger->Geschlecht == "m") &&
(Bürger->Alter >= 18) &&
(Bürger->Alter <= 35))
{ DruckeMusterungsBescheid(Bürger);
}
... jetzt fallen die Damen schon beim ersten Test heraus. Weil bei einer durchschnittlichen Lebenserwartung von 73 Jahren vermutlich mehr Männer über 35 als unter 18 sind (hängt genaugenommen von der Verteilung in der ‘Alterspyramide’ ab), lohnt es sich außerdem, zuerst nach der Überschreitung des 35. Lebensjahres zu fragen.
[Anmerkung. ‘Bürger’ ist eine selbstdefinierte Struktur
in C. In anderen Programmiersprachen werden solche Strukturen mit TYPE oder
RECORD erstellt und die einzelnen Elemente beispielsweise mit
Bürger.Alter abgerufen.]
Beispiel: Das Finanzamt will Steuerbescheide für Pkw’s drucken. Die erste Unterscheidung findet nach dem Motor (im Fahrzeugschein ‘Antriebsart’ genannt) statt.
Langsam ...
switch (AntriebsArt)
{
case "W": // Wankel-Motor
{ SteuerBescheid_W; break; }
case "D": // Diesel-Motor
{ SteuerBescheid_D; break; }
case "O": // Otto-Motor
{ SteuerBescheid_O; break; }
}
[Anmerkung. // leitet in C einen Kommentar ein. In anderen
Programmiersprachen ist z.B. REM oder Einklammerung mit (* ... *) üblich.
Das Vorhandensein von Kommentaren sollten keinen Einfluß auf die
Geschwindigkeit haben.]
Schneller ...
switch (AntriebsArt)
{
case "O": // Otto-Motor
{ SteuerBescheid_O; break; }
case "D": // Diesel-Motor
{ SteuerBescheid_D; break; }
case "W": // Wankel-Motor
{ SteuerBescheid_W; break; }
}
... weil die häufigste Antriebsart bei Pkw der Otto-Motor ist, der Wankel-Motor ist dagegen nur noch in einigen Exoten und Oldtimern zu finden.
|
In manchen Sprachen, insbesondere z.B. SQL (Structured Query Language, Datenbankabfragesprache) wird die folgende Massnahme sehr empfohlen. Sie sollte aber nur erwogen werden, wenn die anderen Regeln nicht verletzt werden.
Beispiel:
Langsam ...
for(A = 0; A < 10; A++)
for(B = 1; B < 7; B++)
if(A × B == A + 3) { MachWas; }
... weil auf beiden Seiten ein berechneter Ausdruck steht.
Schneller ...
for(A = 0; A < 10; A++)
for(B = 1; B < 7; B++)
if(A × B - A == 3) { MachWas; }
...weil konstante und variable Werte getrennt wurden.
Noch schneller ...
for(A = 0; A < 10; A++)
for(B = 1; B < 7; B++)
if((B - 1) × A == 3){ MachWas; }
... weil hier die Variable A nur noch einmal geholt werden
muß.
Noch viel schneller ...
for(A = 0; A < 10; A++)
for(B = 0; B < 6; B++)
if(B*A == 3) { MachWas; }
... weil durch die Änderung des Schleifenzählers eine Subtraktion wegfällt.
Beispiel:
Langsam ...
for(Nr = 1; Nr < 20; Nr++)
if(Eingabe - 3 == Nr - 5)
{ MachWasMit(Eingabe); }
... auf beiden Seiten wird gerechnet. Doch hier kann man durch einfache mathematische Äqivalenzumformungen vereinfachen.
Schnell ...
for(Nr = 1; Nr < 20; Nr++)
if(Eingabe - Nr == -2)
{ MachWasMit(Eingabe); }
... weil auf der einen Seite des Tests wieder eine Konstante steht und eine Subtraktion wegfällt.
Noch schneller ...
for(Nr = -1; Nr < 18; Nr++)
if(Eingabe == Nr)
{ MachWasMit(Eingabe); }
... weil durch die Veränderung des Schleifenzählers die Subtraktion ganz wegfällt. Diese Verbesserung bringt mehr, als die Forderung nach einer Konstanten auf einer Seite der Gleichung.
|
Wenn alle Verzweigungsmöglichkeiten in einer
switch-case-Struktur gleich häufig sind, dann kann man
ab einer Größe von ca. 8 case-Verzweigungen die
Ausführung mit verschachtelten if-Strukturen beschleunigen.
Beispiel: Eine Firma produziert Kunststoffteile für den Küchenschrank (Salatschüsseln, Siebe ...). Die beiden letzten Stellen der Artikelnummer (eine 12-stellige Zahl) geben die Farbe wieder und diese soll im Klartext auf der Rechnung ausgedruckt werden:
Langsam ...
switch (ArtikelNr % 100)
{
case 1 : { printf("ROT "); break; }
case 2 : { printf("ORANGE"); break; }
case 3 : { printf("GELB "); break; }
case 4 : { printf("GRUEN "); break; }
case 5 : { printf("BLAU "); break; }
case 6 : { printf("WEISS "); break; }
case 7 : { printf("GRAU "); break; }
case 8 : { printf("BRAUN "); break; }
}
... weil im statistischen Mittel bei n Farben n/2 Tests – hier also 4 – durchgeführt werden.
Schneller ...
Farbe = ArtikelNr % 100
if (Farbe < 5)
switch (Farbe)
{
case 1 : { printf("ROT "); break; }
case 2 : { printf("ORANGE"); break; }
case 3 : { printf("GELB "); break; }
case 4 : { printf("GRUEN "); break; }
}
else
switch (Farbe)
{
case 5 : { printf("BLAU "); break; }
case 6 : { printf("WEISS "); break; }
case 7 : { printf("GRAU "); break; }
case 8 : { printf("BRAUN "); break; }
}
... weil die if-Abfrage mit einem Test vorsortiert, welche der
beiden switch-case-Statements benutzt werden sollen. Für
die if-Abfrage ist daher ein Test nötig, für
switch-case sind im statistischen Mittel weitere 2 Tests
erforderlich, im Mittel also 3 statt 4 Tests.
Entwickelt man die switch-case-Strukturen in weitere
if-statements, so kommt die nächste Form heraus. Die Anzahl
der Tests beträgt hier immer exakt 3 (also die statistische Komponente
fällt heraus). Bei umfangreicheren switch-case-Strukturen
lohnt es sich im allgemeinen nicht, switch-case-Strukturen auf
weniger als 4 case-Statements zu reduzieren.
Schneller ...
Farbe = ArtikelNr % 100
if (Farbe < 5)
if (Farbe < 3)
if (Farbe == 1) { printf("ROT "); }
else {
printf("ORANGE"); }
else
if (Farbe == 3) { printf("GELB "); }
else {
printf("GRUEN "); }
else
if (Farbe < 7)
if (Farbe == 5) { printf("BLAU "); }
else {
printf("WEISS "); }
else
if (Farbe == 7) { printf("GRAU "); }
else {
printf("BRAUN "); }
... weil hier Farbe zunächst in die Gruppe der Farbnummern
1-4 oder 5-8 eingeordnet wird. Dann erfolgt die Einordnung in Untergruppen
usw. Dadurch sind bei n Farben stets nur ln(n)/ln(2) Tests durchzuführen.
Vorsicht: Aus Gründen der Lesbarkeit wurde auf übermäßige Klammerung mit{}verzichtet. In einem praktischen Anwendungsfall wird man jedoch nicht exakt 2n Fallunterscheidungen treffen. Daher sollte dann geklammert werden, weil bei verschachteltenif-else-Strukturen daselseautomatisch dem letztenifzugeordnet wird.Wenn im Beispiel die Farbe GRUEN wegfällt, dann würden beim gegebenen Programmgerüst die Farben BLAU, WEISS, GRAU und BRAUN nicht mehr ausgegeben.
Hintergrund / Beispiel:
Nehmen wir folgende Zahlenkolonne, die in einem Array von Integerzahlen
gespeichert sein soll.
{ 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }
Wenn man mit switch herausfinden will, ob sich die 42 in dieser
Kolonne befindet, dann müßte man von links nach rechts alle Zahlen
durchtesten:
Ist 42 gleich der 1. Zahl (2) ? Nein.
Ist 42 gleich der 2. Zahl (3) ? Nein.
Ist 42 gleich der 3. Zahl (5) ? Nein .... usw.
Wenn man die Zahlen sortiert anordnen kann, gibt eine bessere Methode, um schneller zum Ergebnis zu kommen, indem man einfach fragt:
Ist 42 kleiner als die 9. Zahl (= mittlere Zahl, 23) ? Nein.
Durch diesen Test wurde bereits die Hälfte aller Zahlen ausgeschlossen.
Ist 42 kleiner als die 13. (= mittlere Zahl der verbliebenen Hälfte, 41) ? Nein.
Durch diesen Test wurde wieder die Hälfte der verbliebenen Zahlen ausgeschlossen.
Natürlich würde man mit switch keine 100 oder gar
1000 Tests durchführen, aber falls doch, dann würde man mit switch
im Mittel n/2, also 100/2 = 50 bzw. 1000/2 = 500 Tests durchführen,
mit verschachtelten if-Statements nur ln(n)/ln(2), also
ln(100)/ln(2) = 7 bzw. ln(1000)/ln(2) = 10 Tests.
Fazit: Bei switch-Strukturen mit vielen
case-Statements ist zu prüfen, ob verschachtelte
if-Statements nicht leistungsfähiger sind.
|
Das Zusammenfassen von Vergleichen kann manchmal auch schief gehen, daher
werden hier einige Problemfälle aufgelistet. In manchen Programmiersprachen
führt das nächste Beispiel zu einem Fehler, falls A
= 0, da diese Programmiersprachen (z.B. Visual Basic) immer alle
Ausdrücke einer Bedingung auswerten.
Bei anderen Programmiersprachen (z.B. Borlands Turbo-Pascal-Compiler) kann die Art der Auswertung vor der Kompilierung ausgewählt werden.
C wertet logische Ausdrücke nur so lange aus, bis das Ergebnis feststeht,
daher läuft die folgende Anweisung auch bei
A = 0 fehlerfrei ab:
if (A !=0 && 1/A > 7)
{ MachWasMit(A); }
[Anmerkung. In anderen Programmiersprachen wird dieser etwas kryptische
Vergleich so formuliert:
IF (A <> 0 AND 1/A > 7) THEN ... ]
Beispiel: In den folgenden Beispielen ist A eine Struktur,
welche von der Funktion InitOK für die weitere Verwendung
vorbereitet werden muß. Wenn die Vorbereitung erfolgreich verlief,
gibt InitOK den Wert true zurück, andernfalls
false.
Schlecht ...
if (InitOK(A) && (Wert > 0))
{ MachWasMit(A, Wert); }
...weil A bei jedem Test initialisiert wird, auch wenn Wert
<= 0 und die folgende Bearbeitung durch die Prozedur
MachWasMit gar nicht stattfindet.
[Anmerkung. In anderen Programmiersprachen wird dieser etwas kryptische
Vergleich so formuliert:
IF (InitOK(A) = TRUE) AND (Wert > 0) THEN ...]
Besser:
if (Wert > 0 && InitOK(A))
{ MachWasMit(A, Wert); }
... hier wird A nur noch bei Bedarf initialisiert.
Aber ...
if (InitOK(A) && Wert > 0)
{ MachWasMit(A, Wert); }
else { MachWasMit(A, 1 - Wert); }
... hier muß A in jedem Falle initialisiert werden, denn
egal wie Wert aussieht, A wird in jedem Falle verwendet.
Gefährlich ...
if (InitOK(A) || InitOK(B))
{ MachWasMit(A, B); }
... denn wenn InitOK(A) den Wert true
zurückmeldet, wird InitOK(B) gar nicht mehr ausgeführt.
[Anmerkung. In anderen Programmiersprachen wird dieser etwas kryptische
Vergleich so formuliert:
IF (InitOK(A) = TRUE) OR (InitOK(B) = TRUE) THEN ...
]
Dann hilft nur folgende Alternative:
Sicher ...
OK_A = InitOK(A)
OK_B = InitOK(B)
if (OK_A || OK_B)
nbsp; { MachWasMit(A, B); }
... denn die Verschachtelung in zwei if-Statements erzwingt
die Ausführung beider InitOK-Prozeduren, ist allerdings nicht mehr Ä.
|
Nachteil ist, daß der WebServer in der Regel für mehrere verschiedene Surfer arbeitet. Je länger er pro Surfer rechnet, um so weniger Surfer kann er gleichzeitig bedienen.
Typische Zeitfresser sind:
Leider wird auch in anderem Zusammenhang gerne und unnötigerweise von solchen Datenbankzugriffen Gebrauch gemacht. Dazu gehört z.B. dass Produktbeschreibungen in Online-Shops jedesmal neu von der Datenbank generiert werden, obwohl sich diese Beschreibungen kaum ändern. Sinnvoller wäre es, die Produkte nur gelegentlich nach Änderungen als HTML-Seite ausgeben zu lassen und diese dann auf dem Web-Server abzuspeichern.
Der Web-Server braucht dann nur noch die angeforderte HTML-Seite von der Festplatte zu holen, statt jedesmal von der Datenbank die Daten anzufordern und dann mit der Servlet-Engine die gleiche Seite wieder zu generieren.
Problem 2 kennt, wer sich gelegentlich im Internet mit den Formularen der verschiedenen Anbieter herumschlägt: Da werden unzählige Daten abgefragt und wenn man dann das Formular abschickt, kommt nach einiger Wartezeit eine Meldung zurück, daß man etwas vergessen habe.
Auch das ist purer Blösdinn, denn Fehler sollte man dann erkennen, wenn sie entstehen und nicht hinterher. Speziell das Internet bietet hier JavaScript, welches man mit einer HTML-Seite mitschicken kann. Es läuft auf dem Web-Browser des Besuchers und kann sofort bei der Eingabe auf Fehler reagieren. Einige Beispiele finden sich in der JavaScript-Ecke.
|
Mit den folgenden Anweisungen kann die Laufzeit eines zu optimierenden Programmabschnitts in C gemessen werden. Dies ist nur ein Beispiel und vom Betriebssystem sowie dem Anbieter des C-Compilers abhängig.
Die angezeigte Genauigkeit liegt bei 0,01 s. clock_t ist ein
Datentyp.
#include <time.h>
...
double LaufZeit; clock_t AnfZeit;
...
AnfZeit = clock();
/* Operationen, deren Laufzeit gemessen
werden soll */
LaufZeit = (double)(clock() - AnfZeit);
printf("%2.2f s\n", LaufZeit/CLOCKS_PER_SEC)
In VBA (Visual Basic for Applications) sieht die Zeitmessung so aus:
Function ZeitMessung()
Dim StartZeit As Currency
DoEvents
StartZeit = Timer
' Operationen, deren
Laufzeit
' gemessen werden soll
MsgBox "Dauer: " & Format(Timer - StartZeit,
_
"0.00") & " s",
, "Laufzeitmessung"
End Function
In jedem Falle sollte man keine anderen Anwendungen laufen lassen und mehrere Messungen durchführen, da sonst multitaskingfähige Betriebssysteme die Messungen zu stark mit ihrem Eigenleben beeinflussen.
Bevor man nach Sichtung der Zeitmessungen zu einer Programmänderung schreitet, sollte man außerdem überzeugende Geschwindigkeitsunterschiede messen, damit das entwickeln und debuggen veränderter Codes nicht mehr Zeit verschlingt, als der verbesserte Code jemals einsparen kann – wie immer im Leben, gilt es auch bei der Geschwindigkeitsoptimierung, das richtige Maß zu finden.