Visualizza il feed RSS

Titolo provvisorio...

LUT? Sì, grazie!

Valuta questo inserimento
di pubblicato il 11-06-2011 alle 01:49 (3693 Visite)
Quote Originariamente inviato da M.A.W. 1968 Visualizza il messaggio
PS: Riguardo al thread, la soluzione più elementare (con gli effetti collaterali di essere generalmente ottima in tempo di esecuzione, e di stimolare ad acquisire la giusta forma mentis informatica) consta nell'uso di una tabella di lookup [...]

Quasi inutile aggiungere che le tabelle di lookup, assieme ai sistemi di hashing, sono un ingrediente essenziale in qualsiasi progetto informatico: dallo sviluppo dei microprocessori ai linguaggi di più alto livello, è pressoché impossibile trovare un progetto di normale complessità che non ne faccia uso.
La citazione è tratta da questo thread.

L'idea è quella di esemplificare l'uso delle onnipresenti tabelle di lookup - per gli amici, LUT: Look-Up Table - prendendo come spunto il banale esempio correlato al thread.

Le LUT, in special modo quelle a chiave posizionale, sono una di quelle tipiche idee informatiche che sembrano banalissime e perfino stupide fin dalla prima volta in cui se ne sente parlare in modo esplicito, ma alle quali pare che la stragrande maggioranza degli studenti non giunga mai autonomamente, come mostrano innumerevoli esperienze didattiche.

Questi concetti fanno parte in modo imprescindibile della forma mentis computazionale: trasformare un dato in un indice e usarlo per recuperare direttamente un altro dato correlato, per quanto suoni come la scoperta dell'acqua calda alle orecchie di qualsiasi practitioner mediamente scafato, è pur sempre un'idea che va appresa.

Sorprendentemente, per alcuni l'idea continua a restare oscura o poco intuitiva anche dopo gli studi e/o dopo anni di professione: in effetti molti ambienti e linguaggi di alto livello nascondono e diluiscono l'idea del lookup in strutture associative avanzate come i dizionari, favoriscono l'abuso di tabelle di database anche per compiti banali, o rendono ardue talune manipolazioni elementari su caratteri ed indici: il che finisce per spedire nel dimenticatoio, per molti, quella che è invece la struttura dati in assoluto più ricorrente nel low level, nella programmazione per sistemi embedded, nella progettazione microelettronica.

Questa entry ci consente, peraltro, di presentare collateralmente nei sorgenti l'uso di alcuni idiomi e tecniche un po' meno banali, sperabilmente d'interesse per tutti gli studenti (e non solo).

Innanzi tutto, il primo concetto da apprendere è relativo agli aspetti prestazionali. In teoria, specialmente su hardware di riferimento convenzionale, nessuna altra soluzione è maggiormente efficiente di una tabella di lookup, in termini di tempo d'esecuzione!

Ciò è immediatamente intuibile già solo osservando la concisione sintattica, al livello in cui operiamo.
Infatti, se sgombriamo il campo dalle variabili intermedie introdotte per migliorare la leggibilità, l'accesso alla stringa target ("nome dell'elemento chimico", nell'esempio) data la stringa di partenza ("simbolo chimico") si riduce nel caso tipico alla seguente espressione:

codice:
    Elements[ElemLookUp[toupper(sym[0]) - 'A'][toupper(sym[1]) - '@']]
Nonostante la leggibilità relativamente scarsa per il profano o il neofita, non si tratta d'altro che di un paio di accessi indicizzati: una espressione che, in linguaggio macchina, richiede (secondo la generazione e il tipo del processore) al caso peggiore una dozzina di istruzioni elementari.

Si intuisce già con estrema chiarezza, dunque, che nessun'altra soluzione basata su confronti espliciti, algoritmi di ricerca o altro può competere in prestazioni con questo tipo di accesso, caratterizzato sostanzialmente da complessità costante O(1).

Naturalmente non esistono pasti gratuiti in Natura, ma l'unica vera controindicazione occasionale all'uso ingenuo ed acritico di LUT proviene dalla relativa occupazione di memoria, che rischia di assumere una dimensione esorbitante rispetto alla dimensione dell'input. Tuttavia, un uso accorto di strutture dati avanzate e accorgimenti di codifica, a partire dall'hashing, consente di minimizzare i costi, mantenendo quasi sempre i palesi vantaggi di un accesso in tempo costante.

Nel nostro caso, la codifica è decisamente banale.
Consideriamo il seguente frammento di LUT per visualizzare meglio l'idea.

Formula LaTeX: \begin{array}{|l|r|r|r|r|r|}\hline  & - & {\color{Red} a} & b & c & d \\ \hline A & 0 & 0 & 0 & 89 & 0 \\ \hline B & 5 & 56 & 0 & 0 & 0 \\ \hline {\color{Red} C} & 6 & {\color{Red} 20} & 0 & 0 & 48 \\ \hline D & 0 & 0 & 105 & 0 & 0 \\ \hline \end{array}

Le righe corrispondono alla prima lettera del simbolo, mentre le colonne sono indicizzate dalla seconda lettera, se presente. La prima colonna a sinistra contempla appunto il caso che il simbolo consti di una singola lettera (es. boro, carbonio, e ovviamente anche fosforo, idrogeno, ossigeno, potassio...).

In modo del tutto elementare, data l'unicità dei simboli chimici, avendo il simbolo Ca la tabella ci dice in modo immediato che il relativo numero atomico è pari a 20. In sostanza, utilizziamo le lettere che compongono il simbolo chimico per indicizzare direttamente l'elemento in questione, tramite il numero atomico.

A tale numero, tramite un secondo banale array di puntatori a char (array di "stringhe"), associamo in modo immediato il nome dell'elemento.

Naturalmente, non è in alcun modo obbligatorio fare uso del peso atomico per indicizzare gli elementi: avremmo benissimo potuto scegliere uno qualsiasi degli altri 118! -1 = 4,684E+194 ordinamenti possibili per l'array di appoggio, e in particolare avremmo potuto ordinare lessicograficamente l'array in base al nome dell'elemento stesso.
Tuttavia, non avendo particolari specifiche da soddisfare, l'uso dell'ordinamento "naturale" per numero atomico ci consente di fornire una informazione in più, potenzialmente utile per numerose altre applicazioni simili.

Ricapitolando, questi due banali passaggi risolvono il problema in modo semplice, elegante, conciso e (soprattutto) tipicamente informatico.

Se avete anche il minimo dubbio sulla corrispondenza intrinseca tra letterine, numeri e indici della matrice avete decisamente bisogno di questa.

Solo una nota ulteriore. Gli elementi transuranici sintetici caratterizzati da simbolo di tre lettere vengono gestiti a parte, in una riga aggiuntiva. Sarebbe stato ovviamente possibile sfruttare il fatto che la tabella presenta almeno una colonna inutilizzata, ma per semplicità si è preferita la soluzione della riga extra. Ciò è comunque del tutto irrilevante...

Ecco a cosa si riduce il main() di un programma siffatto:
codice:
int main(void)
{
    char Sym[MAX_SYM_LEN +1];
    char na;

    while (1)
    {
        printf(PROMPT_MSG);

        if (NULL != fgets(Sym, MAX_SYM_LEN, stdin))
        {
            if (0 == strncmp("*", Sym, 1))
            {
                break;
            }

            if(Translate(Sym, &na))
            {
                printf(ELEM_FMT_STR, na, Elements[na]);
            }
        }
    }

    return(0);
}
Difficile concepire qualcosa di più semplice...

Questo, invece, è il codice maggiormente significativo nella funzione di conversione che prende in input il simbolo (un array di char, ossia stringa null-terminated) e ne restituisce il numero atomico, a meno di errori:
codice:
        switch(strlen(sym))
        {
            case 0:
            default:
                i = 0;
                j = 0;
                puts(ERR_MSG);
                retval = FALSE;
                break;

            case 1:
                i = (char)(toupper(sym[0]) - 'A');
                j = 0;
                break;

            case 2:
                i = (char)(toupper(sym[0]) - 'A');
                j = (char)(toupper(sym[1]) - '@');
                break;

            case 3:
                i = (char)(LUT_ROWS -1);
                j = (char)(toupper(sym[2]) - '@');
                break;

        }
Per il momento possiamo fermarci qui. Negli allegati ptable_c.txt e ptable_h.txt trovate il banale codice sorgente, ampiamente commentato, in versione didattica ma con ricorso a tecniche spesso trascurate nei manuali, specialmente nei corsi introduttivi. Il tutto, ça va sans dire, compilato con BCC 5.5.1.

Naturalmente i nomi degli elementi sono in lingua inglese (e consideratevi fortunati che non li ho proposti in albanese o in rumeno...), perché non siamo qui per svolgere i compiti di alcunchì.

Se non riuscite a dormire per la curiosità di vedere come risulta la tavola periodica in swahili o in urdu, potete sempre rivolgervi qui.

Nella prossima puntata vedremo quella che probabilmente è l'unica parte davvero interessante: come generare la LUT, sempre servendoci del linguaggio C e di una tavola periodica semplificata salvata in formato CDF (anche se il compito sarebbe di gran lunga più idoneo per AWK o ICON, in questo caso).

aggiornamento da 02-01-2012 a 19:37 di M.A.W. 1968

Categorie
Programmazione

Commenti