Gabriele Lami
Co-founder @ Elif Lab : www.eliflab.com
Q è un linguaggio particolare, vive in una categoria diversa rispetto ai linguaggi più diffusi.
Diverso da Python, lontanissimo da Java, diverso da R e da C. Anche se funzionale è diverso da Haskell, Scala (nella sua componente funzionale) e da Lisp.
Ha una componente affine all’SQL ma solo in superficie perché è una felice fusione di un database con la scuola di linguaggi derivati dall’esoterico APL (A Programming Language).
È utile? Direi di sì; il database/interprete kdb+ (gratis nella sua versione a 32bit per uso non commerciale) permette di usare Q sia come linguaggio sia come strumento per gestire un database colonnare con performance notevoli (forse qualcosa di più).
È difficile? Certamente non è facile soprattutto se si hanno anni di esperienza in linguaggi imperativi e se non si conosce APL. È come passare dalla matematica al formalismo della logica, faticoso ma utile.
In questo post non sono interessato a mostrare le capacità di kdb+ perché il web è pieno (esagerazione letteraria) di materiale sul tema. Voglio invece provare ad utilizzare il linguaggio per cercare di formalizzare un problema matematico per fare un’indagine “sperimentale” sui numeri.
Questo post deriva dalla mia fase di apprendimento del linguaggio che è passata da un percorso in cui solitamente provo a riscrivere problemi che conosco bene in altri linguaggi.
Il problema
Il problema oggetto di questo post è la ricerca dei numeri felici.
I numeri felici sono particolari numeri interi che rispettano la seguente caratteristica:
1. se la somma dei quadrati delle cifre di un numero è uguale a 1 allora il numero è felice
100 -> 1² + 0² + 0² = 1
2. se la somma dei quadrati delle cifre di un numero è un numero felice allora il numero iniziale è felice
68 -> 6² + 8² = 36 64 = 100
Se un numero non è felice è ovviamente triste in questa visione duale della matematica emotiva.
L’implementazione in Q
Per calcolare la sequenza che porta alla felicità devo avere una funzione che, preso un numero intero positivo, calcola la somma dei quadrati delle cifre.
Un modo furbo di raggiungere questo obiettivo è quello di trattare il numero come stringa.
La stringa viene vista come lista di caratteri e ogni carattere viene trasformato in intero e elevato al quadrato.
32 → “32” → “3”, “2” → 3, 2
la sequenza dei quadrati viene sommata dalla seguente funzione:
st: {[xn] sum {“i”$xexp[;2] “I”$x} each string xn }
Non è probabilmente la migliore rappresentazione in Q, ma è più che utile allo scopo. Le graffe rappresentano lo scope di una funzione: se dopo la graffa aperta c’è qualcosa tra quadre è da considerarsi il nome della variabile di input (le variabili implicite, se non dichiarate, sono x, y z)
xn quindi è il numero in input. Q si legge da destra a sinistra quindi è molto facile capire cosa viene applicato a cosa (a meno di parentesi).
Xn (a destra) viene trasformato in “string” e alla stringa viene applicata la funzione:
{“i”$xexp[;2] “I”$x}
per ogni cifra grazie al comando “each”.
Questa funzione ha x come variabile di input. “I”$ converte x da stringa a intero.
All’intero che rappresenta una cifra viene quindi applicata la funzione xexp[;2] che eleva al quadrato il numero alla sua destra. Le quadre racchiudono l’input, anche se spesso non è necessario usarle. Il ; separa l’input. Nel caso specifico xexp[<base>;<esponente>] è la funzione utilizzata. Se, come nel caso di xexp[;2], non viene specificato un input, si ottiene come output una nuova funzione.
Le funzioni in Q possono essere infisse o prefisse; in questo caso ho scelto la versione prefissa di xexp per evitare parentesi, ma la stessa funzione è equivalente a
x xexp 2
La parte della funzione:
{“i”$xexp[;2] “I”$x} each string xn
ha come risultato la lista dei quadrati delle cifre
32 → [9, 4]
Come sommare tutti i numeri di una lista? Nel modo più naturale, con la funzione sum.
Abbiamo quindi una funzione che prende un numero e restituisce la somma dei quadrati delle cifre.
st 32 restituisce 13
A questo punto è necessario iterare la funzione fino a quando non si trova un 1.
Il problema di questa condizione di stop è che se il numero è triste il programma non finisce 🙁
Fortunatamente i numeri tristi hanno la caratteristica che, da un certo step in poi del processo, entrano in un loop:
8, 64, 52, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89, …
89 rappresenta l’inizio del loop per il numero (triste) 8.
Dato che per un numero felice il fatto di raggiungere 1 può essere visto come un loop,
1²=1 — -> 1² = 1 , ….
la condizione di stop quindi può essere il raggiungimento di un loop.
Data la condizione di stop che si vuole utilizzare, è necessario tenere tutta la sequenza generata da ogni iterazione (cosa utile anche per studiare i numeri felici/tristi).
Per raggiungere l’obiettivo si può usare una funzione come la seguente:
new_one: {x, st last x}
la virgola concatena due liste o una lista e un numero, quindi la lista x in input viene concatenata con il risultato della funzione st applicato all’ultimo (last) elemento della lista x.
Ora è necessario esprimere la condizione di stop:
cond: {not (last x) in -1_x}
Le funzioni in Q, una volta capita l’alchimia, tendono ad essere molto chiare (linguaggio dichiarativo). Procedi fino a che il “last x” (ultimo elemento che ho calcolato) non si ritrova nella lista x, tolto l’ultimo elemento -1_x.
Last prende l’ultimo numero della sequenza e 1_x prende la sequenza senza l’ultimo numero.
Come si può utilizzare questa condizione? Q ha dei magici iteratori che rendono il compito molto facile. In questo caso l’iteratore è rappresentato da / e si usa nel seguente modo:
(CONDIZIONE) (FUNZIONE) /(ELEMENTO)
Quindi:
cond new_one/(1, 2)
Genera:
(2;4i;16i;37i;58i;89i;145i;42i;20i;4i)
Sarebbe utile però applicare questa ricerca diciamo ai primi 10000 numeri interi. Per fortuna Q permette di farlo in una sola riga:
r:{1_x} each {cond new_one/(1, x)} each til 10000
il risultato è quindi una lista liste che si interrompono quando inizia il loop
(0;0i)
,1
(2;4i;16i;37i;58i;89i;145i;42i;20i;4i)
(3;9i;81i;65i;61i;37i;58i;89i;145i;42i;20i;4i;16i;37i)
(4;16i;37i;58i;89i;145i;42i;20i;4i;16i)
(5;25i;29i;85i;89i;145i;42i;20i;4i;16i;37i;58i;89i)
(6;36i;45i;41i;17i;50i;25i;29i;85i;89i;145i;42i;20i;4i;16i;37i;58i;89i)
(7;49i;97i;130i;10i;1i;1i)
(8;64i;52i;29i;85i;89i;145i;42i;20i;4i;16i;37i;58i;89i)
(9;81i;65i;61i;37i;58i;89i;145i;42i;20i;4i;16i;37i)
(10;1i)
…
Sul mio i7, utilizzando la versione gratuita a 32bit di kdb+, questa operazione costa meno di un secondo.
I numeri felici sono quelli per i quali la lista finisce con 1 quindi:
happy:r where 1 = last each r
,1
(7;49i;97i;130i;10i;1i;1i)
(10;1i)
(13;10i;1i;1i)
(19;82i;68i;100i;1i;1i)
(23;13i;10i;1i;1i)
(28;68i;100i;1i;1i)
(31;10i;1i;1i)
(32;13i;10i;1i;1i)
(44;32i;13i;10i;1i;1i)
(49;97i;130i;10i;1i;1i)
(68;100i;1i;1i)
(70;49i;97i;130i;10i;1i;1i)
(79;130i;10i;1i;1i)
(82;68i;100i;1i;1i)
Se volessi vedere quanti di questi numeri condividono la stessa sequenza potrei utilizzare per comodità la struttura dati tabella in Q:
htab: ([] nu:(first each happy); se:({1_x} each happy))
htab ha due colonne: nu e se. nu rappresenta il numero di partenza e se la sua sequenza
nu se
— — — — — — — — — — — — —
1 `long$()
7 49 97 130 10 1 1i
10 ,1i
13 10 1 1i
19 82 68 100 1 1i
23 13 10 1 1i
28 68 100 1 1i
31 10 1 1i
32 13 10 1 1i
44 32 13 10 1 1i
49 97 130 10 1 1i
Come faccio a raggruppare i numeri con la stessa sequenza? Un quasi SQL realmente rapido mi dà il risultato:
select nu by se from htab
,1i | 10 100 1000
7 49 97 130 10 1 1i | 1112 1121 1211 2111
10 1 1i | 13 31 103 130 301 310 1003 1030 1122 1212 1221 1300 2112 2121 2211 3001 3010 3100
…
Conclusione
Q è un linguaggio da esplorare, molto efficace e divertente. kdb+ è veloce per il lavoro su serie temporali.
In Elif Lab lo utilizziamo anche per cose meno serie della matematica (come ad esempio analizzare grosse moli di dati per risolvere problemi dei nostri clienti).
Codice
st: {[xn] sum {“i”$xexp[;2] “I”$x} each string xn }
new_one: {x, st last x}
cond: {not (last x) in -1_x}
\t r:{1_x} each {cond new_one/(1, x)} each til 10000
happy:r where 1 = last each r
htab: ([] nu:(first each happy); se:({1_x} each happy))Ti incuriosiscono le potenzialità di Q e di kdb+?
Contattaci a info@eliflab.com