Εργασία 3

Last updated on Jun 21, 2024
  • Ανακοινώθηκε: 20/6/2024
  • Προθεσμία παράδοσης: 17/7/2024 23:59
  • 16% του συνολικού βαθμού στο μάθημα
  • Link εγγραφής: https://classroom.github.com/a/gdiqJoQW
  • Repository: https://github.com/chatziko-k08/2024-project-3-<github-username>

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

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

Η ιδέα είναι πολύ απλή: διπλασιάζουμε το μέγεθος του πίνακα όπως και στο συνηθισμένο rehash, αλλά αντί να αντιγράψουμε εκεί όλα τα στοιχεία, αντιγράφουμε μόνο τα στοιχεία από τις δύο πρώτες θέσεις του πίνακα (αν υπάρχουν στοιχεία εκεί), και τα υπόλοιπα τα κρατάμε στον παλιό. Στη συνέχεια, στο επόμενο insert αντιγράφουμε τα στοιχεία από τις επόμενες δύο θέσεις, κλπ, ώστε τελικά όλα τα στοιχεία να αντιγραφούν αλλά σταδιακά. Μέχρι να γεμίσει ξανά ο πίνακας εμείς θα έχουμε μεταφέρει όλα τα στοιχεία, και στον επόμενο διπλασιασμό ξενικάμε ξανά.

Αυτό σημαίνει ότι ανά πάσα στιγμή έχουμε στοιχεία σε δύο πίνακες, τον τρέχοντα πίνακα array μεγέθους capacity, και τον παλιό πίνακα old_array μεγέθους old_capacity. Όλες οι λειτουργίες θα πρέπει να λαμβάνουν υπόψη και τους δύο πίνακες, το οποίο είναι απλό: πχ κατά την αναζήτηση ψάχνουμε πρώτα στον έναν πίνακα, και αν δεν βρούμε το στοιχείο ψάχνουμε και στον άλλο. Προσοχή επίσης στην map_next, πρέπει πρώτα τα διασχίσει τον ένα πίνακα και μετά τον άλλο.

Φύσικα όλα αυτά γίνονται “κρυφά από το χρήστη”, όπως σε όλες τις υλοποιήσεις των ADTs. Ο χρήστης βλέπει ένα ADP Map με τις συνηθισμένες λειτουργίες, χωρίς να γνωρίζει τι συμβαίνει από πίσω.

Στον modules/UsingHashTable/ADTMap.c υπάρχει η υλοποίηση του ADT Map με πίνακα κατακερματισμού από το lecture-code, στην οποία έχουν προστεθεί τα πεδία old_table, old_capacity, και έχει αφαιρεθεί η λειτουργία του rehash. Εσείς πρέπει να προσθέσετε τη λειτουργία του incremental rehash, και να τροποποιήσετε τις λειτουργίες κατάλληλα. Μπορείτε φυσικά να προσθέσετε όσα επιπλέον πεδία χρειαστείτε.

Το test είναι ως συνήθως στο tests/ADTMap_test.c, το τρέχετε με make run.

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

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

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

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

  • make UsingHashTable_ADTMap_test
  • Run UsingHashTable_ADTMap_test

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