MINT lernen

Übungen: Speicherbedarf abschätzen

Zehn Übungen zum Speicher — von der Größe eines int über Videobilder bis zur Frage, wann sich Zusatzspeicher lohnt.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Wie groß ist ein Element?
AFB I

Java legt für jedes Element einer Reihung eine feste Anzahl Byte an. Nennen Sie zu jedem Elementtyp seinen Speicherbedarf, indem Sie die Paare verbinden.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Ein char speichert ein Unicode-Zeichen in 16 Bit. Eine String-Reihung enthält nur Referenzen; die Texte liegen woanders im Speicher. boolean bräuchte nur 1 Bit, Java nimmt in Reihungen aber 1 Byte.
Ansatz: Denken Sie an die Bitbreiten: 8, 16, 32, 64.
Weiter: 1 Byte = 8 Bit.
A2
Speicher aus der Deklaration
AFB I

Geben Sie für jede Deklaration den Speicherbedarf der Elemente in Byte an (ohne Reihungsköpfe).

Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls.
DeklarationByte
new int[500]
new double[300]
new char[750]
new boolean[4096]
new long[20][50]
Immer Anzahl der Elemente · Byte je Element: \(500 \cdot 4\), \(300 \cdot 8\), \(750 \cdot 2\), \(4096 \cdot 1\), \(20 \cdot 50 \cdot 8\).
Ansatz: Multiplizieren Sie die Anzahl der Elemente mit der Größe des Typs.
Weiter: Bei der Tabelle: erst die Elemente zählen (Zeilen · Spalten).
A3
Stimmt's? — Speicher im Kapitel
AFB I

Wenden Sie die Regeln zum Speicherbedarf an und entscheiden Sie bei jeder Aussage, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Zusatzspeicher ist, was der Algorithmus neben der Eingabe anlegt — und zählt nur, wenn es mit \(n\) wächst.
Ansatz: Fragen Sie bei jedem Verfahren: Legt es eine zweite Reihung an?
Weiter: Eine Tabelle \(z \times s\) hat \(z \cdot s\) Elemente.
A4
Ein Video im Arbeitsspeicher
AFB II

Ein Programm hält Videobilder unkomprimiert als int[1080][1920] im Speicher (ein int je Pixel). Berechnen Sie den Speicherbedarf.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. ein Bild: Byte
  2. 10 s Video mit 30 Bildern pro Sekunde: Byte
  3. so viele solcher 10-s-Videos passen vollständig in 16 GB: Videos
\(1080 \cdot 1920 \cdot 4 = 8\,294\,400\) Byte ≈ 8,3 MB je Bild. 300 Bilder ≈ 2,5 GB. \(16 : 2{,}49 \approx 6{,}4\) — nur sechs vollständige Videos. Deshalb werden Videos komprimiert.
Ansatz: Pixel zählen: Zeilen · Spalten.
Weiter: 1 GB = \(10^9\) Byte; abrunden, denn ein halbes Video passt nicht.
A5
Wie viel zusätzlich?
AFB II Mix

Untersuchen Sie für jedes Verfahren, wie viel Zusatzspeicher es in Abhängigkeit von \(n\) braucht, und markieren Sie die Spalte.

Klicken Sie die Felder an, die zutreffen. Ein zweiter Klick nimmt die Markierung zurück.
Verfahren\(O(1)\)\(O(n)\)
lineare Suche
Insertionsort
sortierte Kopie anlegen, Original behalten
Häufigkeiten der Noten 1 bis 6 in int[7] zählen
Reihung umgedreht in eine neue Reihung schreiben
Reihung durch Tauschen umdrehen
Die Zählreihung für Noten hat immer 7 Plätze — egal, wie viele Arbeiten es sind. Eine neue Reihung gleicher Länge wächst dagegen mit \(n\). Tauschen braucht nur eine Hilfsvariable.
Ansatz: Suchen Sie in jedem Verfahren nach einem new: Wie lang ist die neue Reihung?
Weiter: Hängt die Länge von \(n\) ab oder ist sie fest?
A6
Umdrehen ohne Kopie
AFB II

Die Methode soll die Reihung a in-place umdrehen — mit nur einer Hilfsvariablen. Überprüfen Sie sie: Markieren Sie die fehlerhaften Zeilen und korrigieren Sie sie.

static void umdrehen(int[] a) {
Klicken Sie die fehlerhaften Zeilen an — dann klappt ein Feld auf, in das Sie die richtige Zeile schreiben. Geprüft werden Auswahl und Korrekturen.
Zeile 1: Läuft i bis zum Ende, wird jedes Paar zweimal getauscht — die Reihung steht wieder wie vorher. Zeile 3: a[a.length] gibt es nicht. Zeile 4: a[i] ist schon überschrieben; der alte Wert steht in h.
Ansatz: Spielen Sie die Methode mit {1, 2, 3, 4} durch.
Weiter: Das Gegenstück zu Index i ist a.length - 1 - i.
A7
Median mit oder ohne Kopie
AFB II

Aus einer Messreihe double[] werte mit \(n = 2\,000\,000\) Werten soll der Median bestimmt werden; dazu muss sortiert werden. Bestimmen Sie Schritt für Schritt den Speicherbedarf.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Speicher gegen Information: Die Kopie kostet \(O(n)\) Speicher, bewahrt aber die ursprüngliche Reihenfolge.
    Ansatz: Ein double belegt 8 Byte.
    Weiter: Überlegen Sie, was beim In-place-Sortieren mit der ursprünglichen Reihenfolge passiert.
    A8
    Lohnt sich eine Markierungsreihung?
    AFB III

    Doppelte oder Häufigkeiten lassen sich mit einer Markierungs- bzw. Zählreihung in einem Durchlauf finden — sie braucht einen Platz je möglichem Wert. Beurteilen Sie jede Situation.

    Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
    1Zusatzspeicher lohnt sich
    2Zusatzspeicher lohnt sich nicht
    Entscheidend ist der Wertebereich \(W\), nicht \(n\): 100 000 Postleitzahlen brauchen 100 kB, 10⁷ Kundennummern 10 MB — dafür spart man Milliarden Vergleiche. Bei elfstelligen Telefonnummern wären es 100 GB für nur 50 Einträge; dort vergleicht man lieber paarweise.
    Ansatz: Berechnen Sie für jede Situation die Größe der Markierungsreihung: ein Byte je möglichem Wert.
    Weiter: Vergleichen Sie diese Größe mit dem, was man an Vergleichen spart.
    A9
    Das halbe Quadrat
    AFB III Trick

    Eine Entfernungstabelle speichert nur das untere Dreieck:

    int[][] d = new int[1000][];
for (int i = 0; i < 1000; i++) {
    d[i] = new int[i + 1];
}

    Ermitteln Sie den Speicherbedarf aller Elemente in Byte (ohne Köpfe).

    Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
    Zeile i hat \(i + 1\) Elemente: \(1 + 2 + \ldots + 1000 = \frac{1000 \cdot 1001}{2} = 500\,500\) Elemente, also 2 002 000 Byte. Wer \(1000 \cdot 1000 \cdot 4 = 4\,000\,000\) rechnet, übersieht, dass die Zeilen unterschiedlich lang sind.
    Ansatz: Wie viele Elemente hat Zeile 0, Zeile 1, …, Zeile 999?
    Weiter: Kleiner Gauß für 1 bis 1000.
    A10
    Dreimal dieselbe Zahl
    AFB III

    Für eine Reihung von Würfelergebnissen (1 bis 6) soll festgestellt werden, ob eine Augenzahl mindestens dreimal vorkommt — in einem Durchlauf und mit konstantem Zusatzspeicher. Entwerfen Sie die Methode, indem Sie die Lücken füllen.

    Baustein anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Vier Bausteine bleiben übrig.

    static boolean dreifach(int[] wurf) {
      int[] anzahl = new int[];
      for (int w : wurf) {
        anzahl[]++;
        if (anzahl[w] 3) return true;
      }
      return false;
    }
    Zusatzspeicher: , unabhängig von der Zahl der Würfe.

    Mit new int[7] gibt es die Indizes 0 bis 6, jede Augenzahl zählt an ihrem eigenen Index (Index 0 bleibt ungenutzt). 7 · 4 = 28 Byte — egal, ob 10 oder 10 Millionen Würfe. new int[6] würde bei einer Sechs abbrechen.
    Ansatz: Die Augenzahl selbst kann als Index dienen.
    Weiter: Welcher Index wird für die Sechs gebraucht, und wie lang muss die Reihung deshalb sein?