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.

[Projekt][FAQ]

Beispiel "Double Hashing"

"Live"-Implementierung aus den Lehrveranstaltungen vom 13. und 20.4.2018 (im SS 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:  
«Aufzeichnung Teil 1 13.4.» 
«Aufzeichnung Teil 2 20.4.» 
 
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 Projektabschlussklausur

Termin 1

friend double z(const ADS_set &a, const ADS_set &b) {
  if (!a.curr_size && !b.curr_size) return 1.;                       // 1
  size_t ab{0};                                                      // 2
  for (size_t i{0}; i < a.table_size; ++i)                           // 3
    if (a.table[i].mode == Mode::used)                               // 4
      if (b.count(a.table[i].key)) ++ab;                             // 5
  return ab / (static_cast<double>(a.curr_size) + b.curr_size - ab); // 6
}
 
Wenn beide ADS_sets leer sind, dann ist das Ergebnis laut Vorgabe 1 (1). In (3) und (4) werden alle Werte des ADS_sets a durchlaufen, dieser Teil ist je nach Datenstruktur anders zu implementieren. In (5) wird mittels count für jeden Wert in a überprüft, ob dieser Wert auch in b enthalten ist. ab enthält daher am Ende der Schleife die Kardinalität der Schnittmenge. Die Kardinalität der Vereinigungsmenge erhält man durch Addition der Kardinalitäten der beiden Mengen abzüglich der Kardinalität der Schnittmenge (da ja andernfalls jene Elemente, die in beiden Mengen enthalten sind, doppelt gezählt werden). Anders ausgedrückt: 
|A∪B|=|A|+|B|−|A∩B||A \cup B| = |A| + |B| - |A \cap B|
Mit Hilfe dieses Zusammenhangs wird das Ergebnis 
|A∩B||A∪B|=|A∩B||A|+|B|−|A∩B|\frac{|A \cap B|}{|A \cup B|} = \frac{|A \cap B|}{|A| + |B| - |A \cap B|}
in (6) unmittelbar berechnet.  
 
Wenn dieses Geheimwissen der Freimaurer gerade nicht verfügbar ist, dann kann man natürlich auch alle Bestandteile der Vereinigungsmenge eigens berechnen, also die Werte, die in a aber nicht in b enthalten sind (anb), die Werte, die in b aber nicht in a enthalten sind (bna) und die Menge der Werte, die sowohl in a als auch in b enthalten sind (Schnittmenge, ab). 
 
friend double z(const ADS_set &a, const ADS_set &b) {
  if (!a.curr_size && !b.curr_size) return 1.;
  size_t ab{0}, anb{0}, bna{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)) ++ab;
      else ++anb;
    }
  for (size_t i{0}; i < b.table_size; ++i)
    if (b.table[i].mode == Mode::used)
      if (!a.count(b.table[i].key)) ++bna;
  return ab / (static_cast<double>(anb) + ab + bna);
}
 
Die Berechnung muss natürlich in jedem Fall im Datentyp double erfolgen. 

Termin 2

size_t y() const {
  size_t max_len{0}, len{0};                                   // 1
  const key_type *pred{nullptr};                               // 2
  for (size_type i{0}; i < table_size; ++i) {                  // 3
    if (table[i].mode == Mode::used) {                         // 4
      if (pred && key_compare{}(*pred, table[i].key)) ++len;   // 5
      else len = 1;                                            // 6
      if (len > max_len) max_len = len;                        // 7
      pred = &table[i].key;                                    // 8
    }                                                          
  }                                                            
  return max_len;                                              // 9
}
 
Die Aktualisierung von max_len in (7) ist nicht die effizienteste Variante, aber sie erspart Extra-Code für die Behandlung von sortierten Teilfolgen am Ende der Gesamtfolge. 
 

Termin 3

key_type x() const {
  const key_type *left{nullptr}, *middle{nullptr}, *rc{nullptr};
  for (size_type i{0}; i < table_size; ++i) {
    if (table[i].mode == Mode::used) {
      if (left && middle && key_compare{}(*left, *middle) && key_compare{}(table[i].key,*middle) && (!rc || key_compare{}(*middle,*rc)))
        rc = middle;
      left = middle;
      middle = &table[i].key;
    }
  }
  if (!rc) throw std::runtime_error{"order 66"};
  return *rc;
}
Letzte Änderung: 26.02.2019, 21:06 | 705 Worte