Rimandando ad un altro post la discussione sul primo kata, comincio oggi a postare i risultati ottenuti effettuando il secondo. La specifica del problema è molto semplice (l'implementazione di binary search su un array di interi); la sostanza del kata, no. L'esercizio richiede in fatti di implementare la specifica in cinque modi differenti e, se da una parte è molto facile pensare agli approcci tradizionali (iterativo, ricorsivo, funzionale...), trovare nuove strategie risolutive non è affatto banale.
Oggi volevo presentare l'implementazione iterativa a cui sono arrivato (probabilmente niente di speciale ma, in puro stile kata, l'importante non è il risultato, ma la strada percorsa per giungervi... e vi assicuro che anche su una cosa così apparentemente banale, tale strada è stata costellata di tentativi ed errori).
Una premessa: tanto per semplificarmi la vita, ho deciso di affrontare questi kata utilizzando un linguaggio di programmazione che non conoscevo se non di nome: Ruby. Pertanto, a tutti i rubisti (con rispetto parlando) lì fuori: se doveste vedere qualcosa che non vi piace, non giratevi stizziti dall'altra parte; ogni consiglio è bene accetto ;-)
Ok, partiamo con il codice
def chop(i, a)
if a.size > 0
l_index = 0
r_index = a.size - 1
while r_index - l_index > 1
middle = ((r_index - l_index) / 2) + l_index
if a[middle] >= i
r_index = middle
else
l_index = middle
end
end
if a[l_index] == i
return l_index
elsif a[r_index] == i
return r_index
end
end
-1
end
L'implementazione è molto standard, con due indici per tenere traccia dell'inizio e della fine del sotto-array dell'iterazione corrente. Ed è proprio la gestione degli indici a farla da padrona fra le varie considerazioni che mi sono venute in mente effettuando questo kata.
- Il caso di dimensione 0 è triviale
- La divisione intera mi ritorna il valore middle approssimato per eccesso o per difetto? (come ho poi verificato, viene approssimato per eccesso, rendendo la dimensione 2 dell'array un caso particolare, alla stregua di dimensione 1 e 0. Infatti, con un array di due elementi, l'elemento middle diventa il secondo elemento - r_index -, e l'iterazione non va avanti)
- La condizione di terminazione del ciclo nasce proprio dalle considerazione al punto precedente: il ciclo deve terminare quando l'array contiene 0, 1 o 2 elementi
- Anche il blocco di controllo alle righe 15-19 nasce dalla considerazioni ai punti 1 e 2. Inizialmente pensavo che si potesse fare in modo che l'iterazione terminasse sempre puntando ad un singolo elemento dell'array e che dunque fosse necessario un solo controllo. Terminando sempre con due elementi (eventualmente coincidenti) i controlli da effettuare sono due: uno su a[l_index] e l'altro su a[r_index]. (nota: è possibile riprogettare l'algoritmo per farlo terminare sempre su un solo elemento?)
- L'uso dell'offset l_index alla riga 7 per puntare correttamente all'inizio del sotto-array non mi è venuto in mente subito...
Come si può vedere, anche un semplice esercizio come questo, nella sua incarnazione più semplice, ha portato a diverse considerazioni. Altra parte dell'esercizio sarà vedere se le considerazioni fatte adesso saranno d'aiuto nelle prossime implementazioni. Vedremo.
Per ora posso dire che i kata stanno facendo il loro dovere.
