4.1 Definizione della memoizzazione e i suoi concetti fondamentali
Memoizzazione — è una tecnica di ottimizzazione che prevede la memorizzazione dei risultati di funzioni costose per poterli riutilizzare in chiamate successive con gli stessi argomenti. Questo riduce il numero di ricalcoli, aumentando così le prestazioni.
Concetti fondamentali:
1. Caching:
Memorizzare i risultati di una funzione in una struttura di dati (ad esempio, in un dizionario o in un array) in modo che, quando viene richiamata con gli stessi argomenti, possa restituire il risultato già salvato invece di ricalcolarlo.
2. Tabella di ricerca (Lookup Table):
Struttura di dati utilizzata per memorizzare i risultati delle chiamate precedenti alla funzione. Può essere una hash table (dizionario) o un array.
3. Chiamate ricorsive:
La memoizzazione è particolarmente utile per le funzioni ricorsive, dove le stesse sotto-attività possono essere eseguite più volte con gli stessi parametri.
Complessità temporale e spaziale degli algoritmi ottimizzati:
Complessità temporale:
Per molti problemi ricorsivi, la memoizzazione riduce la complessità temporale grazie
alla diminuzione del numero di ricalcoli. Ad esempio, il calcolo ricorsivo
dei numeri di Fibonacci ha una complessità temporale O(2^n), mentre con la memoizzazione è O(n).
Complessità spaziale:
La complessità spaziale aumenta a causa dell'archiviazione dei risultati
nella cache. Solitamente è O(n) per un problema che richiede memoizzazione.
Riassunto:
La memoizzazione è una potente tecnica di ottimizzazione per algoritmi ricorsivi, permettendo di migliorare significativamente le loro prestazioni attraverso la riduzione del numero di ricalcoli.
È particolarmente utile per problemi in cui le stesse sotto-attività vengono eseguite ripetutamente con gli stessi parametri. Comprendere i concetti di memoizzazione e applicarli nella pratica consente
di risolvere in modo efficace problemi con un elevato carico computazionale.
4.2 Esempi di ottimizzazione
Esempi di ottimizzazione di algoritmi ricorsivi tramite memoizzazione
Esempio 1: Numeri di Fibonacci
L'algoritmo ricorsivo per calcolare i numeri di Fibonacci senza memoizzazione ha una complessità temporale esponenziale. Usare la memoizzazione migliora notevolmente le prestazioni.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Esempio di utilizzo:
print(fibonacci(10)) # Output: 55
Importante! Notare che usiamo
memo=None come valore di default, e poi creiamo
un dizionario vuoto all'interno della funzione se memo non è passato. Questo
permette di evitare problemi con un oggetto modificabile come valore di default.
Esempio 2: Somma dei sottoinsiemi
Bisogna determinare se esiste un sottoinsieme di un insieme dato, la cui somma degli elementi sia uguale a un valore specificato.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# Esempio di utilizzo:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Output: True
La memoizzazione è di fatto il caching dei risultati delle sotto-attività.
Ad esempio, il numero di Fibonacci F(10) == F(9) + F(8), ma per
calcolare F(9), bisogna calcolare F(8) e
F(7). Cioè, F(8) dobbiamo calcolarlo due volte: come primo
addendo per F(9) e come secondo addendo per F(10). Per non calcolarlo
due volte, è necessario memorizzarlo nella cache dopo il primo calcolo.
GO TO FULL VERSION