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 29.04. und 13.05.2022
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).
Download:
ADS_set.h (Funktionsumfang für die erste Projektphase)
Der Film zum Code:
«Aufzeichnung Teil 1 (29.04.2022)» (Handlung beginnt bei Minute 8:00)
Unterlagen zu Double Hashing siehe Unterlagen, Vorlesung Kapitel 3 Vektoren (ab Seite 14).
Abschlussklausur Termin 1
Es gibt viele zum Teil sehr unterschiedliche Herangehensweisen, die zum Teil Datenstruktur- und/oder Implementationsabhängig sind, zum Teil auch nicht. Im folgenden ist eine der Lösungsmöglichkeiten am Beispiel Double Hashing beschrieben.
Im wesentlichen ist der Iterator für den Modus speziell so umzubauen, dass beim "Weiterschalten" mittels operator++ nach current_size/2 Elementen zum letzten Element weitergeschaltet wird.
Der Iterator wird um zwei Instanzvariablen erweitert, die angeben, wie viele Elemente in der ersten Hälfte enthalten sind (n1) und wie viele Elemente dann bis zum letzten Element zu überspringen sind (n2).
size_t n1{0}, n2{0};
Wir erweitern den Konstruktor entsprechend:
explicit Iterator(Element *e = nullptr, size_t n1 = 0, size_t n2 = 0): e{e}, n1{n1}, n2{n2} { if (e) skip(); }
Der neue Konstruktor wird in z() verwendet.
const_iterator z() const { return const_iterator{table,current_size/2,current_size-current_size/2-1}; }
Beim letzten Parameter tritt hier für den Fall current_size == 0 ein Underflow auf. Das ist nicht schön, aber in unserer Version unproblematisch, da bei einem leeren ADS_set der Konstruktor einen end-Iterator erzeugt und der operator++ für diesen nicht aufgerufen werden darf.
Zu guter Letzt wird der operator++() erweitert.
Iterator &operator++() {
do { // NEU
++e;
skip();
} while (!(n1 && --n1) && (n2 && n2--)); // NEU
return *this;
}
Im wesentlichen wird der originale Iterator-Code in eine Schleife eingebettet, die im richtigen Augenblick n2 Elemente überspringt. Die Konstruktion (n1 && –n1) (analog für n2) verhindert, dass der Wert dekrementiert wird, wenn dieser bereits 0 ist, um underflows zu vermeiden, denn hier wäre das ungünstig.
Natürlich kann man das Überspringen auch in eine eigene Schleife auslagern und das Dekrementieren der Zählvariablen in eigenen Anweisungen durchführen, dass macht die Schleifenbedingung dann etwas übersichtlicher (siehe auch generische Lösungsmöglichkeiten).
Der Postfix-Operator verwendet den Präfix-Operator und braucht daher nicht geändert zu werden.
Abschlussklausur Termin 2
Die Aufgabe entspricht im wesentlichen der Aufgabe des Termin 1 (siehe oben). Abgesehen von y() können daher alle Änderungen von oben übernommen werden.
const_iterator y() const { return current_size < 3 ? end() : const_iterator{table,current_size/3,current_size-current_size/3}; }
Alternativ können natürlich auch die generischen Lösungsmöglichkeiten für Aufgabe 1 analog angepasst werden.
Abschlussklausur Termin 3
Die Aufgabe entspricht im wesentlichen der Aufgabe des Termin 1 (siehe oben). Abgesehen von x() und vom Konstruktor des Iterators (in dem die ersten current_size/4 bzw. n2 Werte übersprungen werden) können daher alle Änderungen von oben übernommen werden.
const_iterator x() const { return const_iterator{table,current_size-current_size/4,current_size/4}; }
explicit Iterator(Element *e = nullptr, size_t n1 = 0, size_t n2 = 0): e{e}, n1{n1}, n2{n2} {
if (e) skip();
for (auto i{n2}; i; --i) ++*this;
}
Alternativ können natürlich auch die generischen Lösungsmöglichkeiten für Aufgabe 1 analog angepasst werden.
Letzte Änderung: 06.02.2023, 17:53 | 486 Worte