Anpassbare Programmierung

Optimale Speichergröße für jedes Problem

Einfache Implementierung mit der Programmiersprache

Der Index ist ein Schlüssel zu einem Datensatz

Jede Schlüsselmenge kann mit linearen Tabellen effizient umgesetzt werden

Die Suche mit dem Index als Schlüssel dauert ca. O(N)

Die Suche mit dem Index als Schlüssel dauert ca. O(1)

Ein Stapelspeicher basiert auf einer lienaren Tabelle

Anpassbare Programmierung

Optimale Speichergröße für jedes Problem

Einfache Implementierung mit der Programmiersprache

Der Index ist ein Schlüssel zu einem Datensatz

Jede Schlüsselmenge kann mit linearen Tabellen effizient umgesetzt werden

Die Suche mit dem Index als Schlüssel dauert ca. O(N)

Die Suche mit dem Index als Schlüssel dauert ca. O(1)

Ein Stapelspeicher basiert auf einer lienaren Tabelle

Aufgabe 2. In einen Stack werden in der gegebenen Reihenfolge {1,2,3,4} Werte nacheinander gechrieben. In welcher Reihenfolge werden sie wieder ausgegeben?

First-in First-out {1,2,3,4}

First-in First-out {4,3,2,1}

Last-in Last-out {1,2,3,4}

Last-in First-out {4,3,2,1}

Last-in Last-out {1,4,3,2}

First-in First-out {1,2,3,4}

First-in First-out {4,3,2,1}

Last-in Last-out {1,2,3,4}

Last-in First-out {4,3,2,1}

Last-in Last-out {1,4,3,2}

Kommandoklasse

In dieser Übung soll die in der Vorlesung vorgestellte sehr einfache Stackmaschine nachgebaut werden. Dazu wird zuerst eine Kommandoklasse benötigt, die die einfachen Befehlsformate aus der Vorlesung nun durch Kommando Objekte ersetzt. Die VM solle aus zwei Stacks bestehen:

Stackspeicher

Implementiere die beiden Stack Speicherklassen DataStack für den Integer Datentyp (int) und den Codestack für Command Daten.

Immer die Operation prüfen (also leerer oder voller Stack, ungültige Op usw.).

cHVibGljIGNsYXNzIERhdGFTdGFjayB7CiAgaW50IE47CiAgaW50IGRhdGFbXTsKICBpbnQgc3A7CiAgcHVibGljIERhdGFTdGFjayhpbnQgX04pIHsKICAgIHRoaXMuTj1fTjsKICAgIHRoaXMuZGF0YT1uZXcgaW50W3RoaXMuTl07CiAgICB0aGlzLnNwPTA7CiAgfQogIHB1YmxpYyB2b2lkIHB1c2goaW50IHgpIHsKICAgIHRoaXMuZGF0YVt0aGlzLnNwXT14OwogICAgdGhpcy5zcCsrOwogIH0KICBwdWJsaWMgaW50IHBvcCgpIHsKICAgIGlmICh0aGlzLnNwPT10aGlzLk4pIHRocm93ICJFUE9QIjsKICAgIGlmICh0aGlzLnNwPT0wKSB0aHJvdyAiRVBPUCI7CiAgICBpbnQgeCA9IHRoaXMuZGF0YVt0aGlzLnNwLTFdOwogICAgdGhpcy5zcC0tOwogICAgcmV0dXJuIHg7CiAgfQogIHB1YmxpYyB2b2lkIHN3YXAoKSB7CiAgICBpZiAodGhpcy5zcDwyKSB0aHJvdyAiRVBPUCI7CiAgICBpbnQgdD10aGlzLmRhdGFbdGhpcy5zcC0xXTsKICAgIHRoaXMuZGF0YVt0aGlzLnNwLTFdPXRoaXMuZGF0YVt0aGlzLnNwLTJdOwogICAgdGhpcy5kYXRhW3RoaXMuc3AtMl09dDsKICB9Cn0=

cHVibGljIGNsYXNzIENvZGVTdGFjayB7CiAgaW50IE47CiAgaW50IGRhdGFbXTsKICBpbnQgc3A7CiAgcHVibGljIENvZGVTdGFjayhpbnQgTikgewogICAgdGhpcy5OPU47CiAgICB0aGlzLmRhdGE9bmV3IGludFt0aGlzLk5dOwogICAgdGhpcy5zcD0wOwogIH0KICBwdWJsaWMgdm9pZCBwdXNoKENvbW1hbmQgeCkgewogICAgdGhpcy5kYXRhW3RoaXMuc3BdPXg7CiAgICB0aGlzLnNwKys7CiAgfQogIHB1YmxpYyBDb21tYW5kIHBvcCgpIHsKICAgIGlmICh0aGlzLnNwPT10aGlzLk4pIHRocm93ICJFUE9QIjsKICAgIGlmICh0aGlzLnNwPT0wKSB0aHJvdyAiRVBPUCI7CiAgICBDb21tYW5kIHggPSB0aGlzLmRhdGFbdGhpcy5zcC0xXTsKICAgIHRoaXMuc3AtLTsKICAgIHJldHVybiB4OwogIH0KICBwdWJsaWMgdm9pZCBydW4oQ29kZVN0YWNrIEMsRGF0YVN0YWNrIEQpIHsKICAgIENvbW1hbmQgbmV4dD1DLnBvcCgpOwogICAgd2hpbGUgKG5leHQuY21kIT0nLicpIHsKICAgICAgc3dpdGNoIChuZXh0LmNtZCkgewogICAgICAgIGNhc2UgJysnOgogICAgICAgICAgaW50IGE9RC5wb3AoKSwKICAgICAgICAgICAgICBiPUQucG9wKCk7CiAgICAgICAgICBELnB1c2goYStiKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIGNhc2UgJy0nOgogICAgICAgICAgaW50IGE9RC5wb3AoKSwKICAgICAgICAgICAgICBiPUQucG9wKCk7CiAgICAgICAgICBELnB1c2goYS1iKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIGNhc2UgJyUnOgogICAgICAgICAgaW50IGE9RC5wb3AoKSwKICAgICAgICAgICAgICBiPUQucG9wKCk7CiAgICAgICAgICBELnB1c2goYSk7IEQucHVzaChiKTsKICAgICAgICAgIC8vIG9kZXIgRC5zd2FwKCk7CiAgICAgICAgICBicmVhazsKICAgICAgICBjYXNlICdMJzoKICAgICAgICAgIEQucHVzaChuZXh0Lm9wKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIGRlZmF1bHQ6CiAgICAgICAgICB0aHJvdyAiRVJVTiI7CiAgICAgIH0KICAgICAgbmV4dD1DLnBvcCgpOwogICAgfQogIH0KfQ==

Die VM programmieren

Teste die VM mit folgenden Programmen (alle vier Aufgaben sollen unten zusammen getestet werden):

Aufgabe 5. Implementiere die Tests in main und führe die Tests durch bis die Ergebnisse erwartungsgemäß sind.

Aufgabe 6. Wie viele low-level JavaScript VM Operationen (verwende opCount vom Profiling) werden durchschnittlich für eine Stack VM Instruktion benötigt?

Übung Stapelspeicher (03)

Grundlagen

Kommandoklasse

Stackspeicher

Die VM programmieren