Um einen String in einen Integer umzuwandeln, lohnt es sich das ASCII-System auszunutzen. Das Prinzip ist ziemlich einfach: Man nimmt das erste char-Zeichen (was nichts anderes als eine Nummerierungszahl in der ASCII-Tabelle ist) und zieht davon die Position des Null-Zeichens ab. Damit bekommt man zu dem betrachteten Zeichen entsprechenden Integer-Wert, also aus ’8′ wird 8 usw.. Im nächsten Schritt wiederholt man die gleiche Prozedur mit dem nächsten Zeichen und der Wert, den man im letzten Schritt ausgerechnet hat, wird mit der Basis (für Dezimal: 10) multipliziert, so dass er eine Stelle nach links wandert. Das ganze wird wiederholt bis alle String-Zeichen durchlaufen sind.

// String (positive Ganzzahl) -> Integer
int myAtoi(const char* str)
{
	int res = 0;

	while(*str)
		res = res*10 + (*str++ - '0');	// Nutzt ASCII-System aus

	return res;
}

Eine weitere Version unterstützt noch andere Zahlensysteme:

// String (z.B. 0b110010010, 0o1163774, 0x01656E0F, 2234) -> Integer
// Annahme bei 0x-Zahlen: nur Großbuchstaben
int myAtoi(const char* str)
{
	int res = 0;
	const char* ch = str;

	switch(*++ch)
	{
		case 'b':	// binäre zahl
			while(*++ch)
				res = res*2 + (*ch - '0');
			break;

		case 'o':	// oktale zahl
			while(*++ch)
				res = res*8 + (*ch - '0');
			break;

		case 'x':	// hexadezimale zahl
			while(*++ch)
				res = res*16 + (('0' <= *ch && *ch <= '9') ? (*ch - '0') : (*ch - 'A'+ 10));
			break;

		default: // dezimale zahl
			while(*str)
				res = res*10 + (*str++ - '0');
	}

	return res;
}

Viel Spaß damit.

Nehmen wir an, es muss ein zweidimensionales Array vollständig durchlaufen werden. Dieser Fall trifft beispielsweise oft auf, wenn man Bildmanipulationen durchführt. Dazu ein minimales Beispiel.

	// ein Array dynamisch erstellen
	size_t width = 10000;
	size_t height = 10000;
	int* arr = new int[height*width];

	// Array zeilenweise durchlaufen
	for(size_t i = 0; i < height; i++)
		for(size_t j = 0; j < width; j++)
			arr[i*width+j] = i*j;

	// Array spaltenweise durchlaufen
	for(size_t j = 0; j < width; j++)
		for(size_t i = 0; i < height; i++)
			arr[i*width+j] = i*j;

Es wird ein zweidimensionales Integer-Array erstellt und auf zwei unterschiedliche Weisen durchlaufen. In jedem Durchgang wird ein Wert in das Array geschrieben.

Misst man die Zeit, die die beiden Schleifen zum durchlaufen des Arrays brauchen, so bekommt man ein zunächst überraschendes Bild.

Benötigte Zeit zum schreiben eines Arrays in Abhängigkeit von der Array-Größe.

Auf der X-Achse ist die Größe des Arrays aufgetragen und auf der Y-Achse die durchschnittliche Zeit (in Millisekunden, was an dieser Stelle aber unwichtig ist) aus 5 Durchläufen, die für einen Array-Durchlauf benötigt wurde ¹.

Offensichtlich benötigt der Code weniger Zeit, wenn das Array zeilenweise durchlaufen wird. Wie groß dieser Unterschied ist, sieht man besser, wenn man die beiden Zeiten in Verhältnis setzt.

Geschwindigkeitsgewinn beim durchlaufen eines Arrays (Schreibvorgang) zeilenweise, anstatt spaltenweise. Aufgetragen in Abhängigkeit von der Array-Größe.

Nach der Grafik zu urteilen beträgt der Geschwindigkeitsfaktor etwa 13 ². Ein beachtlicher Wert, wenn man bedenkt, dass es sich nur um eine einzige Schleife handelt.

Das gleiche bzw. sogar etwas bessere Bild bekommt man auch, wenn man die Lesezeiten misst.

Benötigte Zeit zum lesen eines Arrays in Abhängigkeit von der Array-Größe.

Geschwindigkeitsgewinn beim durchlaufen eines Arrays (Lesevorgang) zeilenweise, anstatt spaltenweise. Aufgetragen in Abhängigkeit von der Array-Größe.

Der Grund für die Geschwindigkeitsunterschiede ist die Cache-Verwaltung des Prozessors. Ein Computer hat mehrere Speicher, die unterschiedlich schnell und unterschiedlich groß sind, wie in der nachfolgenden Abbildung schematisch dargestellt ist.

Cache-Hierarchie.

L1- Cache ist der kleinste Speicher, er liegt am nächsten zum Prozessor und der Zugriff darauf geschieht am schnellsten ³. Andere Speicher sind größer, aber dafür langsamer.

Muss der Prozessor auf eine Speicheradresse zugreifen, dann wird gleichzeitig in allen Speicherstellen danach gesucht. Da der Zugriff auf L1-Cache am schnellsten geschieht, weiß man zuerst ob die gesuchten Daten dort liegen oder nicht. Wenn nein (man nennt es Cache-Miss), so muss der Prozessor warten bis die Ergebnisse von L2 vorliegen. Es kann sein, dass die Daten auch nicht in L2 liegen, sondern in L3, in Arbeitsspeicher oder sogar auf der Festplatte. In dieser Wartezeit ruht der Prozessor und somit die ganze Berechnung.

Werden die Daten gefunden (Cache-Hit), so werden sie nicht nur an den Prozessor weiter geleitet, sondern auch gleichzeitig in den schnelleren Speicher abgelegt (in Cache geholt). Da schnellere Speicher klein sind, müssen zwangsläufig die alten Inhalte überschrieben werden. Welche Daten man dabei überschreibt ist Prozessorabhängig, aber oft werden die Daten überschrieben, deren Benutzung (Schreibe/Lesen) am weitesten in der Zeit zurück liegt (LRU – Least-recently used). Beim Cache füllen wird nicht nur der Inhalt der gesuchten Speicheradresse kopiert, sondern auch die nachfolgenden Adressen. Wie viele es genau sind, hängt von der Breite des Caches ab.

Darauf ergeben sich zwei wichtige Schlussfolgerungen:

1. Der erneute Zugriff auf eine Speicheradresse wird auf jeden Fall schnell sein, da die Daten nach dem ersten Zugriff im Cache liegen.
2. Der Zugriff auf die nachfolgenden Adressen wird schnell sein (beschränkt auf die Cache-Breite), da beim Cache-Vorgang die nachfolgenden Elemente ebenfalls in den Cache abgelegt wurden.

Diese Schlussfolgerungen erfüllen die Prinzipien der zeitliche und räumliche Lokalität, die aus den statistischen Überlegungen zum Ablauf eines Computerprogramms hervorgehen.

• Zeitliche Lokalität: Nach einem Zugriff auf eine Adresse wird wahrscheinlich erneut darauf zugegriffen.
• Räumliche Lokalität: Nach einem Zugriff auf eine Adresse wird wahrscheinlich auf eine benachbarte Adresse zugegriffen.

Mit anderen Worten gesagt, sind die zeitliche und die räumliche Lokalität eine Folgerung aus der theoretischen Informatik und die Cache-Verwaltung der Prozessoren ist eine praktische Realisierung davon.

Jetzt können wir auch den Geschwindigkeitsunterschied in dem Einführungsbeispiel verstehen. Beim zeilenweisen Zugriff, werden nach dem ersten Cache-Miss die nächsten Elemente in den Cache gelegt. Somit ist der nachfolgende Zugriff (auf die nachfolgende Adresse) besonders schnell. Beim spaltenweisen Zugriff werden ebenfalls die nachfolgenden Elemente in den Cache abgelegt, aber man greift als nächstes nicht auf die nachfolgende Adresse zu, sondern auf die erste Adresse + Arraybreite. In der Regel liegt diese Adresse nicht im Cache und es muss wieder auf den langsameren Speicher geholt werden, was schließlich zur längeren Ausführungszeit führt.

Die Aufgabe des Programmierers ist auf diesen beiden Prinzipien aufzubauen und so die Programme schneller zu machen.

Selbstverständlich sollten diese Protokolle auch dazu dienen die eigene Ausarbeitung zu verbessern.Man sollte aber beachten, dass wenn die Protokolle auch testiert sind, so sind sie nie absolut fehlerfrei.

Wenn ihr selbst eure Ausarbeitung online stellen wollt, dann schreibt mir eine E-Mail mit der PDF im Anhang und ich werde sie in die Liste einfügen. Beachtet nur, dass beide Praktikanten mit der Veröffentlichung einverstanden sein müssen.

3.3: Polarisation und Doppelbrechung
Polarisation und Doppelbrechung 18.04.2011 504,19 kB -

4.2: Test der Bell’schen Ungleichung

4.3: Kühlen und Fangen von Rubidium Atomen in einer magneto-optischen Falle.

4.4-A: Holographie

4.6: Laserdiodengepumpter ND:YAG-Laser und Frequenzverdopplung
Laserdiodengepumpter ND:YAG-Laser und Frequenzverdopplung 23.01.2012 732,26 kB -

4.9-A: Laserresonator

4.10: Akusto-optischer Modulator

4.11: Optisches Pumpen

1.5: Zeeman-Effekt
1.8: Infrarot-Spektroskopie
3.10: Gepulste Kernspinresonanz
Gepulste Kernspinresonanz 16.01.2012 197,4 kB -

3.16-A: Quanten-Hall-Effekt

3.16-B: Supraleitung
Supraleitung 21.11.2011 119,67 kB -

3.17: Strukturanalyse mit Röntgenstrahlen nach Debye-Scherrer
Röntgenstrukturanalyse nach Debye-Scherrer 23.05.2011 374,07 kB -

3.20: Dielektrische Relaxationsspektroskopie an Polymeren
3.21: Röntgenkleinwinkelstreuung an teilkristallinen Polymeren
5.4: Thermometrie bei tiefen Temperaturen

1.1: Magnetfeldmessung
2.2-A: Wechselwirkung von Gamma-Strahlung mit Materie

2.2-B: Radioaktivität in der Umwelt
Radioaktivität in der Umwelt 01.11.2010 364,09 kB -
Radioaktivität in der Umwelt 20.12.2011 609,52 kB -

2.3: Alpha-Spektroskopie mit einem Halbleiterzähler
2.4: Mößbauer-Effekt an Fe-57
Mößbauer-Effekt an Fe-57 14.11.2011 440,64 kB -

2.5: Bremsung und Diffusion von Neutronen
2.6: Höhenstrahlung
Höhenstrahlung 24.10.2011 707,36 kB -

2.7: Paritätsverletzung beim Beta-Zerfall
2.8-A: Messung der Lebensdauer von Positronen in Materie
2.8-B: Positronen-Emissions-Tomographie
Positronen-Emissions-Tomographie 29.11.2010 2,73 MB -

2.9: Bestimmung der Lebensdauer von Myonen

5.1-A: Transistorverstärker und digitale Bauelemente
Transistorverstärker und digitale Bauelemente 20.12.2010 439.41 kB -

5.1-B: Operationsverstärker

Kommt ein Besucher auf die Website, liest 30 Minuten lang einen Artikel und schließt danach das Fenster, so erkennt Piwik nur eine Aktion und als Aufenthaltsdauer werden 0s und eine Absprungrate von 100% angezeigt.

Um diesen Designfehler zu beheben gibt es generell zwei Möglichkeiten:

1. Trackingsystem von Piwik umschreiben
2. Aktionen vortäuschen, wenn der Besucher noch auf der Website ist

Die Aufenthaltsdauer von einer auf neuen Minuten angestiegen.

Die erste Möglichkeit wäre die beste, aber auch die komplizierteste.
Dagegen ist die zweite Möglichkeit ziemlich schnell realisiert: Wird die Website neu geladen, so startet man einen Timer, der nach einer bestimmter Zeit Piwik neu aufruft und so eine Aktion vortäuscht. So lange der Besucher sich auf der Website befindet bekommt Piwik immer den (mehr oder weniger) letzten Aufenthaltszeitpunkt und kann daraus die Aufenthaltsdauer bestimmen.

Bevor man den Timer implementiert muss man sich überlegen wie oft der Timer aufgerufen werden soll. Jede Sekunde eine Serveranfrage zu senden ist nicht empfehlenswert.
Ich habe folgende Zeiten gewählt: 10s, 30s, 1min, 4min, 24min, 84min. Danach wird der Timer nicht weiter aufgerufen um die Statistik nicht unnötig zu verfälschen, wenn jemand vergessen hat das Browserfenster zu schließen.

Letztendlich muss folgenden Tracking-Code auf der Website:

<script type="text/javascript">
try {
var piwikTracker = Piwik.getTracker(pkBaseURL + "piwik.php", 1);
piwikTracker.trackPageView();
piwikTracker.enableLinkTracking();
} catch( err ) {}
</script>

durch diesen ersetzen:

<script type="text/javascript">
     var piwikTracker = Piwik.getTracker(pkBaseURL + "piwik.php", 1);

    function prtc(i)
    {
        // Piwik aufrufen
        try {
            piwikTracker.trackPageView();
            piwikTracker.enableLinkTracking();
        } catch( err ) {}

        // Zeiten festlegen (in Millisekunden)
        // Unterteilung selbst wählen.
        if(i == 5)
            rt = 10000;
        else if(i==4)
            rt = 20000;
        else if(i==3)
            rt = 30000;
        else if(i==2)
            rt = 3*60000;
        else if(i==1)
            rt = 20*60000;
        else if(i==0)
            rt = 60*60000;

        if(i >= 0)
        {
            i--;
            // Funktion soll nach einer Recall-Time starten
            window.setTimeout("prtc("+i+")",rt);
        }
    }

// Piwik-Tracking-Funktion aufrufen
prtc(5);

</script>

Die Absprungrate von 80% auf 20% gesunken.

Durch diese Änderung habe ich endlich realistische Werte für meinen Blog bekommen. Die durchschnittliche Besuchszeit ist von einer Minute auf neun angestiegen und die Absprungrate von ungefähr 80% auf 20% gesunken.

Der Nachteil dieser Methode ist, dass die Aktionenanzahl nicht mehr stimmt. Jeder muss für sich entscheiden an welcher Information er mehr interessiert ist. Für mich persönlich ist die Aufenthaltsdauer und die Absprungrate wichtiger als die Aktionenanzahl, da ich daran sehe, ob meine Arbeit sinnvoll ist oder nicht.

Als erstes definiert man eine Variable, die den aktuellen Fortschritt beschreibt. Wird beispielsweise ein Feld durchlaufen, so gibt diese Variable die Position, an der gerade eine Berechnung durchgeführt wird an. Ich nenne sie hier iter.

Anschließend benutzt man die Funktion ProgressIndicator und übergibt als Argument den Iterator (iter), wobei man angeben muss, dass er dynamisch ist.

ProgressIndicator[Dynamic[iter], {1, maxIter}]

Um jetzt den Fortschritt einer Berechnung anzuzeigen muss man in der Berechnung dem Iterator immer die aktuelle Laufvariable zuweisen.

Am Beispiel von Selectionsort könnte es so aussehen:

maxIter = 1000; (* Maximale Anzahl von Zahlenwerten *)

iter = 0; (* aktueller Fortschritt.  iter <= maxIter *)

(* Fortschrittsbalken einbauen. iter gleich maxIter –> 100% *)
ProgressIndicator[Dynamic[iter], {1, maxIter}]  

(* Liste mit Zufallswerten *)
numb = Table[Random[Integer, {1, 10000}], {x, 1, maxIter}];

(* Selectionsort *)
For[i = 1, i < maxIter, i++,
 minpos = i;
 For[j = i + 1, j <= maxIter, j++,
  If[numb[[j]] < numb[[minpos]],
   minpos = j,
   ]
  ];
 temp = numb[[i]];
 numb[[i]] = numb[[minpos]];
 numb[[minpos]] = temp;
 iter = i; (* iterator aktualisieren*)
 ]

Optimal wäre natürlich auch eine Restrechenzeitangabe. Die einfachste Möglichkeit ist eine lineare Zeitinterpolation, die je nach dem wie man den Iterator setzt für eine Abschätzung der Restzeit gut genug sein soll.

Fügt man den diesen Codeblock anstatt ProgressIndicator in dem oberen Beispiel…

Dynamic[
 {{"Status:",
    ProgressIndicator[iter, {0, maxIter}], (iter/maxIter)*100.0, "%"},
   {"Restzeit (min):",
    AccountingForm[((maxIter -
          iter)/((iter + 0.0001)/(AbsoluteTime[] - startTime)))/
      60, {Infinity, 1}], "", ""}} // MatrixForm
 ]
startTime = AbsoluteTime[];

… so sieht die Aussage folgendermaßen aus.

Viel Spaß beim Warten und Tee trinken