Il termine Memoizzazione deriva dalla parola latina memorandum ( ricordare ), che nell'inglese americano viene comunemente abbreviato in memo, e che significa trasformare il risultato di una funzione in qualcosa da ricordare..

Nell'informatica, la memorizzazione viene utilizzata per accelerare i programmi del computer eliminando il calcolo ripetitivo dei risultati ed evitando chiamate ripetute a funzioni che elaborano lo stesso input.

Cos'è la memorizzazione

Sommario

• Cos'è la memorizzazione?
• Perché viene utilizzata la Memoizzazione>
• Dove utilizzare la memorizzazione?
• Tipi di memorizzazione
• Come viene utilizzata la tecnica di memorizzazione nella programmazione dinamica?
  • Approccio dall 'alto verso il basso
  • Approccio dal basso verso l'alto
• In che modo la memorizzazione è diversa dalla tabulazione?
• Problemi pratici di codifica per la memorizzazione
• Domande frequenti
  • 1) La memorizzazione è migliore della DP?
  • 2) La memorizzazione è la stessa cosa della memorizzazione nella cache?
  • 3) Perché la memorizzazione avviene dall'alto verso il basso?
  • 4) La memorizzazione utilizza la ricorsione?
  • 5) Dovrei usare la tabulazione o la memorizzazione?
  • 6) Dove viene utilizzata la memorizzazione?
  • 7) Perché si chiama memoizzazione?
  • 8) In che modo la memorizzazione riduce la complessità temporale?
  • 9) Qual è la differenza tra memoizzazione e memorizzazione nella cache?
  • 10) Perché la tabulazione è più veloce della memorizzazione?
• Conclusione

Perché viene utilizzata la Memoizzazione?

La memorizzazione è una forma specifica di memorizzazione nella cache che viene utilizzato in programmazione dinamica . Lo scopo della memorizzazione nella cache è migliorare le prestazioni dei nostri programmi e mantenere accessibili i dati che possono essere utilizzati in seguito. Fondamentalmente memorizza il risultato precedentemente calcolato del sottoproblema e utilizza il risultato memorizzato per lo stesso sottoproblema. Ciò elimina lo sforzo aggiuntivo di eseguire calcoli più e più volte per lo stesso problema. E sappiamo già che se lo stesso problema si verifica ancora e ancora, allora quel problema è di natura ricorsiva.

Dove utilizzare la memorizzazione?

Possiamo usare la tecnica di memorizzazione dove il utilizzo dei risultati precedentemente calcolati entra in scena. Questo tipo di problema viene utilizzato principalmente nel contesto di ricorsione , soprattutto con i problemi che comportano sottoproblemi sovrapposti .

Facciamo un esempio in cui lo stesso sottoproblema si ripete ancora e ancora.

Esempio per mostrare dove utilizzare la memorizzazione:

  Let us try to     find the factorial of a number    .>

Di seguito è riportato un metodo ricorsivo per trovare il fattoriale di un numero:

int fattoriale(unsigned int n)
{
se (n == 0)
ritorno 1;
return n * fattoriale(n – 1);
}

Cosa succede se utilizziamo questo metodo ricorsivo?

Se scrivi il codice completo per lo snippet sopra, noterai che ci saranno 2 metodi nel codice:

1. factorial(n) 2. main()>

Ora, se abbiamo più query per trovare il fattoriale, ad esempio trovare il fattoriale di 2, 3, 9 e 5, allora dovremo chiamare il metodo fattoriale() 4 volte:

factorial(2) factorial(3) factorial(9) factorial(5)>

Metodo ricorsivo per trovare il fattoriale

Quindi è sicuro affermare che per trovare il fattoriale dei numeri K numeri, la complessità temporale necessaria sarà O(N*K)

• SU) per trovare il fattoriale di un particolare numero, e
• FRECCIA) per chiamare il metodo fattoriale() K volte diverse.

In che modo la memorizzazione può aiutare con tali problemi?

Se notiamo nel problema precedente, durante il calcolo fattoriale di 9:

java come eseguire l'override

• Stiamo calcolando il fattoriale di 2
• Stiamo anche calcolando il fattoriale di 3,
• e stiamo calcolando anche il fattoriale di 5

Pertanto, se memorizziamo il risultato di ogni singolo fattoriale al primo momento del calcolo, possiamo facilmente restituire il fattoriale di qualsiasi numero richiesto in solo tempo O(1). Questo processo è noto come Memoizzazione .

Soluzione che utilizza la memoizzazione (come funziona la memoizzazione?):

Se troviamo prima il fattoriale di 9 e memorizziamo i risultati dei singoli sottoproblemi, possiamo facilmente stampare il fattoriale di ciascun input in O(1).

Pertanto la complessità temporale per trovare i numeri fattoriali utilizzando la memoizzazione sarà SU)

• SU) per trovare il fattoriale dell’input più grande
• O(1) per stampare il fattoriale di ciascun input.

Tipi di memorizzazione

L'implementazione della memorizzazione dipende dalla modifica dei parametri responsabili della risoluzione del problema. Esistono varie dimensioni di memorizzazione nella cache utilizzate nella tecnica di memorizzazione, di seguito ne vengono riportate alcune:

• Memoizzazione 1D: La funzione ricorsiva che ha un solo argomento il cui valore non è costante dopo ogni chiamata di funzione.
• Memoizzazione 2D: La funzione ricorsiva che ha solo due argomenti il ​​cui valore non era costante dopo ogni chiamata di funzione.
• Memoizzazione 3D : La funzione ricorsiva che ha solo tre argomenti i cui valori non erano costanti dopo ogni chiamata di funzione.

Come viene utilizzata la tecnica di memorizzazione nella programmazione dinamica?

La programmazione dinamica aiuta a risolvere in modo efficiente problemi che presentano sottoproblemi sovrapposti e proprietà della sottostruttura ottimali. L'idea alla base della programmazione dinamica è quella di suddividere il problema in sottoproblemi più piccoli e salvare il risultato per un uso futuro, eliminando così la necessità di calcolare ripetutamente il risultato.

Esistono due approcci per formulare una soluzione di programmazione dinamica:

1. Approccio dall 'alto verso il basso: Questo approccio segue il memorizzazione tecnica . Consiste in ricorsione E memorizzazione nella cache . Nel calcolo, la ricorsione rappresenta il processo di chiamata ripetuta di funzioni, mentre la cache si riferisce al processo di memorizzazione dei risultati intermedi.
2. Approccio dal basso verso l’alto: Questo approccio utilizza il tabulazione tecnica per implementare la soluzione di programmazione dinamica. Risolve gli stessi problemi di prima, ma senza ricorsione. In questo approccio, l’iterazione sostituisce la ricorsione. Pertanto, non vi è alcun errore di overflow dello stack o sovraccarico delle procedure ricorsive.

Come viene utilizzata la tecnica di memorizzazione nella programmazione dinamica

In che modo la memorizzazione è diversa dalla tabulazione?

Tabulazione vs Memoizzazione

Per maggiori dettagli consultare: Tabulazione vs. Memoizzazione

Problemi pratici di codifica sulla memorizzazione

Domande frequenti (FAQ) sulla memoizzazione

1: La memorizzazione è migliore della DP?

La memorizzazione è l'approccio top-down per risolvere un problema con la programmazione dinamica. Si chiama memoizzazione perché creeremo un promemoria per i valori restituiti dalla risoluzione di ciascun problema.

2: La memorizzazione è la stessa cosa della memorizzazione nella cache?

La memorizzazione è in realtà un tipo specifico di memorizzazione nella cache. Il termine caching può generalmente riferirsi a qualsiasi tecnica di memorizzazione (come il caching HTTP) per un uso futuro, ma la memorizzazione si riferisce più specificamente alla funzione di caching che restituisce il valore.

3: Perché la memorizzazione avviene dall'alto verso il basso?

L’approccio top-down suddivide il grande problema in molteplici sottoproblemi. se il sottoproblema è già risolto, riutilizzare la risposta. Altrimenti, risolvi il sottoproblema e memorizza il risultato in un po' di memoria.

java elseif

4: La memorizzazione utilizza la ricorsione?

La memorizzazione segue un approccio top-down per risolvere il problema. Consiste in ricorsione e memorizzazione nella cache. Nel calcolo, la ricorsione rappresenta il processo di chiamata ripetuta di funzioni, mentre la cache si riferisce al processo di memorizzazione dei risultati intermedi.

5: Dovrei usare la tabulazione o la memorizzazione?

Per i problemi che richiedono la risoluzione di tutti i sottoproblemi, la tabulazione in genere supera la memorizzazione di un fattore costante. Questo perché la tabulazione non ha un sovraccarico di ricorsione, il che riduce il tempo necessario per risolvere lo stack di chiamate di ricorsione dalla memoria dello stack.
Ogni volta che è necessario risolvere un sottoproblema affinché il problema originale possa essere risolto, la memorizzazione è preferibile poiché un sottoproblema viene risolto pigramente, ovvero vengono eseguiti solo i calcoli richiesti.

6: Dove viene utilizzata la memorizzazione?

La memorizzazione è una tecnica di ottimizzazione utilizzata per velocizzare i programmi del computer memorizzando nella cache i risultati di costose chiamate di funzioni e restituendoli quando si incontrano nuovamente gli stessi input.

7: Perché si chiama memorizzazione?

Il termine memoizzazione deriva dalla parola latina memorandum (ricordare), comunemente abbreviato in memo nell'inglese americano, e che significa trasformare i risultati di una funzione in qualcosa da ricordare.

8: In che modo la memorizzazione riduce la complessità temporale?

Risolvere ripetutamente lo stesso problema richiede tempo e aumenta la complessità di esecuzione dell'intero programma. Questo problema può essere risolto mantenendo una cache o memoria in cui memorizzeremo il risultato già calcolato del problema per qualche input particolare. In modo che se non vogliamo ricalcolare lo stesso problema, possiamo semplicemente utilizzare il risultato archiviato in memoria e ridurre la complessità temporale.

9: Qual è la differenza tra memorizzazione e memorizzazione nella cache?

La memorizzazione è in realtà un tipo specifico di memorizzazione nella cache che prevede la memorizzazione nella cache del valore restituito di una funzione in base all'input. La memorizzazione nella cache è un termine più generale. Ad esempio, la memorizzazione nella cache HTTP è la memorizzazione nella cache ma non la memorizzazione.

10: Perché la tabulazione è più veloce della memorizzazione?

La tabulazione è solitamente più veloce della memorizzazione, perché è iterativa e la risoluzione dei sottoproblemi non richiede un sovraccarico di chiamate ricorsive.

La memorizzazione è una tecnica utilizzata in informatica per accelerare l'esecuzione di funzioni ricorsive o computazionalmente costose memorizzando nella cache i risultati delle chiamate di funzione e restituendo i risultati memorizzati nella cache quando si verificano nuovamente gli stessi input.

L'idea di base della memorizzazione è memorizzare l'output di una funzione per un dato insieme di input e restituire il risultato memorizzato nella cache se la funzione viene richiamata nuovamente con gli stessi input. Questa tecnica può far risparmiare tempo di calcolo, soprattutto per le funzioni che vengono chiamate frequentemente o che hanno un'elevata complessità temporale.

Ecco una guida passo passo per implementare la memorizzazione:

Identifica la funzione che desideri ottimizzare utilizzando la memorizzazione. Questa funzione dovrebbe avere calcoli ripetuti e costosi per lo stesso input.

Crea un oggetto dizionario per archiviare i risultati della funzione memorizzati nella cache. Le chiavi del dizionario dovrebbero essere i parametri di input della funzione e i valori dovrebbero essere i risultati calcolati.

All'inizio della funzione, controlla se i parametri di input sono già presenti nel dizionario della cache. Se lo sono, restituisci il risultato memorizzato nella cache.

Se i parametri di input non sono nel dizionario della cache, calcola il risultato e memorizzalo nel dizionario della cache con i parametri di input come chiave.

Restituisce il risultato calcolato.

Ecco un esempio di codice Python per implementare la memorizzazione utilizzando un dizionario:

Python3

>

>

>

Nel codice sopra, definiamo una funzione chiamata Fibonacci che calcola l'ennesimo numero nella sequenza di Fibonacci. Usiamo un oggetto dizionario chiamato cache per memorizzare i risultati delle chiamate di funzione. Se il parametro di input n è già presente nel dizionario della cache, restituiamo il risultato memorizzato nella cache. Altrimenti, calcoliamo il risultato utilizzando chiamate ricorsive alla funzione Fibonacci e lo memorizziamo nel dizionario della cache prima di restituirlo.

La memorizzazione può essere utilizzata per ottimizzare le prestazioni di molte funzioni che richiedono calcoli ripetuti e costosi. Memorizzando nella cache i risultati delle chiamate di funzione, possiamo evitare calcoli non necessari e accelerare l'esecuzione della funzione.

Conclusione

La memorizzazione è un concetto di programmazione e può essere applicato a qualsiasi linguaggio di programmazione. Il suo obiettivo assoluto è ottimizzare il programma. Di solito, questo problema si verifica quando i programmi eseguono calcoli pesanti. Questa tecnica memorizza nella cache tutti i risultati precedenti calcolati in modo che non sia necessario ricalcolarli per lo stesso problema.

Articoli Correlati:

• Memoizzazione utilizzando decoratori in Python
• Memoizzazione JavaScript