Please disable Adblockers and enable JavaScript for domain CEWebS.cs.univie.ac.at! We have NO ADS, but they may interfere with some of our course material.
Beispiel "Double Hashing"
"Live"-Implementierung aus den Lehrveranstaltungen vom 13. und 20.4.2018.
Der Code ist so wie in der Lehrveranstaltung erstellt, daher nicht optimiert und stellenweise auch nicht "schön", eventuell auch fehlerhaft (Fehler bitte im Forum melden).
Anmerkung zum "Fehler" am Ende der Lehrveranstaltung vom 13.4. (01:33:35), die Erklärung am Ende ist in der Aufzeichnung leider kaum zu hören, da ein Mikro bereits aus war:
Das Problem bestand darin, dass in simpletest zuvor die noch nicht implementierte Methode insert aufgerufen wurde (insert huhuh, 01:33:09). Diese hat planmäßig die Exception Not implemented! ausgelöst. Allerdings wurde der Wert huhuh in das Referenzset natürlich sehr wohl eingefügt. Der Reparaturversuch mit iin huhu (kurz für iinsert huhu) wollte nicht so recht gelingen (ein "h" fehlt). Im Referenzset befanden sich also nun unter anderem die Werte huhuh und huhu, in unserem ADS_set hingegen nur huhu. Beim Aufruf von size ergab sich daher eine Diskrepanz (104 im Referenzset vs. 103 in unserem ADS_set). Auch beim Testen gilt also: gewußt wie…
Der Film zum Code:
Download:
ADS_set.h (Stand 20.4.2018, Funktionsumfang für die zweite Projektphase)
ADS_set_Phase_1.h (Stand 13.4.2018, Funktionsumfang für die erste Projektphase; aus technischen Gründen trägt die Datei einen anderen Namen. Vor Verwendung bitte in ADS_set.h umbenennen)
Unterlagen zu Double Hashing siehe Unterlagen, Vorlesung Kapitel 3 Vektoren (ab Seite 14).
Beispiellösungen zur Abschlussklausur
Termin 1A
friend bool z(const ADS_set &a, const ADS_set &b) {
if (!a.curr_size || !b.curr_size) return !a.curr_size && !b.curr_size;
size_t n{0};
for (size_t i{0}; i < a.table_size; ++i) {
if (a.table[i].mode == Mode::used) {
if (b.count(a.table[i].key)) ++n;
}
}
return n > 0.9 * a.curr_size && n > 0.9 * b.curr_size;
}
z() ließe sich durch diverse Maßnahmen etwas effizienter machen (zb von vornherein abfragen, ob die Bedingung aufgrund der Größenverhältnisse überhaupt erfüllt sein kann, immer die kleinere Tabelle durchlaufen und in der größeren suchen, etc). Das war aber aufgrund der Laufzeitvorgabe in der Aufgabenstellung nicht erforderlich.
Termin 1B
bool y(const key_type &a, const key_type &b) const {
bool found_first{false};
for (size_type i{0}; i < table_size; ++i) {
if (table[i].mode == Mode::used) {
if (key_equal{}(table[i].key, a) || key_equal{}(table[i].key, b)) {
if (found_first) return true;
found_first = true;
} else if (found_first) {
return false;
}
}
}
return false;
}
Termin 1C
size_t x(const key_type &a, const key_type &b) const {
bool found_a{false}, found_b{false};
size_t rc{0};
for (size_type i{0}; i < table_size; ++i) {
if (table[i].mode == Mode::used) {
if (key_equal{}(table[i].key, a)) found_a = true;
if (key_equal{}(table[i].key, b)) found_b = true;
if (found_a && found_b) return rc;
if (found_a || found_b) ++rc;
}
}
throw std::runtime_error{"order 66"};
}
Mittels der folgenden Änderung in den Zeilen 6 und 7 können unnötige Schlüsselvergleiche eingespart werden.
if (!found_a && key_equal{}(table[i].key, a)) found_a = true;
if (!found_b && key_equal{}(table[i].key, b)) found_b = true;
Termin 2
Vorgangsweise am besten nach Anleitung (siehe Angabe), ausgenommen B+-Baum (da kann man einige Schritte einsparen).
Zusätzliche Instanzvariablen in der Klasse Iterator, der Einfachheit halber gleich initialisiert.
bool is_special{false};
value_type limit;
Zusätzlicher Konstruktor. Dieser ist eine Kopie des vorhandenen Konstruktors, der zusätzlich die neuen Instanzvariablen setzt und die Startposition mit Hilfe der schon vorhandenen privaten Methode skip() setzt. skip() müssen wir dann natürlich noch entsprechend modifizieren.
Iterator(element *pos, const value_type &limit): pos{pos}, is_special{true}, limit{limit} { if (pos) skip(); }
Die vorhandene Methode skip() zum Überspringen von leeren Tabellenpositionen wird nun modifiziert, sodass im Modus speziell auch unpassende Werte übersprungen werden. Verfügt ein Iterator noch nicht über eine solche Methode, dann kann eine solche implementiert werden, die dann im neuen Konstruktor und in den Inkrement-Operatoren im Modus speziell aufgerufen wird.
void skip() {
while (pos->mode != Mode::end && (pos->mode != Mode::used || (is_special && !std::less<value_type>{}(limit,pos->key)))) ++pos;
}
Die beiden operator++() rufen skip() ohnehin (direkt oder indirekt) auf und brauchen daher nicht modifiziert zu werden.
Alternative Standardvariante: Im operator++ eine Schleife vorsehen, die im Modus speziell die gesamte bisherige Funktionalität so lange durchführt, bis ein passender Wert oder das Ende erreicht ist. Diesen operator++ dann im Konstruktor aufrufen, sofern der aktuelle Wert nicht den Vorgaben entspricht.
Zu guter Letzt die neue Methode w() in ADS_set. Eine Kopie von begin(), die allerdings im Unterschied zu begin() den neuen Iterator-Konstruktor verwendet, um einen Iterator im Modus speziell zu erzeugen.
const_iterator w(const key_type &limit) const { return const_iterator{table, limit}; }
Termin 3
Vorgangsweise am besten nach Anleitung (siehe Angabe).
Eine zusätzliche Instanzvariable in der Klasse Iterator. Da bei n == 0 der Iterator "normal" funktioniert (also keine Werte übersprungen werden), reicht eine Instanzvariable:
size_t n;
Zusätzlicher Konstruktor, oder vorhandenen Konstruktor um Parameter n erweitern (wir entscheiden uns für letzteres):
explicit Iterator(element *pos = nullptr, size_t n = 0): pos{pos}, n{n} { if (pos) skip(); }
Den operator++() anpassen. In einer zusätzlichen Schleife werden bei jedem Aufruf n Werte übersprungen, es sei denn das Ende wird vorher erreicht:
Iterator& operator++() {
for (size_t i{0}; i <= n && pos->mode != Mode::end; ++i) { // NEU
++pos;
skip();
} // NEU
return *this;
}
Der operator++(int) ruft den operator++() auf und braucht daher nicht modifiziert zu werden.
Zu guter Letzt die neue Methode v() in ADS_set. Eine Kopie von begin(), die allerdings im Unterschied zu begin() den zusätzlichen Iterator-Konstruktor-Parameter verwendet, um einen Iterator im Modus speziell zu erzeugen.
const_iterator v(size_t n) const { return const_iterator{table, n}; }
Letzte Änderung: 25.09.2018, 21:31 | 905 Worte