Una guida all'algoritmo della finestra scorrevole e come implementarlo in Go

Eseguire operazioni su sequenze di numeri e caratteri è un aspetto cruciale della programmazione. L'algoritmo della finestra scorrevole è uno degli algoritmi standard per farlo.

È una soluzione elegante e versatile che ha trovato la sua strada in più domini. Dalla manipolazione delle stringhe agli attraversamenti degli array e all'ottimizzazione delle prestazioni, questo algoritmo può svolgere un ruolo.

Quindi, come funziona l'algoritmo della finestra scorrevole e come puoi implementarlo in Go?

Comprensione dell'algoritmo della finestra scorrevole

Ci sono molti dei migliori algoritmi che sono utili da conoscere come programmatore, e la finestra scorrevole è una di queste. Questo algoritmo ruota attorno al semplice concetto di mantenere una finestra dinamica su una sequenza di dati, per elaborare e analizzare in modo efficiente sottoinsiemi di tali dati.

È possibile applicare l'algoritmo durante la risoluzione di problemi computazionali che coinvolgono matrici, stringhe o sequenze di dati.

L'idea centrale dietro l'algoritmo della finestra scorrevole è definire una finestra di dimensione fissa o variabile e spostarla attraverso i dati di input. Ciò consente di esplorare diversi sottoinsiemi dell'input senza calcoli ridondanti che possono ostacolare le prestazioni.

Ecco una rappresentazione visiva di come funziona:

I confini della finestra possono essere adattati in base ai requisiti specifici del problema.

Implementazione dell'algoritmo della finestra scorrevole in Go

Puoi utilizzare un problema di codifica popolare per scoprire come funziona l'algoritmo della finestra scorrevole: trovare la somma più grande di un sottoarray con una determinata lunghezza.

Lo scopo di questo problema di esempio è trovare il sottoarray di dimensione K i cui elementi si sommano al massimo valore. La funzione di soluzione accetta due parametri: l'array di input e un intero positivo che rappresenta K.

Lascia che l'array di esempio sia numeri, come mostra il codice seguente:

nums := []int{1, 5, 4, 8, 7, 1, 9}

E lascia che la lunghezza del sottoarray sia K, con un valore pari a 3:

k := 3

È quindi possibile dichiarare una funzione per trovare la somma massima di sottoarray con lunghezza k:

funcmaximumSubarraySum(nums []int, k int)int {
// body
}

Potresti pensare che la finestra debba essere un array che memorizza copie degli elementi di destinazione. Anche se questa è un’opzione, funziona male.

Invece, devi solo definire i confini della finestra per tenerne traccia. Ad esempio, in questo caso, la prima finestra avrà un indice iniziale di 0 e un indice finale di k-1. Nel processo di scorrimento della finestra, aggiornerai questi confini.

Il primo passo per risolvere questo problema è ottenere la somma del primo sottoarray di dimensione k. Aggiungi il seguente codice alla tua funzione:

var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
}
maxSum = windowSum

Il codice sopra dichiara le variabili necessarie per l'algoritmo e trova la somma della prima finestra nell'array. Quindi si inizializza somma max con la somma della prima finestra.

Il prossimo passo è far scorrere la finestra eseguendo l'iterazione del file numeri array da indice K all'estremità. In ogni fase di scorrimento della finestra:

1. Aggiornamento windowSum aggiungendo l'elemento corrente e sottraendo l'elemento a finestraInizio.
2. Aggiornamento somma max se il nuovo valore di windowSum è maggiore di esso.

Il codice seguente implementa la finestra scorrevole. Aggiungilo al massimaSubarraySum funzione.

for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++
}

Una volta completato il ciclo, avrai la somma più grande somma max, che puoi restituire come risultato della funzione:

return maxSum

La tua funzione completa dovrebbe assomigliare a questa:

funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
 windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
 }
 maxSum = windowSum
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++ 
 }
return maxSum
}

È possibile definire una funzione principale per testare l'algoritmo, utilizzando i valori di numeri E K da prima:

funcmain() {
 nums := []int{1, 5, 4, 8, 7, 1, 9}
 k := 3
 fmt.Println(maximumSubarraySum(nums, k))
}

L'output in questo caso sarà 19, che è la somma del sottoarray [4, 8, 7], che è il più grande.

Ora puoi applicare la stessa tecnica a problemi simili, anche in altri linguaggi, come gestire elementi ripetuti all'interno di una finestra utilizzando un file Mappa hash Java, Per esempio.

Gli algoritmi ottimali si traducono in applicazioni efficienti

Questo algoritmo testimonia il potere delle soluzioni efficienti quando si tratta di risolvere i problemi. La finestra scorrevole massimizza le prestazioni ed elimina calcoli non necessari.

Una solida conoscenza dell'algoritmo della finestra scorrevole e della sua implementazione in Go ti consente di affrontare scenari del mondo reale durante la creazione di applicazioni.