CL-Blog

Computerlinguistik & Politik

Du durchsuchst gerade das Archiv der Kategorie ‘C++ in der Computerlinguistik II’.

Kategorie: C++ in der Computerlinguistik II

2017 29 Jul

C++ II: Projektabgabetermin und allgemeine Hinweise

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

  • Hier finden Sie allgemeine Hinweise zur Form Ihres Projekts. Bitte beachten Sie diese genauestens, Nichtbeachtung geht in meine Notenbildung ein.
  • Der Abgabetermin ist der 15.10.2017
  • Noch hat mir niemand ihr/sein gewähltes Projektthema genannt. Die Mitteilung an mich ist aber obligatorisch. Bitte machen Sie dies bis Montag, 31.7.

 

2017 24 Jul

C++ II, 24.7. (Schluss)

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Inkrementelle Minimierung von Wortlisten

  • Hash-Funktion für Zustände mit boost::hash_combine
  • Funktionsobjekte mit Nicht-Defaultkonstruktoren
  • Übergabe von Funktionsobjektinstanzen an ihre Container (z.B. unordered_set) per Konstruktor-Aufruf
  • Weitergehende Optimierungen:
    • Gelöschte Zustände und Übergänge werden zunächst inaktiv gesetzt, wir sollten sie wieder verwenden => Man kann das einfach mit zwei Listen machen — eine für Zustände, eine für Übergänge — wo wir StateIDs und Übergangsindices speichern und bei Bedarf wieder benutzen können (vgl. Funktionen new_state() und new_transition() in FSAListRepr. Man verwendet hier am besten eine double ended queue (std::deque), diese hat gute Speicherlokalität.
    • Auch dann können noch Lücken in der Zustandsnummerierung bleiben. Beim Umkopieren in eine Nur-Lesen-Repräsentation kann man diese noch schließen
  • Zu klären ist noch, in welchem Verhältnis der Minimierungsalgorithmus und der fertige Automat stehen. Am besten baut man um die Repräsentation herum eine Klasse ähnlich wie Trie (im Beispielcode DFA genannt). Diese verwendet dien Minimierer dann beim Einlesen einer Wortliste.
  • Testen ist im Kurs etwas zu kurz gekommen. Heutzutage testet man automatisiert und zufallsbasiert (fuzzing). Das folgende Shell-Skript nimmt z.B. zufallsbasiert 1000 Wörter aus der Derewo-Liste und minimiert diese. Gibt es einen Absturz, so erkennt man diesen und speichert die das Problem generierende Liste. Statt einer vorhandenen Liste wie Derewo kann man das Eingabematerial auch nach einer W’keitsverteilung erzeugen, ggf. sogar durch einen Markov-Zufallsprozess. Das lässt man dann ein paar Stunden laufen und fühlt sich gleich besser.
    while :
    do 
    	shuf -n 1000 derewo.txt > wl.list
    	./build-dawg wl.list
    	if [ $? -eq 139 ]; then
    		echo "CRASH"
    		cp wl.list crash.list
    		exit 1
    	fi
    done
  • Auch Äquivalenztests kann man auf diese Weise machen: man erzeugt eine zufällige Wortliste und  einen DWAG daraus. Dann gibt man von diesem die Wörter wieder sortiert aus. Beide Listen vergleicht man per diff und beendet das Testskript wieder, wenn sie nicht gleich sind

Weitere interessante Dinge:

  • Die Boost-Bibliotheken bieten zahlreiche nützliche Klassen, z.B. Mengen etc. auf Vektor-Basis (boost::container::flat_set), dynamische Bit-Mengen (boost::dynamic_bitset), Ringpuffer (boost::circular_buffer), Prüfsummen (boost::crc), Hashing (boost::hash), Python-Wrapping von C++-Klassen (boost::python) und vieles mehr. Einfach mal reinsehen
  • Portables Befehlszeilenparsing kann man gut mit tclap machen (von Bibliotheken wie boost::program_options rate ich ab)
  • Hocheffiziente Tokenisierer, auch für natürlichsprachliche Eingaben, macht man mit re2c.

Programmcode:

 

2017 21 Jul

C++ II: Katalog der Programmierprojekte [UPDATE]

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Hier finden Sie einen Katalog von Programmierprojekten. Für das Abschlussprojekt können Sie jedes mit C++ II gekennzeichnete Projekt auswählen. Bitte teilen Sie mir Ihre Entscheidung bis Ende nächster Woche mit. Dann folgt auch noch ein Dokument mit allgemeinen Hinweisen zur Bearbeitung der Projekte.

Hinweis: Update: ich habe noch zwei weitere, komplexere Projektthemen hinzugefügt.

 

2017 17 Jul

C++ II, 17.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Implementierung des inkrementellen Minimierungsalgorithmus’ von Daciuk et al

  • Goldene Regel: Mache aus jedem Algorithmus eine eigene Klasse (also ein Funktionsobjekt). Der Konstruktor dieser Klasse führt den Algorithmus dann aus.
  • std::stringstream: Streams im Speicher
  • Fortgeschrittene Verwendung Hash-Container (wie unordered_set)
  • Hash-Container basieren auf Äquivalenz ihrer Elemente, nicht auf Gleichheit
  • Funktionsobjekte mit Referenzen auf externe Daten.Wichtig: die von Funktionsobjekten realisierten Funktionen müssen zeitinvariant sein, dh. unabhängig vom Aufrufszeitpunkt immer das gleiche Ergebnis liefern. In der Regel stellt man das sicher, indem die Datenelemente in den Funktionen const, also unveränderlich sind (meist als const-Referenzen). Nun kann sich aber die Variable, auf die sich die Referenz bezieht, zwischen den Funktionsaufrufen ändern (dies ist bei der Automatenminimierung der Fall). Dann muss dennoch die Zeitinvarianz der durch das Funktionsobjekt realisierten Funktion gewährleistet sein.

Programmcode:

 

2017 10 Jul

C++ II, 10.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Hashing

  • Hash-Funktionen: sollen zeitinvariant, deterministisch, effizient sein und gut streuen. Hier finden Sie einige Beispiele. Eine gute Hash-Funktion ist CityHash.
  • Hash-Funktionen bestehen meist aus 3 Bausteinen:
    • der Verrechung des aktuellen Datenblocks in das Hash-Register (mit bitlogischen Operationen wie xor),
    • einer Mix-Phase (Durcheinanderwürfeln der Bits des Hash-Registers mit Verschiebe und Rotationsoperationen
    • einer Normalisierungsphase am Ende
  • Hash-Funktionen in C++: für viele eingebauten Datentypen wie string sind Hash-Funktionen im hash-Template-Funktionsobjekt schon definiert (Beispiel: std::hash<std::string>
  • Für benutzerdefinierte Klassen muss man sich ein eigenes Hash-Funktionsobjekt definieren. Dies passiert in 3 Schritten:
    • Definieren einer size_t hash() const Funktion in der Klasse und Auswahl einer geeigneten Hash-Funktion. Diese kann durchaus auf vorhandenen Hash-Funktion wie std::hash<string> basieren.
    • Definieren eines Funktionsobjekts, welches diese hash()-Funktion “wrappt”:
      struct MyClassHash {
        size_t operator()(const MyClass& x) const
        {
          return x.hash();
        }
      };
    • Funktionsobjekt dem Container bekannt machen:
      typedef std::unordered_set<MyClass,MyClassHash> MyClassSet;
  • Hier finden Sie einige Benchmarks zum Vergleich von Hash-Funktionen
  • Hashing mit offenen Listen noch mal erklärt
  • Tabellenhashing mit Sondierung
  • Interessant: die Sondierungs-Funktion (in Python) j = ((5*j) + 1) mod 2**k gibt bei allen 2^k Aufrufen jeweils einen neuen Wert zwischen 0 und 2**k-1 aus (“besucht” also jeden Wert in diesem Intervall genau ein Mal), unabhängig vom ersten Wert von j. Nehmen Sie z.B. k =3 und probieren Sie es aus!
  • Andere Sondierungsmethoden: linear, quadratisch
  • Dictionaries in Python: Hierzu ein Video und die kommentierte Implementierung in C.

Programmcode:

2017 3 Jul

C++ II, 3.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Funktionsobjekte:
    • Klassen, die nur (beliebige) Funktionen definieren.
    • Meistens ohne Instanzvariablen (daher auch ohne Benutzerkonstruktor), manchmal mit Instanzvariablen (die dann in der Regel const-Zeiger oder const-Referenzen sind)
    • In C++ wird gerne in Funktionsobjekten der Funktionsaufrufoperator operator() definiert. Rückgabewert und Argumente hängen von der Verwendungsweise ab; z.B. ist der Rückgabewert bei Vergleichsobjekten wie std::equal, std::less usw. immer bool, und operator() hat immer zwei Argumente.
  • Extensionale Typisierung (“Duck typing“)
  • In C++ über Templatisierung realisierbar
  • Repräsentationstausch durch Kombination von Templates und speziellen Konstruktoren

Programmcode:

2017 27 Jun

C++ II: Literatur

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Literatur

  • Für die Erweiterung unseres Trie-Klasse in Richtung DAWGs (“Directed acyclic word graphs”) lesen Sie bitte Abschnitte 1-3 dieses Artikels. Wir werden dies ab übernächster Woche anfangen zu implementieren.
  • Dieser Artikel beschreibt Techniken, wie man den Speicherverbrauch von Tries und DAWGs reduzieren kann.

 

2017 27 Jun

C++II, 26.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Besprechung der HA

  • Vorwärtsdeklaration lässt typedef-Benutzung vor der kompletten Klassendefinition zu (diese erfolgt unten -> übersichtlicher)
  • Eine eingebettete Klasse (hier Iterator) kennt nicht die Instanzvariablen der Klasse, in die sie eingebettet ist; also müssen alle nötigen Daten übergeben werden (per Konstruktor etc.)
  • Ungültigen Zustand zurückgegeben:
    1. Wert zurückgeben, von dem wir wissen, dass der Iterator ihn nicht verarbeitet: ein ganz großer Wert wie unsigned(-1) oder eine andere ganz große Zahl
    2. std::numeric_limits<unsigned>::max() aus der STL führt Punkt 1 eleganter aus; max() ist dabei eine Klassenfunktion der Klasse numeric_limits<unsigned>.
    3. Flexibelste Lösung: Klassenfunktion InvalidState() definieren . Wird mit static gekennzeichnet und kann ohne Instanz aufgerufen werden.
      => Der Code ist lesbarer, verständlicher und die Methode kann schnell global geändert werden.
  • Header verschiedener Repräsentationen muss unbedingt verschieden sein, damit keine falschen Datenstrukturen in den Trie eingelesen werden
  • böswillige Manipulation der Binärdateien kann bspw. durch Prüfsummen getestet werden
  • header-String soll nun nicht mehr vor der Klassendefinition stehen, damit er nicht für jeden sichtbar ist => private Funktion definieren, die den String enthält und zurückgibt

Ergänzung/Verbesserung des Trie

  • Startindex für Übergänge setzen: In der Schleife über die Zustände wird nach dem push_back() aller ausgehender Übergänge, die neue transition-Vector-Größe bestimmt und die Anzahl der gerade hinzugefügten Übergänge abgezogen.
    • Nur wenn q mindestens einen Übergang hat (Defaultwert -1 muss dann nicht verändert werden)
    • Überlegungen wie diese gleichen einem Induktionsbeweis: Korrektheit der Anweisungen für trivialen Fall (Startzustand) zeigen und dann zeigen, dass es für die nächsten Schritte (in der Schleife) nicht falsch wird.
  • Trie sortieren: Schnellere Suche, in der Folge keine weitere Sortierung bspw. bei auto_complete() nötig.
    • Übergänge pro Zustand sortieren => states.size()-mal muss sortiert werden
    • Über states-Vector iterieren und Übergangsblöcke herausfinden (! nur wenn Startindex nicht -1)
    • Man kann mit Vector-Iteratoren rechnen (Random Access Iterator) => Ab transitions.begin() kann mit + weitergezählt werden um die Intervallgrenzen eines Übergangsblocks zu bestimmen.
    • Um Übergänge zu vergleichen muss im struct der Transition der <Operator überladen werden.
    • Für Tupel-Sortierung gilt generell: Es wird spaltenweise sortiert mit if-Bedingungen. (Für uns reicht der einfache Vergleich der char-Symbole)
    • Guter Stil: Beim Überladen eines Operators innerhalb der Deklaration keinen anderen Operator benutzen.
    • Andere Möglichkeit wäre der Vergleich über Funktionsobjekte: Das sind Klassen wie bspw. class Compare im std::set Hier kann der Standardwert std::less<Key> angepasst werden.
  • Der Optimierer erkennt öfters verwendete gleiche Ausdrücke im Syntaxbaum und rechnet deren Wert nur einmal aus. Also keine Sorge um Effizienz: Der Ausdruck wird nur einmal berechnet.

Programmcode:

2017 20 Jun

C++ II, 19.6: Hausaufgabe

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Hausaufgabe (bitte machen bis nächsten Sonntag Abend)

  1. Erweitern Sie FSAVectorRepr um einen Iterator (anolog dem in FSAListRepr). Natürlich muss FSAVectorRepr::outgoing_transitions_of() auch implementiert werden.
    Hinweis: Da wir die FSAVectorRepr noch nicht effektiv befüllen können (man kann damit ja keinen Trie aufbauen), muss man zum Testen tricksen. Sie könnten FSAVectorRepr z.B. im Defaultkonstruktor von Hand mit einigen (korrekten) Zuständen und Übergängen befüllen und in der Trie-Klasse temporär die Listen- durch die Vektor-Repräsentation austauschen. Zum Test des Iterators eignet sich dann z.B. Trie::as_dot().
    Noch ein Hinweis: der Iterator hier muss auf andere Weise feststellen, ob er am Ende ist (wir haben ja keine Endmarke -1 mehr). FSAVectorRepr hat aber die Information, wieviele Übergänge ein gegebener Zustand hat.
  2. Stellen Sie die read() und write()-Funktionen von FSAVectorRepr fertig (in Analogie zu FSAListRepr). D.h., schreiben Sie auch einen Vorspann-String, anhand dem Sie beim Wiedereinlesen feststellen können, ob Sie auch wirklich eine binäre Vektor-Repräsentation vor sich haben.
  3. Stellen Sie Trie::auto_complete() so um, dass eine set<string> zurückgegeben wird. Variante: verwenden Sie vector<string> und sortieren Sie vor der Rückgabe.

Bitte Programm syntaxfehlerfrei übersetzbar und funktional.

Programmcode (aktualisiert wegen Syntaxfehler :-;):

2017 19 Jun

C++ II, 19.6

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen

  • Besprechung der HA
    • nochmal der Hinweis: prüfe korrekte Vektorindizierung (intern mit asserts, bei Interaktion mit dem Benutzer mit if-Abfragen)
  • Return Value Optimization (RVO): Vermeidung eines Kopierkonstruktoraufrufs durch return Konstruktor();
  • rekursive Funktionen am Beispiel der Trie::auto_complete_at_state()
    • rekursive Aufrufe werden auf dem Stack gespeichert (mit den Parametern des Aufrufs und lokalen Variablen wie bspw. Iteratoren)
    • Wert von auto_complete_at_state(pref,q) bekommt man, wenn man für jeden ausgehenden Übergang q -a-> p den Befehl auto_complete_at_state(pref+a,p) ausführt und deren Ergebnisse zusammenführt. Die Rekursion terminiert, wenn Zustände ohne ausgehende Übergänge erreicht werden.
  • sentinel:  grob gesagt ein spezieller Wert, der ‘Ende’ signalisiert
    • in unserem Trie-Kontext: statt zeitraubende if-Abfragen ob gültiger Vektorindex (current_index!=-1) könnte man die nullte Zelle des Vektors benutzen: diese verweist auf sich selbst (vec[0].next_index=0) und ändere jede -1 in vec[x].next_index=-1 in die Null.
  • std::set: als binärer Suchbaum implementierbar
    • verlangt Definition einer totalen Ordnung über den Elementen (üblicherweise ‘kleiner’)
    • bei einem balancierten binären Suchbaum wie bspw. Rot-Schwarz- oder AVL-Bäumen hat die Suche logarithmische Zeitkomplexität
    • Nachteile: nicht speicherlokal, viel Verwaltung, Rebalancing evtl. aufwendig. Daher prüfe vorher, ob nicht auch ein Vektor als Datenstruktur infrage käme
    • bietet verschiedene Iteratoren (const, nicht_const, reverse_iterator…)
    • mit std::set::find() prüfbar, ob ein Element in der Menge ist. Rückgabe ist ein Iterator, der auf dieses Element zeigt, falls es existiert,  sonst der von std::set::end() zurückgegebene Iterator
  • WICHTIG: dereferenziere nie einen ein_objekt.end()-Iterator! Prüfe daher vor der Dereferenzierung ,wo immer nötig,  ob der Iterator aktuell noch auf ein gütliges Element zeigt.
  • Sortieren:
    • wenn Elemente schon in einer set gespeichert sind, kann diese unter Benutzung von Iteratoren mit einem speziellen Konstruktoraufruf in einem Vektor abspeichern: StringVector sv(menge.begin(),menge.end()); (man kann auch Iteratoren von anderen Containern für die Initialisierung eines Vektors benutzen)
    • STL bietet auch Algorithmen, u.a. std::sort an, das nach #include <algorithm> verfügbar ist.
      • Beispielaufruf: std::sort(vec.begin(),vec.end()); // implizit mit operator< sortiert
      • an diesem Beispiel zeigt sich, dass Iteratoren das Bindeglied zwischen Containern und Algorithmen sind: die Eingabe von std::sort sind Iteratoren (nicht Container).

 

Nachdenkaufgabe:

Wie könnte eine totale Ordnung aussehen, nach der man Tries sortieren könnte?

2017 13 Jun

C++ II, 13.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Besprechung der HA
  • Binäres Lesen und Schreiben von Repräsentationen; Vor- und Nachteile;
  • Iteratoren in der STL
  • typedef-Schlüsselwort zum Definieren neuer Typnamen
  • Iterator: Zeigerabstraktion
    • Iteratoren implementieren typischerweise Funktionen zum Erzeugen, Vergleichen, Weitersetzen und Dereferenzieren
    • Iteratoren haben privilegierten Zugriff auf ihren Container
    • Iteratoren verbergen jedoch die internen Implementierungsdetails der Container und stellen eine logische Sicht auf den Container her
    • Iteratoren haben stets einen internen Zustand; sie “wissen” also, wo sie gerade “sind” im Container

Nachdenk-Hausaufgabe:

  • Denken Sie über die Implementierung eines Übergangsiterators nach. Wir er sich verhalten könnte, können Sie dem Konstruktor von FSAVectorRepr entnehmen.
  • Dieser Iterator wird auch an anderen Stellen benötigt:
    • bei Trie::as_dot()
    • bei Trie::auto_complete()

Programmcode:

2017 30 Mai

CPP2 29.05.2017

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Testverfahren für endliche Datenmengen (Beispiel: Trie):

  • Alle Wörter in Datei ausgeben
  • Input- und Outputdatei ordnen (sort)
  • diff ausführen

Zwei Arten, Vektoren zu benutzen:

  1. resize() Vergrößert einen Vektor auf eine festgesetzte Größe
    Wird dann verwendet, wenn sich die Vektorgröße “sprunghaft” ändert
  2. reserve() reserviert für den Vektor, ohne Elemente zu erzeugen. push_back() fügt neues Element ans Ende eines Vektors und verändert dazu möglicherweise
    Wird dann verwendet, wenn die Vektorelemente kontinuierlich “hereinkommen”, z.B. beim Aufbau eines Tries

Initialisierungsliste:

  • Befindet sich zwischen dem Namen einer Funktion und der ersten öffnenden Klammer
  • Ort für die Initialisierung von Instanzvariablen und delegierenden Konstruktoren

const:

  •  (Referenzen und Rückgabewerte)
  •  Hinter Funktionen, die keine Instanzvariablen verändern
  •  const wird propagiert, d.h., alle Funktionen, die von einer const-Funktion aufgerufen werden, müssen selbst const sein
  • Regel: Immer von Anfang an const verwenden, um das Programm sicherer zu machen! Späteres Verwenden kann viel Zeit kosten!

Repräsentation von Funktionalität trennen:

  •  Eigene Klassen für komplexe Datenstrukturen bzw. die damit in Verbindung stehende Funktionalität anlegen
  •  Erhöht die Wiederverwendbarkeit
  •  Ermöglicht die Verwendung  von unterschiedlichen Repräsentationen für unterschiedliche Zwecke (bspw. Aufbauen eines Tries vs. Benutzen eines fertigen Tries)
  •  Instanzvariablen und alle Funktionen, die auf diese zugreifen und sie verändern, gehören in die Repräsentationsklasse
  •  Die Repräsentationsklasse wird im Header der Funktionalitätsklasse mit #include “repräsentationsklasse” eingebunden
  •  (transitive) Doppeleinbindungen von Klassen führen zu einer Ambiguität des Texts und werden durch #pragma once im Header vermieden
  •  Instanzvariablen werden in der Initialisierungsliste der Konstruktoren der Funktionalitätsklasse initialisiert.
  •  Effizienz einer Repräsentation (besonders einer solchen, die auf Vektoren basiert) kann wesentlich erhöht werden, wenn man darauf achtet, dass Dinge,  auf die hintereinander zugegriffen werden soll, auch in der Datenstruktur nebeneinander angeordnet sind. (s. caches)

Binärdateien:

  • Am effizientesten schreib- bzw. einlesbares Format; Daten werden in Binärrepräsentation direkt vom Speicher in den Stream geschrieben bzw. aus diesem gelesen
  • Besonders für Vektoren geeignet

Speicherlokalität:

  • Der RAM-Speicher wird vom Prozessor nicht direkt angesprochen, sondern über sog. Caches
  • Ein Cache ist ein besonders effizienter Speicher
  • Wird eine Speicherzelle adressiert und eingelesen, werden sie (sofern sie nicht schon im Cache ist) und ihre Nachbarn gleich mit den Cache transferiert (sog. Cacheline)
  • Vektoren sind im sequentiellen Zugriff (Beispiel: for-Schleife) besonders effizient, weil die Wahrscheinlichkeit groß ist, dass sich das nächste Element bereits im Cache befindet.
  • Literatur: What Every Programmer Should Know about Memory (Ulrich Depper, 2007)

 

 

 

 

2017 30 Mai

C++ II, 29.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

=> Eric

Hausaufgabe (bis 11.6. abends, bitte alle machen (zip mit .hpp und .cpp-Dateien)):

  1. Definieren Sie für die FSAListRepr-Klasse einen Ausgabe-Operator <<, der eine JSON-Ausgabe erzeugt. Komplettieren Sie dazu zunächst print_json(), indem Sie sich eine geeignete JSON-Repräsentation überlegen. operator<<() ruft dann nur noch print_json() auf.
  2. Fügen Sie der Trie-Klasse einen Operator += hinzu, mit dem Wörter hinzufügen kann. Der Operator soll wie folgt benutzt werden können: my_trie += "Auto";
    Halten Sie die Definition so einfach wie möglich.
  3. Definieren Sie eine zweite Nur-Lesen-Repräsentationsklasse FSAVectorRepr für Tries gemäß den in der Vorlesung besprochenen Ideen:
    Alle von Zustand q ausführenden Übergänge liegen adjazent im transitions-Vektor; die Listenstruktur entfällt damit.
    In Zustand q ist dann neben dem Index, an dem die Übergänge für q in transitions beginnen, nur noch deren Anzahl gespeichert .
    Sie müssen nicht die komplette Repräsentation definieren; es reicht zunächst die Hülle FSAVectorRepr und die privaten structs für State und AdjacencyList.

Programmcode:

 

 

2017 23 Mai

C++ II, 22.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Hausaufgabe (bis Sonntag Abend an mich)

  • Passen Sie die Trie-Implementierung vom WS so an, dass sie std::vector anstelle der statischen C-Vektoren für Zustände und Übergänge verwendet.

Hinweise:

  • add_transition() muss nun nicht mehr abbrechen, sobald die Maximalkapizität der beiden Vektoren erreicht ist. Stattdessen wird resize() verwendet, um die Datenstrukturen mitwachsen zu lassen. Testen Sie Ihre Implementierung mit einer großen Wortliste, z.B. DeReWo vom IDS Mannheim.
  • Implementieren Sie add_transition() aber nicht so, dass Sie die Vektoren nur um jeweils ein weiteres Element vergrößern. Lassen Sie die Vektoren immer um einen gewissen Prozentsatz wachsen (z.B. 20%). Damit erreichen Sie exponentielles Wachstum.
  • NEU: Setzen Sie auch alle anderen bereits erworbenen Techniken ein, z.B. const-Referenzen, Konstruktoren (auch für eingebettete Klassen) usw.

 

 

2017 22 Mai

C++ II, 22.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • gute Klassenarchitektur
    1. default-Konstruktor
    2. parsing Konstruktoren (istream, string, etc.)
    3. Wird ein Kopier- bzw. Zuweisungskonstruktor benötigt (bspw. für std::vector) oder braucht man sie überhaupt (vgl. std::cout)
    4. Sollen Operatoren überladen werden?
      • Gleichheitsoperator, Kleiner-als-Operator, etc.
      • Stream-operator (<<) als friend in der Klasse definiert, damit auf private Eigenschaften zugegriffen werden kann
  • Repräsentation von Fließkommazahlen
  • Repräsentationen für endliche Automaten
    • Adjazenzmatrix, Inzidenzmatrix, Adjazenzlisten, Tarjan-Yao-Algorithmus (link1, link2)
    • Vor- und Nachteile (Modifizierbarkeit, Zeitaufwand, Speicheraufwand)
  • Standard Template Library (STL) für C++
    • Code-Muster, die für bestimmte Typen realisiert werden
    • std::vector
      • resize-Operation auf Vektoren als Bewegung in nächst größere Lücke

Programmcode

Hausaufgabe (bis Sonntag Abend an mich)

Passen Sie die Trie-Implementierung vom WS so an, dass sie std::vector anstelle der statischen C-Vektoren für Zustände und Übergänge verwendet.


Hinweise:

  • add_transition() muss nun nicht mehr abbrechen, sobald die Maximalkapizität der beiden Vektoren erreicht ist. Stattdessen wird resize() verwendet, um die Datenstrukturen mitwachsen zu lassen. Testen Sie Ihre Implementierung mit einer großen Wortliste, z.B. DeReWo vom IDS Mannheim.
  • Implementieren Sie add_transition() aber nicht so, dass Sie die Vektoren nur um jeweils ein weiteres Element vergrößern. Lassen Sie die Vektoren immer um einen gewissen Prozentsatz wachsen (z.B. 20%). Damit erreichen Sie exponentielles Wachstum.

 

2017 16 Mai

C++ II, 15.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Speicherverwaltung:
  1. Programmsegment
  2. Datensegment ( → globale Variablen)
  3. Stacksegment  ( → lokale Variablen)
  4. Heap  ( → Heap-Manager: verweist auf freie Speicherstellen und gibt diesen Speicher nach Benutzung wieder frei)
  • Kopierkonstruktor: konstruiert ein neues Objekt, das identisch (Kopie) zu einem bereits vorhandenen Objekt ist. Wichtig: Referenzaufruf benutzen, um Endlosschleife zu vermeiden: FSA(FSA& rhs) {…}
  • const: verhindert, dass eine Variable in der Funktion verändert werden kann: FSA(const FSA& rhs) {…}  → rhs kann nun vom Kopierkonstruktor nicht verändert werden
  • Operatoren sind Funktionen mit spezieller Syntax. Wir können bereits vorhandene Operatoren überladen, indem wir ihnen eine neue Bedeutung geben, z.B. Überladung von “=” als Zuweisungsoperator
  • Zuweisungsoperator: weist ein bereits existierendes Objekt einem anderen zu, sodass Objekt 1 danach identisch zu Objekt 2 ist       fsa1 = fsa2;    ≙    fsa1.operator=(fsa2);   Zuweisung ist rechtsassoziativ – der Rückgabewert einer Automatenzuweisung muss ein Automat sein:  const FSA& operator=(const FSA& rhs)  { …   return *this}
  • Google Style Guide für C++

Hausaufgabe bis nächste Woche:

Recherchieren, welche Datenstrukturen es gibt um Automaten zu repräsentieren.

 

Programmcode:

2017 8 Mai

C++ II, 8.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Funktionsaufrufe: Wertaufruf (call-by-value), Referenzaufruf (call-by-reference), Zeigeraufruf
  • Zeiger: Deklaration von Zeigern, Adressoperator &, Dereferenzierung, Deklaration von Referenz-Variablen, rekursive Zeiger

 

Programmcode:

2017 24 Apr

C++ II, 24.4.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Ziele des Kurses:

  • effizientes Programmieren – Konstanten im Programm möglichst klein halten
  • Schreiben von skalierbaren Programmen – beanspruchter Speicherplatz wächst mit Größe der Eingabedaten

Es soll auf den ersten Kurs aufbauend näher auf Konstruktoren wie dem Kopierkonstruktor und dem Move-Konstruktor eingegangen werden.
Daneben sollen der Destruktor, der Zuweisungsoperator und Zeiger behandelt werden.

Ein weiterer Teil wird den Bibliotheken STL (Standard Template Library) und Boost gewidmet. Diese Bibliotheken bieten Container, Iteratoren, Funktionsobjekte und Algorithmen an, um Datenstrukturprobleme für C++-Programmierer zu vereinfachen oder gar zu lösen.

 

Goldene Regel “Rule of Four”

Wenn nicht von Hand für eine Klasse definiert, definiert der Compiler den:

  • Default-Konstruktor
  • Kopierkonstruktor
  • Destruktor
  • Zuweisungsoperator

Wikipedia-Eintrag zu der daran angelehnten “Rule of Three“, die besagt:
Wenn eine der drei Methoden:

  • Kopierkonstruktor
  • Destruktor
  • Zuweisungsoperator

definiert ist, sollten alle drei explizit definiert werden.

2016 18 Jul

C++ II, 18.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Earley-Parser Teil 4 : complete-Schritt
  • Parser-Optimierung durch Einsatz von Regel-Tries. Ziel: Itemanzahl in der Chart so weit wie möglich reduzieren (vgl. auch)
  • Parsbaumkonstruktion

Materialien:

  • Endstand Earley-Parser
    Hinweis: Projekt dient auch als Referenz für Ihre Projekte
  • Experiment: ich habe den Parser einmal mit einem 8-Wort-Satz mit einer PP und der TübaDZ-Grammatik mit 19,000 Regeln profiliert. Dabei ergab sich folgendes:
    • Es wurden rund 320,000 Items durch die Agenda verarbeitet.
    • Am Ende enthielt die Chart rund 187,000 Einträge
    • Die Schleife in complete() wurde rund 23 Mio mal (!) durchlaufen (hier wurde auch die meiste Zeit verbraucht).
    • Gesamt-Parszeit: 5s
    • Die Frage ist also: wie macht man complete() effizienter?

 

 

2016 12 Jul

C++ II, 11.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Earley-Parser: Teil 3: Datenstrukturen und Parsingalgorithmus
    Wir realisieren die Chart als einen Vektor mit einer Dimensionalität wie die Eingabelänge. In der Chart befinden sich Hashmaps mit Items als Schlüssel und ihrer bis zu diesem Zeitpunkt konstruierten Wahrscheinlichkeit als Wert.
  • Bei einem Viterbi-Parser kann es vorkommen, dass wir das gleiche-Item (i,A → α•β,bp) mehrfach konstruieren, nur mit verschiedenen Wahrscheinlichkeiten. Wenn der Parse abgeschlossen ist, dann soll die Chart dasjenige mit der höchsten Wahrscheinlichkeit enthalten. Darüber hinaus kann die Verbesserung der Item-Wahrscheinlichkeit bewirken, dass sich auch andere Items, die A verwenden, verbessern. Dem muss unser Parser Rechnung tragen. Ein Ansatz, wie man diese Probleme löst, findet sich in Klein&Manning (2001)
  • Parsing auf GPUs

Materialien:

Hausaufgabe (bis nächsten Mo, 10Uhr per Email)

Komplettieren Sie alle mit TODO gekennzeichneten Funktionen und fügen Sie eine print(stream,mapper)-Funktion zu EarleyItem hinzu, die in der while-Schleife aufgerufen alle Agenda-Items in menschenlesbarer Form ausgibt. Erstellen Sie eine kleine Spielgrammatik samt Mini-Lexikon und testen Sie die bereits funktionierenden Teile des Parsers (wenn alles korrekt ist, sollten die an Position 0 prädizierten Items plus das Scan-Item für das erste Wort plus die an Position 1 prädizierten Items ausgegeben werden).

2016 4 Jul

C++ II, 4.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • static_assert: Assertierugen zur Übersetzungszeit
  • type_traits: Typ-Metainformationen
  • Earley-Parser: Teil 2: Lexikonrepräsentation
  • Berkeley NLP group

Programme:

Hausaufgabe (verpflichtend, bis nächsten Mo, 10 Uhr)

Stellen Sie die Klasse Lexicon fertig und definieren Sie alle voraussichtlich benötigten Funktionen. Definieren Sie einen Konstruktor, der einen Input-Stream nimmt und eine Instanz des String-Mappers und der das Bitpar-Lexikon einliest. Integrieren Sie die Lexikonklasse in earley-parser.cpp und testen Sie das Lexikon-Einlesen (indem Sie operator<<() für Lexicon defineren und das Lexikon wieder ausgeben).

Hinweis: Als interne Datenstruktur eignet sich eine unordered_map mit Symbol als Schlüssel (als Übersetzung des Wort-Strings) und einem Vektor von Symbol-float-Paaren als Wert (die Symbol-Komponente im Paar ist das übersetzte Präterminial).

2016 27 Jun

C++ II, 27.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Konzeption eines Earley-Parsers: Teil 1: die probabilistische Grammatik

Programme:

Literatur:

Hausausgabe (verpflichtend, bis nächsten Mo, 10.00 per Email)

  • Ergänzen Sie alle mit TODO gekennzeichneten Stellen in PCFG.hpp (dabei wird sich die Musterlösung von hier als wertvoll erweisen)
  • Fügen Sie auch noch die Funktionen max_arity(), average_arity(), has_chain_rules() und has_epsilon_rules() zur PCFG-Klasse hinzu.
  • Schreiben Sie ein Testprogramm, welches die Bitpar-Grammatik einliest und die Funktionen von PCFG damit demonstriert.

 

2016 20 Jun

C++ II, 20.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Besprechung der HA
  • Techniken zur Speicherung von bijektiven Abbildungen
  • std::hash<T>: Funktionsobjekt, welches von vielen Klassen zur Erzeugung von Hashwerten benutzt wird. Es ist zustandslos (keine Instanzvariablen) und definiert als Hash-Funktion
    unsigned operator()(const T& x) const
    {
      ...
    }

    (statt unsigned auch std::size_t), mit der Instanzen von T in positive Ganzzahlen überführt werden.

  • std::hash<T> ist für viele Typen T wie unsigned , float, Zeiger, std::string bereits vordefiniert.
  • Für benutzerdefinierte Klassen muss man std::hash<T> entweder selber spezialisieren oder ein eigenes Funktionsobjekt erstellen (siehe Blogeintrag von letzter Woche)
  • typedefs in Klassen
  • static
  • Interne Darstellung von Gleitpunktzahlen

Programmcode

Hausaufgabe:

  • Machen Sie sich mit der Funktionsweise des Earley-Parsers (wieder) vertraut und denken Sie über Datenstrukturen dafür nach.

Sonstiges:

 

 

2016 13 Jun

C++ II, 13.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Besprechung der Hausaufgabe
  • Boost-C++-Bibliotheken
  • Offenes vs. geschlossenes Hashing
  • Hash-Funktionen: sollen zeitinvariant, deterministisch, effizient sein und gut streuen. Hier finden Sie einige Beispiele. Eine gute Hash-Funktion ist CityHash.
  • Hash-Funktionen bestehen meist aus 3 Bausteinen:
    • der Verrechung des aktuellen Datenblocks in das Hash-Register (mit bitlogischen Operationen wie xor etc.),
    • einer Mix-Phase (Durcheinanderwürfeln der Bits des Hash-Registers mit Verschiebe- und Rotationsoperationen
    • einer Normalisierungsphase am Ende
  • Hash-Funktionen in C++: für viele eingebauten Datentypen wie string sind Hash-Funktionen im hash-Template-Funktionsobjekt schon definiert (Beispiel: std::hash<std::string>
  • Für benutzerdefinierte Klassen muss man sich ein eigenes Hash-Funktionsobjekt definieren. Dies passiert in 3 Schritten:
    • Definieren einer unsigned hash() const Funktion in der Klasse und Auswahl einer geeigneten Hash-Funktion. Diese kann durchaus auf vorhandenen Hash-Funktionen der Komponenten basieren.
    • Definieren eines Funktionsobjekts, welches diese hash()-Funktion “wrappt”:
      struct MyClassHash {
        // Funktionsaufrufoperator() wird überladen
        unsigned operator()(const MyClass& x) const
        {
          // Aufruf der Hash-Funktion der benutzerdefinierten Klasse
          return x.hash();
        }
      };
    • Funktionsobjekt dem Container bekannt machen:
      typedef std::unordered_set<MyClass,MyClassHash> MyClassSet;
  • Daneben muss noch ein Funktionsobjekt definiert werden, welches die Gleichheit zweier Instanzen der Benutzerklasse berechnet. Diese Anforderung erfüllt man am einfachsten, indem man operator==() in der Klasse definiert.
  • Tabellenhashing mit Sondierung
  • Interessant: die Sondierungs-Funktion (in Python) j = ((5*j) + 1) mod 2**k gibt bei allen 2^k Aufrufen jeweils einen neuen Wert zwischen 0 und 2^k-1 aus (“besucht” also jeden Wert in diesem Intervall genau ein Mal), unabhängig vom ersten Wert von j.
  • Dictionaries in Python: Hierzu ein Video und die kommentierte Implementierung in C.

Programmcode & Weiterführendes:

Goldene Regeln:

  • Ordne die Hash-Funktion immer der jeweiligen Klasse zu.

Hausaufgabe [bis Montag morgen, 10.00 Uhr per Email]:

Implementieren Sie eine unordered_map<CFGRule,double> RuleFreq mit kontextfreien Regeln als Schlüssel und unsigned als Frequenz dieser Regel. Verwenden Sie als Testdaten die Bitpar-Grammatik (unter Tiger/). Verwenden Sie zum Tokenisieren dieser Datei boost::tokenizer (das Format ist wie folgt: Frequenz LHS RHS1 RHS2 …). Zum Umwandeln der Frequenz in eine Zahl eignet sich std::stoi()). Implementieren Sie CFGRule als Template-Klasse mit Parameter SymbolType (mit Defaultwert unsigned) mit den Komponenten

SymbolType lhs; // Symbol-ID für die linke Seite
std::vector<SymbolType> rhs; // Vektor von Symbol-IDs für die rechte Seite
const SymbolTypeToStringMap* symbol_index_to_string; // bildet Symbol-IDs wieder auf Strings ab

M.a.W.: die Symbol-IDs sind Zahlen, die den Nichtterminalen der Grammatik eineindeutig zugeordnet werden. Definieren Sie geeignete Konstruktoren, unsigned hash() (wie oben beschrieben), operator==() und operator<<(), mit dem die Regeln in benutzerfreundlicher Form ausgegeben wird.

Das Prozedere ist wie folgt:

  1. Die Grammatikdatei wird zeilenweise eingelesen und tokenisiert (es kann nützlich sein, die Token von boost::tokenizer erst einmal in einem Stringvektor zu speichern; hierzu eignet sich der Bereichs (range)-Konstruktor von std::vector, der das Interval begin() – end() von boost::tokenizer nimmt). Dann werden mittels zweier Hashmaps string->unsigned und unsigned->string die Nichtterminale bijektiv auf Zahlen abgebildet. Statt zweier unordered_maps können Sie hierfür auch eine boost::bimap verwenden.
  2. Für jede Zeile wird ein CRGRule-Regelobjekt konstruiert, welches als Parameter den Symbolindex für die linke Seite und einen Vektor  von Indices für die rechte Seite erhält. Zusätzlich erhält der Konstruktor einen Zeiger auf die unsigned->string-Map (bzw. die bimap), mit der operator<<()  von CFGRule die internen Symbolindices wieder in lesbare Strings umwandeln kann.
  3. Die Regelfrequenz (erste Spalte der Bitpar-Grammatik) wird zum Wert der RuleFreq-Hashmap. Die konstruierte CFGRule-Instanz wird zu ihrem Schlüssel.
  4. Geben Sie die eingelesene Grammatik nach dem Einlesen einfach wieder in lesbarer Form aus (also mittels des oben beschriebenen Operators << von CFGRule.

Teil der Aufgabe ist natürlich auch, eine gute Hashfunktion für CFGRule zu implementieren. Es ist sicher eine gute Idee, alle Operationen der Abbildung von Nichtterminalen auf IDs in einer Klasse zu kapseln.

NB: meine Referenzimplementierung hat knapp 160 Zeilen.

Wenn Fragen zur Aufgabenstellung sind, schreiben Sie bitte eine Email.

2016 6 Jun

C++ II, 6.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

Hausaufgabe (bis So per Email an mich)

  • Implementieren Sie ein Wortbigramm-Zählprogramm auf der Basis einer std:: map. Schreiben Sie einen einfachen Tokenizer, der die Token in einen String-Vektor packt, die dann in der count()-Funktion gezählt werden (besser ist es natürlich, direkt vom Tokenizer in die Map einzufügen, indem man immer ein Token vorausliest).
  • Geben Sie am Ende alle Bigramme samt ihrer Frequenzen aus. Hinweis: es ist nützlich, für das Bigramm-Paar einen operator<< zu definieren.

2016 23 Mai

C++ II, 23.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Binärdateien: lesen und schreiben mit read() und write()
  • Prüfsummen zum Sicherstellen von Datenintegrität: CRC, MD5
  • Standard Template Library (STL)
  • std::vector: dynamische Vektor-Klasse

HA (bis nächsten Mo, 12 Uhr per Email):

  • Besorgen Sie sich eine Textdatei mit etwa 1 Mio Zeilen, lesen Sie diese in einen Vektor und sortieren Sie diesen (mit std::sort).
    Probieren Sie zwei Varianten aus: einmal die push_back-Methode und einmal die basierend auf resize(). Nehmen Sie bei beiden Methoden die Zeit (z.B. mit clock() im ctime-Header)
  • Hinweis: große Textdateien finden sich z.B. bei Wikimedia oder hier.
    Sie sollten allerdings keine größeren Dateien als etwa die Hälfte der Größe des Computer-RAMS verwenden

2016 2 Mai

C++ II, 2.5.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Lexikographischer Vergleich von Tupeln
  • const und const-Propagation
  • Referenzen als Rückgabe
  • Kopierkonstruktor
  • Return value optimization
  • Ausgabeoperator <<: Konzeptuell niemals Teil der Klasse, höchstens syntaktisch
  • Iteratoren: Objekte mit Zustand und privilegiertem Zugriff auf ihre Containerklasse. Erlauben Zuweisung, Vergleich, In/Dekrementierung und Dereferenzierung

Programmcode:

Hausaufgabe (bis So Abend per Email)

  • Implementieren Sie den privaten Verkettungskonstruktor

2016 25 Apr

C++ II, 25.4.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen

  • Exceptions auswerfen und behandeln
  • this: ein Zeiger, der stets die Adresse der aktuellen Instanz enthält; *this ist dementsprechend die Instanz selbst
  • flache vs. tiefe Kopie
  • Referenzen: andere Namen (Aliasnamen für schon vorhandene Objekte)
  • Verwendung von Referenzen:
    • beim Aufruf von Funktionen, um das Originalobjekt unter einem anderen Namen ansprechbar zu machen (das ist z.B. der Standard bei ifstreams und ofstreams als Funktionsparameter)
    • als Rückgabewert von Funktionen
  • const-Schlüsselwort: besagt, dass die damit versehene Variable nicht verändert werden kann.
  • Anwendungen von const:
    • bei der Definition von Konstanten
    • in Kombination mit Referenzparametern, um auszudrücken, dass das Original nicht verändert werden kann
  • Operatoren: generell ganz normale Funktionen mit abweichender Syntax (Präfix, Infix, Postfix)
  • Zuweisungsoperator: überschreibt die Werte der Instanz auf der linken Seite der Zuweisung mit denen, die sich die Instanz auf der rechten Seite befinden
  • Vergleichsoperator usw.
  • Operatordefinition ist eine Form der Funktionsnamenüberladung (viele gleichnamige Funktionen, die sich nur durch die Parametertypen etc. unterscheiden)
  • Speicherhierarchie, Caches, Speicherlokalität

Programmcode:

Goldene Regeln:

  • Benutzt eine Klasse dynamischen Speicher und new, dann sind in der Regel Zuweisungsoperator, Kopierkonstruktor und Destruktor vom Programmierer zu implementieren.
  • Möchte man, dass eine Instanz nicht kopierbar und /oder zuweisbar sein soll, dann macht man eine Dummy-Implementierung von Zuweisungsoperator und/oder Kopierkonstruktor privat.

Hausaufgabe [bis So Abend per Email an mich]

Implementieren Sie die Funktionen clear(), copy_list() und operator==() der Listenklasse. Erweitern Sie auch das Testprogramm um einschlägige Funktionsaufrufe.

2016 18 Apr

C++ II, 18.4.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Zeiger, Vektoren und Adressarithmetik
  • Zeigerstrukturen am Beispiel der verkettenen Liste
  • auto-Schlüsselwort in C++ 11
  • Das Konzept von Knoten und Zeigern ist auch namengebend für ein abstraktes Computermodell, die sog. Pointer machine. Dieses ist weniger ausdrucksstark als eine Turing-Maschine, weil es z.B. keine Arithmetik kann (Frage: warum kann die TM Arithmetik?)
  • Rule of Four: sofern man es nicht verhindert, generiert der Compiler automatisch für jedes struct oder class vier Funktionen:
    • einen Defaultkonstruktor (dieser initialisiert eine Instanz mit Defaultwerten)
    • einen Kopierkonstruktur (dieser erlaubt die Konstruktion einer Instanz als Kopie einer bereits bestehenden)
    • einen Zuweisungsoperator (dieser erlaubt die Zuweisung der Werte einer bestehenden Instanz an eine weitere bereits bestehende)
    • einen Destruktor (dieser ist verantwortlich für das Aufräumen, nachdem eine Instanz ihr Leben ausgehaucht hat: Rückgabe von Ressourcen wie Speicher, Schließen von Dateien, etc.)

Programcode: cpp_ii_18042016

Goldene Regeln:

  • Dereferenziere niemals einen Nullzeiger (weder mit * noch mit ->)
  • Nach delete p; darf p nicht mehr dereferenziert werden

Hausaufgabe (bis Sonntag Abend per Email an mich) [bitte machen]:

  • Implementieren Sie die Funktionen front() / back(), push_front() /pop_back() und pop_front() der Listenklasse. Bei den ersten beiden, aber auch bei den pop-Funktionen stellt sich die Frage, was zu tun ist,  wenn die Liste leer ist (wir müssen ja einen string zurückgeben). Im Moment ist die einzig folgerichtige Vorgehensweise die, das Programm mit abort() zu beenden (eigentlich ist das ein Reflex der Partialität dieser Funktionen). Die weniger radikale Lösung wird später sein, eine sog. Exception zu werfen (“to throw an exception”) .
    Bei den pop-Funktionen müssen Sie auch delete einsetzen, damit der Speicher für die gelöschten ListElements nicht weiter herumliegt. Achten Sie aber darauf, nicht die 2. Goldene Regel oben zu verletzen.
  • Verschönern Sie print(), so dass die Strings in Anführungszeichen stehen mit einem Komma dazwischen
  • Ergänzen Sie das Testprogramm um Tests für die neuen Funktionen.

 

 

2016 11 Apr

C++ II, 11.4.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

Materialien:

Goldene Regeln

  • Gebe jeder Zeigervariablen bei der Definition einen Wert (entweder die Adresse eines vorhandenen Objekts oder eines mit new erzeugten)
  • Zeigerwerte für Zeiger, bei denen man noch nicht weiß, auf was sie zeigen sollen, werden auf 0 (NULL) gesetzt.
  • Dereferenziere niemals einen Nullzeiger
  • Zu jedem new gehört genau ein delete
  • Nach delete darf man keinesfalls noch auf das Heap-Objekt zugreifen

 


CL-Blog läuft unter Wordpress 3.5.1
Anpassung und Design: Gabis Wordpress-Templates
21 Verweise - 0,314 Sekunden.