Εργασία 3

Last updated on May 29, 2023

Ανακοινώθηκε: 29/5/2023
Προθεσμία παράδοσης: 2/7/2023 23:59
16% του συνολικού βαθμού στο μάθημα
Link εγγραφής: https://classroom.github.com/a/wO7TpuKZ
Repository: https://github.com/chatziko-k08/2023-project-3-<github-username>

Σημαντικό: διαβάστε τις οδηγίες (κοινές για όλες τις εργασίες). Περιέχουν μεταξύ άλλων και πληροφορίες για τη χρήση του git, η οποία είναι ολόιδια με τα εργαστήρια.

Στο μάθημα είδαμε την τεχνική του open addressing με linear probing στους πίνακες κατακερματισμού. Η απλή αυτή τεχνική αυτή εκμεταλλεύεται με βέλτιστο τρόπο την κρυφή μνήμη (cache) του υπολογιστή: όταν ψάχνουμε σε σειριακές θέσεις, μεγάλο ποσοστό των στοιχείων βρίσκονται ήδη στην cache από προηγούμενες αναγνώσεις και μπορούν να διαβαστούν γρήγορα. Από την άλλη, το βασικό πρόβλημα του open addressing με linear probing είναι η δημιουργία clusters που έχει ως αποτέλεσμα στοιχεία να τοποθετούνται μακριά από την κανονική τους θέση, κάνοντας την αναζήτηση πιο αργή.

Η εργασία αυτή έχει ως στόχο να βελτιώσουμε την τεχνική αυτή. Για κάθε θέση $i$, θεωρούμε ότι ένας προκαθορισμένος αριθμός από τις επόμενες θέσεις, μέχρι την $i + $ NEIGHBOURS, θεωρούνται γειτονικές της $i$. Ο στόχος είναι να φροντίσουμε ώστε κάθε στοιχείο $k$ θα τοποθετείται πάντα σε μια θέση γειτονική προς το $h(k)$, δηλαδή σε κοντινή απόσταση από την “κανονική” του θέση.

Άσκηση 1 (50%)

Η πρώτη ιδέα είναι απλή: θα φτιάξουμε μια υβριδική λύση που να συνδυάζει open addressing και separate chaining. Κατά κύριο λόγο τα στοιχεία θα αποθηκεύονται σε έναν πίνακα με open addressing, με έναν σημαντικό περιορισμό:

Όταν εισάγουμε ένα στοιχείο $k$ και υπάρχει ελεύθερη θέση γειτονική προς την $h(k)$, τότε τοποθετείται εκεί.
Αν όμως δεν υπάρχει γειτονική θέση, τότε δεν τοποθετούμε το στοιχείο στον πίνακα, αλλά δημιουργούμε ένα vector για τη θέση $h(k)$ (αν δεν υπάρχει ήδη), και τοποθετούμε εκεί το στοιχείο όπως θα κάναμε σε μια λύση separate chaining.

Κατά συνέπεια, για να αναζητήσουμε ένα στοιχείο $k$ ελέγχουμε την θέση $h(k)$, τις επόμενες NEIGHBOURS γειτονικές θέσεις, και τέλος το vector (αν υπάρχει).

Ας σημειωθεί ότι κατά τη διαγραφή δεν χρειάζεται πλέον να σημειώνουμε μια θέση ως DELETED. Αυτό χρειαζόταν για να γνωρίζουμε μέχρι που να συνεχίσουμε μια αναζήτηση, όμως τώρα μπορούμε πάντα να σταματήσουμε μετά από NEIGHBOURS αναζητήσεις, οπότε τις διεγραμμένες θέσεις μπορούμε απλά να τις σημειώσουμε ως EMPTY. Αν ένα στοιχείο βρίσκεται στο vector, απλά το αφαιρούμε.

Δημιουργήστε στο modules/UsingHybridHash/ADTMap.c μία υλοποίηση που να χρησιμοποιεί την παραπάνω υβριδική μέθοδο. Για το vector μπορείτε να χρησιμοποιήσετε την υλοποίηση από το lecture-code. Η υλοποίησή σας θα πρέπει να περνάει το αντίστοιχο test (tests/ADTMap_test.c) χωρίς leaks.

Στο README.md, περιγράψτε την πολυπλοκότητα των search και insert στην υλοποίηση αυτή, για όλους τους συνδυασμούς worst/average-case και real/amortized-time, και συγκρίνετέ τες με αυτή της κλασσικής υλοποίησης open addressing.

Άσκηση 2 (50%)

Στην άσκηση αυτή θα πάμε την ιδέα της προηγούμενης άσκησης ένα level παραπάνω: θα αφαιρέσουμε τελείως το vector, διατηρώντας όμως τον περιορισμό ότι κάθε στοιχείο $k$ θα τοποθετείται σε μια θέση γειτονική προς την $h(k)$. Τι θα συμβεί όμως αν δεν υπάρχει ελεύθερη τέτοια θέση; Θα δημιουργήσουμε μία!

Έστω για παράδειγμα ότι εισάγουμε το στοιχείο $k$ το οποίο πρέπει να μπει στη θέση $h(k)$. Αρχικά βρίσκουμε την επόμενη ελεύθερη θέση, έστω $e$. Αν η $e$ είναι γειτονική της $h(k)$ τότε απλά τοποθετείται εκεί. Αν όχι, τότε προσπαθούμε να ελευθερώσουμε μια θέση πιο κοντά στην $h(k)$. Eστω πχ ότι στη θέση $i$ (ανάμεσα στις $h(k)$ και $e$) βρίσκεται ένα στοιχείο $k'$ όπως φαίνεται στο παρακάτω σχήμα:

      [  ...  X   ...  k' ...  EMPTY ... ]
θέση         h(k)      i         e

Η θέση $i$ προφανώς είναι γειτονική της κανονικής θέσης $h(k’)$ του στοιχείου αυτού, αφού είναι τοποθετημένο εκεί. Αν και η $e$ είναι γενιτονική της $h(k’)$ τότε μπορούμε να μετακινήσουμε εκεί το $k'$ δημιουργώντας μια νέα ελεύθερη θέση $i$ πιο κοντά στην $h(k)$:

      [  ...  X  ... EMPTY ...   k'  ... ]
θέση         h(k)      i         e

Ο αλγόριθμος αυτός ονομάζεται Hopscotch hashing, και συνολικά λειτουργεί ως εξής για την εισαγωγή ενός στοιχείου $k$:

Ξεκινώντας από τη θέση $h(k)$ βρίσκουμε την επόμενη ελεύθερη θέση $e$
Οσο η ελεύθερη θέση $e$ δεν είναι γειτονική της $h(k)$ την μετακινούμε πιο κοντά ως εξής:
- Ελέγχουμε τις θέσεις ανάμεσα στα $h(k)$ και $e$
- Αν σε μια τέτοια θέση $i$ υπάρχει ένα στοιχείο $k'$ και η θέση $h(k’)$ είναι γειτονική της $e$, τότε μετακινούμε το στοιχείο στη θέση $e$ και θέτουμε $e = i$ αφού η $i$ ελευθερώθηκε, συνεχίζοντας τη διαδικασία μέχρι η $e$ να γίνει γειτονική της $h(k)$.
Τοποθετούμε το στοιχείο $k$ στη θέση $e$ (που πλέον είναι γειτονική της $h(k)$).

Τέλος, υπάρχουν δύο περιπτώσεις στις οποίες θα χρειαστεί να κάνουμε rehash:

Αν ο βαθμός πληρότητας του πίνακα (συνολικός αριθμός στοιχείων διά το μέγεθος) ξεπεράσει το 0.5, όπως και στους κλασσικούς πίνακες κατακερματισμού.
Αν η διαδικασία μετακίνησης της ελεύθερης θέσης $e$ αποτύχει, δηλαδή δεν μπορέσουμε να βρούμε στοιχείο $k'$ που να μετακινηθεί στην $e$.

Και στις δύο περιπτώσεις, το rehash γίνεται ως συνήθως: διπλασιάζουμε τον πίνακα, και εισάγουμε τα στοιχεία στις νέες τους θέσεις. Προσοχή όμως: η περίπτωση (2) μπορεί να ξανασυμβεί, οπότε ίσως χρειαστούμε παραπάνω από ένα διαδοχικά rehash!

Δημιουργήστε στο modules/UsingHopscotchHash/ADTMap.c μία υλοποίηση που να χρησιμοποιεί την παραπάνω δομή. Η υλοποίησή σας θα πρέπει να περνάει το αντίστοιχο test (tests/ADTMap_test.c) χωρίς leaks.

Tests και εκτέλεση στο github

Για να βεβαιωθείτε ότι ο κώδικας που παραδίδετε είναι σωστός, σε κάθε commit στο github γίνεται αυτόματα compilation και εκτελούνται τα tests. Τα αποτελέσματα του ελέγχου αυτού βρίσκονται στον παρακάτω σύνδεσμο:

https://github.com/chatziko-k08/2023-project-3-<github-username>/actions

Επιλέξτε το τελευταίο commit, μετά run-tests, και θα δείτε τα αποτελέσματα σε 4 ενότητες:

make UsingHybridHash_ADTMap_test
Run UsingHybridHash_ADTMap_test
make UsingHopscotchHash_ADTMap_test
Run UsingHopscotchHash_ADTMap_test

Καμία άσκηση δε θα γίνει δεκτή αν ο αντίστοιχος κώδικας δεν κάνει compile. Επίσης, καμία άσκηση δε θα θεωρηθεί πλήρως σωστή αν δεν περνάνε σωστά τα tests.