Słowniki z haszowaniem (algorytmy w Pythonie; projekt)

Wariant podstawy (na oceny 3,5 z algorytmów)

Należy zaimplementować dwa słowniki, używające haszowania i rozwiązujące kolizje za pomocą:

1. metody łańcuchowej (tablica tablic albo list);
2. adresowania otwartego liniowego.

Za każdy słownik wystawiana jest osobna ocena.

Oba słowniki powinny oferować wszystkie 3 operacje słownikowe: insert, find, delete. Powinny one unikać duplikatów kluczy.

Dodatkowo należy opanować (ze zrozumieniem) teorię dotyczącą tych operacji (zasady działania, złożoności obliczeniowe czasowe i pamięciowe).

Rozszerzenia, na wyższe oceny z algorytmów

Każde z poniższych rozszerzeń umożliwia podwyższenie maksymalnej oceny, za słownik do którego to rozszerzenie zaaplikowano (za każdy ze słowników wystawiana jest osobna ocena).

Rozszerzenia obu słowników

Rehaszowanie (+1,5 do oceny)

Metody insert/delete w razie potrzeby (gdy jest w niej zbyt wiele/mało elementów) wykonują rehaszowanie, czyli dynamiczne zwiększają/zmniejszają tablicę, przepisując zawartości do nowego obszaru pamięci.

Rozszerzenia słownika z adresowaniem otwartym

Adresowanie podwójne (+0,5 do oceny)

Słownik używa adresowania podwójnego zamiast liniowego.

Usuwanie z przesuwaniem elementów (+1 do oceny)

Usuwanie z tablicy z adresowaniem liniowym, które przesuwa elementy zamiast specjalnie oznaczać komórki jako skasowane.

Robin-Hood hashing (+1,5 do oceny)

Słownik z adresowaniem liniowym używa Robin-Hood hashing.

Wymagania dotyczące programowania (wariant podstawowy, na ocenę 3)

Słowniki mogą implementować zwykły zbiór liczb całkowitych, nieujemnych.

Program powinien być napisany w sposób czytelny i zorientowany obiektowo. Ściślej, poszczególne operacje słownikowe powinny być zaimplementowanie jako metody klasy słownika. Nie wolno pomieszać kodu słownika z kodem programu demonstracyjnego/testującego. W celu sporządzenia ewentualnego wykresu, do kodu słownika można jedynie dodać licznik wykonanych operacji porównania kluczy.

Rozszerzenia, na wyższe oceny z programowania

Mapa klucz->wartość (+0,5 do oceny)

Każdy element jest parą klucz-wartość, zaś słowniki realizuje mapę klucz->wartość.

Dowolne typy kluczy (+0,5 do oceny)

Klucze (elementy w przypadku zbioru) mogą być dowolnych typów haszowalnych. Należy użyć wbudowanej funkcji hash do obliczania wartości funkcji haszującej.

Błędy komunikowane za pomocą wyjątków (+0,5 do oceny)

Błędy typu brak wyszukiwanego klucza powinny być komunikowane za pomocą wyjątków. Typy wyjątków powinny być takie same jak zgłaszają standardowe słowniki (dict, set) zawarte w pythonie.

Przeciążenie operatorów (+0,5 za każde dwa operatory, maksymalnie +1 do oceny)

Przeciążyć operatory i operacje takie jak: indeksowanie za pomocą [] (w przypadku mapy), del, in, len, str, repr, możliwość iterowania po słowniku (__iter__). Zachowanie operatorów powinno być takie samo jak w standardowych typach (dict, set).

Wykres zależności liczby porównań od liczby elementów w słowniku (+1 do oceny)

Należy wykonać wykres ilustrujący zależność: liczba elementów w słowniku -> średnia liczba porównań kluczy potrzebna by znaleźć element.

Do narysowania wykresów można użyć zewnętrznych bibliotek. Polecam bibliotekę matplotlib i samouczek dostępny na jej stronie domowej.

Dane do wykresu można spreparować następującym algorytmem:

1. Utwórz pusty słownik.

2. Dodaj do słownika element o wylosowanym kluczu.

   Uwaga: jeśli wylosowany klucz znajduje się już w słowniku (i jako duplikat nie zostałby dodany), to należy wylosować kolejny, do skutku.

3. Wylosuj kolejny klucz i wyszukaj go w słowniku. Zmierz liczbę porównań kluczy wykonaną przez operację wyszukiwania. Zapisz liczbę elementów znajdujących się w słowniku (x) oraz uzyskaną liczbę porównań (y). Te dwie liczby (x, y) stanowią pojedynczy punkt do wykresu.

   Uwaga: dla zmniejszenia przypadkowości można wylosować kilka kluczy i uśrednić uzyskane dla nich liczby porównań.

4. Wróć do punktu 2, chyba że w słowniku znajduje się już wystarczająco dużo elementów (np. 100000).

Uwaga: W punktach 2 i 3 zaleca się losowanie kluczy z możliwie dużego zakresu.

Wskazówka implementacyjna dotycząca oznaczania pustych oraz skasowanych komórek w tablicy z adresowaniem otwartym

Do oznaczania pustych oraz skasowanych komórek w tablicy z adresowaniem otwartym można użyć typu wyliczeniowego, który w Pythonie można uzyskać wykorzystując standardowy moduł enum.

Przykład (za każdym assert wstawiono wyrażenie, które jest prawdziwe):

from enum import Enum, auto

class Marker(Enum):
    Empty = auto(),
    Deleted = auto()
    
data = [Marker.Empty] * 10		# tablica 10 elementów oznaczonych jako puste
assert data[4] is Marker.Empty		# komórka o indeksie 4 jest oznaczona jako pusta
assert data[4] is not Marker.Deleted	# ale nie jest oznaczona jako skasowana
data[4] = 1				# wpisujemy 1 w komórkę o indeksie 4
assert data[4] is not Marker.Empty	# komórka o indeksie 4 nie jest więc już oznaczona jako pusta
assert data[4] is not Marker.Deleted	# ani skasowana
data[4] = Marker.Deleted		# oznaczamy komórkę jako skasowaną
assert data[4] is not Marker.Empty
assert data[4] is Marker.Deleted

Alternatywnie (w starszych wersjach Pythona, w których enum nie jest dostępny): W roli specjalnych markerów oznaczających puste oraz skasowane komórki w tablicy z adresowaniem otwartym można użyć pustych klas. Uwaga: chodzi o używanie klas samych w sobie (które w Pythonie są obiektami posiadającymi adres w pamięci), a nie obiektów tych klas.

Przykład (za każdym assert wstawiono wyrażenie, które jest prawdziwe):

class Empty: pass	# klasa do oznaczania komórek pustych
class Deleted: pass	# klasa do oznaczania komórek skasowanych

data = [Empty] * 10		# tablica 10 elementów, każdy jest klasą Empty.
# Uwaga: powyżej po słowie Empty nie ma nawiasów, więc nie tworzymy obiektów klasy Empty
assert data[4] is Empty		# komórka o indeksie 4 jest oznaczona jako pusta
# powyżej sprawdzane jest czy data[4] i Empty są tym samym, mają ten sam adres w pamięci
assert data[4] is not Deleted	# komórka o indeksie 4 nie jest oznaczona jako skasowana
data[4] = 1			# wpisujemy 1 w komórkę o indeksie 4
assert data[4] is not Empty	# komórka o indeksie 4 nie jest więc już oznaczona jako pusta
assert data[4] is not Deleted	# ani skasowana
data[4] = Deleted		# oznaczamy komórkę jako skasowaną
assert data[4] is not Empty
assert data[4] is Deleted

Przykładowe pytania sprawdzające z algorytmów

• Zilustrować działanie wskazanej operacji na zadanym przykładzie, np. jak będzie przebiegało wstawianie podanego klucza do słownika o podanej zawartości?
• Jaka jest złożoność czasowa wskazanej operacji? Wskazać miejsca w kodzie (pętle, rekurencje), które za to opowiadają.
• (dla słowników z rehaszowaniem) Jak na złożoność operacji wstawiania wpływają operacje wykonywane przez rehaszowanie? Jaka jest złożoność zamortyzowana?
• Jaka jest złożoność pamięciowa słownika?
• Jaka jest złożoność pamięciowa wskazanej operacji? Wskazać miejsca w kodzie gdzie alokowana jest pamięć (w jakiej ilości?).
• (w przypadku sporządzenia wykresów) Jakie wnioski można wyciągnąć ze wskazanego wykresu? Jak zmienia się liczba porównań wykonanych przez operację wyszukiwania w zależności od liczby wstawionych elementów? Postawić hipotezę, dlaczego uzyskano taką zależność?
• Czym różnią się komórki puste od skasowanych w słowniku z adresowaniem otwartym? Z czego wynika potrzeba ich rozróżniania?

Przykładowe pytania sprawdzające z programowania

• Wyjaśnić jak działa użyta w programie składnia Pythona albo funkcja.
• Za co odpowiedzialna jest w programie wskazana linia?