Irgendwie beschreibt das meine Haltung zu Fußball im Fernsehen im Moment, auch wenn es schon 13 Jehre alt ist:

Vor kurzem habe ich mich mal auf den Seiten der Freiburger Kreisverbände der bekannten Parteien umgeschaut. Bei der CDU habe ich mir die aktuelle Ausgabe der Union Intern durchgelesen.

Es gibt einen langen Standpunkt, in dem gegen die Versuche der CDU “die linksgrünen Parteien […] nachzuahmen” gewettert wird. Dieser Standpunkt verdient eine eigene Replik, aber nicht hier und jetzt.

Was ist mir sonst aufgefallen?

Auf Seite 12 steht:

Auf Seite 9 fordert der Kreisvorsitzende infolge der Maskenaffäre:

Und was sieht man, wenn man weiter blättert? Folgende Anzeige:

Hier werden Grundstücke in Kanada beworben. Ein angepriesener Vorteil lautet dabei:

auch als Firmensitz sind sie interessant aufgrund von Steuervorteilen.

Das Ortsblatt fordert also die Abschaffung von Steuerschlupflöchern und die moralische Reinigung der Partei. Und im gleichen Haft werden Anzeigen für Steuerschlupflöcher veröffentlicht. Wie passt das zusammen?

Meine mail an den Kreisverband blieb leider zwei Wochen ohne Antwort, so dass ich das jetzt ohne eine Stellungnahme des Kreisverbandes veröffentliche.

Ich hab mich mal an einer Aufgabe bei Leetcode versucht. Die Aufgabe lautet:

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Natürlich habe ich mich gleich an einer Aufgabe aus der Kategorie Hard versucht.

Hier gibt es natürlich mehrere Lösungsmöglichkeiten, die unterschiedlich komplex sind, aber auch unterschiedliche Laufzeitverhalten zeigen.

Kombination beider Arrays

Die einfachste Lösung ist natürlich, beide Arrays in einen neuen Array zu kopieren, diesen neuen Array sortieren zu lassen und dann den Median zu berechnen.

public static double findMedianSortedArraysSimple(int[] nums1, int[] nums2) {
	int[] combined = new int[nums1.length + nums2.length];
	if (nums1.length > 0)
		for (int i = 0; i < nums1.length; i++)
			combined[i] = nums1[i];
	if (nums2.length > 0)
		for (int i = 0; i < nums2.length; i++)
			combined[nums1.length + i] = nums2[i];
	Arrays.sort(combined);

	if (combined.length == 0) {
		return 0.0;
	} else if (combined.length % 2 == 0) {
		return 0.5 * (combined[combined.length / 2 - 1] + combined[combined.length / 2]);
	} else {
		return combined[combined.length / 2];
	}
}

Eine sehr einfache Lösung. Da aber der ganze Array sortiert wird, ist das die asymptotische Laufzeit proportional zu n*log(n) sein wird. Zudem benötigt man den doppelten Speicher, da man ja eine Kopie der Eingangswerte ablegen muss.

Lineare Suche

Eine bessere Variante ist es, mit zwei Indizes über beide Arrays zu iterieren, wobei jeweils der Index inkrementiert wird, dessen zugehöriger Wert geringer ist. Dies wird fortgeführt, bis die Hälfte der Einträge erreicht ist. Der Median lässt sich dann aus dem letzten Wert oder den letzten beiden Werten berechnen.

public static double findMedianSortedArraysLinear(int[] nums1, int[] nums2) {
	if (nums1.length == 0 && nums2.length == 0)
		return 0.0;

	int lengthOfBothArrays = nums1.length + nums2.length;
	int index1 = 0;
	int index2 = 0;
	int previous = 0;
	int current = 0;
	while (index1 + index2 <= lengthOfBothArrays / 2) {
		previous = current;
		
		if (index1 >= nums1.length) {
			current = nums2[index2];
			index2++;
			continue;
		}
		if (index2 >= nums2.length) {
			current = nums1[index1];
			index1++;
			continue;
		}
		if (nums1[index1] < nums2[index2]) {
			current = nums1[index1];
			index1++;
		} else {
			current = nums2[index2];
			index2++;
		}
	}
	if (lengthOfBothArrays % 2 == 0) {
		return 0.5 * (previous + current);
	} else {
		return current;
	}
}

Diese Vorgehensweise hat den Vorteil, dass keine Kopie der Eingangswerte angefertigt werden muss. Die asymptotische Laufzeit wird proportional zu n sein, also eine Verbesserung im Vergleich zum obigen Ansatz, aber noch nicht wie in der Aufgabe gefordert.

Binäre Suche

Meine beste Lösung ist eine Binäre Suche. Hier wird gesucht, wieviele der Elemente aus dem ersten Array unterhalb des Medians liegen. Die Anzahl der Elemente des zweiten Arrays, die unterhalb des Medians liegen, lässt sich damit berechnen. Das Kriterium ist, dass die jeweils größten berücksichtigten Werte beider Arrays jeweils kleiner sein müssen als die ersten nicht-berücksichtigten Werte des anderen Arrays.

public static int[] getCompositionOfLowerHalfBinary(int[] nums1, int[] nums2) {
	int requiredNumberForHalf = (nums1.length + nums2.length) / 2;

	int nEntriesToTakeMin = 0;
	int nEntriesToTakeMax = Math.min(nums1.length, requiredNumberForHalf);

	while (nEntriesToTakeMin < nEntriesToTakeMax) {
		int nEntriesToTakeFromFirst = (nEntriesToTakeMin + nEntriesToTakeMax) / 2;
		int nEntriesToTakeFromSecond = requiredNumberForHalf - nEntriesToTakeFromFirst;

		if (nEntriesToTakeFromSecond > nums2.length) {
			// increase number of entries taken from first array
			nEntriesToTakeMin = nEntriesToTakeFromFirst + 1;
			continue;
		}
		// check that this composition is correct. That means that the last chosen
		// elements are lower than
		// the first non-chosen one from the other array
		if (nEntriesToTakeFromFirst > 0 && nEntriesToTakeFromSecond < nums2.length) {
			if (nums1[nEntriesToTakeFromFirst - 1] > nums2[nEntriesToTakeFromSecond]) {
				nEntriesToTakeMax = nEntriesToTakeFromFirst - 1;
				continue;
			}
		}
		if (nEntriesToTakeFromSecond > 0 && nEntriesToTakeFromFirst < nums1.length) {
			if (nums2[nEntriesToTakeFromSecond - 1] > nums1[nEntriesToTakeFromFirst]) {
				nEntriesToTakeMin = nEntriesToTakeFromFirst + 1;
				continue;
			}
		}

		// already found the solution, no need to search further
		nEntriesToTakeMin = nEntriesToTakeFromFirst;
		break;
	}
	return new int[] { nEntriesToTakeMin, requiredNumberForHalf - nEntriesToTakeMin };
}

Mit dieser Information kann dann der Median berechnet werden. Er ergibt sich entweder als der kleinste nicht-berücksichtigte Wert oder als Mittelwert aus dem größten berücksichtigten Wert und dem kleinsten nicht-berücksichtigten Wert

public static double findMedianSortedArraysComp(int[] nums1, int[] nums2) {
	int[] composition = getCompositionOfLowerHalfBinary(nums1, nums2);
	int lengthOfBothArrays = nums1.length + nums2.length;

	if (lengthOfBothArrays == 0) {
		return 0.0;
	} else if (lengthOfBothArrays % 2 == 0) {
		// even number of elements -> return average of highest from the lower half and
		// the lowest from the higher half
		return 0.5 * (getHighestFromLowerHalf(nums1, nums2, composition)
				+ getLowestFromHigherHalf(nums1, nums2, composition));
	} else {
		// odd number -> return the lowest from the higher half
		return getLowestFromHigherHalf(nums1, nums2, composition);
	}
}

Die Berechnung dieser Werte ist relativ simpel:

private static int getHighestFromLowerHalf(int[] nums1, int[] nums2, int[] composition) {
	if (composition[0] == 0)
		return nums2[composition[1] - 1];
	if (composition[1] == 0)
		return nums1[composition[0] - 1];
	return Math.max(nums1[composition[0] - 1], nums2[composition[1] - 1]);
}

private static int getLowestFromHigherHalf(int[] nums1, int[] nums2, int[] composition) {
	if (composition[0] == nums1.length)
		return nums2[composition[1]];
	if (composition[1] == nums2.length)
		return nums1[composition[0]];
	return Math.min(nums1[composition[0]], nums2[composition[1]]);
}

Test

Ich habe die verschiedenen Ansätze gegeneinander getestet, um sicherzustellen, dass alle die gleichen Ergebnisse liefern. Die Testroutine sah wie folgt aus:

public static int[] getRandomSortedArray(int maxLength) {
	int[] nums = new int[(int) Math.floor(Math.random() * maxLength)];
	if (nums.length > 0) {
		nums[0] = (int) Math.floor(Math.random() * 10);
	}
	if (nums.length > 1) {
		for (int i = 1; i < nums.length; i++) {
			nums[i] = nums[i - 1] + (int) Math.floor(Math.random() * 10);
		}
	}
	return nums;
}

public static void test() {
	int[] nums1 = null;
	int[] nums2 = null;
	double medianSimple = 0.0;
	double medianLinear = 0.0;
	double medianComp = 0.0;
	do {
		nums1 = getRandomSortedArray(10);
		nums2 = getRandomSortedArray(10);

		System.out.print("nums1 (" + nums1.length + ") ");
		for (int i = 0; i < nums1.length; i++)
			System.out.print(" " + nums1[i]);
		System.out.println();
		System.out.print("nums2 (" + nums2.length + ") ");
		for (int i = 0; i < nums2.length; i++)
			System.out.print(" " + nums2[i]);
		System.out.println();

		medianSimple = findMedianSortedArraysSimple(nums1, nums2);
		medianLinear = findMedianSortedArraysLinear(nums1, nums2);
		medianComp = findMedianSortedArraysComp(nums1, nums2);
		System.out.println("medians: " + medianSimple + " " + medianLinear + " " + medianComp);
		System.out.println();
	} while (Math.abs(medianLinear - medianComp) < 0.1 && Math.abs(medianSimple - medianLinear) < 0.1);
}

Also eine Funktion, die zufällige, aber sortierte Arrays variabler Länge generiert, und eine Endlosschleife, die nach Fällen sucht, in denen die verschiedenen Funktionen unterschiedliche Ergebnisse zurückgeben.

Laufzeit

Und ich habe auch das Laufzeitverhalten gemessen, wenn auch auf sehr einfache Weise. Ich habe jeweils eine Million mal den Median eines Paares von Arrays berechnet. Die Länge der Arrays war dabei zufällig zwischen 0 und einem vorgegebenen Maximalwert.

public static void profile() {
	final int nTests = 1_000_000;
	final int[] nEntriesMax = new int[] { 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000 };

	int[][] nums = new int[nTests + 1][];

	long durations[] = new long[3];

	for (int nEntries = 0; nEntries < nEntriesMax.length; nEntries++) {
		for (int nTest = 0; nTest <= nTests; nTest++) {
			nums[nTest] = getRandomSortedArray(nEntriesMax[nEntries]);
		}

		long start = System.currentTimeMillis();
		for (int nTest = 0; nTest < nTests; nTest++) {
			findMedianSortedArraysSimple(nums[nTest], nums[nTest + 1]);
		}
		durations[0] = System.currentTimeMillis() - start;

		start = System.currentTimeMillis();
		for (int nTest = 0; nTest < nTests; nTest++) {
			findMedianSortedArraysLinear(nums[nTest], nums[nTest + 1]);
		}
		durations[1] = System.currentTimeMillis() - start;

		start = System.currentTimeMillis();
		for (int nTest = 0; nTest < nTests; nTest++) {
			findMedianSortedArraysComp(nums[nTest], nums[nTest + 1]);
		}
		durations[2] = System.currentTimeMillis() - start;

		System.out.println(nEntriesMax[nEntries] + "\t" + durations[0] + "\t" + durations[1] + "\t" + durations[2]);
	}
}

Die folgende Tabelle zeigt die benötigten Millisekunden für eine Million Aufrufe.

max. Länge	Kombination	Linear	Binär
1	23	11	9
2	32	41	25
5	62	19	34
10	96	32	22
20	225	56	29
50	746	121	38
100	1598	232	55
200	2204	450	89
500	3224	1106	172
1000	5318	2167	209
2000	10314	4443	266
5000	24966	10946	394

Wie man sieht ist die binäre Suche am schnellsten und steigt auch am wenigsten für längere Arrays an. An der linearen Suche sieht man gut, wie die Laufzeit linear mit der maximalen Länge steigt. Es überrascht mich, dass die Laufzeit für die Kombination nicht stärker ansteigt, vielleicht hat Java hier schon Optimierungen für die Sortierung teilweise sortierter Arrays eingebaut.

Natürlich gibt es auch die komplette und kommentierte Java-Datei zum Download.

Ein Buch, das ich in der Bibliothek gefunden hab. Ich hab gerade gesehen, dass das Buch neu 80€ kostet, also soviel wie fünf Jahre Mitgliedschaft in der Stadtbibliothek Freiburg. Also wieder viel Geld gespart.

Bei einem Buch mit solch einem Preis bin ich allerdings erstaunt, wieviele Tippfehler und Ungenauigkeiten bei den Diagrammen es ins Buch geschafft haben. Aber es ist wohl ein Nischenbuch.

Was ich aus dem Buch gelernt hab:

• Der Ausbau des Stromnetzes ist ebenso wichtig wie der Ausbau der regenerativen Energien.

• Energieversorgung wird dezentraler werden.

• Thermische Kraftwerke beziehungsweise deren Generatoren erfüllen einen Zweck für die Frequenzstabilität des Netzes, man benötigt sie auch in Zukunft.

• Bei Windkraftanlagen macht es zum Beispiel Sinn, einen Rotor mit einem Generator zu kombinieren, dessen maximale Leistung geringer ist als die maximale Leistung des Rotors. Die Leistungseinbuße kommt nur selten vor, und zwar dann, wenn es viel Wind und Windenergie gibt, die Strompreise also gering sind. Dadurch ist der Nachteil der geringeren Generatorleistung nur gering. Der Vorteil ist aber, dass der Generator im Durchschnitt mit einem höheren Anteil seiner eigenen Leistung läuft, also Leistung mit weniger Variabilität erzeugt. Und sämtliche Versorgungslinien müssen auch nur auf die geringere Maximalleistung ausgelegt werden.

• In Zukunft wird es sinnvoll sein, Solaranlagen an Privathäusern mit Batterien oder anderen Speichern zu kombinieren, so dass sie möglichst wenig Leistung ins Netz zurückspeisen. Ähnlich wie bei Windkraftanlagen werden sie ja zumeist dann Leistung ins Netz speisen, wenn Leistung im Überfluss vorhanden und deshalb relativ wertlos ist. Ein Speicher könnte dann die Energie für den Abend speichern. Derartig ausgerüstete Häuser wären für das Netz lediglich Consumer mit saisonal geringerem Bedarf, was den Ausbau des Netzes vereinfachen würde.

  Ein erstaunlich interessantes Gebiet, das Buch vermittelt die Grundlagen, wenn auch mit einigen nervigen Fehlern.

Dieses Buch habe ich spontan in einer Buchhandlung gekauft. Es behandelt laut seines Umschlags die kleinen und großen Fragen, mit denen Mathematik, Physik und Philosophie sich immer wieder beschäftigen. Das Inhaltsverzeichnis versprach auch eine Menge an interessanten Artikeln. Also genau ein Buch für mich.

Ich habe angefangen, die Kapitel des Buches der Reihe nach zu lesen. Und meine Erwartungen wurden nicht erfüllt. Es ist alles angenehm zu lesen, aber weder in die Tiefe gehend, noch immer fachlich korrekt. Dazu ein paar Beispiele:

Im Artikel über die Zeit schreibt Holt (S. 33)

Wie Einstein gezeigt hatte, gibt es kein universelles Jetzt. Ob zwei Ereignisse gleichzeitig ablaufen, ist relativ und hängt vom Beobachter ab. Und sobald die Gleichzeitigkeit über Bord geht, verliert die Einteilung von Momenten in vergangen, gegenwärtig und zukünftig jede Bedeutung.

Sehr schön zu lesen, nur leider großer Unsinn. Es stimmt, dass nach Einsteins Relativitätstheorien der Begriff der Gleichzeitigkeit seine Bedeutung ändert. Es stimmt aber überhaupt nicht, dass vergangen, gegenwärtig und zukünftig jede Bedeutung verlieren. Von einem Punkt in der Raumzeit ausgehend gibt es die beiden sogenannten Lichtkegel, den Rückwärts-Lichtkegel und den Vorwärts-Lichtkegel. Der Vorwärts-Lichtkegel dieses Punktes beinhaltet alle Ereignisse, die von dem Punkt aus mit Geschwindigkeiten bis zu Lichtgeschwindigkeit erreichbar sind, also alles, was kausal beeinflussbar ist. Entsprechend beinhaltet der Rückwärts-Lichtkegel alles, was den Punkt beeinflusst haben könnte. Alles was sich innerhalb des Rückwärts-Lichtkegel befindet, ist vergangen und alles, was sich innerhalb des Vorwärts-Lichtkegels befindet ist zukünftig für diesen Punkt der Raumzeit. Und diese Einteilung ist auch nicht veränderlich. Lediglich für Punkte außerhalb beider Kegel ist nicht vorgegeben, ob sie zukünftig, gleichzeitig oder vergangen sind, für sie lassen sich Beschreibungsweisen finden, wo das Verhältnis der Punkte beliebig ist. Korrekt müsste man gegenwärtig durch raumartig ersetzen und vergangen und zukünftig auf das Innere der Lichtkegel beschränken. Aber da ist es dann einfacher und effektheischender zu schreiben, dass die Einteilung jede Bedeutung verliert.

Im Kapitel über die Bedeutung der Zahlen im Jahre 1 Million, auf Seite 65, findet sich folgender Abschnitt:

Und Zahlen werden die Aura des Transzendenten verloren haben und als lokale Artefakte angesehen werden, wie das Operationssystem eines Computers oder ein Buchhaltungssystem. Wenn ich recht habe, dann sollten SETI-Forscher nicht nach Primzahlen oder den Nachkommastellen von p Ausschau halten, sondern nach etwas ganz anderem.

Die Übersetzung von operating system als Operationssystem wirft natürlich kein gutes Licht auf die Übersetzung. Woher die Suche nach Nachkommastellen von p kommt, hier kann sicherlich nur π gemeint sein, erschließt sich mir nicht. Jeder Übersetzer, der sich ein bisschen mit Mathematik auskennt, sollte aber erkennen, dass es keine Zahl p gibt, nach deren Nachkommastellen man in außerirdischen Signalen suchen könnte.

Am Ende des Kapitels über reine und unreine Mathematik beschreibt Holt den Kurzfilm des Mathematikers Edward Frenkel, in dem ein Mathematiker seiner Geliebten eine Liebesformel auf den Bauch tätowiert. Und die Formel wird nicht gezeigt, es wird nur über sie gesagt:

Sie ist wunderbar, aber furchteinflößend. Die einzigen Zahlen darin sind 0, 1 und 8. Ist Liebe nicht genauso?

Im Screenshot der Formal auf der Webseite zum Film erkenne ich keine 0 und keine 8. Aber warum wurde die Formel nicht im Buch zumindest abgedruckt? War die Angst, dass eine Formel im Buch die Absatzzahlen verringern könnte so stark?

Wer die Formel und den Film sehen möchte, findet sie auf der Homepage von Edward Frenkel

Ich bin dann im Buch etwas weiter nach hinten gesprungen, weil ich ein paar der Kürzeren Essays lesen wollte. Im Essay über das Ziegenproblem wird der Verlauf des Spiels wie folgt beschrieben (S. 398):

Angenommen, Sie wählen Tür A. Statt Ihnen zu zeigen, was sich dahinter befindet, öffnet der Moderator Monty Hall verschlagen Tür B und offenbart … eine Ziege. Dann bietet er Ihnen die Möglichkeit, sich für Tür C umzuentscheiden. Sollten Sie das tun?

Der entscheidende Punkt des Ziegenproblems wird hier vollkommen ignoriert. Dieser entscheidende Punkt ist, dass der Moderator die Tür, hinter der sich der Preis befindet, kennt und die Tür, die er öffnet, in Abhängigkeit dieses Wissens auswählt. Dieser Punkt ist entscheidend für die Interpretation dieses Spiels, wird aber hier im Buch überhaupt nicht erwähnt.

Damit habe ich das Buch nach ca. 150 von 500 Seiten abgelegt. Wenn nicht einmal das Ziegenproblem schlüssig dargestellt wird, kann ich dem Buch nicht weiter vertrauen. Alles in Allem kann ich das Buch niemandem empfehlen, es ist eines der Bücher, die ich absichtlich nicht zu Ende lese. Und das kommt selten vor. Ein paar Anekdoten aus der Wissenschaft der letzten Jahrzehnte, und sonst viel nett anzuhörendes, aber oft falsches, Geschwurbel.