ggT / gcd, wer kann’s am Kürzesten?

Posted by Chris on Januar 05, 2012

No Gravatar

ggT / gcd, wer kann’s am Kürzesten? Diese Frage, tauchte auf, nachdem ich versuchte, den grössten gemeinsamen Teiler aus Lust und Laune in ein paar Programmiersprachen zu implementieren (und einige male kläglich scheiterte). Von der Auswahl ausgenommen sind esoterische oder „unleserliche“ Sprachen (APL) und natürlich solche, die eine gcd-Funktion bereits in den Bibliotheken haben. Unter diesen Gesichtspunkten gewinnt hier relativ klar Forth! Irgendwie überraschend (aber beim zweiten Nachdenken doch nicht mehr so überraschend), dass eine Programmiersprache aus den Sechzigerjahren des vorigen Jahrhunderts so unglaublich effizient im Ausdruck ist:

: gcd ( a b -- n )
  begin dup while tuck mod repeat drop ;

Zugegeben, ohne genau zu wissen, was tuck macht, ist es etwas schwierig zu verstehen, aber das Prinzip der wiederholenden Modulo ist schon klar zu erkennen.
Aufrufe dieser Funktion macht man dann in etwa so:

142864 24 gcd . 8

oder pro Linie ein Argument (da merkt man deutlich, dass Forth nur auf einem Stack arbeitet):

14361672
649981417530
gcd
. 1446

Wer dies unbedingt austesten will, sollte sich gforth (GNU) installieren. Für Fans der UPN: In Forth rechnet man aufgrund des Stacks natürlich mit der umgekehrten polnischen Notation:

5 3 + 7 2 + * .

(mit dem Punkt holt man sich das letzte Resultat vom Stack, quasi ein pop). Natürlich gibt es auch andere Kandidaten, die zumindest ähnlich kurz sind, aber meines Erachtens ist Forth noch die bekannteste (ich habe jedenfalls noch nie was von K oder Joy gehört). Interessanterweise bietet auch gnuplot eine Lösung dafür an. Ich weiss nicht, ob man Gnuplot zu den Turing-vollständigen Sprachen zählt, deshalb ausser Konkurrenz:

gcd (a, b) = b == 0 ? a : gcd (b, a % b)

Ach ja, der Preis für die längste Implementierung von gcd geht an SED (ein Streaming-Editor von Unix, der eigentlich nie als Programmiersprache gedacht war), den Sourcecode kann man sich bei rosettacode.org angucken ;-)

[1] http://rosettacode.org/wiki/Gcd

Klein und fein: Der Boyer-Moore-Horspool Algorithmus

Posted by Chris on November 01, 2011

No Gravatar

Zugegeben, ich verstand den Boyer-Moore Algorithmus nicht ganz, was alleine schon ein Grund war, eine einfachere Variante zu implementieren. Der Boyer-Moore-Horspool ist so eine Variante. Glücklicherweise zeigt sich, dass die Horspool-Vereinfachung die Textsuche im durchschnittlichen Fall nicht oder nicht viel langsamer werden lässt (rein subjektive Einschätzung!). Neugierige sollten den Code 1:1 kopieren und verwenden können mit einem beliebigen Java-Compiler. Und bitte einfach den Programmierstil ausblenden, es ging mir nur darum, den Algorithmus zu testen und wenigstens halbwegs zu verstehen. Heute braucht man sich kaum mehr selber um Implementierungen von Suchalgorithmen zu bemühen, die meisten Programmierumgebungen bringen entsprechende Bibliotheksfunktionen seit vielen Jahren mit.

public class BoyerMooreHorspoolSearch {
	private char[] text;
	private int text_len;
	private static final int ALPHABET_SIZE = 256;
 
	public BoyerMooreHorspoolSearch() {
		String str = "overeovere The oxen-brown Fox jumped over the Fox-lake. It (fox) didn't" +
				" know why, but it was kinda fun overemphasized! xxxxxxxxxxx aaaaaaa";
		this.text = str.toCharArray();
		text_len = text.length;
		System.out.println("DEBUG: text_len: " + text_len);
	}
 
	public BoyerMooreHorspoolSearch(String text) {
		this.text = text.toCharArray();
		text_len = this.text.length;
	}
 
	private void search(final String pattern) {
		char[] pat = pattern.toCharArray();
		int pat_len = pat.length;
		int[] occurrenceTable = initOccurrence(pat);
		int pos = 0; // our text index position
		int countloops = 0;
 
		while (pos <= text_len-pat_len) {
			int j = pat_len-1; // our pattern index position
			// As long as the pattern chars are hits (we start at the
			// end of the pattern) => go one backwards (to the left).
			while (j >= 0 && pat[j] == text[pos+j]) j--; // hits
			if (j < 0) report(pattern, pos);
 
			// We get here, when: a) a full hit was found
			// and b) nothing was found or partially pattern was found
			// in either case, we have to check, how far to the right we
			// can jump now.
			//
			// Now we do this in one step: take the jump-length from
			// the occurrenceTable indicating pat_len, if the character
			// of the current pos in text is _not_ in the pattern and
			// giving the difference from the right to the rightmost character
			// in the pattern, if the character at pos in text _is_ in our
			// pattern
			pos += occurrenceTable[text[pos+pat_len - 1]];
			countloops++;
		}
		System.out.println("DEBUG: Loops: " + countloops);
	}
 
	private int[] initOccurrence(final char[] pat) {
		int[] occurrenceTable = new int[ALPHABET_SIZE];
		char a;
		int pat_len = pat.length;
 
		for (a = 0; a < ALPHABET_SIZE; a++)
			occurrenceTable[a] = pat_len;
 
		// We fill the table at the position of the ASCII char
		// (for example occurrenceTable[97] for 'a') with the
		// index value of it's last occurrence in the pattern.
		for (int j = 0; j < pat_len-1; j++)
			occurrenceTable[pat[j]]=pat_len - j - 1;
 
		return occurrenceTable;
	}
 
	private void report(final String pat, final int pos) {
		System.out.println("Found \"" + pat + "\" at position "
				+ (pos+1) + " (index " + pos + ") in the text!");
	}
 
	// Driver
	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		BoyerMooreHorspoolSearch bmh = new BoyerMooreHorspoolSearch("Is there a fox?");
		BoyerMooreHorspoolSearch bmh = new BoyerMooreHorspoolSearch();
 
		bmh.search("Fox");
		bmh.search("fox");
		bmh.search(" fox"); // this should _not_ be found
		bmh.search("ox");
		bmh.search("xxx");
		bmh.search("overe");
	}

Automatisierte Server-infrastruktur mit Puppet in der KMU: Lohnt sich das?

Posted by Chris on September 08, 2011

No Gravatar

Puppet ist seit Jahren im Aufwind und entwickelt sich zum Nonplusultra im professionellen Konfigurationsmanagement. Es ist schon längst nicht mehr nur die “Alternative zu cfengine” die es anfangs noch war. Die Liste der Firmen, die seit längerem und im grossen bis sehr grossen Umfang (bis zehntausende von Servern oder Instanzen) auf Puppet setzen ist beeindruckend, darunter finden sich unter anderem Google, Twitter, Red Hat, Sun, Citrix, match.com, Rackspace etc. Wegen der ausgezeichneten Reputation von Puppet und der möglichen Vollautomatisierung (ein heiliger Gral von Systemadministratoren, leider wird dies manchmal eher als Bedrohung ihres Jobs wahrgenommen) entschieden wir uns für eine Evaluation dieser Software. Der Preis für die Flexibilität und die überragende Mächtigkeit dieses Instruments ist allerdings am Anfang ziemlich hoch: Nicht wegen dem Kaufpreis, es handelt sich ja um Opensource, aber die Lernkurve ist am Anfang wirklich sehr steil. So steil, dass ich mich die erste Woche mehr als einmal gefragt habe: Sollen wir wirklich? Lohnt sich das überhaupt für unsere 20 Linux-Server? Vielleicht ist es gar nicht so schlecht, dass die Einstiegshürde so hoch ist, damit wird sichergestellt, dass sich nur eingehend damit beschäftigt, wer genau weiss, was er tut (das ist auch bei Linux-Administratoren nicht automatisch der Fall ;-) und was genau mit dem Werkzeug erreicht werden soll.

Nach zwei Wochen intensiven Lernens (Meistens “Learning by doing”, denn praktisch alle  Puppet-Bücher sind nicht wirklich brauchbar) ist die Antwort Ja. Ja, und es würde sich sogar nur mit 10 Servern bereits lohnen. Denn nach dem hohen Lernaufwand am Anfang wird das Erstellen von neuen Modulen und Konfigurationen immer einfacher und schneller. Es macht Spass, ein derartig mächtiges Werkzeug immer besser zu beherrschen. Zudem gibt es eine Unmenge von vorgefertigten Modulen auf den entsprechenden Internetseiten zu finden. Und nicht zuletzt lernt man sehr viel über deklarative Sprachen und wenn man will, kann man zugleich noch etwas Ruby Programmieren lernen, je nachdem wie tief man in die Materie eintauchen möchte.

Einen anständigen Workflow vorausgesetzt kommt man unter Umständen auch intensiv mit Git in Kontakt, was einem den zukünftigen Umgang mit diesem ebenfalls sehr mächtigen Versionierungswerkzeug in anderen Projekten sehr einfach macht (Projektleiter, ob kommerziell oder Opensource sind froh, wenn sie nicht erst einen Kurs in “Git basics” geben müssen). Als kleiner Bonus wird durch den Workflow auch ein Produktionsrelease-Zyklus eingaführt mit Test und Live-Szenarien, ohne die sonst üblichen Probleme eines Paradigmen- oder Prozesswechsels (Akzeptanz u.ä.), denn die ersten Früchte der Arbeit werden sehr schnell auch individuell spürbar. Für vorsichtigere Naturen lohnt sich bestimmt ein Blick auf die Enterprise-Version, mit der die Installation vollautomatisch auf Klick funktioniert und für die man auch offiziellen Support bekommt.

Warum scheuen dennoch viele Administratoren den Weg in die Vollautomatisierung? Bei einigen herrscht wohl noch die altbekannte Angst vor dem Überflüssigwerden des Administrators vor. Dies lässt sich in der Welt der proprietären Betriebssysteme und Software (aber nicht nur dort) sehr häufig beobachten, wo selbst einfachste, repetierbare Aufgaben teilweise Stunden benötigen. Mein Argument gegen diese Angst ist, dass wir unseren Job nicht machen, um langweilige, wiederholende und im Prinzip immergleiche Arbeiten zu machen. Dazu kann man auch Roboter (sprich: Puppet) nehmen! Als Systemadministrator / Entwickler etc. hat man genug zu tun, kreative und nachhaltige Lösungen für nicht-alltägliche Probleme zu finden. Diese Arbeit ist essentiell das, was uns  implizit motiviert! Typische Situation: Die ersten 10 Apache-Installationen macht man noch gerne, weil man lernt und das Ergebnis sehen kann. Danach merkt man schnell, dass es immer dasselbe ist. Warum also nicht automatisieren? Jeder Systemadministrator den ich kenne, hat eine Liste mit 100+ interessanteren Problemen und Ideen, welche ihrer Firma einen echten Mehrwert bieten würden, wenn man denn neben den alltäglichen Aufgaben Zeit für sie fände. Deshalb ist Automatisierung keine Bedrohung sondern eine Befreiung! Sobald man mit vielen Servern zu tun hat, muss man sich ohnehin überlegen, wie man diese effizient und nachvollziehbar gleich aufsetzen und administrieren will, daher ist in grösseren Firmen diese Form der Automatisierung schon eher ein Sachzwang, will man motivierte und kreative anstatt genervte Administatoren.

Im Gegensatz zu cfengine besteht derzeit leider noch keine offizielle Windows-Unterstützung. Es sind jedoch Entwicklungen im Gange, dass bald die wichtigsten Ressourcen durch einen Windows-Agent realisiert werden können.

In diesem Sinne gelte das alte Administratoren-Credo: Wenn eine Arbeit automatisch erledigt werden kann, soll man keinen Menschen damit belästigen. Denn Menschen haben Interessanteres zu tun.

[1] http://cfengine.com/
[2] http://projects.puppetlabs.com/projects/puppet/wiki/Whos_Using_Puppet
[3] http://forge.puppetlabs.com/
[4] http://puppetlabs.com/puppet/puppet-enterprise/
[4] http://projects.puppetlabs.com/projects/puppet/wiki/Puppet_Windows

Die Schonzeit ist vorbei: Tatort Kommunikation und Erwartungen 1

Posted by Chris on August 17, 2011

No Gravatar

Nachdem die Vorzeichen es schon erahnen liessen, bestätigten die meisten Kritiken dann auch die Befürchtungen: Der erste Schweizer Tatort seit 9 Jahren ist Müll. Ich möchte gar nicht auf die Details eingehen (Verschiebung wegen schlechter Qualität / zu vielen Klischees, Gastschauspielerin mit Silikonhügeln ist bei Scientology und motzt hintenrum über die Dauer des Drehs usw.) Viel interessanter ist doch die Beantwortung der Frage, die man sich stellte, als man vor dem Fernseher dieses Trauerspiel mitansah: Wie kommt sowas überhaupt auf den Schirm? Gibt es keine Testvorführungen oder Qualitätskontrollen? Wenn man sich die Interviews mit den Beteiligten und die Artikel so anschaut, läuft es auf die übliche Problematik hinaus: Nicht kommunizierte Erwartungen. Was heute in jedem Projekt als Grundwissen vorhanden ist, fehlte: Stelle am Anfang klar, was der Auftraggeber wünscht und kommuniziere auch im Laufe des Projekts immer weiter mit ihm, um nötige Anpassungen rechtzeitig machen zu können.

Offenbar erwartete der Auftraggeber (ARD und co.), dass Schweizer _nicht_ sauber Hochdeutsch sprechen sollen. Die meisten Schauspieler kommen aus dem Theaterbereich und sind es sich gewöhnt, einen Goethe in klarsten Hochdeutsch zu präsentieren. Sie nach dem Dreh zu zwingen, die Synchronisation von Hochdeutsch auf unser “dümmliches Gekrächze” (Zitat eines deutschen Kommentators im Tagesanzeiger) umzustellen, tat bestimmt weh, und das merkt man auch. Man realisiert es nicht direkt, aber der ganze Film kam dadurch noch viel behäbiger und schwerfälliger rüber.

Dem gegenüber standen ebenfalls nicht kommunizierte Erwartungen der Macher und des Regisseurs, wie auch der Silikonzicke Schauspielerin Sofia Milos, die monierte, dass eine CSI-Folge in 9 Tagen gedreht sei, während der Tatort 5 Wochen in Anspruch genommen hätte (da darf sich jetzt jeder das Seinige dazu denken).

Knackig...irgendwie...

Einige Schweizer waren (siehe Leserkommentare im Tagi) etwas erschrocken, dass unser Land in letzter Zeit nicht mehr mit den sonst üblichen Samthandschuhen angefasst wird von  ausländischen Medien, wähnen sich gar als Opfer einer weltweiten Verschwörung. Ich denke mal, daran sollten wir uns langsam gewöhnen, denn nach den letzten 10 Jahren ist für uns die Schonfrist definitiv abgelaufen. Ich befürchte fast, dass man (um am Schluss noch wirschaftspolitisch zu werden) eine Parallele zur Schweizer Wirtschaft ziehen kann: Angestachelt von riesigen Bankgewinnen und gutem Image überschätzen wir uns und unsere Fähigkeiten in letzter Zeit zu häufig, dasselbe scheint auch den Filmemachern passiert zu sein. Das Ausland blieb indes nicht stehen, sondern hat heute ebenfalls höchste Qualitätsansprüche.

Was lernen wir daraus? Eigentlich nichts, ausser, dass man vor allem am Anfang von Projekten immer gut mit dem Auftraggeber kommunizieren sollten, um dessen Ansprüche und Erwartungen wirklich zu verstehen. Ansonsten ist später Ärger auf beiden Seiten vorprogrammiert.

[1] http://www.tagesanzeiger.ch/kultur/fernsehen/Deutsche-Presse-verreisst-Schweizer-Tatort/story/20270242 
[2] http://www.tagesanzeiger.ch/kultur/fernsehen/TVKritik-Botox-und-Berge/story/15718206

Apropos Vermögenssteuer: Von der Gier nach weniger… 1

Posted by Chris on August 10, 2011

No Gravatar

Ein paar Zahlen:

71000 = 0

150000 = 9

200000 = 67

Bedeutet: Bis zu einem Vermögen von 71’000 Franken zahlt man im Kanton Zürich gar nix. Bei einem Vermögen von 200’000 Franken muss man im Kanton Zürich eine Vermögenssteuer von 67 Franken bezahlen. Punkt. Und das ist der FDP und der SVP immer noch zuviel. Jeder kann sich seine eigenen Schlüsse daraus ziehen. Als ich vor einigen Jahren ein anständiges Sümmchen zusammengespart hatte (bevor ich es mit Aktien vernichtete), erschrak ich effektiv, wie wenig ich dafür zahlen musste (ein paar Franken höchstens). Wer also richtig reich ist und kein Einkommen versteuern muss (denn da wird’s bereits für die Mittelschicht so richtig teuer), der hat in der Schweiz ein Paradies gefunden. Wen wundert es bei dieser unverminderten, höhnischen Gier der Begüterten, dass die Chancenlosen es ihnen gleichtun (siehe London), einfach mit den ihnen gegebenen Mitteln? Mal ganz ehrlich, wer findet diese Gier nicht seit langem abstossend? Vielleicht noch diejenigen, die mit dem Motto “Tiefere Steuern helfen allen” eine Lüge durch vielfache Wiederholung zur Wahrheit werden lassen wollen? Man bedenke: Die Vermögenssteuern machen in unserem Land nicht einmal 1% des Bruttoinlandproduktes (BIP) aus. Wie soll dieses eine Prozent halbiert unsere Wirtschaft ankurbeln? Rein mathematisch gesehen merkt ein Zweitklässler schon, dass dies Unsinn ist.

[1] http://www.estv.admin.ch/dokumentation/00079/00080/00736/index.html?lang=de&download=NHzLpZeg7t,lnp6I0NTU042l2Z6ln1acy4Zn4Z2qZpnO2Yuq2Z6gpJCDdYR5f2ym162epYbg2c_JjKbNoKSn6A–
[2] http://www.svp-zuerich.ch/nt/download/zb/bote090220.pdf
[3] http://de.wikipedia.org/wiki/Verm%C3%B6gensteuer
[4] http://www1.arbeiterkammer.at/taschenbuch/tbi2011/einkommens-_und_vermoegenssteuern_in_-_des_bip.html