C/C++ - Sapere qual'è la lettera più utilizzata in un file di testo

Ciao a tutti!

Stò lavorando su un algoritmo che mi dice qual'è la lettera più utilizzata in un file di testo. Per esempio se scrivo "mio zio rocco" il programma mi deve dire che la lettera più utilizzata è la 'o'. Ho già pensato come fare, creo un array di unsigned int lungo 0x100 e ogni volta che legge una lettera, incrementa di uno una determinata posizione dell'array (detto molto più semplicemente, l'array all'inizio è settato interamente a 0 e poi ogni lettera letta ci sarà array[*testo++]++; ). Dopo aver letto l'intera frase, farò un altro ciclo che memorizzerà il numero di lettere più utilizzato (qui ci sarà if(array[i] > max) max = i; ) e infine ci sarà l'ultimo ciclo che mi dirà qual'è la lettera più utilizzata (if (array[i] == max) return i; ). Si lo so, l'algoritmo va bene ma a parer mio è troppo macchinoso e lento in runtime, dato che il vero algoritmo che userò non funzionerà su semplici frasi ma su file binari abbastanza lunghi. 3 cicli soltanto per vedere qual'è la lettera più utilizzata è assurdo, solo che non ho trovato altri modi per semplificare l'algoritmo ed è per questo che chiedo qui .

Aspetto risposte

fai così...

ogni volta che inserisci una lettera nell'array, controlla il valore di quella cella dell'array, confrontandolo con una variabile chiamata maxCount

int maxCount;
char maxValue;

if (array[corrente] > maxCount)
{
maxCount = array[corrente];
maxValue = corrente;
}

alla fine dell'algoritmo, ti ritroverai con la lettera più frequente dentro la variabile maxValue, e la sua frequenza sarà dentro maxCount.

In realtà però, il risparmio è solo apparente, perchè invece di scorrere tutto l'array alla fine, spalmi il calcolo su ogni iterazione. In termini matematici, hai un solo ciclo di complessità O(2T), anzichè due cicli di complessità O(N) + O(T), dove N è il numero di caratteri e T è la dimensione del testo. Il secondo approccio è ovviamente più efficiente per T molto maggiore di N, mentre il primo è più efficiente nel caso opposto, cioè dove hai un testo di lunghezza T molto minore di N.

Ho capito il tuo ragionamento alla perfezione e con la tua soluzione sembra che risparmio qualche millisecondo in runtime. Non è la prima volta che ricevo il tuo aiuto e ti ringrazio per tutto

prego, figurati :-)