Εργασία 3

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

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

Στο μάθημα είδαμε ότι ένας πίνακας κατακερματισμού μας επιτρέπει να αναζητούμε στοιχεία σε σταθερό χρόνο, το οποίο είναι εξαιρετικό επίτευγμα. Αλλά με μια σημαντική λεπτομέρεια: η πολυπλοκότητα αυτή είναι average case. Στη χειρότερη περίπτωση (worst case), η αναζήτηση είναι $O(n)$, πολύ πιο αργή. Στην πράξη αυτό συνήθως δεν είναι πρόβλημα, μας αρκεί να είμαστε αποδοτικοί στη μέση περίπτωση. Σε αρκετές εφαρμογές όμως η γραμμική worst-case πολυπλοκότητα μπορεί να είναι απαγορευτική.

Η εργασία αυτή έρχεται να απαντήσει στο ερώτημα: μπορούμε να κάνουμε τη worst-case αναζήτηση πιο γρήγορη;

Άσκηση 1 (40%)

Η πρώτη ιδέα είναι απλή: θα χρησιμοποιήσουμε τη λύση του separate chaining, αλλά αντί τα στοιχεία κάθε κάδου να τοποθετούνται σε μία λίστα, θα τα προσθέτουμε σε ένα ADT Set, επιλέγοντας φυσικά μια υλοποίηση του ADT Set η οποία να παρέχει worst-case αναζήτηση καλύτερη από $O(n)$. Έτσι, ακόμα και αν υπερβολικά πολλά στοιχεία τοποθετηθούν στον ίδιο κάδο, η αναζήτηση θα συνεχίσει να είναι αποδοτική.

Το αρνητικό μίας τέτοιας λύσης είναι ότι στη μεγάλη πλειοψηφία των περιπτώσεων, στον κάδο θα βρίσκονται λίγα αντικείμενα, και η εισαγωγή στο Set ενδέχεται να δημιουργεί καθυστέρηση (λόγω των επιπλέον malloc, κλπ). Σαν optimization, λοιπόν, θα κρατάμε τα πρώτα FIXED_SIZE (πχ τα πρώτα 3) στοιχεία κάθε κάδου σε ένα array, και μόνο αν έχουμε περισσότερα θα τα εισάγουμε στο Set.

Δημιουργήστε στο modules/UsingHashWithSet/ADTMap.c μία υλοποίηση που να χρησιμοποιεί την παραπάνω παραλλαγή του separate chaining. Μπορείτε να χρησιμοποιήσετε οποιαδήποτε υλοποίηση του ADT Set επιθυμείτε από το lecture-code. Η υλοποίησή σας θα πρέπει να περνάει το αντίστοιχο test (tests/ADTMap_test.c) χωρίς leaks.

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

Άσκηση 2 (60%)

Η χρήση ενός ADT Set της προηγούμενης άσκησης, βελτιώνει μεν τη worst-case πολυπλοκότητα, αλλά αυτή εξακολουθεί να μην είναι σταθερή. Το ερώτημα λοιπόν είναι, μπορούμε να πετύχουμε αναζήτηση σε worst-case $O(1)$;

Μπορεί να ακούγεται παράδοξο, αλλά η απάντηση είναι ΝΑΙ, χρησιμοποιώντας μια σχετικά απλή λύση που ονομάζεται κατακερματισμός του Κούκου (Cuckoo hashing). Η βασική ιδέα είναι ότι αντί να έχουμε έναν πίνακα κατακερματισμού $Τ$, και μια συνάρτηση κατακερματισμού $h$ (όπως στην κλασσική περίπτωση), θα έχουμε δύο πίνακες και δύο συναρτήσεις: $Τ_1,Τ_2$ και $h_1,h_2$. Ένα κλειδί $k$, αντί να έχει μία θέση $Τ[h(k)]$, θα έχει δύο: είτε θα βρίσκεται στη θέση $T_1[h_1(k)]$, είτε στη θέση $Τ_2[h_2(k)]$.

Η δεύτερη πολύ σημαντική διαφορά από τους κλασσικούς πίνακες κατακερματισμού είναι ότι κάθε στοιχείο $k$ θα βρίσκεται πάντα σε μία από τις δύο αυτές θέσεις! Ποτέ κάπου αλλού! Οπότε η αναζήτησή του θα είναι προφανώς $Ο(1)$, ακόμα και στη χειρότερη περίπτωση.

Ωραίο ακούγεται αυτό, αλλά τι θα συμβεί στην περίπτωση συγκρούσεων; Οι θέσεις αυτές, ναι μεν είναι δύο, αλλά κάλλιστα μπορεί και οι δύο να είναι γεμάτες όταν κάνουμε μια εισαγωγή. Πρέπει λοιπόν να χειριστούμε τις εισαγωγές με έξυπνο τρόπο:

• Έστω ότι θέλουμε να εισάγουμε ένα στοιχείο $k_1$. Το στοιχείο αυτό πάντα θα τοποθετείται στη θέση του στον πρώτο πίνακα, δηλαδή στη θέση $T_1[h_1(k_2)]$. Αν η θέση αυτή ήταν κενή τότε τελειώσαμε.

• Αν η θέση ήταν κατειλημμένη από κάποιο άλλο στοιχείο $k_2$ (για το οποίο προφανώς ισχύει $h_1(k_1) = h_1(k_2)$), εμείς δεν ψάχνουμε άλλη θέση, αλλά εισάγουμε το $k_1$ πάρα ταύτα, διώχνοντας ουσιαστικά το $k_2$.

• Φυσικά το $k_2$ δεν μπορεί να χαθεί, αλλά για αυτό ακριβώς τον σκοπό έχουμε τον δεύτερο πίνακα! Θα το βάλουμε στη δεύτερη θέση του, δηλαδή στη θέση $T_2[h_2(k_2)]$, η οποία πιθανόν να είναι κενή.

• Αν πάλι δεν είναι, και υπάρχει εκεί ένα στοιχείο $k_3$, τότε διώχνουμε το $k_3$ και το τοποθετούμε στον πρώτο πίνακα. Η ίδια διαδικασία συνεχίζεται, διώχνοντας κάθε φορά το υπάρχον στοιχείο, και τοποθετώντας το στον άλλο πίνακα, μέχρι να βρούμε κάποια θέση που να είναι κενή.

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

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

2. Αν η διαδικασία εισαγωγής πέσει σε κύκλο: αν δηλαδή φτάσουμε σε κάποιο στοιχείο $k_n$, το οποίο στη θέση που προσπαθούμε να το βάλουμε, βρίσκεται κάποιο στοιχείο που έχουμε ήδη μετακινήσει! Ένας απλός τρόπος να εντοπίσουμε τέτοιους κύκλους είναι να μετράμε τον αριθμό στοιχείων που μετακινήθηκαν. Αν φτάσουμε στα $n$ (όσα τα συνολικά στοιχεία που υπάρχουν στον πίνακα), τότε αναγκαστικά υπάρχει κύκλος.

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

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

Για συναρτήσεις κατακερματισμού μπορείτε να χρησιμοποιήσετε τις παρακάτω: $$ \begin{align} h_1(k) &= h(k) \mod M \\
h_2(k) &= \frac{h^2(k)}{M} \mod M \end{align} $$ όπου $h(k)$ είναι η συνάρτηση που δίνει ο χρήστης (δείτε το modules/UsingHashTable/ADTMap.c) και $M$ το μέγεθος του πίνακα.

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

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

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

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

• make UsingHashWithSet_ADTMap_test
• Run UsingHashWithSet_ADTMap_test
• make UsingCuckooHash_ADTMap_test
• Run UsingCuckooHash_ADTMap_test

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