PREMESSA: potreste avere una visualizzazione parziale del blog, in futuro, a causa di una necessita’ di ridurre le visibilita’ all’interno dell’ambiente lavorativo. Cosi’ e’. Aggiornate i vostri bookmark.

PREMESSA 2: il seguente post e’ una nerdata tecnica. Evitatelo se non siete informatici. 😛

Ultimamente sono stato contattato da una azienda per un colloquio. Tale azienda, essendo esperta di gestione di grandi moli di dati, ha bisogno di gente che sappia scrivere algoritmi ottimizzati, quindi, a fronte di un contratto abbastanza interessante in una qualsiasi delle loro sedi (tra cui c’e’ Roma… lavorare a Roma con uno stipendio da California non sarebbe male), esigono un colloquio molto tecnico.
Cosi’ mi sono state date alcune cose da leggere, ma ahime’ troppo tardi, e alcuni esercizi su cui spendere un po’ di tempo. Uno di questi e’ diventato tormentone tra i miei amici perche’, spendendoci un’oretta, ho trovato la soluzione ottima. Ve lo propongo con la soluzione quindi se volete cimentarvici fate pure, ma leggete solo il testo e non la soluzione.
Ovviamente il fatto che io metta la soluzione che ho trovato non vi permettera’ mai piu’ di dire di averne trovata una anche voi. La mia e’ ottimale in tempo e spazio, saputa la mia potete scimmiottarne altre, ma saranno tutte considerate copie.

“You are told to program on an ancient hardware system and due to some unfortunate design decisions there is no division. Given a list [a,b,c … z] return a list [b..z, ac..z, to a..y] where you multiply all the other elements in the list together except for the current element. (i.e., [3,5,2] => [10,6,15]) ”
HINT: Even without division it’s possible to do this in O(n).

Traduzione:
“Ti e’ stato detto di programmare su un vecchio systema hardware e a causa di alcune decisioni di design sfortunate non c’e’ la divisione. Data una lista [a, b, c, … z] ritorna la lista [b..z, ac..z, fino a a..y] dove moltiplichi tutti gli altri elementi nella lista assieme tranne per l’elemento corrente. (per esempio [3,5,2] => [10,6,15]”
SUGGERIMENTO: anche senza la divisione e’ possibile farlo in O(n)

Ovviamente vista la notazione considero le liste come array. Viene da se’ che se fossero liste si potrebbero mutare in Array in O(n), scorrendole una volta e mettendo nell’array il valore. Questo non influirebbe sulla linearita’ computazionale dell’algoritmo (anche se influerebbe sul suo costo in termini di spazio).
Il primo algoritmo, chiamiamolo di bruteforce, e’ banale: per ogni elemento della lista, si scorre tutta la lista e si moltiplicano tutti gli elementi meno quello considerato. Computazionalmente si scorrono gli N elementi per N volte, O(N^2).

Per migliorare questo io avevo pensato anche ad una soluzione intermedia. Un albero binario (mappato su un vettore di meno di N elementi) dove come foglie abbiamo gli elementi del vettore originario, e ogni padre e’ la moltiplicazione dei due figli. Per ogni N basterebbe scorrere dalla radice all’elemento da escludere “invalidando” tutti i nodi trovati. Il valore sarebbe la moltiplicazione delle radici dei due sottoalberi creati. Probabilmente con delle buone funzioni matematiche e con uno studio sugli alberi si potrebbe fare tutto questo con un costo lineare, perche’ trovando una funzione che ti indica quali sono i due nodi radice dei sottoalberi orfani dato un nodo foglia, questo torna a essere una moltiplicazione per tutti gli N elementi.
Tuttavia come spazio si ha un ulteriore costo (un altro vettore), e se non si trova la funzione adatta a trovare le giuste sottoradici, bisogna scorrere l’albero (costo logN) col risultato di avere un costo computazionale di O(NlogN).

Ma quale motivo ci porta a ricalcolare tutte le volte le moltiplicazioni? Mentre scorriamo sulla destra il vettore, infatti, abbiamo una situazione bizzarra: facciamo tutte le volte le moltiplicazioni degli elementi iniziali, a cui alla successiva interazione aggiungiamo solo la moltiplicazione col precedente elemento. Per capirci, alla i+1-esima interazione abbiamo gia’ fatto la moltiplicazione degli i-1 elementi all’interazione i-esima, e basta avere quel valore e moltiplicarlo per l’elemento i-esimo per avere la parte di moltiplicazione precedente all’elemento i+1esimo.
Per capirci, dato il vettore [1, 3, 2, 1, 5, 3, 8, 2 ] quando vogliamo calcolare la quinta posizione (il corrispondente del 5) noi abbiamo gia’ calcolato la quarta posizione, quindi abbiamo gia’ fatto la moltiplicazione 1*3*2. Se ci siamo tenuti questo valore, bastera’ moltiplicarci il valore dell’elemento precedente al quinto (cioe’ l’1) per avere gia’ tutta la lista dei valori precedenti.
Il problema e’ che non possiamo fare lo stesso con i valori seguenti, perche’ all’iterazione i-esima al limite potremmo avere la moltiplicazione dei volori a partire da i in poi, dati dalla computazione precedente, e dovremmo dividerli per l’i-esimo elemento, ma non abbiamo la divisione.
Come risolvere il problema? Semplice: lo facciamo in due step. Alla prima passata mettiamo nel vettore dei risultati tutti i valori precedenti, scorrendo il vettore da sinistra a destra, alla seconda passata mettiamo tutti i valori tutti i valori seguenti, scorrendo da destra a sinistra e facendo la stessa cosa. Con una variabile e 2N passate, abbiamo cosi’ ottenuto il risultato finale.

Un po’ di benchmark. Sulle macchine da lavoro (abbastanza potenti) i risultati ottenuti eseguendo 100 volte i due algoritmi (bruteforce e quello finale, non ho implementato quello degli alberi) su liste di 5000 numeri interi scelti a caso in valori compresi tra 1 e 5 sono i seguenti, in nanosecondi:

Bruteforce Algorithm statistics:
Min: 39191000 Max: 39259000 Average: 39200409 Total: 3920040999
2 Step Algorithm statistics:
Min: 28000 Max: 32000 Average: 29149 Total: 2914999

Stay tuned!