Key index counting - Algoritmi e strutture dati

Compito e codifica delle variabili categoriche

Elenco di "che compito ha fatto". Notiamo che il vettore che indica che compito ha fatto lo studente in questo caso usa dei numeri, ma potrebbe usare delle etichette. L’unica cosa rilevante è che queste etichette siano in numero finito. A questo punto, se mi trovo delle etichette, o dette variabili categoriche, posso sempre rimpiazzarle con dei numeri. Quindi si tratta di un passaggio alla codifica numerica, esso è il primo passo da fare.

Ci aspettiamo di trovare questo risultato: abbiamo quindi che i numeri sono ordinati, ma anche i nomi sono ordinati. L’idea ora è che, siccome noi abbiamo codificato le variabili categoriche con dei numeri, noi possiamo fare un giro all’interno del vettore.

Conteggio e riordino delle categorie

Considerando che le variabili sono codificate 1, 2, 3, 4 ma il vettore lo consideriamo che parte da 0, contiamo quanti 1 ci sono, quanti 2 ci sono, etc. Quindi, quando trovo un 2, incremento la colonna 2+1, quando trovo un 3, incremento la colonna 3+1, etc.: notiamo che in questo caso la colonna 0 e 1 sono sempre pari a 0 perché incremento la colonna i+1. La colonna 0 mi dice da dove devo cominciare a mettere gli elementi etichettati 1, gli elementi etichettati 2 devono cominciare alla fine degli elementi etichettati 1, quindi alla colonna 3 perché ho 3 elementi 1.

Ora devo capire dove finiranno gli elementi nel vettore riordinato. Faccio il conto e dico che gli elementi 1 cominciano dalla colonna 0 e occupano 0, 1, 2 perché sono 3 elementi. Gli elementi 2 cominciano dalla colonna 3, ce ne sono 5, quindi occuperanno 3, 4, 5, 6, 7. Allora gli elementi 3 cominciano dalla colonna 8, etc.: sono passato quindi da quella che è la frequenza relativa degli elementi (l’immagine prima della precedente) a quella cumulativa, quest’ultima riportata, che mi dice che gli 1 cominceranno dalla posizione 0, i 2 dalla colonna 3, i 3 dalla colonna 8, i 4 dalla 14 e i 5 dalla 20.

A questo punto, in una passata arrivo a ciò: quindi dico ad esempio: Anderson è un 2 quindi lo metto nella colonna dove ci stanno i 2 che è aux[3], poi Brown è 3 quindi lo metto nel primo posto dei 3, etc.

Complessità computazionale

La prima operazione di conteggio prima delle frequenze relative e poi quelle cumulative è proporzionale al numero di elementi N. Il riordino del vettore è anch’esso proporzionale al N perché la faccio in una passata. Per riordinare il vettore sulla base delle categorie anziché sulla base dei nomi ci vuole ancora un tempo proporzionale a N.

Nel caso dei confronti, la complessità minima richiesta è N*log(N). Se invece ci basiamo sul calcolo, portiamo la complessità a N, cioè lineare. Siamo quindi riusciti a fare il meglio del meglio in un caso in cui possiamo evitare di fare i confronti perché abbiamo codificato le categorie.