Wenn man den den %-Operator verwendet, aber weiß, daß bei x=i%m gilt i>=0 und i<2*m-1, dann ist es besser auf den %-Operator zu verzichten.

Der Rechenaufwand des %-Operators ist offenbar höher, als der eines Vergleichs und einer Addition.

Für 0<=i und m eine Potenz von 2 ist der Tip
" statt %2, %4, %8, %16, ... lieber &1, &3, &7, &15, ..."
effektiver, als dieser.

Wenn zwischen mehreren Fällen unterschieden werden muß, dann versuche die wahrscheinlichsten mit möglichst wenig Aufwand zu erkennen.

Für switch bedeutet das, daß oben die wahrscheinlichsten Fälle stehen sollten, da die switch-Anweisung vom Compiler in Code, der Ähnlichkeit mit einer if...else if...else if...else-Konstruktion hat, übersetzt wird (zumindest bei Java).

Die einzelnen Fälle werden von oben nach unten durchgetestet, bis ein Test positiv ist. Stehen die häufigen Fälle oben, dann werden im Durchschnitt weniger Test durchgeführt.

Weniger durchgeführte Tests bedeuten höhere Geschwindigkeit.

Wenn sie nicht wissen, wie häufig welche Fälle sind, lassen sie ihr Programm doch einfach mal zum Test mitzählen.

Wenn es sich um wirklich zeitkritischen Code handelt, lesen sie den Typ 1-Tip:
" if-else-Baum statt switch"

Variablen oder Parameter sollten, wenn sie später nicht nochmal etwas zugewiesen werden als final deklariert werden.

Vor allem Methoden-Parameter sind, zumindest bei mir, fast immer final.

• Hinweis für den Compiler / die VM . Je mehr man diesen Programmen hilft desto höher die Chance, dass diese die Hinweise zur Optimierung nutzen können.
• bessere Lesbarkeit des Codes(Verständnishilfe)
• Selbstkontrolle des Programmierers

Oft werden Methoden unnötigerweise häufiger mit gleichen Parametern aufgerufen, obwohl klar ist, daß sie immer das gleiche Ergebnis liefern.

Besonders häufige Beispiele für solche Methoden sind:
.length
.length()
.size()

  for(int i=0; i<a.length(); i++)
  {
    ... //Code der die Länge von a nicht verändert
  }//next i

  //runter- statt raufzählen
  for(int i=a.length()-1; 0<=i; i--)
  {
    ... //Code der die Länge von a nicht verändert
  }//next i

  {//start block
    final int len=a.length()
    for(int i=0; len>i; i++)
    {
      ... //Code der die Länge von a nicht verändert
    }//next i
  }//end block

  for(int len=a.length(), i=0; len>i; i++)
  {
    ... //Code der die Länge von a nicht verändert
  }//next i

Unnötige Arbeit sollte man immer einsparen. Zudem weiß man nie, wie aufwändig die unnötig oft aufgerufene Methode ist.

  for(int y=0; 40>y; y++)
  { for(int x=0; 20>x; x++)
    { c[y*40+x]=1;
    }//next x
  }//next y

  for(int y=0; 40>y; y++)
  { final int y40=y*40;
    for(int x=0; 20>x; x++)
    { c[y40+x]=1;
    }//next x
  }//next y

Mehrfachberechnungen kosten unnötig Performance.

Bei m=2, 4, 8, 16 ... ist
x%m == x&(m-1)
für positive, ganzzahlige x.

Diese Optimierung ist so alt, wie das Programmieren selbst.

Diese Optimierung wird z.B von fast jedem C/C++ -Compiler bei unsigned Variablen automatisch gemacht. Da java aber keine rein positiven Variablentypen (außer char) kennt, darf der java-Compiler derartige Optimierungen nicht machen.

Da der Programmierer aber weiß, ob seine Zahlen positiv sind, oder er damit leben kann, daß er für negative Zahlen auch positive Reste erhält, kann er selbst diese Optimierung nutzen.

Der &-Operator ist eine reine Bitverknüpfung ohne Rechenaufwand, während der %-Operator auf quasi jedem Computer langsamer ist.

Das Verhalten bei negativen Zahlen ist mir persönlich bei der Variante mit & sogar lieber als das der %-Variante.

Der Entscheidung der Java-Designer keine unsigned Typen in die Sprache aufzunehmen verdanken wir es, daß diese Optimierung nicht vom Compiler gemacht werden kann :-(

Diese Optimierung bring mehr, als der Tip:
" if-else statt %"
Der ist dafür aber für beliebige m anwendbar.

Teilen durch Potenzen von 2 (2, 4, 8, 16, 32 ...) bei positiven ganzen Zahlen sollte man durch Bitschieben (um 1, 2, 3, 4, 5, ...) ersetzen.

Diese Optimierung ist so alt, wie das Programmieren selbst.

Teilt man eine negative Zahl auf diese Weise, ist Das Ergebnis nicht genau gleich, da das Bitschieben bei negativen Zahlen immer aufrundet statt abzurunden.

Diese Optimierung wird z.B von fast jedem C/C++ -Compiler bei unsigned Variablen automatisch gemacht. Da java aber keine rein positiven Variablentypen (außer char) kennt, darf der java-Compiler derartige Optimierungen nicht machen.

Da der Programmierer aber weiß, ob seine Zahlen positiv sind, oder er damit leben kann, daß er für negative Zahlen aufgerundet wird, kann er selbst diese Optimierung nutzen.

Bitschiebereien sind auf allen mir bekannten Systemen deutlich (um ein vielfaches) schneller als Dividieren.

Der Entscheidung der Java-Designer keine unsigned Typen in die Sprache aufzunehmen verdanken wir es, daß diese Optimierung nicht vom Compiler gemacht werden kann :-(

Multiplizieren mit Potenzen von 2 (2, 4, 8, 16, 32 ...) bei ganzen Zahlen sollte man durch Bitschieben (um 1, 2, 3, 4, 5, ...) ersetzen.

Diese Optimierung ist so alt, wie das Programmieren selbst.

Diese Optimierung wird z.B von fast jedem C/C++ -Compiler Ganzzahlvariablen automatisch gemacht.

Bitschiebereien sind auf allen mir bekannten Systemen schneller als Multiplizieren.

Auch, wenn man glaubt, daß der Compiler diese Optimierung macht, kann es nicht schaden sie selbst vorzunehmen.

Wenn sie von positiven Zahl n eine Zahl x abziehen wollen, n=2k-1 und x<=n, dann ist das bitweise exklusiv-oder (XOR) gleich der Subtraktion.

Also nur für Werte von x, so daß das Ergebnis positiv bleibt!

Bemerkung1: Die Bitverknüpfung XOR wird in java mit ^ ausgedrückt.

Bemerkung2: Mir ist klar, daß diese Optimierung nur selten anwendbar ist.

Bit-Operationen sind, auf allen mir bekannten Systemen, schneller als Rechenoperationen. (eventuell aber nur sehr wenig)

n=2k-1 sind Zahlen, die in der binären Darstellung nur aus Einsen bestehen. Die oben zur Optimierung angegebenen Subtraktionen (binäre Zahlendarstellung!), sind solche, bei denen beim Berechnen keine Überträge entstehen.

Wenn der Programmierer aufgrund der in seinem Programm vorkommenden Zahlen weiß, daß in der Subtraktion (binäre Zahlendarstellung!) keine Überträge vorkommen, kann auch in solchen Fällen XOR statt der Subtraktion verwenden. (Aber Vorsicht, sie sollten ganz sicher sein!)

Bei Bedingungen, die aus mehreren Teilbedingungen bestehen sollte man, auf die Reihenfolge achten.

Bedingungen werden von links nach rechts ausgewertet!

Wenn man z.B. den Fall:
if((Bedingung1) && (Bedingung2))
Wenn beide Bedingungen ähnlich teuer sind, dann sollte man den, der am wahrscheinlichsten false liefert nach vorn stellen. (wenn Bedingung1 false liefert, wird Bedingung2 gar nicht ausgewertet.)

Kriterien der Reihenfolge sollten sein:

• Aufwand beim Prüfen der Bedingungen
• bei und-Verknüpfung wahrscheinlicher fehlschlagende Bedingungen nach links
• bei oder-Verknüpfung wahrscheinlicher erfolgreiche Bedingungen nach links

So minimiert man den durchschnittlichen Aufwand bei der Auswertung der Gesamtbedingung.

Eine switch-Verzweigung wird vom Compiler in eine Art von hintereinander stehende if-Anweisungen übersetzt. (Da immer die selbe variable getestet wird, gibt es einen speziellere Bytecode als wenn man selbst lauter if-Anweisungen schreibt.)

Bei gleicher Wahrscheinlichkeit aller n Fälle, werden im Durchschnitt n/2 Vergleiche gemacht.

Die Idee diese Tips ist es die Fälle zu ordnen, und dann durch fortlaufende Intervallhalbierung den richtigen Fall zu finden.
Das reduziert die Anzahl der durchschnittlichen Vergleiche auf log2n. Bildlich ergibt das einen binär-verzweigten Entscheidungsbaum.

Sollten die Fälle nicht alle gleich wahrscheinlich sein, und man die Wahrscheinlichkeiten der Einzelfälle kennen, kann man statt das Intervall in jedem Schritt zu halbieren auch eine andere Aufteilung wählen, so daß die Wahrscheinlichkeit der entstehenden beiden Intervalle annähernd gleich ist. (siehe: Huffman-Kodierung, Shannon-Fano-Kodierung [siehe WIKIPEDIA]).

Wie in der Beschreibung erklärt, sinkt die Anzahl der durchschnittlichen Vergleiche von O(n) auf O(log n).

Damit rentiert sich dieser Tip mit zunehmender Anzahl von Fällen immer mehr.

In einem Test für gleich wahrscheinliche Fälle hat sich dieser Tip bei mir schon bei 8 verschiedenen Fällen (manchmal sogar schon bei 4) gelohnt.

Viele Algorithmen werden rekursiv erklärt, können aber auch mit Schleifen implementiert werden. In solchen Fällen sollte man die nicht rekursive Variante bevorzugen, auch wenn der Programmcode meist komplizierter erscheint.

Viele Algorithmen basieren auf der Idee "divide and conquer" ("Teile und herrsche") [siehe WIKIPEDIA] und sind daher schon von ihrer Idee her rekursiv. Daher sind sie auch besonders elegant und leicht verständlich, wenn sie als rekursives Programm geschrieben werden. Rekursionen bedeuten aber besonderen Aufwand für den Computer. Deshalb gibt es für viele Algorithmen auch eine nicht-rekursive Variante, die zwar meist komplizierter aussieht, aber fast immer schneller und speichersparender ist.

  int fakultaet(final int n)
  {
    if(1>=n)
      return 1;
    return fakultaet(n-1)*n;
  }

  int fakultaet(final int n)
  {
    int erg=1;
    for(int i=n; 1<i; i--)
      erg*=i;
    return erg;
  }

Bei einer Rekursion (wenn der Compiler sie nicht selbst zu einer Schleife optimieren kann ("Optimierung von Endrekursion" [WIKIPEDIA])), Müssen, wie bei jedem Methoden-Aufruf alle lokalen Variablen und Prozessor-Register gesichert, ein Sprung zum Code der Methode durchgeführt, ...
pro Rekursionsschritt gemacht werden.

Dieser nicht unerhebliche Aufwand entfällt bei einer nicht-rekursiven Lösung, die dadurch, auch wenn sie komplexer aussieht, meist schneller ist und weniger Speicher benötigt.

Die Berechnung der Fakultät ist ein Beispiel, das sich besonders leicht in eine Schleifenvariante bringen läßt, da der rekursive Algorithmus endrekursiv ist [WIKIPEDIA].

Dieser spezielle Rekursionstyp wird von vielen Compilern erkannt und selbst zu einer Schleife optimiert (aber nicht von jedem Compiler :-( ). Komplizierte Rekursionen können aber nicht vom Compiler optimiert werden, da das Auflösen in Schleifen oft zusätzliche Verwaltungsstrukturen benötigt, die der Programmierer sich problemspezifisch überlegen muß.

Wenn es eine Klasse (z.B. in einer großen Bibliothek) gibt, die sie verwenden könnten, dann ist diese nicht unbedingt optimal für ihr Problem.

Zum Beispiel Containerklassen sind in Bibliotheken meist so geschrieben, daß sie eine weite Spanne von Zugriffsarten/Manipulationen erlauben. Aber z.B. Einfügen/Löschen ist je nach Implementierung sehr verschieden wenn sie am Position 0, in der Mitte oder am Ende einer Datenstruktur gemacht werden. Deshalb gibt es auch in den Bibliotheken so viele verschiedene Containerklassen mit oft sehr ähnlicher, oder gleicher Pragrammierschnittstelle.

Hat man aber einen sehr speziellen Anwendungsfall lohnt es sich oft selbst eine für diesen Fall optimierte Implementation zu schreiben.

Allgemeine Lösungen sind fast nie optimal für einen speziellen Fall, wie eine maßgeschneiderte Lösung.

Verwenden sie java.util.ArrayList statt java.util.Vector.

Der Unterschied besteht darin, daß in der Klasse Vector die Methoden synchronized sind, was zu geringerer Geschwindigkeit führt. In der Klasse ArrayList ist nicht synchronized.

Oft braucht man die Synchronisation jeder einzelnen Methode nicht. Wenn doch, kann man die Zugriffe auf ArrayList-Objekte ja selbst synchronisieren.

Wenn sie eine Zeichenkette zusammenbauen wollen, dann vermeiden sie es den '+'-Operator für Strings zu verwenden. Dieser ist relativ langsam, da immer neue Objekte erzeugt und der Inhalt kopiert werden.

Vorzuziehen ist es die Zeichenkette in einem java.lang.StringBuffer-Objekt zusammenzubauen und, wenn er fertig ist in einen java.lang.String umzuwandeln. Das ist deutlich schneller.

Wenn sie ein Array kopieren wollen, verwenden sie nicht eine selbstprogrammierte Schleife, sondern die java.lang.System.arraycopy(...) Methode.

If you use the %-operator. For x=i%m under the condition that i>=0 and i<2*m-1 is true, you should avoid the %-operator.

The computational effort of the %-operators is higher than the comparison and addition.

For 0<=i and m is a power of 2 the tip
" instead of %2, %4, %8, %16, ... better use &1, &3, &7, &15, ..."
is more effective than this tip.

If a decision between multiple cases which are of different like lines, you should try to detect the most likely ones with as few effort as possible.

For the switch-statement this means, that the most likely ones should be placed on top, because the compiler translates the switch-statement to something like a if...else if...else if...else-construction (this is true at least for java).

The different cases are tested, starting at the top, until one matches. If the most likely cases are the topmost ones, the average number of tests made decrease in comparison to any other order.

Less tests means after execution.

If you have no idea which cases are the most likely ones, count each occurrence while a test run.

If your code is a speed critical part, you should read the Typ 1-Tip:
" if-else-tree instead of switch"

Variables or parameters should, if they are used like constants, be declared as final.

Especially method parameters are, in my code, nearly always final.

• This is a hint for the compiler / the VM . The more hints you give to this programs, the more likely it is that they can use them for optimisations.
• Readability of code also increases
• A kind of self-control when for the programmer

Often methods are called with same parameters more often than needed, because the programmer knows, that he always gets the same result.

Often seen examples for such methods:
.length
.length()
.size()

  for(int i=0; i<a.length(); i++)
  {
    ... //Code which did not modify the length of a
  }//next i

  //count down instead of up
  for(int i=a.length()-1; 0<=i; i--)
  {
    ... //Code which did not modify the length of a
  }//next i

  {//start block
    final int len=a.length()
    for(int i=0; len>i; i++)
    {
      ... //Code which did not modify the length of a
    }//next i
  }//end block

  for(int len=a.length(), i=0; len>i; i++)
  {
    ... //Code which did not modify the length of a
  }//next i

If you can help the computer to avoid work, make it. When you call methods not implemented yourself, you never know how much time they need. length() and size() are for most Objects quite cheap to be computed, but you can never relay on this.

  for(int y=0; 40>y; y++)
  { for(int x=0; 20>x; x++)
    { c[y*40+x]=1;
    }//next x
  }//next y

  for(int y=0; 40>y; y++)
  { final int y40=y*40;
    for(int x=0; 20>x; x++)
    { c[y40+x]=1;
    }//next x
  }//next y

avoiding unnecessary computations improve speed.

When m=2, 4, 8, 16 ... than
x%m == x&(m-1)
is the same for positive integers x.

This optimisation is as old, as programming itself.

Par example nearly every C/C++ -compiler makes this optimisation for unsigned variables. Because java has no unsigned types (except of char), the java-compiler is not allowed to make this optimisation.

The programmer knows, if the values are always positive, or he can live with the different result for negative values, he is able to use this optimisation.

The &-operator is a simple bit-operation without any computation. The %-operator is slower on all CPUs (as far as I know).

The result for negative values when you use & is even preferred by me (because it always returns positive values).

The decision of the Java-designer to have no unsigned variable types is the reason why the javacompilers are not allowed to make this optimisation :-(

This optimisation is more effective than the tip:
" if-else instead of %"
which can, in contrary to this tip, be used for every m.

Divide by powers of 2 (2, 4, 8, 16, 32 ...) for positive integers should be replaced by bit-shifting (by 1, 2, 3, 4, 5, ... bits).

This optimisation is as old, as programming itself.

The result of bit-shifting is not the same as if you use division for negative integers, because because shifting rounds always to the next bigger integer value. Division always rounds to the next smaller integer value. (the difference of the results may be 0 or 1 for negative values)

Par example nearly every C/C++ -compiler makes this optimisation for unsigned variables.

java has no unsigned types (except of char). Therefore no java compiler is allowed to make this optimisation.

The programmer knows if the values are always positive, he can make this optimisation himself (is the different result for negative values did not bother him, he can also use this tip if the values are negative).

Bit-Manipulations are faster than computations on all system I know. Division is quite expensive on most CPUs, therefore this optimisation speeds up a lot.

The decision of the Java-designer to have no unsigned variable types is the reason why the javacompilers are not allowed to make this optimisation :-(

Multiply with a power of 2 (2, 4, 8, 16, 32 ...) can be replaced for integers by bit-shifting (by 1, 2, 3, 4, 5, ... bits).

This optimisation is as old, as programming itself.

Par example nearly every C/C++ -compiler makes this optimisation for unsigned variables.

Bit-manipulations are, on all Systems I know, faster than multiplying (on some systems only a little)

Also If you think the compiler will make this optimisation, you can make it yourself (avoids relaying on the compiler optimisation).

If you want to subtract from n the value x and n=2k-1 and x<=n, than you can use bitwise exclusive-or (XOR) instead of the subtraction.

That means for Values of x, that lead to a positive result!

Remark1: The bitwise operation XOR is written in java as ^ .

Remark2: This optimisation is quite exotic, because it can only be used in a very special kind of cases.

Bit-operations are, on all systems known by me, faster than arithmetical operations. (probably only very little faster than subtraction)

n=2k-1 are values where the binary representation has only ones. The subtractions which can be optimised by this tip are therefore once, where no carry occur.

If the programmer knows, that the binary subtraction for his specific values lead to no carrys, he can use this optimisation also for other values than the ones described in this tip. (Be aware that the result is only correct if no carry occur in the binary subtraction!)

If a condition is a combination of subconditions, you can often choose the order of the subconditions without changing the behaviour.

Conditions are tested from left to right!

If you have e.g. the case:
if((condition1) && (condition2))
If testing of each of the both conditions costs about the same, you should make the one which delivers more likely false should be placed as condition1. (if the condition1 delivers false , the condition2 is not tested at all.)

Criteria for the order of sub-conditions should be:

• costs for the test of the sub-conditions
• when sub-conditions are connected by a and-operation, the sub-condition which is more likely false should be left
• when sub-conditions are connected by a or-operation, the sub-condition which is more likely true should be left

This way you minimise the number of sub-condition to be tested.

A switch-statement is replaced by the compiler by code, which looks like a row of if-conditions. (Because all condition refer to the same variable there is a special bytecode in java so the code differs form the code generated for a row of if-conditions.)

If all n cases a equal likely, in average n/2 test must be made.

The idea of this tip is to order all cases in a way that you can make a kind of binary search for the case that matches.
This way you reduce the number of test to make to log2n. This means create a decision-tree.

If not all cases are equal likely, you may create a not balanced decision-tree to minimise the average number of needed comparisons. (see: Huffman-Code, Shannon-Fano-Code [see WIKIPEDIA]).

Like mentioned in the description the average number of comparisons are reduced from O(n) to O(log n).

This means this optimisation get more effective the more cases you have.

In a test, where all cases where equal likely, this tip improves the speed when at least 8 cases exists (for 4 cases nearly no speed-up).

A lot algorithms are explained in a recursive way, but can also be implemented by using loops instead of recursion. If this is the case, you should prefer the non recursive version even if the code looks more complicated.

There are a lot of algorithms which are based on the idea of "divide and conquer" ("divide and rule") [see WIKIPEDIA] and are because of this idea recursive. This is the reason why they can be easy understood when described in a recursive way. But recursion is always a lot of work for the computer. Therefore there is often also non recursive version, which looks in most cases more complicated but are mostly faster and need less memory.

  int factorial(final int n)
  {
    if(1>=n)
      return 1;
    return factorial(n-1)*n;
  }

  int factorial(final int n)
  {
    int result=1;
    for(int i=n; 1<i; i--)
      result*=i;
    return result;
  }

For each recursive call (if the compiler cannot itself optimises it to a loop ("optimisation of tail-recursion" [WIKIPEDIA])), all local variables must be stored before the call, also CPU-registers, the jump to the method, ... must be performed.

All this is not needed in an non-recursive implementation, which can therefore be faster and needs less memory, even if it looks more complicated.

The computation of n! is an example which can be easily transformed to a loop because the algorithm is tail-recursion [WIKIPEDIA].

This special type of recursion can be detected and optimised to a loop by most compilers (but not every compiler :-( ). More complicated recursions can, in most cases, not be optimised by compilers because special data structures for each problem must be invented by the programmer to implement a loop based implementation.

If there is a class (e.g. part of a big code-library) which can fulfil your needs, it must not be the optimal choice for your special problem.

Container classes are par example written to fulfil a wide variety of needs. Because the is no data structure which is optimal for all cases there are often different implementations with equal APIs in the libraries. Insert or delete have very different speeds for different data structures. If you only need delete/insert at special position you may be able to invent (or find) a implementation optimal for your need.

General data structures are in most cases as optimal for your special needs as a specially for your case invented/implemented structure.

Use java.util.ArrayList instead of java.util.Vector.

The difference is, that in the class Vector the methods are synchronized what slows them down. In class ArrayList are the methods not synchronized.

In a lot of cases you do not need the Synchronisation of each method separately. If you need synchronisation, you can synchronise ArrayList-objects of your own.

If you want to create a String by concatenation, avoid to use the '+'-operator for Strings. This operator is quite slow because every time a new Object is created and the contend of the old String must be copied to it.

It is better to use a java.lang.StringBuffer-Object and when you have created the hole String by the .append(...)-methods, call the toString()-method at the end to get a java.lang.String. This way is a lot faster.

If you want to copy an array, did not use a loop to copy each element. Use the java.lang.System.arraycopy(...)-method.