Convertitevi! – Workshop 1

Translate To English!

Introduzione

Benvenuti!

Come promesso iniziamo una piccola serie di articoli per approfondire, e proporre adeguate soluzioni, riguardo un problema apparentemente semplice/banale, ma che nasconde caratteristiche estremamente interessanti.

Il problema è molto semplice: data una lista di stringhe, convertirle in maiuscolo in modo alterno (la prima, la terza, etc…). Ovviamente cercando di risolvere il problema con algoritmi “funzionali”, cercando quindi, per quanto possibile, di staccarci dagli algoritmi e funzioni tipiche dei linguaggi imperativi.

Facciamo un esempio (in Pure Basic, perchè molto semplice e di facile comprensione):

dim myList$(6)
myList$(1) = "string 1"
myList$(2) = "string 2"
myList$(3) = "string 3"
myList$(4) = "string 4"
myList$(5) = "string 5"
myList$(6) = "string 6"

for i=1 to 6 step 2
  myList$(i) = uppercase(myList$(i))
next

Analizziamo il problema…

Il programma sopra mostrato, in Pure Basic, è semplice e veloce. Provare però ad affrontarlo senza l’uso di un ciclo for… step può nascondere difficoltà non previste. Talvolta il problema non si pone nel trovare un algoritmo in sè, ma quanto alla sua ottimizzazione, in termini di eleganza / performance / compattezza del codice / etc…

Il problema è riuscire a trovare quale sia la posizione dell’elemento che siamo analizzando, per decidere poi se convertirlo oppure no.
Ciò di cui abbiamo bisogno allora è:

1) capire quali elementi dobbiamo convertire. E’ facile constatare che, nel nostro caso, si tratta di elementi posizionati in “caselle” dispari (posizione 1, posizione 3, posizione 5, etc…). Dobbiamo quindi trovare un algoritmo per “scoprire” quali numeri sono dispari.

Dopo alcuni giorni di brain-storming sul forum di newLisp (vedi qui: http://www.alh.net/newlisp/phpbb/viewtopic.php?t=2574&postdays=0&postorder=asc&start=0) sono venute fuori diverse soluzioni. Vediamole una per una, verificando anche altri fattori come, ad esempio, le performance.

ALGORITMO -1-

(define (even? x)
    (= (/ x 2) (div x 2) ) )

(define (odd? x)
    (!= (/ x 2) (div x 2) ) )

ALGORITMO -2-

(define (odd? num)
    ( (bits num true) 0) )

(define (even? num)
    (not ( (bits num true) 0) ) )

ALGORITMO -3- (versione semplificata dell’ALGORITMO 2)

; Bit test per posizione.
(define (bit? pos num)
    (bits num true) pos)

(define (odd? num)
    (bit? 0 num) )

(define (even? num)
    (not (bit? 0 num) ) )

ALGORITMO -4-

(define (odd? num)
    (= (& num 1) 1) )

(define (odd? num)
    (= (& num 1) 0) )

Ok, già da questa prima lista possiamo vedere come, per un’attività semplice come verificare se un numero è pari o dispari si possano adottare diverse tecniche. Il secondo algoritmo (ed il terzo) sono interessanti perchè mettono in evidenza un fatto: un algoritmo può essere un pò più lento (il terzo) ma anche più leggibile.

Facciamo un controllo preliminare sulle performance. Ho usato questo piccolo script newLisp (potete usarlo per fare i vostri tests):

(define (bit? pos num)
    (bits num true) pos)

(define (even-1? x)
  (= (/ x 2) (div x 2) ) )

(define (even-2? num)
    (not ( (bits num true) 0) ) )

(define (even-3? num)
    (not (bit? 0 num) ) )

(define (even-4? num)
    (= (& num 1) 0) )

;==============================================================

(setq start (time-of-day))
(dotimes (x 1000000)
    (even-1? x)
)
(println "Risultato 1: " (- (time-of-day) start) )

(setq start (time-of-day))
(dotimes (x 1000000)
    (even-2? x)
)
(println "Risultato 2: " (- (time-of-day) start) )

(setq start (time-of-day))
(dotimes (x 1000000)
    (even-3? x)
)
(println "Risultato 3: " (- (time-of-day) start) )

(setq start (time-of-day))
(dotimes (x 1000000)
    (even-4? x)
)
(println "Risultato 4: " (- (time-of-day) start)

Questi sono i risultati che ho avuto sul mio PC (ho lanciato i tests tre volte, solo sulle funzioni per il calcolo dei numeri pari):

Risultato 1: 459 / 445 / 437 – MEDIA = 447
Risultato 2: 855 / 857 / 870 – MEDIA = 860
Risultato 3: 1022 / 976 / 976 – MEDIA = 991
Risultato 4: 298 / 301 / 294 – MEDIA = 297

Mi ha colpito il primo risultato: pensavo che l’uso della divisione avrebbe alzato i tempi di calcolo, invece si è rivelato un algoritmo piuttosto efficiente. Il migliore però è l’ultimo: il calcolo di un AND logico tra i bit è velocissimo! Al contrario mi sarei aspettato buone performance dall’algoritmo 2, mentre è risultato molto lento!

Chiudiamo quindi questa prima parte del workshop, valutando i seguenti punti:

1. Quali algoritmi sono più leggibili, quindi comprensibili a chi non li conosce?
2. Quali operazioni sono risultate più veloci?
3. Alcuni algoritmi portano a risultati inaspettati.
4. Notate che alcuni algoritmi forniranno risultati differenti per la funzione (odd?) e per la (even?), in quanto non usano le stesse istruzioni (un esempio è l’algoritmo 2, in quanto uno include anche un not).

Per ora è tutto. Questo articolo introduttivo vi offre un assaggio di quello che saranno i prossimi workshop: vi garantisco che questo è solo l’inizio, e per i prossimi articoli ci sarà molta carne al fuoco, molti algoritmi, performance molto diverse, algoritmi più o meno comprensibili ed eleganti (alcuni degni di un’opera d’arte!).

Alla prossima!

Convertitevi!

Translate To English!

Poco tempo fà ho avuto una interessante riflessione con un mio amico, sui possibili modi per implementare, in newLisp, alcuni algoritmi usati nei linguaggi imperativi. newLisp infatti fornisce molti strumenti, molti dei quali, lo fanno somigliare ad un linguaggio imperativo e non ad uno funzionale. Questo è vero sopratutto per persone come me, che provengono da linguaggi come il Pascal, Java, C, assembler, etc…

Talvolta è difficile affrontare un problema togliendosi dalla testa molti dei concetti/esperienze accumulate sui linguaggi imperativi.

Abbiamo quindi provato ad affrontare un semplice problema, risolvendolo in “modo imperativo” e in “modo funzionale”. Ho poi chiesto consiglio/aiuto anche sul forum ufficiale di newLisp, e mi sono state fornite soluzioni fantastiche! Ho imparato moltissimo da questo esercizio.

Nei prossimi giorni scriverò un paio di workshops proprio per descrivere e spiegare le soluzioni trovate.

Il problema che doveva essere risolto era apparentemente banale ma molto stuzzicante:
avendo a disposizione una lista di stringhe minuscole, dovevamo convertire in maiuscolo solo le stringhe in posizione dispari (1, 3, 5, etc…). Esempio:

"a" "b" "c" "d" "e" "f" "g" --> "A" "b" "C" "d" "E" "f" "G"

Ovviamente abbiamo cercato di risolvere il problema in newLisp evitando l’uso dei classici cicli FOR, WHILE, etc… ma piuttosto usando un metodo più “funzionale” (uso di funzioni mappate sulla stringa, indici impliciti, etc…).

Sono venute fuori delle soluzioni incredibili! Ce ne sono di cose da imparare!

Ci rivedremo nei prossimi giorni, e nel frattempo provate anche voi a risolvere l’esercizio!