Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Sapere qual'è la lettera più utilizzata in un file di testo
Forum - C/C++ - Sapere qual'è la lettera più utilizzata in un file di testo

Avatar
xeeynamo (Normal User)
Pro


Messaggi: 66
Iscritto: 14/03/2008

Segnala al moderatore
Postato alle 13:52
Venerdì, 15/10/2010
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 > max) max = i; ) e infine ci sarà l'ultimo ciclo che mi dirà qual'è la lettera più utilizzata (if (array == 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

Ultima modifica effettuata da xeeynamo il 15/10/2010 alle 13:57
PM
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Up
3
Down
V
Segnala al moderatore
Postato alle 14:01
Venerdì, 15/10/2010
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.

Ultima modifica effettuata da TheKaneB il 15/10/2010 alle 14:02


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM
Avatar
xeeynamo (Normal User)
Pro


Messaggi: 66
Iscritto: 14/03/2008

Up
0
Down
V
Segnala al moderatore
Postato alle 11:25
Sabato, 16/10/2010
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 :k:

PM
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Up
0
Down
V
Segnala al moderatore
Postato alle 11:58
Sabato, 16/10/2010
Testo quotato

Postato originariamente da xeeynamo:

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 :k:



prego, figurati :-)


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM