Sebastian Schmidts Blog

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.

Einstellung per Zufallsprinzip

Watch the Football

Union Intern Ausgabe 2 - 2021

Median zweier sortierter Arrays

Kombination beider Arrays

Lineare Suche

Binäre Suche

Test

Laufzeit

Energiesysteme: regenerativ und dezentral