MINT lernen

Abituraufgaben: Speicherbedarf abschätzen

Zwei Aufgaben im Abiturformat — von Temperaturtabellen einer Wetterstation bis zur Suche nach doppelten Einträgen.

Dein Fortschritt:
0 / 0 Aufgaben
1

Wetterstation

14 BEAFB I–II

Eine Wetterstation misst stündlich die Temperatur in °C. Die Werte der letzten zehn Jahre (3650 Tage) liegen in double[][] w = new double[3650][24]; — Zeile = Tag, Spalte = Stunde. Rechnen Sie mit 8 Byte je double, 8 Byte je Referenz und 16 Byte Kopf je Reihung; 1 MB = \(10^6\) Byte.

  1. Berechnen Sie den Speicherbedarf der Tabelle — getrennt nach Nutzdaten und Verwaltung (Köpfe und Referenzen). (3 BE)
  2. Erläutern Sie, warum die gleichen Daten als double[24][3650] (Zeile = Stunde, Spalte = Tag) weniger Speicher belegen. (3 BE)
  3. Implementieren Sie eine Methode static double[] tagesmittel(double[][] w), die für jeden Tag den Mittelwert der Stundenwerte zurückgibt. Geben Sie den Zusatzspeicher der Methode in Abhängigkeit von der Zahl der Tage \(t\) an. (4 BE)
  4. Beurteilen Sie den Plan, die minütlichen Messwerte von 100 Stationen über 30 Jahre gemeinsam als double-Werte im Arbeitsspeicher eines Rechners mit 16 GB auszuwerten. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Die Tabelle besteht aus 3650 Zeilenreihungen und einer äußeren Reihung mit 3650 Referenzen.
Hinweis zu Aufgabe b)
Die Nutzdaten bleiben gleich — was ändert sich an der Zahl der Zeilen?
Hinweis zu Aufgabe c)
Eine neue Reihung mit einem Platz je Tag; darin für jede Zeile Summe durch Anzahl.
Hinweis zu Aufgabe d)
Rechnen Sie die Zahl der Werte aus: Stationen · Jahre · Tage · Minuten.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Nutzdaten: \(3650 \cdot 24 \cdot 8 = 700\,800\) Byte. Verwaltung: 3650 Zeilenköpfe \(\cdot\) 16 B = 58 400 B, 3650 Referenzen \(\cdot\) 8 B = 29 200 B, dazu 16 B für die äußere Reihung — zusammen 87 616 B. Gesamt etwa 788 400 B ≈ 0,79 MB; die Verwaltung macht hier rund 11 % aus, weil die Zeilen kurz sind.

Erwartungshorizont zu Aufgabe b)

Die Nutzdaten sind in beiden Fällen \(87\,600 \cdot 8\) Byte. Die Verwaltung hängt aber von der Zahl der Zeilen ab: 24 statt 3650 Zeilenreihungen, also nur \(24 \cdot (16 + 8) + 16 = 592\) Byte statt rund 87 600 Byte. Viele kurze Zeilen sind teurer als wenige lange.

Erwartungshorizont zu Aufgabe c)
static double[] tagesmittel(double[][] w) {
    double[] m = new double[w.length];
    for (int t = 0; t < w.length; t++) {
        double summe = 0;
        for (int h = 0; h < w[t].length; h++) {
            summe = summe + w[t][h];
        }
        m[t] = summe / w[t].length;
    }
    return m;
}

Zusatzspeicher: die Ergebnisreihung mit \(t\) Werten zu 8 Byte, also \(O(t)\) — für 3650 Tage 29 200 Byte (plus Kopf); die Hilfsvariablen sind konstant.

Erwartungshorizont zu Aufgabe d)

\(100 \cdot 30 \cdot 365 \cdot 1440 = 1{,}58 \cdot 10^9\) Werte, also etwa \(12{,}6\) GB Nutzdaten. Das passt theoretisch in 16 GB, lässt aber kaum Platz für Betriebssystem, Programm und Zwischenergebnisse (schon eine Ergebnisreihung gleicher Größe wäre zu viel). Besser: Stationen nacheinander auswerten (je 126 MB), Werte kompakter speichern (z. B. Zehntelgrad als short, 2 Byte: rund 3,2 GB) oder nur nötige Aggregate halten. Der Plan ist in dieser Form nicht zu empfehlen.

2

Doppelte Einträge

13 BEAFB II–III

Eine Reihung int[] a mit \(n\) Werten zwischen 0 und \(W\) soll darauf geprüft werden, ob ein Wert doppelt vorkommt. Drei Varianten stehen zur Wahl:

  • V1: jedes Paar \(i < j\) vergleichen (vorzeitiges Ende beim ersten Treffer).
  • V2: eine Kopie anlegen, sie mit Insertionsort sortieren und dann benachbarte Werte vergleichen.
  • V3: eine Markierungsreihung boolean[W + 1] anlegen und in einem Durchlauf jeden Wert markieren.
  1. Entwerfen Sie Variante V3 als Java-Methode static boolean hatDoppelte(int[] a, int W). (4 BE)
  2. Bestimmen Sie für \(n = 50\,000\) und \(W = 10^6\) für jede Variante die Zahl der Vergleiche bzw. Markierungen im ungünstigsten Fall und den Zusatzspeicher in Byte. (4 BE)
  3. Erklären Sie, warum V2 eine Kopie anlegt, statt a selbst zu sortieren. (2 BE)
  4. Entscheiden Sie sich begründet für eine Variante, wenn 200 Telefonnummern mit bis zu elf Ziffern (\(W \approx 10^{11}\)) geprüft werden sollen. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Vor dem Markieren prüfen, ob der Platz schon markiert ist.
Hinweis zu Aufgabe b)
Ungünstigster Fall: kein Wert kommt doppelt vor. Insertionsort im ungünstigsten Fall: \(\frac{n(n-1)}{2}\).
Hinweis zu Aufgabe c)
Was geschieht mit der ursprünglichen Reihenfolge?
Hinweis zu Aufgabe d)
Rechnen Sie den Speicher von V3 aus und die Vergleiche von V1.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
static boolean hatDoppelte(int[] a, int W) {
    boolean[] gesehen = new boolean[W + 1];
    for (int i = 0; i < a.length; i++) {
        if (gesehen[a[i]]) {
            return true;
        }
        gesehen[a[i]] = true;
    }
    return false;
}
Erwartungshorizont zu Aufgabe b)

V1: \(\frac{n(n-1)}{2} = 1\,249\,975\,000\) Vergleiche, Zusatzspeicher \(O(1)\) (einige Byte). V2: bis zu 1 249 975 000 Vergleiche beim Sortieren plus 49 999 Nachbarvergleiche; Kopie \(50\,000 \cdot 4 = 200\,000\) Byte. V3: 50 000 Prüfungen und Markierungen; Markierungsreihung \(10^6 + 1\) Byte ≈ 1 MB. Zu beachten: Java setzt beim Anlegen alle \(10^6 + 1\) Plätze auf false — V3 kostet also \(O(n + W)\) Zeit.

Erwartungshorizont zu Aufgabe c)

Sortieren verändert die Reihenfolge der Werte in a. Hängt an der Position eine Bedeutung (z. B. Reihenfolge der Anmeldung), ginge sie verloren; eine Methode, die nur prüfen soll, darf ihre Eingabe nicht unbemerkt verändern. Die Kopie kostet dafür \(O(n)\) Zusatzspeicher.

Erwartungshorizont zu Aufgabe d)

V3 bräuchte eine Markierungsreihung mit \(10^{11}\) Byte = 100 GB — unmöglich (in Java auch wegen der maximalen Reihungslänge). V1 braucht höchstens \(\frac{200 \cdot 199}{2} = 19\,900\) Vergleiche ohne Zusatzspeicher — ein Bruchteil einer Millisekunde. Entscheidung: V1. V2 böte bei so kleinem \(n\) keinen Vorteil und bräuchte zusätzlich eine Kopie.