Veröffentlicht am 30.06.2021
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.
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.
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.
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]]);
}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.
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.
Veröffentlicht am 30.07.2020
In der achten Folge der sechsten Staffel von Taskmaster wird ein Spiel gespielt, das erstaunlich schwierig ist, dafür, dass es so simpel ist. Der Spielleiter sagt die Namen von drei Körperteilen und die Spielenden müssen dann ein Post-It möglichst schnell auf das Körperteil kleben, dass alphabetisch in der Mitte steht. Das Video und ein kleines Programm, dass Listen von Triplets von Körperteilen ausgibt, gibt’s unten.
Ich habe ein kleines Programm geschrieben. Es ist nicht sehr hochentwickelt, es werden einfach drei Körperteile aus der List zufällig gewählt, was bedeutet, dass Körperteile in der Mitte der alphabetischen Sortierung häufiger die Lösung sind, es wird auch nicht geprüft, ob Körperteile überlappen.
package de.sebastiantschmidt.armmouthzygote;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;
public class Main {
private static int nRounds = 100;
public static void main(String[] args) {
List<String> bodyparts = getEnglishBodyParts();
System.out.println(bodyparts.size() + " entries, " + bodyparts.stream().distinct().count() + " distinct entries");
for(int round = 0; round < nRounds; round++) {
Collections.shuffle(bodyparts);
String middle = getMiddleEntry(bodyparts.get(0), bodyparts.get(1), bodyparts.get(2));
System.out.println(String.format("%3d", round+1)
+ String.format("%-16s", (bodyparts.get(0).equals(middle) ? ">" + bodyparts.get(0) + "<" : " " + bodyparts.get(0) + " "))
+ String.format("%-16s", (bodyparts.get(1).equals(middle) ? ">" + bodyparts.get(1) + "<" : " " + bodyparts.get(1) + " "))
+ String.format("%-16s", (bodyparts.get(2).equals(middle) ? ">" + bodyparts.get(2) + "<" : " " + bodyparts.get(2) + " ")) );
}
}
private static String getMiddleEntry(String string1, String string2, String string3) {
return Stream.of(string1, string2, string3).sorted().skip(1).findFirst().orElseThrow();
}
private static List<String> getEnglishBodyParts() {
ArrayList<String> bodyparts = new ArrayList<String>();
bodyparts.add("arm");
bodyparts.add("mouth");
bodyparts.add("knee");
bodyparts.add("knee cap");
bodyparts.add("eye");
bodyparts.add("foot");
bodyparts.add("leg");
bodyparts.add("fingernails");
bodyparts.add("hand");
bodyparts.add("stomach");
bodyparts.add("toes");
bodyparts.add("shoulders");
bodyparts.add("tongue");
bodyparts.add("nose");
bodyparts.add("hair");
bodyparts.add("thumb");
bodyparts.add("index finger");
bodyparts.add("middle finger");
bodyparts.add("ring finger");
bodyparts.add("lips");
bodyparts.add("head");
bodyparts.add("ear");
bodyparts.add("eyebrow");
bodyparts.add("forearm");
bodyparts.add("elbow");
bodyparts.add("heel");
bodyparts.add("calf");
bodyparts.add("neck");
bodyparts.add("palm");
bodyparts.add("wrist");
bodyparts.add("chin");
bodyparts.add("ankle");
bodyparts.add("shin");
bodyparts.add("armpit");
bodyparts.add("biceps");
bodyparts.add("spine");
bodyparts.add("sternum");
bodyparts.add("forehead");
bodyparts.add("toenail");
bodyparts.add("belly button");
bodyparts.add("thigh");
bodyparts.add("umbilicus");
bodyparts.add("navel");
bodyparts.add("pinky finger");
bodyparts.add("pinky toe");
bodyparts.add("sole");
bodyparts.add("abdomen");
return bodyparts;
}
}Eine Beispielhafte Ausgabe von 100 Runden wäre dann
1 knee sternum >shin<
2 toes >nose< forearm
3>leg< tongue forehead
4 foot >palm< shin
5>hair< toes arm
6>sternum< palm toes
7>forehead< palm eye
8 umbilicus >shin< ankle
9>elbow< hand abdomen
10 toes heel >nose<
11>heel< thigh calf
12 hand middle finger >index finger<
13>tongue< umbilicus mouth
14 umbilicus armpit >ear<
15 neck wrist >tongue<
16 foot wrist >nose<
17 thumb >palm< knee
18 middle finger >ear< armpit
19>heel< toes eye
20 toenail >pinky finger< hand
21 knee cap eyebrow >index finger<
22 knee cap >knee< eye
23 toenail navel >sole<
24 abdomen >eye< shin
25 index finger arm >hair<
26 wrist >shoulders< biceps
27 toenail >shin< forehead
28 sole >middle finger< heel
29 eyebrow shoulders >pinky toe<
30>leg< ear lips
31 tongue hand >pinky finger<
32 fingernails shoulders >hair<
33>elbow< arm heel
34 forehead tongue >toenail<
35>shoulders< belly button sternum
36 umbilicus >index finger< eyebrow
37 nose >head< armpit
38 tongue eye >forehead<
39 eye nose >forehead<
40 ankle umbilicus >neck<
41>mouth< umbilicus eye
42 forehead umbilicus >shin<
43 arm >eye< eyebrow
44>heel< hand shin
45 eyebrow >hair< pinky toe
46 toes >foot< biceps
47 neck biceps >heel<
48 middle finger stomach >navel<
49 lips >hand< elbow
50 fingernails thumb >stomach<
51 ankle >shin< thigh
52>toes< tongue knee
53>knee cap< eyebrow palm
54 arm >middle finger< pinky finger
55>foot< mouth biceps
56 navel elbow >fingernails<
57 palm >ring finger< stomach
58 chin >head< index finger
59>shoulders< sternum elbow
60>ear< pinky toe biceps
61 calf >spine< stomach
62>head< index finger chin
63 leg >index finger< hair
64 tongue >spine< elbow
65>sole< stomach middle finger
66 thigh >palm< knee
67 mouth >forehead< abdomen
68>biceps< abdomen forehead
69 wrist belly button >palm<
70>knee< heel knee cap
71 toenail forehead >nose<
72>ring finger< thumb index finger
73>navel< ankle spine
74>navel< wrist calf
75>middle finger< wrist index finger
76>shoulders< umbilicus heel
77 biceps >knee< navel
78>sole< toenail pinky finger
79 tongue >toes< shin
80 spine ear >knee<
81 toenail >lips< forehead
82 shin toenail >thumb<
83 ankle >elbow< heel
84 tongue fingernails >thigh<
85>lips< leg sole
86>eye< knee elbow
87 middle finger >belly button< arm
88 knee cap wrist >stomach<
89 wrist >toenail< knee cap
90>heel< belly button tongue
91 umbilicus >spine< knee cap
92>navel< stomach elbow
93>ear< umbilicus arm
94 pinky finger >head< elbow
95>forearm< biceps nose
96 calf >spine< umbilicus
97 thumb abdomen >neck<
98 head >leg< umbilicus
99 toenail >pinky toe< forearm
100 elbow thigh >mouth< Zygote ist übrigens eine Zelle, die bei der Vereinigung einer Eizelle und eines Spermiums entsteht. Zum Glück so weit hinten im Alphabet, dass sie nie die Lösung ist.
Veröffentlicht am 13.06.2017
Tom Scott erklärt, warum man in seinem Programm niemals so etwas wie Zeitzonen implementieren sollte. Tom Scott hat auch einen sehr empfehlenswerten Kanal mit vielen Videos zu Programmieren, Linguistik und anderen Themen.
(Update 2020-07-11:) Eine weitere Liste mit Problemen, die auftauchen, wenn man Zeit und Zeitzonen in seinem Programm implementiert: Falsehoods programmers believe about time