[C] Selezionare 10 parole più usate di un file di testo

[kingal]

salve ragazzi...ho questo problema...devo studiare una struttura dati effieciente che mi consenta di registrare le 10 parole + utilizzate di un file di testo. A parte quelle banali come liste semplici (ordinate o meno) sapete consigliarmi qualche struttura adatta a questo problema??? perchè se si considera un file da 500.000 parole una lista semplice ordinata per frequenza sarebbe lentissima o magari la cosa più semplice è anche la più efficiente?
Grazie

[wingman87]

Secondo me puoi iniziare con un albero binario ordinato alfabeticamente in cui in ogni modo metti la parola e il numero di occorrenze, poi lo potresti sciogliere in una lista ordinata per il numero di occorrenze quando hai finito di inserire le parole nell'albero (oppure implementi un qualche algoritmo sull'albero per trovare subito le 10 parole + frequenti).

[kingal]

ah molto bene ...ma per passare dall'albero binario ordinato alfabeticamente ad una lista oridinata per frequenze non mi basta fare una visita
INORDER-tree-walk che me lo ordinerebbe alfabeticamente e non è quello che mi serve....dovrei implementarmi cmq un algoritmo...giusto???

[gugoXX]

Se devi veramente trovare l'algoritmo piu' efficiente, allora voto per una hashtable (classica, non ordinata), in cui la chiave e' la singola parola, mentre il valore e' l'occorrenza di tale parola.
Alla fine ordini una sola volta per occorrenza e prendi le prime 10 parole.

Se e' un'implementazione che ti serve per lavoro ok, altrimenti in C gestire una hashtable mi sa che e' proprio scomodo.

vuoi un assaggio di C# che faccia proprio la stessa cosa?
La hashtable in questione e' nascosta nel codice linq nell'istruzione Group By.
La manipolazione di "gruppi", come liste, hastable, code, stack, etc. e' quello che e' considerato il secondo punto forte del C#, dopo l'introduzione della Garbage Collection in un linguaggio C++ style.


string text = new WebClient().DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt"); // Great Expectations
string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);

var res = from word in words
group word by word into gruppo
select new {parola = gruppo.Key, occorrenza = gruppo.Count()};

var first10 = res.OrderByDescending(t => t.occorrenza).Take(10);

first10.ForEach(Console.WriteLine);



{ parola = the, occorrenza = 7806 }
{ parola = and, occorrenza = 6611 }
{ parola = I, occorrenza = 5734 }
{ parola = to, occorrenza = 5077 }
{ parola = of, occorrenza = 4394 }
{ parola = a, occorrenza = 3971 }
{ parola = in, occorrenza = 2847 }
{ parola = was, occorrenza = 2695 }
{ parola = that, occorrenza = 2673 }
{ parola = had, occorrenza = 2058 }

[kingal]

non è per lavoro...sto studiando per l'università...cmq non è necessario che sia la migliore in assoluto, mi basta una buona implementazione e non troppo complessa perchè non ho molto tempo tra l'altro, e devo farla in C. grazie cmq la terrò in considerazione.

[gugoXX]

non è per lavoro...sto studiando per l'università...cmq non è necessario che sia la migliore in assoluto, mi basta una buona implementazione e non troppo complessa perchè non ho molto tempo tra l'altro, e devo farla in C. grazie cmq la terrò in considerazione.

Allora fai pure come ti ha consigliato wingman.
E fai che usare anche la qsort, cosi' non scrivi neppure troppo, meno errori, e impari ad usare una delle poche utility del C standard.

[kingal]

Secondo me puoi iniziare con un albero binario ordinato alfabeticamente in cui in ogni modo metti la parola e il numero di occorrenze, poi lo potresti sciogliere in una lista ordinata per il numero di occorrenze quando hai finito di inserire le parole nell'albero (oppure implementi un qualche algoritmo sull'albero per trovare subito le 10 parole + frequenti).

Come riesco a sciogliere l'albero ordinato alfabeticamente in una lista ordinata per n° di occorrenze??? grazie per la disponibilità

[wingman87]

Crei una struttura classica per una lista e un metodo per l'inserimento ordinato per occorrenza. A quel punto basta una visita dell'albero in qualsiasi ordine e per ogni nodo ne inserisci uno equivalente (stessa parola e stesse occorrenze) nella lista

EDIT: però se a sto punto la lista non ti servisse più sarebbe un po' uno spreco, quindi ti converrebbe creare un algoritmo che trova direttamente le parole nell'albero

[kingal]

a bè giusto....infatti dp dovrei scrivere le 10 parole in un file

[Vincenzo1968]

Ciao,

io l'ho implementato così:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX_STACK 1024
#define BUFFER_SIZE 4096

int NumParole = 0;

typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2, S_ERROR = -1, S0 = 0, S1
} Stati;

typedef struct tagTree
{
char *parola;
int count;
struct tagTree *left;
struct tagTree *right;
} Tree;

Tree *NewNode(char *info);
Tree *InsertNode(Tree *node, char *key);
void FreeTree(Tree *head);

void InOrder(Tree *head, int nMax, Tree **a);

Stati DFA(char *szFileName, Tree **pTree);

int Confronta(const void *p1, const void *p2);

Tree *NewNode(char* info)
{
Tree *r;
int len;

r = (Tree *) malloc(sizeof(Tree));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = 1;
r->left = NULL;
r->right = NULL;

++NumParole;

return r;
}

Tree *InsertNode(Tree *node, char *key)
{
Tree *pRadice = NULL;
int nRes;

if( !node )
{
node = NewNode(key);
return node;
}

pRadice = node;

while( 1 )
{
nRes = strcmp(key, node->parola);

if ( nRes < 0 )
{
if ( !node->left )
{
node->left = NewNode(key);
break;
}
node = node->left;
}
else if ( nRes > 0 )
{
if ( !node->right )
{
node->right = NewNode(key);
break;
}
node = node->right;
}
else // Trovato
{
node->count++;
break;
}
}

node = pRadice;

return node;
}

void FreeTree(Tree *head)
{
Tree *temp1, *temp2;

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( !head )
return;

temp1 = temp2 = head;

while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
stack[top++] = temp1;

while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
free(temp2->parola);
free(temp2);
if ( top == 0 )
return;
temp1 = stack[--top];
}

stack[top++] = temp1;
temp1 = temp1->right;
}
}

void InOrder(Tree *head, int nMax, Tree **a)
{
int k = 0;
Tree *temp;

Tree *stack[MAX_STACK];
int top;
top = -1;

if ( !head )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
if ( top < MAX_STACK )
{
stack[++top] = temp; // Push
temp = temp->left;
}
else
{
printf("Errore: lo stack e' pieno.\n");
return;
}
}
else
{
if ( top >= 0 )
{
temp = stack[top--]; // Pop

a[k++] = temp;

temp = temp->right;
}
else
{
break;
}
}
}
}

Stati DFA(char *szFileName, Tree **pTree)
{
Stati stato = S0;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;

fp = fopen(szFileName, "rb"); // Apre il file in modalità binaria per la lettura
if ( fp == NULL )
return S_ERROR_OPEN_FILE;

numread = fread(buffer, sizeof(char), BUFFER_SIZE, fp);
*(buffer + numread + 1) = '\0';

while ( 1 )
{
c = *(buffer + k++);

if ( c == '\0' || c == EOF )
{
k = 0;
numread = fread(buffer, sizeof(char), BUFFER_SIZE, fp);
if ( numread <= 0 )
break;
*(buffer + numread + 1) = '\0';
c = *(buffer + k++);
}

switch (stato)
{
case S0:
if ( c == ' ' || c == '\r' || c == '\n' )
{
stato = S0;
}
else
{
*(szTemp + x++) = c;
stato = S1;
}
break;

case S1:
if ( c == ' ' || c == '\r' || c == '\n' )
{
*(szTemp + x) = '\0';
x = 0;
*pTree = InsertNode(*pTree, szTemp);
if ( *pTree == NULL )
return S_ERROR;
stato = S0;
}
else
{
*(szTemp + x++) = c;
stato = S1;
}
break;
}
}

if ( fp )
fclose(fp);

return stato;
}

int Confronta(const void *p1, const void *p2)
{
Tree** s1 = (Tree**)p1;
Tree** s2 = (Tree**)p2;

/* Ordine decrescente */
if ( (*s1)->count > (*s2)->count )
return -1;
else if ( (*s1)->count < (*s2)->count )
return 1;
else
return strcmp((*s1)->parola, (*s2)->parola);
}

int main()
{
Tree * p = NULL;
Stati stato;
Tree **a;
int k, x;

stato = DFA("prova.txt", &p);

if ( stato == S0 || stato == S1 )
{
a = (Tree**)malloc(sizeof(Tree*)*NumParole);
if ( a != NULL )
{
for ( x = 0; x < NumParole; x++ )
{
a[x] = (Tree*)malloc(sizeof(Tree));
if ( a[x] == NULL )
{
printf("Memoria non sufficiente.\n");
return -1;
}
}

InOrder(p, 10, a);

qsort(a, NumParole, sizeof(Tree*), Confronta);

for (k = 0; k < NumParole; k++)
{
printf("%s -> %d\n", a[k]->parola, a[k]->count);
if ( k == 9 )
break;
}

for ( x = 0; x < NumParole; x++ )
free(a[x]);
free(a);
}
else
{
printf("Memoria non sufficiente.\n");
}
}

return 0;
}


In pratica utilizzo un piccolo automa a stati finiti deterministico per leggere le parole dal file di testo e memorizzarle in un albero binario di ricerca. Per ogni parola restituita dall'automa, la cerchiamo nell'albero. Se è già presente incrementiamo il conteggio, altrimenti la inseriamo con conteggio uguale a 1.

Una volta creato l'albero, lo leggiamo inorder e inseriamo ogni nodo in un array di puntatori ai nodi dell'albero. L'array è allocato dinamicamente in base al valore della variabile globale NumParole.

A questo punto, con la funzione qsort della libreria del C, ordiniamo in modo decrescente(in base al campo count) l'array e lo stampiamo.

Se hai qualche dubbio in merito all'implementazione, chiedi pure.

:)

[Vincenzo1968]

Un'altra possibilità è quella di memorizzare il risultato in un secondo albero di ricerca ordinato in base al conteggio delle parole.
Ho modificato anche l'automa in modo che escluda, dalle parole trovate, i simboli di punteggiatura e, in generale, tutti i caratteri che non siano alfanumerici.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX_STACK 1024
#define BUFFER_SIZE 4096

int NumParole = 0;

typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
} Stati;

typedef struct tagTree
{
char *parola;
int count;
struct tagTree *left;
struct tagTree *right;
} Tree;

Tree *NewNode(char *info);
Tree *InsertNode(Tree *node, char *key);
Tree *InsertNode2(Tree *node, char *key, int count);
void FreeTree(Tree *head);

void InOrder(Tree *head, Tree **a);
void ReverseInOrder(Tree *head, int nMax);

Stati DFA(char *szFileName, Tree **pTree);

Tree *NewNode(char* info)
{
Tree *r;
int len;

r = (Tree *) malloc(sizeof(Tree));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = 1;
r->left = NULL;
r->right = NULL;

++NumParole;

return r;
}

Tree *InsertNode(Tree *node, char *key)
{
Tree *pRadice = NULL;
int nRes;

if( !node )
{
node = NewNode(key);
return node;
}

pRadice = node;

while( 1 )
{
nRes = strcmp(key, node->parola);

if ( nRes < 0 )
{
if ( !node->left )
{
node->left = NewNode(key);
break;
}
node = node->left;
}
else if ( nRes > 0 )
{
if ( !node->right )
{
node->right = NewNode(key);
break;
}
node = node->right;
}
else // Trovato
{
node->count++;
break;
}
}

node = pRadice;

return node;
}

Tree *InsertNode2(Tree *node, char *key, int count)
{
Tree *pRadice = NULL;
int nRes;

if( !node )
{
node = NewNode(key);
return node;
}

pRadice = node;

while( 1 )
{
nRes = strcmp(key, node->parola);

nRes = count < node->count ? -1 : 1;

if ( nRes < 0 )
{
if ( !node->left )
{
node->left = NewNode(key);
node->left->count = count;
break;
}
node = node->left;
}
else
{
if ( !node->right )
{
node->right = NewNode(key);
node->right->count = count;
break;
}
node = node->right;
}
}

node = pRadice;

return node;
}

void FreeTree(Tree *head)
{
Tree *temp1, *temp2;

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( !head )
return;

temp1 = temp2 = head;

while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
stack[top++] = temp1;

while ( (temp1 != NULL) &&
(temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
free(temp2->parola);
free(temp2);
if ( top == 0 )
return;
temp1 = stack[--top];
}

stack[top++] = temp1;
temp1 = temp1->right;
}
}

void InOrder(Tree *head, Tree **a)
{
int k = 0;
Tree *temp;

Tree *stack[MAX_STACK];
int top;
top = -1;

if ( !head )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
if ( top < MAX_STACK )
{
stack[++top] = temp; // Push
temp = temp->left;
}
else
{
printf("Errore: lo stack e' pieno.\n");
return;
}
}
else
{
if ( top >= 0 )
{
temp = stack[top--]; // Pop

*a = InsertNode2(*a,
temp->parola, temp->count);
temp = temp->right;
}
else
{
break;
}
}
}
}

void ReverseInOrder(Tree *head, int nMax)
{
Tree *temp;
int k = 0;

Tree *stack[MAX_STACK];
int top;
top = -1;

if ( !head )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
if ( top < MAX_STACK )
{
stack[++top] = temp; // Push
temp = temp->right;
}
else
{
printf("Errore: lo stack e' pieno.\n");
return;
}
}
else
{
if ( top >= 0 )
{
temp = stack[top--]; // Pop
printf("%s -> %d\n",
temp->parola, temp->count);
k++;
if ( k == nMax )
break;
temp = temp->left;
}
else
{
break;
}
}
}
}

Stati DFA(char *szFileName, Tree **pTree)
{
Stati stato = S0;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
return S_ERROR_OPEN_FILE;

numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
*(buffer + numread + 1) = '\0';

while ( 1 )
{
c = *(buffer + k++);

if ( c == '\0' || c == EOF )
{
k = 0;
numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
if ( numread <= 0 )
break;
*(buffer + numread + 1) = '\0';
c = *(buffer + k++);
}

switch (stato)
{
case S0:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
stato = S0;
}
break;

case S1:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
*(szTemp + x) = '\0';
x = 0;
*pTree = InsertNode(*pTree, szTemp);
if ( *pTree == NULL )
return S_ERROR;
stato = S0;
}
break;
}
}

if ( fp )
fclose(fp);

return stato;
}

int main()
{
Tree * p = NULL;
Tree *a = NULL;
Stati stato;

stato = DFA("prova.txt", &p);

if ( stato == S0 || stato == S1 )
{
InOrder(p, &a);

ReverseInOrder(a, 10);

FreeTree(p);
FreeTree(a);
}

return 0;
}


:)

[kingal]

ah..grazie...quindi le scelte che posso fare dopo aver costruito l'albero binario di ricerca in ordine alfabetico sono :
-mettere tutti gli elementi (attraverso puntatori) in un array e ordinarli con qsort.
oppure
-ricostruire un nuovo albero stavolta ordinate in base al numero di occorrenze.

Quale potrebbe essere la scelta migliore???

Poi alcune domande sull'implementazione:
-Cosa serve lo stack nel free e nella visita inorder?
-Il secondo paramentro passato a Inorder (10 che va a nMax) che ruolo svolge?

Ulteriore domanda:
Se scelgo la prima ipotesi una volta terminato tutto mi converrebbe eliminare ogni elemento dell'albero attraverso l'array di puntatori agli elementi, poi liberare anche anche l'array ?

E se invece più semplicemente visto che devo prendere un numero costante di parole....dopo aver inserito tutte le parole nell'albero, faccio una ricerca del massimo, lo stampo e poi cancello l' elemento, 10 volte, ma volendo anche 100, cmq un numero costante di volte non mi costerebbe tanto?

[Vincenzo1968]

ah..grazie...quindi le scelte che posso fare dopo aver costruito l'albero binario di ricerca in ordine alfabetico sono :
-mettere tutti gli elementi (attraverso puntatori) in un array e ordinarli con qsort.
oppure
-ricostruire un nuovo albero stavolta ordinate in base al numero di occorrenze.

Quale potrebbe essere la scelta migliore???

Poi alcune domande sull'implementazione:
-Cosa serve lo stack nel free e nella visita inorder?
-Il secondo paramentro passato a Inorder (10 che va a nMax) che ruolo svolge?

Ulteriore domanda:
Se scelgo la prima ipotesi una volta terminato tutto mi converrebbe eliminare ogni elemento dell'albero attraverso l'array di puntatori agli elementi, poi liberare anche anche l'array ?

E se invece più semplicemente visto che devo prendere un numero costante di parole....dopo aver inserito tutte le parole nell'albero, faccio una ricerca del massimo, lo stampo e poi cancello l' elemento, 10 volte, ma volendo anche 100, cmq un numero costante di volte non mi costerebbe tanto?

La soluzione che hai proposto(ricerca del massimo e cancellazione dopo la stampa) sarebbe la scelta migliore se l'albero fosse ordinato in base al campo count: si risparmierebbe e in spazio in memoria e in tempo di esecuzione.
Tra le due implementazioni penso che la scelta migliore sia la seconda. Qui chiederei l'intervento di qualcuno bravo in matematica(Gugo, per esempio, se la cava benissimo con la notazione O grande).

Il parametro nMax, nella funzione InOrder non serve. Chiedo scusa ma non mi ero accorto dell'errore. Puoi toglierlo (come ho fatto nella seconda versione).

Lo stack serve per implementare una versione non ricorsiva degli algoritmi. Se da un lato la ricorsione è più elegante (e anche più facile da implementare), dall'altro non è il massimo dal punto di vista dell'efficienza(le chiamate a funzione costano).

Ciao :)

P.S. un suggerimento per migliorare le prestazioni: potresti implementare l'albero binario di ricerca in una delle versioni che lo mantengono bilanciato dopo ogni operazione di inserimento/cancellazione come, per esempio, gli alberi AVL o Red-Black.

[gugoXX]

Ciao.
Per la ricerca di un singolo massimo in un insieme l'algoritmo e' O(N), senza riordinare nulla.

Detto invece M il numero di "Massimi" che si vogliono (ovvero voglio i primi 10, p.es.) allora l'algoritmo ottimo si risolve in O(N Log M), con M<<N
L'implementazione e' la seguente:

Scorro la lista di N elementi non ordinati su cui devo cercare gli M piu' grandi.
Tengo di volta in volta una seconda lista ordinata dei M elementi che fino a quel momento risultavano essere i massimi. L'inserimento di un nuovo eventuale elemento nella sottolista cubera' O(Log M), come da insertion sort in lista ordinata. La lista serve ordinata perche' cosi' e' facile eliminare l'elemento che non e' piu' massimo, e calcolare il nuovo minimo-soglia degli elementi ordinati.

Pertanto alla peggio effettuero' N volte un inserimento O(Log M).

[kingal]

Ciao.
Per la ricerca di un singolo massimo in un insieme l'algoritmo e' O(N), senza riordinare nulla.

Detto invece M il numero di "Massimi" che si vogliono (ovvero voglio i primi 10, p.es.) allora l'algoritmo ottimo si risolve in O(N Log M), con M<<N
L'implementazione e' la seguente:

Scorro la lista di N elementi non ordinati su cui devo cercare gli M piu' grandi.
Tengo di volta in volta una seconda lista ordinata dei M elementi che fino a quel momento risultavano essere i massimi. L'inserimento di un nuovo eventuale elemento nella sottolista cubera' O(Log M), come da insertion sort in lista ordinata. La lista serve ordinata perche' cosi' e' facile eliminare l'elemento che non e' piu' massimo, e calcolare il nuovo minimo-soglia degli elementi ordinati.

Pertanto alla peggio effettuero' N volte un inserimento O(Log M).

io però ho implementato un albero binario, ma potrei cmq affiancarlo con una lista ordinata. Non ho capito la parte evidenziata, cioè se voglio tenere una lista ordinata con quale metodo ogni inserimento mi costa solo log M ? E cosa fa l'insertion sort in lista ordinata?
Grazie

[kingal]

La soluzione che hai proposto(ricerca del massimo e cancellazione dopo la stampa) sarebbe la scelta migliore se l'albero fosse ordinato in base al campo count: si risparmierebbe e in spazio in memoria e in tempo di esecuzione.
Tra le due implementazioni penso che la scelta migliore sia la seconda. Qui chiederei l'intervento di qualcuno bravo in matematica(Gugo, per esempio, se la cava benissimo con la notazione O grande).

Il parametro nMax, nella funzione InOrder non serve. Chiedo scusa ma non mi ero accorto dell'errore. Puoi toglierlo (come ho fatto nella seconda versione).

Lo stack serve per implementare una versione non ricorsiva degli algoritmi. Se da un lato la ricorsione è più elegante (e anche più facile da implementare), dall'altro non è il massimo dal punto di vista dell'efficienza(le chiamate a funzione costano).

Ciao :)

P.S. un suggerimento per migliorare le prestazioni: potresti implementare l'albero binario di ricerca in una delle versioni che lo mantengono bilanciato dopo ogni operazione di inserimento/cancellazione come, per esempio, gli alberi AVL o Red-Black.

Scusate il doppio post, però quello che mi sfugge è proprio qui...se io l'albero lo ordino in base al valore cont non ottengo cmq il massimo in testa...perchè il bst non è completamente ordinato, trovare il massimo anche in questi caso come per ogni tipo di ricerca su bst mi costa sempre O(h), dove h è l'altezza dell'albero, quindi non avrebbe senso costrurmi un ulteriore albero.

[gugoXX]

io però ho implementato un albero binario, ma potrei cmq affiancarlo con una lista ordinata. Non ho capito la parte evidenziata, cioè se voglio tenere una lista ordinata con quale metodo ogni inserimento mi costa solo log M ? E cosa fa l'insertion sort in lista ordinata?
Grazie

Con il divide et impera.
Provi a leggere l'elemento centrale della lista. Se e' piu' grande consideri la prima sottolista, se e' piu' piccolo consideri la seconda sottolista.
Continui ricorsivamente fino a che trovi 2 elementi contigui in cui inserire il tuo nuovo elemento.

Riassumo cosa farei io.

L'albero ordinato l'hai implementato per avere la lista delle occorrenze, ora fai finta di doverlo scorrere per cercare l'occorrenza piu' alta.
Dovrai leggere tutti i nodi, e di volta in volta confrontare l'occorrenza del nodo con quella piu' alta fino ad allora trovata.
Per scandire tutti i nodi non ti serve piu' considerarlo come albero. Va benissimo come lista, disordinata.

L'estensione della ricerca dei 10 elmenti piu' occorrenti e' simile.
Prendi i primi 10 nodi, quasiasi essi siano, e mettili in modo ordinato nella lista di output, che conterra' sempre e solo 10 elementi, sempre ordinati secondo l'occorrenza.
Il minimo valore di tale sottolista e' l'occorrenza del primo elemento.
continui a scandire quello che era il tuo vecchio albero a partire dall'11 nodo.
Se il valore di questo nodo e' minore del minimo della lista, allora non ti interessa.
Altrimenti lo inserisci nella sottolista da 10 elementi ( O(Log M), come detto prima), scodi quello che il nuovo elemento piu' piccolo che non ti serve piu', calcoli quale e' il piu' piccolo nuovo elemento della sottolista che e' per definizione sempre il primo, e continui con il prossimo nodo dell'albero.
(In realta' prima scoderei il vecchio e poi aggiungerei il nuovo, ma la complessita' e' identica).

[kingal]

ok...ci sono, cmq anche in questo caso se devo inserire un elemento in una lista di 10 elementi , fissi, non è che sia poi così importante, una volta visto che l'elemento è maggiore del minimo nella sottolista, trovare il posto giusto nella sottolista con divide et impera, sono sempre solo 10 elementi, non si avrebbe un miglioramento sensibile rispetto allo scorrimento classico 1 per 1 partendo dalla testa..oppure sbaglio?

[gugoXX]

Assolutamente.
Se li scorri tutti e 10 hai O(N), se usi il divide et impera O(Log N), ma ovviamente se ci sono solo 10 elementi rischi addirittura che il divide et impera sia effettivamente piu' lento del ciclo esaustivo.

Il mio era un approccio generale.
Pensa di dover trovare i top 10.000 su una popolazione di 1.000.000.000

[kingal]

si si quello chiaramente, mi riferivo al caso specifico. ti ringrazio molto;) .

[Vincenzo1968]

Questa è la mia implementazione di quanto suggerito da Gugo(che ringrazio, e un pochettino 'invidio', per le sue analisi matematiche sulle prestazioni degli algoritmi):


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX_STACK 1024
#define BUFFER_SIZE 4096

int NumParole = 0;

typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
} Stati;

typedef struct tagTree
{
char *parola;
int count;
struct tagTree *left;
struct tagTree *right;
} Tree;

typedef struct tagList
{
char *parola;
int count;
struct tagList *next;
} List;

Tree *NewNode(char *info);
Tree *InsertNode(Tree *node, char *key);
void FreeTree(Tree *head);

List *ListNewNode(char *info, int count);
void ListInsertNode(List **head, List *newNode);
void FreeList(List **head);

void InOrder(Tree *head, List **a, int nMax);

Stati DFA(char *szFileName, Tree **pTree);

List *ListNewNode(char *info, int count)
{
List *r;
int len;

r = (List *) malloc(sizeof(List));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = count;
r->next = NULL;

return r;
}

void ListInsertNode(List **head, List *newNode)
{
List *current = *head;

if ( *head == NULL ||
(*head)->count <= newNode->count )
{
newNode->next = *head;
*head = newNode;
}
else
{
while ( current->next != NULL &&
current->next->count > newNode->count )
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}

void FreeList(List** head)
{
List *current = *head;
List *next;

while ( current != NULL )
{
next = current->next;
free(current->parola);
free(current);
current = next;
}

*head = NULL;
}

Tree *NewNode(char* info)
{
Tree *r;
int len;

r = (Tree *) malloc(sizeof(Tree));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = 1;
r->left = NULL;
r->right = NULL;

++NumParole;

return r;
}

Tree *InsertNode(Tree *node, char *key)
{
Tree *pRadice = NULL;
int nRes;

if( !node )
{
node = NewNode(key);
return node;
}

pRadice = node;

while( 1 )
{
nRes = strcmp(key, node->parola);

if ( nRes < 0 )
{
if ( !node->left )
{
node->left = NewNode(key);
break;
}
node = node->left;
}
else if ( nRes > 0 )
{
if ( !node->right )
{
node->right = NewNode(key);
break;
}
node = node->right;
}
else // Trovato
{
node->count++;
break;
}
}

node = pRadice;

return node;
}

void FreeTree(Tree *head)
{
Tree *temp1, *temp2;

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( !head )
return;

temp1 = temp2 = head;

while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
stack[top++] = temp1;

while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
free(temp2->parola);
free(temp2);
if ( top == 0 )
return;
temp1 = stack[--top];
}

stack[top++] = temp1;
temp1 = temp1->right;
}
}

void InOrder(Tree *head, List **a, int nMax)
{
int k = 0;
int min = 0;
Tree *temp;

List *listNode;
List *tempListNode;
List *tempListNodePrev;

Tree *stack[MAX_STACK];
int top;
top = -1;

if ( !head )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
if ( top < MAX_STACK )
{
stack[++top] = temp; // Push
temp = temp->left;
}
else
{
printf("Errore: lo stack e' pieno.\n");
return;
}
}
else
{
if ( top >= 0 )
{
temp = stack[top--]; // Pop

if ( min > temp->count )
min = temp->count;

if ( k < nMax )
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
}
else
{
if ( temp->count > min )
{
tempListNode = tempListNodePrev = *a;
while ( tempListNode->next != NULL )
{
tempListNodePrev = tempListNode;
tempListNode = tempListNode->next;
}
tempListNodePrev->next = NULL;
free(tempListNode);

listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
}
}

k++;

temp = temp->right;
}
else
{
break;
}
}
}
}

Stati DFA(char *szFileName, Tree **pTree)
{
Stati stato = S0;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
return S_ERROR_OPEN_FILE;

numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
*(buffer + numread + 1) = '\0';

while ( 1 )
{
c = *(buffer + k++);

if ( c == '\0' || c == EOF )
{
k = 0;
numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
if ( numread <= 0 )
break;
*(buffer + numread + 1) = '\0';
c = *(buffer + k++);
}

switch (stato)
{
case S0:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
stato = S0;
}
break;

case S1:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
*(szTemp + x) = '\0';
x = 0;
*pTree = InsertNode(*pTree, szTemp);
if ( *pTree == NULL )
return S_ERROR;
stato = S0;
}
break;
}
}

if ( fp )
fclose(fp);

return stato;
}

int main()
{
Tree * p = NULL;
List *a = NULL;
List *t = NULL;
Stati stato;

stato = DFA("prova.txt", &p);

if ( stato == S0 || stato == S1 )
{
InOrder(p, &a, 10);

t = a;
while ( t != NULL )
{
printf("%s -> %d\n", t->parola, t->count);
t = t->next;
}

FreeTree(p);
FreeList(&a);
}

return 0;
}


Nota che adesso il parametro nMax serve e, quindi, l'ho riaggiunto alla funzione InOrder. La funzione chiama ListInsertNode per inserisce in ordine decrescente i nodi nella lista. Prima di inserire il nodo, cancelliamo l'ultimo dalla lista(poichè la lista è ordinata in ordine decrescente, ciò significa cancellare il nodo col valore di count più basso).

[gugoXX]

Nota che adesso il parametro nMax serve e, quindi, l'ho riaggiunto alla funzione InOrder. La funzione chiama ListInsertNode per inserisce in ordine decrescente i nodi nella lista. Prima di inserire il nodo, cancelliamo l'ultimo dalla lista(poichè la lista è ordinata in ordine decrescente, ciò significa cancellare il nodo col valore di count più basso).

Bello.
Certo che il C e' lungo.
Continuano ad insegnare il C, e con il C si perdono analisi importanti come le hashtable, che sono un po' scomode da implementare. Altrimenti ci si potrebbe concentrare sugli algoritmi, e non sul linguaggio e sulle sue peculiarita'.
E non capisco perche'. Tanto una volta che si conosce un paradigma, conoscere un linguaggio nuovo e' questione di una settimana, e dopo un mese lo si possiede gia' decentemente.
O forse un po' lo capisco. Anche in ambito informatico inzia a sentirsi puzza di vecchio, e mentre una volta i professori erano giovani perche' l'informatica era giovane, ora i professori sono vecchi perche' sono rimasti gli stessi, e insegnano quello che hanno imparato.
E bisogna stare attenti, perche' mentre per ambiti come Civile o Meccanica le cose sono oramai consolidate, cambiano i mezzi e gli strumenti ma le idee e i fondamenti sono sempre gli stessi, in Informatica invece le cose sono ancora molto mobili, e restare fermi alle cose di 10 anni fa significa essere davvero tagliati fuori.
Ci sono intere aziende che basano il loro business su ambiti dell'informatica che 10 anni fa neppure esistevano oppure erano appena accennati.

[DanieleC88]

O forse un po' lo capisco. Anche in ambito informatico inzia a sentirsi puzza di vecchio, e mentre una volta i professori erano giovani perche' l'informatica era giovane, ora i professori sono vecchi perche' sono rimasti gli stessi, e insegnano quello che hanno imparato.
Voglio essere ottimista e voglio credere che la tua analisi sia sbagliata; voglio credere che il motivo per cui si insegna il linguaggio di alto livello di più basso livello che ci sia (scusa il gioco di parole :D), lo stesso che è in giro da 40 anni, è perché è diventato un po' lo standard ed è molto richiesto tutt'ora, quindi può essere buono averne padronanza.

In fondo però ho solo paura che tu abbia perfettamente ragione. Il che sarebbe preocupante, non si dovrebbero insegnare argomenti riguardanti un mondo in continua evoluzione con la mente rivolta ai decenni passati. :stordita:

[k0nt3]

io penso e l'ho scritto anche in altri thread che il C è un buon linguaggio per insegnare la programmazione strutturata. e ci tengo a far notare che la programmazione strutturata è anche alla base della programmazione OO moderna.
magari non è il miglior linguaggio per questo scopo, ma considerando la sua sintassi molto popolare e la sua diffusione probabilmente è la scelta migliore.
detto questo penso proprio che si usino anche linguaggi più moderni e consoni a un corso di laurea che si può considerare tale.. quando si affronta la programmazione a oggetti quasi sempre si usa Java. poi spero che diano anche un'infarinatura di linguaggi funzionali e logici (io l'ho avuta).

[k0nt3]

come struttura dati io userei una cosa semplicissima.. una struct contenente i seguenti campi:
- lista delle 10 parole più ricorrenti (inizializzata con stringhe vuote)
- lista dei conteggi corrispondenti alle 10 parole più ricorrenti (inizializzata con zeri)

l'algoritmo funziona così:
si prende la prima parola che si incontra e si conta quante volte sta nel file. si guarda se il conteggio è superiore al minimo conteggio contenuto nella lista dei conteggi.
se è superiore si prende questa parola e la si sbatte nella lista delle parole (prendendosi anche la briga di aggiornare l'indice corrispondente nella lista dei conteggi con il conteggio della parola in questione).
poi si fa lo stesso con la seconda parola (prima però si controlla se per caso è già nella lista delle parole ricorrenti.. nel caso la si ignora) ecc... alla fine si avrà la lista con le parole più ricorrenti (rigorosamente in disordine) e la lista con i rispettivi conteggi (nello stesso disordine dell'altra lista ovviamente). ah tutte le volte che ho detto lista intendevo array :p

ho provato anche a implementarlo e sono un centinaio di righe di codice ;)

[DanieleC88]

Certo, anche io scrivo codice quasi sempre in C ormai. Ma forse per una questione di abitudine, non so, non c'è un vero motivo per farlo. Non mi dispiace come linguaggio, anzi, a me piace anche sintatticamente (cdimauro, abbia pietà :D), però è didatticamente "assurdo". Alcuni miei compagni di corso sono ancora alle prese con i puntatori perché non hanno capito bene cosa siano. Non avendo mai avuto esperienze di programmazione, è normale che abbiano difficoltà ad entrare nell'ottica, in particolare se poi tutto ciò che vedono è "segmentation fault". In Python, ad esempio, avrebbero avuto un output più o meno indicativo direttamente da parte dell'interprete ed avrebbero trovato rapidamente l'errore.

Alcuni argomenti di base sono molto, molto, molto più semplici da imparare "logicamente" con altri linguaggi; imparare a farne implementazioni corrette anche in C poi può venire dopo.
A me pare strano che invece mi facciano due corsi di programmazione C all'università, e che all'ultimo giorno del secondo corso mi si dica "molti problemi di sicurezza sono legati alla natura stessa del C: evitate questo linguaggio quando possibile". A questo punto insegnami Java dall'inizio e poi fammi studiare il C per Sistemi Operativi e basta. ;)

[k0nt3]

due corsi di C??! e a cosa servono :fagiano: come ho detto l'unica utilità a livello didattico è la programmazione strutturata.
al massimo concepisco un corso sulla programmazione di sistema in C, ma non altre cose.
non è assolutamente vero che l'unica informazione disponibile è segmentation fault... ma vi insegnano a usare il debugger? da noi chi non lo usava si beccava le ire del prof :asd: non ti dico se vedeva variabili globali :asd:
è fondamentale anche imparare a usare il debugger, poi è ovvio che quando incontreranno un linguaggio dotato di eccezioni e compagnia avranno la vita un pò più facile, ma intanto hanno imparato a usare uno strumento molto utile.

ps. io non scrivo quasi mai codice C

pps. i puntatori sono facili :D (concetto simile al reference nei linguaggi OO, solo che i reference non hanno un'aritmetica) :ciapet:

[DanieleC88]

No aspe', due corsi di programmazione, che però usavano il C come linguaggio di riferimento... E il debugger è già "oltre", pretendi troppo... :p
Non ce lo insegnano purtroppo, chi lo sa usare è avvantaggiato.

[gugoXX]

come struttura dati io userei una cosa semplicissima.. una struct contenente i seguenti campi:
- lista delle 10 parole più ricorrenti (inizializzata con stringhe vuote)
- lista dei conteggi corrispondenti alle 10 parole più ricorrenti (inizializzata con zeri)

l'algoritmo funziona così:
si prende la prima parola che si incontra e si conta quante volte sta nel file. si guarda se il conteggio è superiore al minimo conteggio contenuto nella lista dei conteggi.
se è superiore si prende questa parola e la si sbatte nella lista delle parole (prendendosi anche la briga di aggiornare l'indice corrispondente nella lista dei conteggi con il conteggio della parola in questione).
poi si fa lo stesso con la seconda parola (prima però si controlla se per caso è già nella lista delle parole ricorrenti.. nel caso la si ignora) ecc... alla fine si avrà la lista con le parole più ricorrenti (rigorosamente in disordine) e la lista con i rispettivi conteggi (nello stesso disordine dell'altra lista ovviamente). ah tutte le volte che ho detto lista intendevo array :p

ho provato anche a implementarlo e sono un centinaio di righe di codice ;)

Funziona, ma e' O(N^2)
Migliorandolo un pelo diventa O(N Log N) (le ricorrenze di una NUOVA parola le devi cercare solo a partire da quella parola li' in poi)
Ma O(N * M) oppure addirittura O(N Log M) sono decisamente meglio. Sono praticamente sempre lineari quando, come nel testo di questo problema, M << N

[gugoXX]

io penso e l'ho scritto anche in altri thread che il C è un buon linguaggio per insegnare la programmazione strutturata. e ci tengo a far notare che la programmazione strutturata è anche alla base della programmazione OO moderna.
magari non è il miglior linguaggio per questo scopo, ma considerando la sua sintassi molto popolare e la sua diffusione probabilmente è la scelta migliore.
detto questo penso proprio che si usino anche linguaggi più moderni e consoni a un corso di laurea che si può considerare tale.. quando si affronta la programmazione a oggetti quasi sempre si usa Java. poi spero che diano anche un'infarinatura di linguaggi funzionali e logici (io l'ho avuta).

Va bene. Sono parzialemente d'accordo.
Solo pero' dovrebbero smettere di insegnare nello stesso corso il C e gli Algoritmi.
Io lo studio degli Algoritmi li avevo fatti in un corso, "Fondamenti di Informatica II", che era anche il corso preposto all'insegnamento del C.
Secondo me e' un errore. Lo studente medio non avra' la padronanza e la capacita' di scrivere, analizzare, capire bene strutture complesse come la hastable, ricerche e ordinamenti non lineari, algoritmi greedy, etc. usando il C che sta pure solo imparando.
Va bene insegnare il C che e' un linguaggio procedurale, diffuso e utile per affrontare altri linguaggi di cui e' la base (Java, C++, C# etc.), pure se ha oramai molte pecche e problemi da affrontare che normalmente non si affrontano sul mondo del lavoro.
Ma quando mi insegni la logica, gli algoritmi, quando mi insegni a programmare, io sceglierei un altro strumento.

[k0nt3]

No aspe', due corsi di programmazione, che però usavano il C come linguaggio di riferimento... E il debugger è già "oltre", pretendi troppo... :p
Non ce lo insegnano purtroppo, chi lo sa usare è avvantaggiato.
nono dovrebbero insegnare a usarlo nelle ore di laboratorio (se previste). non è possibile che uno esce dall'università e non è capace di usarlo :muro:
Funziona, ma e' O(N^2)
Migliorandolo un pelo diventa O(N Log N) (le ricorrenze di una NUOVA parola le devi cercare solo a partire da quella parola li' in poi)
Ma O(N * M) oppure addirittura O(N Log M) sono decisamente meglio. Sono praticamente sempre lineari quando, come nel testo di questo problema, M << N
in realtà è simile alla tua (anche se un pò mi sono perso e non ho capito esattamente quale algoritmo consigli :fagiano: ), cioè di tenere una lista provvisoria con le 10 parole più ricorrenti, solo che la lista non la tengo ordinata :D
perchè trovare il minimo di 10 elementi è abbastanza immediato, quindi lo calcolo al momento di inserire il nuovo elemento nella lista (che è banalmente un array di 10 elementi).
ovviamente si può ottimizzare, ma dal punto di vista della memoria è particolarmente efficente perchè tiene in memoria solo le liste delle 10 parole e dei 10 conteggi delle occorrenze corrispondenti.
dal punto divista temporale direi che è in O(nN) dove n sono le parole diverse tra loro e N è il numero di parole totale (quindi contando anche le ripetizioni), ma ho visto che in pratica si comporta bene, quindi non ho cercato altre soluzioni.
secondo me non ha senso costruire una struttura dati che contiene tutte le occorrenze di tutte le parole, sarebbe troppo dispendioso contando che le parole sono nell'ordine dei 500000
Va bene. Sono parzialemente d'accordo.
Solo pero' dovrebbero smettere di insegnare nello stesso corso il C e gli Algoritmi.
Io lo studio degli Algoritmi li avevo fatti in un corso, "Fondamenti di Informatica II", che era anche il corso preposto all'insegnamento del C.
Secondo me e' un errore. Lo studente medio non avra' la padronanza e la capacita' di scrivere, analizzare, capire bene strutture complesse come la hastable, ricerche e ordinamenti non lineari, algoritmi greedy, etc. usando il C che sta pure solo imparando.
Va bene insegnare il C che e' un linguaggio procedurale, diffuso e utile per affrontare altri linguaggi di cui e' la base (Java, C++, C# etc.), pure se ha oramai molte pecche e problemi da affrontare che normalmente non si affrontano sul mondo del lavoro.
Ma quando mi insegni la logica, gli algoritmi, quando mi insegni a programmare, io sceglierei un altro strumento.
sono assolutamente d'accordo sul fatto che non si può fare un corso di algoritmi e strutture dati in C, noi ad esempio abbiamo fatto informatica1 come classico corso di base (C e architettura basilare del PC EDIT: in effetti anche strutture dati basilari, ma roba molto semplice).
poi informatica2 sempre in C ma che riguardava le basi della programmazione di rete e di sistema (processi, socket, filesystem, funzionamento del processore, della memoria e delle periferiche (bus))
poi informatica3 (panoramica sui paradigmi di programmazione, algoritmi e strutture dati, concorrenza) e ingegneria del software1 (programmazione a oggetti sostanzialmente.. unito ad altri concetti basilari dell'ingegneria del software).
questi ultimi due erano in parallelo e si usava sostanzialmente Java (in informatica3 si portava avanti lo studio di 3 linguaggi.. nel mio caso python, java e ada.. in realtà anche accenni a C++).
infine informatica teorica (con tutti gli argomenti teorici del caso e con particolare attenzione all'argomento complessità)
direi che da qui in poi si inizia a programmare sul serio ;)

[^TiGeRShArK^]

:mbe:
ma veramente il tuo algoritmo ha complessità quadratica nel caso peggiore in cui tutte le parole siano diverse.
Quello di gugo invece tiene in memoria solo le 10 parole con + occorrenze e lo fa con complessità O(N log m) con m = 10 in questo caso.
Ovviamente la lista originale delle parole da ricercare la tenete in memoria sia tu che lui, quindi non c'è assolutamente alcuna differenza nell'utilizzo della memoria, mentre c'è una differenza sostanziale per quanto riguarda la complessità computazionale.

[k0nt3]

:mbe:
ma veramente il tuo algoritmo ha complessità quadratica nel caso peggiore in cui tutte le parole siano diverse.
non mi sembra di aver detto qualcosa di diverso. O(nN) nel caso in cui n=N è O(N^2)

Quello di gugo invece tiene in memoria solo le 10 parole con + occorrenze e lo fa con complessità O(N log m) con m = 10 in questo caso.
Ovviamente la lista originale delle parole da ricercare la tenete in memoria sia tu che lui, quindi non c'è assolutamente alcuna differenza nell'utilizzo della memoria, mentre c'è una differenza sostanziale per quanto riguarda la complessità computazionale.
io la lista non la tengo in memoria ma estraggo una parola alla volta dal file.
è per questo che non capisco a cosa serve l'albero :fagiano:

[^TiGeRShArK^]

vabbè..
e anche lui può leggere una parola alla volta dal file, però tu dovresti rileggere N volte il file per ogni n-esima parola che incontri che sia diversa da quelle che hai in memoria.
Lui invece legge 1 sola volta il file.
In effetti ora che ci penso non basta che si mantenga in memoria solo 10 parole perchè questo andrebbe bene solo per una distribuzione uniforme delle varie parole all'interno del file, e quindi è necessario in effetti memorizzarsi un numero maggiore di parole, anche se così ad occhio direi che è minore del numero totale di parole diverse contenute nel file...

[k0nt3]

per essere più chiaro posto il codice:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void clean_string(char *string);
int count_in_file(char *word, FILE *fp);
int get_index_of_min_count(int counts[10]);
int list_contains_word(char *list[], char *word);

int main()
{
char *top_ten_words[10];
int top_ten_counts[10];

int i;
for(i=0; i<10; ++i)
{
top_ten_counts[i]=0;
top_ten_words[i] = "";
}

FILE *fp = fopen("./testo.txt", "r");
if(fp == NULL)
{
printf("ERROR: file not opened");
return -1;
}

char *current_token;
fscanf(fp, "%as", &current_token);
while(current_token != NULL)
{
clean_string(current_token);
printf("%s ", current_token);
if(list_contains_word(top_ten_words, current_token) < 0)
{
int count = count_in_file(current_token, fp);
int index_of_min_count = get_index_of_min_count(top_ten_counts);
if(count > top_ten_counts[index_of_min_count])
{
top_ten_counts[index_of_min_count] = count;
top_ten_words[index_of_min_count] = current_token;
}
}
fscanf(fp, "%as", &current_token);
}

printf("\n\n");
for(i=0; i<10; ++i)
{
printf("%s (%d)\n", top_ten_words[i], top_ten_counts[i]);
}

return 0;
}

int list_contains_word(char *list[], char *word)
{
int i;
for(i=0; i<10; ++i)
{
if(list[i] != NULL && strcasecmp(word, list[i]) == 0)
return i;
}

return -1;
}

int get_index_of_min_count(int counts[])
{
int min = 0;
int i;
for(i=1; i<10; ++i)
{
if(counts[i]<counts[min])
min = i;
}

return min;
}

int count_in_file(char *word, FILE *fp)
{
int count = 0;
long original_position = ftell(fp);
rewind(fp);

char *current_token;
fscanf(fp, "%as", &current_token);
while(current_token != NULL)
{
clean_string(current_token);
if(strcasecmp(word, current_token) == 0)
++count;

fscanf(fp, "%as", &current_token);
}

fseek(fp, original_position, SEEK_SET);

return count;
}

void clean_string(char *string)
{
char *black_list = ".,!?();:";
char *found = strpbrk(string, black_list);
while(found != NULL)
{
strcpy(found, &found[1]);
found = strpbrk(string, black_list);
}
}

ripeto: non sarà la soluzione più veloce in assoluto, ma usa decisamente poca memoria e nelle prove che ho fatto si comporta anche in maniera accettabile.

ps. fscanf(fp, "%as", &current_token) non è nello standard C, ma è un'estensione GNU. si può ovviare al problema implementando una funzione analoga oppure usando un numero di massimo di caratteri per parola con fscanf(fp, "%20s", current_token) dove 20 è il numero massimo di caratteri e per current_token è stato allocato lo spazio necessario

pps. non ho nemmeno ottimizzato in alcuni punti in cui è possibile ottimizzare

ppps. mi sono permesso di usare strcpy invece di strncpy perchè in quel caso la stringa di destinazione è sempre più grande della stringa sorgente

pppps. la presenza di almeno un bug è certa :asd: (infatti non dealloco mai della memoria.. lo lascio come compito per casa :asd: )

[gugoXX]

Per ogni parola del file, passi di nuovo tutto il file nella Count_In_file.
Questa e' la O(N^2).
Poi aggiungi anche la M per la lista da 10.

Sei a O(N (N+M))
Trascuri la M che ' piccola, sei a O (N^2)
L'algoritmo con hashtable e' O(N)
L'algoritmo con albero implementato prima e' invece O (N Log N).

[k0nt3]

Per ogni parola del file, passi di nuovo tutto il file nella Count_In_file.
Questa e' la O(N^2).
Poi aggiungi anche la M per la lista da 10.

Sei a O(N (N+M))
Trascuri la M che ' piccola, sei a O (N^2)
L'algoritmo con hashtable e' O(N)
L'algoritmo con albero implementato prima e' invece O (N Log N).

La O(N^2) e' da scartare.
passo tutto il file solo se la parola non è contenuta nella lista delle 10 parole più ricorrenti. quindi è un pò più di n*N, ma meno di N^2
in ogni caso si comporta bene se le 10 parole più riccorrenti sono molto più ricorrenti delle altre, mentre si comporta in O(N^2) se le parole hanno tutte le stessa frequenza.
in ogni caso se si risparmia in memoria quasi sempre si perde in prestazioni

[k0nt3]

l'algoritmo con hashtable non è in O(N).. prima devi calcolare tutte le occorrenze di tutte le parole (o no?).

[gugoXX]

E' poco meno di O(N^2), e resta comunque quadratico.
Per quanto riguarda il computo di memoria la hastable o la lista ordinata occupano poco piu' che il file stesso.

Proviamo con un file di testo da 512MB, tu in C veloce e io in C# lento e vediamo cosa succede?

[gugoXX]

l'algoritmo con hashtable non è in O(N).. prima devi calcolare tutte le occorrenze di tutte le parole (o no?).

No. La hastable serve proprio per calcolare le occorrenze. Leggo il file una volta, e ho tutte le occorrenze. Leggo tutta la hashtable e trovo i 10 massimi.
Totale O(2N) (sempre togliendo la M piccola, altrimenti O (2N Log M)

[k0nt3]

sisi con l'hashtable si può trovare tutte le occorrenze di tutte le parole in O(N) quindi è senza dubbio più veloce.
vabbè io l'ho scritto così per usare poca memoria e perchè il codice è più semplice. il prezzo è la complessità temporale

[gugoXX]

sisi con l'hashtable si può trovare tutte le occorrenze di tutte le parole in O(N) quindi è senza dubbio più veloce.
vabbè io l'ho scritto così per usare poca memoria e perchè il codice è più semplice. il prezzo è la complessità temporale

E' esatto, hai fatto un buon lavoro per essere C, ma come sostenevo prima la semplicita' del codice e' dato dallo strumento. Il C e' talmente grezzo da far passare la voglia di implementare le cose come teoria comanda. Ci si perde in problemi secondari come puntatori, memoria, liberare, etc. (che fra l'altro sono sempre gli stessi), e si perde il vero scopo.
Come dicevi giustamente anche tu prima non e' il linguaggio piu' adatto per scrivere algoritmi e strutture dati.
Per inciso, le 5 righe che avevo scritto all'inzio del post risolvono perfettamente il problema in O(N log N), e passare alla O(N * M) e' comunque ancora abbastanza facile.

[Vincenzo1968]

Eqque qua l'implementazione con hash table:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX_STACK 1024
#define BUFFER_SIZE 4096
#define HASHTABLE_SIZE 4093

int NumParole = 0;

typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
} Stati;

typedef struct tagList
{
char *parola;
int count;
struct tagList *next;
} List;

List *ListNewNode(char *info, int count);
List *ListAppend(List *head, char *szKey);
void ListInsertNode(List **head, List *newNode);
void FreeList(List **head);

int Hash(char *szKey, int M);
int FindValue(List **pHashTable, char *szKey);

void BuildFinalList(List **ht, List **a, int nMax);

Stati DFA(char *szFileName, List **pHashTable);

List *ListNewNode(char *info, int count)
{
List *r;
int len;

r = (List *) malloc(sizeof(List));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = count;
r->next = NULL;

return r;
}

List *ListAppend(List *head, char *szKey)
{
List *t = head;

if ( !head )
{
head = ListNewNode(szKey, 1);
return head;
}

while ( t->next != NULL )
{
t = t->next;
}

t->next = ListNewNode(szKey, 1);

return head;
}

void ListInsertNode(List **head, List *newNode)
{
List *current = *head;

if ( *head == NULL ||
(*head)->count <= newNode->count )
{
newNode->next = *head;
*head = newNode;
}
else
{
while ( current->next != NULL &&
current->next->count > newNode->count )
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}

void FreeList(List** head)
{
List *current = *head;
List *next;

while ( current != NULL )
{
next = current->next;
free(current->parola);
free(current);
current = next;
}

*head = NULL;
}

int Hash(char *szKey, int M)
{
int h;
int a = 31415;
int b = 27183;

for ( h = 0; *szKey != 0; szKey++, a = a*b % (M-1) )
h = (a * h + *szKey) % M;

return h < 0 ? h + M : h;
}

int FindValue(List **pHashTable, char *szKey)
{
int index;
List *t;

index = Hash(szKey, HASHTABLE_SIZE);

t = pHashTable[index];
while ( t != NULL )
{
if ( strcmp(t->parola, szKey) == 0 )
{
t->count++;
return 1;
}
t = t->next;
}

return 0;
}

Stati DFA(char *szFileName, List **pHashTable)
{
Stati stato = S0;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;
int index;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
return S_ERROR_OPEN_FILE;

numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
*(buffer + numread + 1) = '\0';

while ( 1 )
{
c = *(buffer + k++);

if ( c == '\0' || c == EOF )
{
k = 0;
numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
if ( numread <= 0 )
break;
*(buffer + numread + 1) = '\0';
c = *(buffer + k++);
}

switch (stato)
{
case S0:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
stato = S0;
}
break;

case S1:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
*(szTemp + x) = '\0';
x = 0;

index = Hash(szTemp, HASHTABLE_SIZE);
if ( !FindValue(pHashTable, szTemp) )
pHashTable[index] = ListAppend(pHashTable[index], szTemp);

stato = S0;
}
break;
}
}

if ( fp )
fclose(fp);

return stato;
}

void BuildFinalList(List **ht, List **a, int nMax)
{
int k = 0;
int min = 0;
int count = 0;
List *temp;

List *listNode;
List *tempListNode;
List *tempListNodePrev;

for (k = 0; k < HASHTABLE_SIZE; k++)
{
temp = ht[k];
while ( temp != NULL )
{
if ( min > temp->count )
min = temp->count;

if ( count < nMax )
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
++count;
}
else
{
if ( temp->count > min )
{
tempListNode = tempListNodePrev = *a;
while ( tempListNode->next != NULL )
{
tempListNodePrev = tempListNode;
tempListNode = tempListNode->next;
}
tempListNodePrev->next = NULL;
free(tempListNode);

listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
}
}

temp = temp->next;
}
}
}

int main()
{
List* ht[HASHTABLE_SIZE];

List *a = NULL;
List *t = NULL;
Stati stato;
int k = 0;

for ( k = 0; k < HASHTABLE_SIZE; k++ )
ht[k] = NULL;

stato = DFA("prova.txt", ht);

if ( stato == S0 || stato == S1 )
{
BuildFinalList(ht, &a, 10);

t = a;
while ( t != NULL )
{
printf("%s -> %d\n", t->parola, t->count);
t = t->next;
}

for ( k = 0; k < HASHTABLE_SIZE; k++ )
FreeList(&ht[k]);

FreeList(&a);
}

return 0;
}

[k0nt3]

certo che se l'hashtable fosse implementata nella libreria standard sarebbe tutta un'altra cosa (EDIT: come non detto :asd: ) linguaggi come C# e java possono anche contare su un framework davvero completo, oltre ovviamente a tutti i costrutti di alto livello.
per il fatto che si perde tempo sulla gestione della memoria sono anche daccordo, per quello dicevo che esistono anche linguaggi migliori per imparare la programmazione strutturata, penso che si usa C per via della sua popolarità (forse è l'unico linguaggio procedurale con cui può capitare di lavorare in una azienda, anche se sono settori di nicchia)

[kingal]

Grazie a tutti per la disponibilità...:)

[Vincenzo1968]

Un miglioramento nella versione con hash table: calcoliamo la dimensione della tabella di hash dinamicamente in base alle dimensioni del file di testo. La dimensione calcolata dalla funzione GetDimHashTable è, per motivi di efficienza, un numero primo:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
} Stati;

typedef struct tagList
{
char *parola;
int count;
struct tagList *next;
} List;

List *ListNewNode(char *info, int count);
List *ListAppend(List *head, char *szKey);
void ListInsertNode(List **head, List *newNode);
void FreeList(List **head);

int GetDimHashTable(char *szFileName);
int Hash(char *szKey, int M);
int FindValue(List **pHashTable, char *szKey, int HashTableSize);

void BuildFinalList(List **ht, List **a, int nMax, int HashTableSize);

Stati DFA(char *szFileName, List **pHashTable, int HashTableSize);

List *ListNewNode(char *info, int count)
{
List *r;
int len;

r = (List *) malloc(sizeof(List));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = count;
r->next = NULL;

return r;
}

List *ListAppend(List *head, char *szKey)
{
List *t = head;

if ( !head )
{
head = ListNewNode(szKey, 1);
return head;
}

while ( t->next != NULL )
{
t = t->next;
}

t->next = ListNewNode(szKey, 1);

return head;
}

void ListInsertNode(List **head, List *newNode)
{
List *current = *head;

if ( *head == NULL ||
(*head)->count <= newNode->count )
{
newNode->next = *head;
*head = newNode;
}
else
{
while ( current->next != NULL &&
current->next->count > newNode->count )
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}

void FreeList(List** head)
{
List *current = *head;
List *next;

while ( current != NULL )
{
next = current->next;
free(current->parola);
free(current);
current = next;
}

*head = NULL;
}

int Hash(char *szKey, int M)
{
int h;
int a = 31415;
int b = 27183;

for ( h = 0; *szKey != 0; szKey++, a = a*b % (M-1) )
h = (a * h + *szKey) % M;

return h < 0 ? h + M : h;
}

int FindValue(List **pHashTable, char *szKey, int HashTableSize)
{
int index;
List *t;

index = Hash(szKey, HashTableSize);

t = pHashTable[index];
while ( t != NULL )
{
if ( strcmp(t->parola, szKey) == 0 )
{
t->count++;
return 1;
}
t = t->next;
}

return 0;
}

Stati DFA(char *szFileName, List **pHashTable, int HashTableSize)
{
Stati stato = S0;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;
int index;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
return S_ERROR_OPEN_FILE;

numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
*(buffer + numread + 1) = '\0';

while ( 1 )
{
c = *(buffer + k++);

if ( c == '\0' || c == EOF )
{
k = 0;
numread = fread(buffer,
sizeof(char),
BUFFER_SIZE,
fp);
if ( numread <= 0 )
break;
*(buffer + numread + 1) = '\0';
c = *(buffer + k++);
}

switch (stato)
{
case S0:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
stato = S0;
}
break;

case S1:
if ( (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z' )
|| (c >= 'A' && c <= 'Z' ) )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
*(szTemp + x) = '\0';
x = 0;

index = Hash(szTemp, HashTableSize);
if ( !FindValue(pHashTable, szTemp, HashTableSize) )
pHashTable[index] = ListAppend(pHashTable[index], szTemp);

stato = S0;
}
break;
}
}

if ( fp )
fclose(fp);

return stato;
}

void BuildFinalList(List **ht, List **a, int nMax, int HashTableSize)
{
int k = 0;
int min = 0;
int count = 0;
List *temp;

List *listNode;
List *tempListNode;
List *tempListNodePrev;

for (k = 0; k < HashTableSize; k++)
{
temp = ht[k];
while ( temp != NULL )
{
if ( min > temp->count )
min = temp->count;

if ( count < nMax )
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
++count;
}
else
{
if ( temp->count > min )
{
tempListNode = tempListNodePrev = *a;
while ( tempListNode->next != NULL )
{
tempListNodePrev = tempListNode;
tempListNode = tempListNode->next;
}
tempListNodePrev->next = NULL;
free(tempListNode);

listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
}
}

temp = temp->next;
}
}
}

int GetDimHashTable(char *szFileName)
{
int ret = -1;
FILE *fp;
fpos_t pos;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
return -1;

if ( fseek(fp, 0, SEEK_END) )
return -1;

if( fgetpos(fp, &pos) != 0 )
return -1;

fclose(fp);

ret = (int)pos / 5;

if ( ret < 509 )
ret = 251;
else if ( ret < 1021 )
ret = 509;
else if ( ret < 2039 )
ret = 1021;
else if ( ret < 4093 )
ret = 2039;
else if ( ret < 8191 )
ret = 4093;
else if ( ret < 16381 )
ret = 8191;
else if ( ret < 32749 )
ret = 16381;
else if ( ret < 65521 )
ret = 32749;
else if ( ret < 131071 )
ret = 65521;
else if ( ret < 262139 )
ret = 131071;
else if ( ret < 524287 )
ret = 262139;
else if ( ret < 1048573 )
ret = 524287;
else
ret = 1048573;

return ret;
}

int main()
{
//List* ht[HASHTABLE_SIZE];
List **ht;

List *a = NULL;
List *t = NULL;
Stati stato;
int x = 0;
int DimensioneHashTable;
char *szNomeFile = "random.txt";

DimensioneHashTable = GetDimHashTable(szNomeFile);
if ( DimensioneHashTable <= 0 )
return -1;

ht = (List**)malloc(sizeof(List*)*DimensioneHashTable);
if ( !ht )
{
printf("Memoria insufficiente.\n");
return -1;
}
for ( x = 0; x < DimensioneHashTable; x++ )
{
ht[x] = (List*)malloc(sizeof(List));
if ( ht[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}

printf("Allocata una hash table di dimensione -> %d\n\n", DimensioneHashTable);

for ( x = 0; x < DimensioneHashTable; x++ )
ht[x] = NULL;

stato = DFA(szNomeFile, ht, DimensioneHashTable);

if ( stato == S0 || stato == S1 )
{
BuildFinalList(ht, &a, 10, DimensioneHashTable);

t = a;
while ( t != NULL )
{
printf("%s -> %d\n", t->parola, t->count);
t = t->next;
}

FreeList(&a);
}

for ( x = 0; x < DimensioneHashTable; x++ )
free(ht[x]);
free(ht);

return 0;
}

[gugoXX]

Vincenzo, hai gia' provato ad usare linguaggi come Python o C#?
(non so se oggi il Java sia messo altrettanto bene dal punto di vista della gestione delle collezioni, quindi non lo cito per ignoranza)

[^TiGeRShArK^]

Vincenzo, hai gia' provato ad usare linguaggi come Python o C#?
(non so se oggi il Java sia messo altrettanto bene dal punto di vista della gestione delle collezioni, quindi non lo cito per ignoranza)
Il java non è male ed è paragonabile al C# 2.0, anzi forse ha qualcosina in + (tipo i Set e qualche altra cazzatina).
Ma rispetto al C# 3.0 con Linq imho è una spanna sotto.
A me al lavoro ha semplificato di MOLTO la vita il Linq, poi ovviamente dipende sempre dai tipi di software con cui si ha a che fare, ma credo che la maggior "potenza" del Linq sia praticamente certa nella maggior parte dei casi.

[Vincenzo1968]

Vincenzo, hai gia' provato ad usare linguaggi come Python o C#?
(non so se oggi il Java sia messo altrettanto bene dal punto di vista della gestione delle collezioni, quindi non lo cito per ignoranza)

Ciao Gugo,

C# lo utilizzo quotidianamente, per lavoro(e lo considero un gran bel linguaggio). In Python, invece, non ho mai programmato.

Questa è la versione 'hash table' in C#:


using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.InteropServices;
using System.IO;

namespace HashTable
{
class Program
{
static Hashtable ht;
static SortedList sl = new SortedList();

[DllImport("kernel32.dll")]
static extern uint GetTickCount();

enum Stati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
}

static private long GetDimHashTable(string FileName)
{
long ret = -1;

FileInfo fi = new FileInfo(FileName);
ret = fi.Length;

ret /= 5;

if (ret < 509)
ret = 251;
else if (ret < 1021)
ret = 509;
else if (ret < 2039)
ret = 1021;
else if (ret < 4093)
ret = 2039;
else if (ret < 8191)
ret = 4093;
else if (ret < 16381)
ret = 8191;
else if (ret < 32749)
ret = 16381;
else if (ret < 65521)
ret = 32749;
else if (ret < 131071)
ret = 65521;
else if (ret < 262139)
ret = 131071;
else if (ret < 524287)
ret = 262139;
else if (ret < 1048573)
ret = 524287;
else
ret = 1048573;

return ret;
}

static private Stati DFA(string FileName)
{
Stati stato = Stati.S0;
string buffer;
StringBuilder strTemp = new StringBuilder();
string strKey;
char c;
int k = 0;

StreamReader sr = new StreamReader(FileName);

buffer = sr.ReadToEnd();
if (buffer.Length <= 0)
{
sr.Close();
return Stati.S_ERROR;
}

for (;;)
{
if (k == buffer.Length)
break;

c = buffer[k++];

switch (stato)
{
case Stati.S0:
if ((c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z')
|| (c >= 'A' && c <= 'Z'))
{
strTemp.Append(c);
stato = Stati.S1;
}
else
{
stato = Stati.S0;
}
break;

case Stati.S1:
if ((c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z')
|| (c >= 'A' && c <= 'Z'))
{
strTemp.Append(c);
stato = Stati.S1;
}
else
{
strKey = strTemp.ToString();
strTemp = new StringBuilder();

if (strKey.Length > 3)
{
if (!ht.ContainsKey(strKey))
{
ht.Add(strKey, 1);
}
else
{
int count = (int)ht[strKey];
ht[strKey] = count + 1;
}
}

stato = Stati.S0;
}
break;
}
}

return stato;
}

static void Main(string[] args)
{
int min = 0;
int nMax = 20;
int count = 0;
string KeyToRemove = "";

uint ms1 = GetTickCount();

ht = new Hashtable((int)GetDimHashTable("romanzo.txt"));

Stati stato = DFA("romanzo.txt");
if (stato == Stati.S0 || stato == Stati.S1)
{
foreach (DictionaryEntry de in ht)
{
if (count < nMax)
{
sl.Add(de.Key, de.Value);

if ((int)de.Value < min || min == 0)
{
min = (int)de.Value;
KeyToRemove = (string)de.Key;
}

count++;
}
else
{
if ((int)de.Value > min)
{
sl.Remove(KeyToRemove);
sl.Add(de.Key, de.Value);

min = 0;

foreach (DictionaryEntry de2 in sl)
{
if ((int)de2.Value < min || min == 0)
{
min = (int)de2.Value;
KeyToRemove = (string)de2.Key;
}
}
}
}
}

foreach (DictionaryEntry de in sl)
{
Console.WriteLine(de.Key + " -> " + de.Value);
}
}

uint ms2 = GetTickCount();

Console.WriteLine("\nTempo impiegato -> " + (ms2 - ms1));
}
}
}


Ho preso i tempi di esecuzione del programma tramite la funzione GetTickCount della api di Windows. Il file di testo contiene il romanzo "I Viceré" di Federico De Roberto e ha una dimensione di circa 1.22 MB.

In C# il tempo ottenuto è 235 millisecondi; in C è leggermente più veloce con 156 millisecondi.

[gugoXX]

Scusami se mi permetto Vincenzo.
Hai fatto un ottimo lavoro, ma non e' cosi' che si usa il C#.

Un neofita che capitasse da queste parti e leggesse la tua prima implementazione in C, e la seconda in C#, pure piu' lenta, che conclusioni ne trarrebbe?

Una versione potenziale dello stesso problema, risolto in C#, la trovi all'inzio, 7 righe, che riporto qui, dove per un testo da 2MB impiega 180ms sulla mia macchina. e non e' l'algoritmo che avevamo studiato, ma quello con l'ordinamento dopo l'hashtable.

string text = File.ReadAllText(@"C:\temp\grext10.txt");
text += text;

Stopwatch watch = new Stopwatch();
watch.Start();

string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);

var res = from word in words
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(10);

var finale = first10.ToList();

watch.Stop();

finale.ForEach(Console.WriteLine);
Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);
Console.ReadKey();


Se non ti dovesse paicere quella versione, posso proporne una in C#2.0, senza il LINQ, ma sono sicuro che verrebbe comunque piu' concisa della tua versione.
Il bello del C# e' che molto e' gia' implementato, come le hashtable, e non vedo il motivo di rifarle a mano.

Per prendere i tempi c'e' la classe Stopwatch della diagnostic, per non scomodare l'SDK.

[Vincenzo1968]

Scusami se mi permetto Vincenzo.
Il bello del C# e' che molto e' gia' implementato, come le hashtable, e non vedo il motivo di rifarle a mano.

.

Figurati Gugo, quando c'è da imparare sono sempre disponibile.
La maggior parte del codice che ho postato serve per implementare l'automa a stati finiti. Per la hash table utilizzo quella disponibile in C#.

Provo a utilizzare i tuoi suggerimenti(con la text.Split al posto dell'automa e ti faccio sapere i risultati del confronto).

[gugoXX]

OK.

Metto qui una versione C#2.0 (quasi, non avevo voglia di implementare l'ordinatore e ho barato con una lambda function).


using KVP = KeyValuePair<string, int>;

class Program
{
static void Main(string[] args)
{
//string text = new WebClient().DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt"); // Great Expectations
string text = File.ReadAllText(@"C:\temp\grext10.txt");
text += text;

Stopwatch watch = new Stopwatch();

watch.Start();
string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);

Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (occorrenze.ContainsKey(word)) occorrenze[word]++;
else occorrenze[word] = 0;
}

List<KVP> partial = new List<KVP>(occorrenze);
partial.Sort((t, u) => (u.Value - t.Value));

List<string> output = new List<string>();
for (int t = 0; t < 10 && t < partial.Count; t++)
{
output.Add(partial[t].Key);
}

watch.Stop();

output.ForEach(Console.WriteLine);

Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);
Console.ReadKey();
}
}

[Vincenzo1968]

Ho effettuato i test con questo codice:


int nMax = 10;
string text = File.ReadAllText("romanzo.txt");
text += text;

Console.WriteLine();

Stopwatch watch = new Stopwatch();
watch.Start();

//string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
string[] words = text.Split(new char[] { '«', '»', '.', ',', ';', ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);

var res = from word in words where word.Length > 10
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(nMax);

var finale = first10.ToList();

watch.Stop();

finale.ForEach(Console.WriteLine);
Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);


Questo è il risultato per la versione in C# con LINQ:

http://www.guidealgoritmi.it/images/VersioneCSharp.jpg

Questo è il risultato per la versione C:

http://www.guidealgoritmi.it/images/VersioneC.jpg

Purtroppo tale confronto non può considerarsi valido perché, nella versione C#, il conteggio risulta errato. Ho verificato manualmente(con il comando trova di 'BLocco Note', non rileggendomi tutto il romanzo ;) ) che, per esempio, la parola 'rivoluzione' è presente 52 volte e non 78.

Bisognerebbe aggiungere dei caratteri di controllo all'array

... new char[] { '«', '»', '.', ',', ';', ' ', '\t', '\n', '\r', '-' }, ...

in modo da ottenere il risultato corretto. Sai come si possa fare?

Il file di testo che uso(Il romanzo "I Viceré" di De Roberto), lo puoi creare incollando il testo dal file che puoi scaricare, in formato pdf o rtf, da qui:

http://www.liberliber.it/biblioteca/d/de_roberto/index.htm

[Vincenzo1968]

Lo stesso problema si verifica con la versione C#2.0.

Se riusciamo a splittare l'input nel modo giusto(il che è relativamente facile con un automa a stati finiti) siamo a posto.

[Vincenzo1968]

E c'è anche un risultato sorprendente: la versione C con albero binario di ricerca risulta molto più veloce rispetto a quella(sempre in C) con hash table.

Considerando la ricerca delle dieci parole più frequenti(con lunghezza > 10 ), ottengo questo risultato:

http://www.guidealgoritmi.it/images/VersioneC_ConAlbero.jpg

Posto nuovamente il codice perchè ho effettuato qualche modifica per ottimizzarlo un po' (per esempio, il file non viene più letto a blocchi):


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <windows.h>

#define MAX_STACK 1024

typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
} Stati;

typedef struct tagTree
{
char *parola;
int count;
struct tagTree *left;
struct tagTree *right;
} Tree;

typedef struct tagList
{
char *parola;
int count;
struct tagList *next;
} List;

Tree *NewNode(char *info);
Tree *InsertNode(Tree *node, char *key);
void FreeTree(Tree *head);

List *ListNewNode(char *info, int count);
void ListInsertNode(List **head, List *newNode);
void FreeList(List **head);

void InOrder(Tree *head, List **a, int nMax);

Stati DFA(char *szFileName, Tree **pTree);

List *ListNewNode(char *info, int count)
{
List *r;
int len;

r = (List *) malloc(sizeof(List));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = count;
r->next = NULL;

return r;
}

void ListInsertNode(List **head, List *newNode)
{
List *current = *head;

if ( *head == NULL ||
(*head)->count <= newNode->count )
{
newNode->next = *head;
*head = newNode;
}
else
{
while ( current->next != NULL &&
current->next->count > newNode->count )
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}

void FreeList(List** head)
{
List *current = *head;
List *next;

while ( current != NULL )
{
next = current->next;
free(current->parola);
free(current);
current = next;
}

*head = NULL;
}

Tree *NewNode(char* info)
{
Tree *r;
int len;

r = (Tree *) malloc(sizeof(Tree));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}

strcpy(r->parola, info);
r->count = 1;
r->left = NULL;
r->right = NULL;

++NumParole;

return r;
}

Tree *InsertNode(Tree *node, char *key)
{
Tree *pRadice = NULL;
int nRes;

if( !node )
{
node = NewNode(key);
return node;
}

pRadice = node;

while( 1 )
{
nRes = strcmp(key, node->parola);

if ( nRes < 0 )
{
if ( !node->left )
{
node->left = NewNode(key);
break;
}
node = node->left;
}
else if ( nRes > 0 )
{
if ( !node->right )
{
node->right = NewNode(key);
break;
}
node = node->right;
}
else // Trovato
{
node->count++;
break;
}
}

node = pRadice;

return node;
}

void FreeTree(Tree *head)
{
Tree *temp1, *temp2;

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( !head )
return;

temp1 = temp2 = head;

while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
stack[top++] = temp1;

while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
free(temp2->parola);
free(temp2);
if ( top == 0 )
return;
temp1 = stack[--top];
}

stack[top++] = temp1;
temp1 = temp1->right;
}
}

void InOrder(Tree *head, List **a, int nMax)
{
int k = 0;
Tree *temp;

List *listNode;
List *tempListNode;
List *tempListNodePrev;

Tree *stack[MAX_STACK];
int top;
top = -1;

if ( !head )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
if ( top < MAX_STACK )
{
stack[++top] = temp; // Push
temp = temp->left;
}
else
{
printf("Errore: lo stack e' pieno.\n");
return;
}
}
else
{
if ( top >= 0 )
{
temp = stack[top--]; // Pop

if ( k < nMax )
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
}
else
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);

tempListNode = tempListNodePrev = *a;
while ( tempListNode->next != NULL )
{
tempListNodePrev = tempListNode;
tempListNode = tempListNode->next;
}
tempListNodePrev->next = NULL;
free(tempListNode);
}

k++;

temp = temp->right;
}
else
{
break;
}
}
}
}

Stati DFA(char *szFileName, Tree **pTree)
{
Stati stato = S0;
FILE *fp;
char *buffer;
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;
int dimFile = 0;
fpos_t pos;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
return S_ERROR_OPEN_FILE;

if ( fseek(fp, 0, SEEK_END) )
return -1;

if( fgetpos(fp, &pos) != 0 )
return -1;

dimFile = (int)pos;

if ( fseek(fp, 0, SEEK_SET) )
return -1;

buffer = (char*)malloc(sizeof(char)*dimFile + 1);
if ( !buffer )
{
printf("Errore nell'allocazione della memoria.");
fclose(fp);
return -1;
}

numread = fread(buffer,
sizeof(char),
dimFile,
fp);
if ( numread != dimFile )
{
fclose(fp);
return -1;
}
*(buffer + numread + 1) = '\0';

while ( k < dimFile )
{
c = *(buffer + k++);

switch (stato)
{
case S0:
if ( isalnum(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò' )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
stato = S0;
}
break;

case S1:
if ( isalnum(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò' )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
*(szTemp + x) = '\0';
x = 0;

if ( strcmp("principessa", szTemp) == 0 )
g_countPrincipessa++;

if ( strlen(szTemp) > 10 )
{
*pTree = InsertNode(*pTree, szTemp);
if ( *pTree == NULL )
return S_ERROR;
}

stato = S0;
}
break;
}
}

free(buffer);

if ( fp )
fclose(fp);

return stato;
}

int main()
{
Tree * p = NULL;
List *a = NULL;
List *t = NULL;
Stati stato;
DWORD ms;
char *szNomeFile = "romanzo.txt";
int nMax = 10;

ms = GetTickCount();

stato = DFA(szNomeFile, &p);

if ( stato == S0 || stato == S1 )
{
InOrder(p, &a, nMax);

t = a;
while ( t != NULL )
{
printf("%s -> %d\n", t->parola, t->count);
t = t->next;
}

FreeTree(p);
FreeList(&a);
}

printf("\n\nTempo impiegato(in millisecondi) -> %d\n", GetTickCount() - ms);

return 0;
}

[gugoXX]

Vincenzo, occhio che con
text += text;
Contavo di raddoppiare il testo, perche' il mio testo di prova era troppo piccolo...

Comunque la versione a Dictionary dovrebbe essere piu' veloce della versione LINQ.
Ho anche idea che una parte consistente del tempo la si passi nella split invece che nell'algoritmo vero e proprio.
Se vuoi testare gli algoritmi di conteggio sarebbe bene togliere la split e l'automa a stati finiti dal conteggio.

[Vincenzo1968]

Vincenzo, occhio che con
text += text;
Contavo di raddoppiare il testo, perche' il mio testo di prova era troppo piccolo...

Comunque la versione a Dictionary dovrebbe essere piu' veloce della versione LINQ.
Ho anche idea che una parte consistente del tempo la si passi nella split invece che nell'algoritmo vero e proprio.
Se vuoi testare gli algoritmi di conteggio sarebbe bene togliere la split e l'automa a stati finiti dal conteggio.

Non mi ero accorto di text += text;

Il codice è naturalmente molto più veloce ma il conteggio è comunque errato(per 'rivoluzione', ad esempio, dovrebbe essere 52 anziché 48):

http://www.guidealgoritmi.it/images/VersioneCSharp2.jpg

Il codice è questo :


int nMax = 10;
string text = File.ReadAllText("romanzo.txt");

Console.WriteLine();

Stopwatch watch = new Stopwatch();
watch.Start();

//string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
string[] words = text.Split(new char[] { '\'', '«', '»', '.', ',', ':', ';', '!', '?', ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);

var res = from word in words where word.Length > 10
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(nMax);

var finale = first10.ToList();

watch.Stop();

finale.ForEach(Console.WriteLine);
Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);

[Vincenzo1968]

Comunque la versione a Dictionary dovrebbe essere piu' veloce della versione LINQ.


No. Ottengo questo risultato:

http://www.guidealgoritmi.it/images/VersioneCSharp3.jpg

con questo codice:


string text = File.ReadAllText("romanzo.txt");

Stopwatch watch = new Stopwatch();

watch.Start();
//string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
string[] words = text.Split(new char[] { '\'', '«', '»', '.', ',', ':', ';', '!', '?', ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);

Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (occorrenze.ContainsKey(word) && word.Length > 10)
occorrenze[word]++;
else
occorrenze[word] = 0;
}

List<KVP> partial = new List<KVP>(occorrenze);
partial.Sort((t, u) => (u.Value - t.Value));

List<string> output = new List<string>();
for (int t = 0; t < 10 && t < partial.Count; t++)
{
output.Add(partial[t].Key);
}

watch.Stop();

output.ForEach(Console.WriteLine);

Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);

[gugoXX]

Ci sono 2 errori



Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (occorrenze.ContainsKey(word) && word.Length > 10)
occorrenze[word]++;
else
occorrenze[word] = 0;
}



Se il dizionario contiene la parola e se la parola e' piu' lunga di 10 caratteri allora incrementi il contatore.
Altrimenti azzeri il dizionario. Non mi quadra.
Direi che dovresti scrivere qualcosa tipo

Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (word.Length > 10)
{
if (occorrenze.ContainsKey(word)) occorrenze[word]++;
else occorrenze[word]=1;
}
}

[Vincenzo1968]

Ci sono 2 errori

Se il dizionario contiene la parola e se la parola e' piu' lunga di 10 caratteri allora incrementi il contatore.
Altrimenti azzeri il dizionario. Non mi quadra.
Direi che dovresti scrivere qualcosa tipo

Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (word.Length > 10)
{
if (occorrenze.ContainsKey(word)) occorrenze[word]++;
else occorrenze[word]=1;
}
}


Fatto.
Questo è il codice :


string text = File.ReadAllText("romanzo.txt");

Stopwatch watch = new Stopwatch();

watch.Start();
//string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
string[] words = text.Split(new char[] { '\'', '«', '»', '.', ',', ':', ';', '!', '?', ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);

/*
Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (occorrenze.ContainsKey(word) && word.Length > 10)
occorrenze[word]++;
else
occorrenze[word] = 0;
}
*/

Dictionary<string, int> occorrenze = new Dictionary<string, int>();
foreach (string word in words)
{
if (word.Length > 10)
{
if (occorrenze.ContainsKey(word)) occorrenze[word]++;
else occorrenze[word] = 1;
}
}

List<KVP> partial = new List<KVP>(occorrenze);
partial.Sort((t, u) => (u.Value - t.Value));

List<string> output = new List<string>();
for (int t = 0; t < 10 && t < partial.Count; t++)
{
output.Add(partial[t].Key);
}

watch.Stop();

output.ForEach(Console.WriteLine);

Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);


e questo è il risultato:

http://www.guidealgoritmi.it/images/VersioneCSharp4.jpg

Il tempo di esecuzione migliora ma il problema è nella split( nota la parola '?Eccellenza' col punto interrogativo davanti.

È possibile stampare il conteggio accanto a ogni parola?

[gugoXX]

Il tempo di esecuzione migliora ma il problema è nella split( nota la parola '?Eccellenza' col punto interrogativo davanti.

È possibile stampare il conteggio accanto a ogni parola?

Per il conteggio accanto ad ogni parola usa la:

var first10 = res.OrderByDescending(t => t.value).Take(nMax);
var output = first10.ToList();


Invece che tutto il blocco

List<KVP> partial = new List<KVP>(occorrenze);
partial.Sort((t, u) => (u.Value - t.Value));

List<string> output = new List<string>();
for (int t = 0; t < 10 && t < partial.Count; t++)
{
output.Add(partial[t].Key);
}


Comunque stiamo parlando un decimo di secondo. Secondo me in tempi cosi' brevi ci sono troppi overhead per poter apprezzare effettivamente la bonta' di un algoritmo. Proverei con testi piu' lunghi, oppure con lo stesso testo replicato un centinaio di volte.
Per altro non prenderei il primo risultato dopo una compilazione, ma i successivi 3-4 e poi farei una media.
Poi occorre compilare il Release in tutti gli ambienti, per poter apprezzare la velocita' del C rispetto al C#, a parita' di tutto il resto.

Per quanto riguarda il punto interrogativo sembra un mistero. A meno che quello del testo non sia proprio un punto interrogativo...

[Vincenzo1968]

Per quanto riguarda il punto interrogativo sembra un mistero. A meno che quello del testo non sia proprio un punto interrogativo...


Per quanto riguarda il punto interrogativo sembra un mistero. A meno che quello del testo non sia proprio un punto interrogativo...

No, non c'è:

http://img26.imageshack.us/img26/6194/eccellenza.jpg

e anche se ci fosse, un buon analizzatore lessicale dovrebbe essere in grado di gestire la situazione. Come avviene con i compilatori che, per esempio, sono in grado di suddividere in token un'espressione sia nel caso che questa contenga spazi, come in '8 + 5', sia nel caso contrario, '8+5'. In entrambi i casi il compilatore suddivide la stringa nei token costante numerica - operatore - costante numerica.
Questa cosa si realizza facilmente con un automa a stati finiti(ed è il metodo adottato dai compilatori per l'analisi lessicale).
Forse, qualche volta, vale la pena scrivere qualche riga di codice in più, se non altro per ottenere una maggiore flessibilità.
Considera per esempio se, invece di contare tutte le parole, volessimo contare solo quelle contenute all'interno dei dialoghi(quindi quelle contenute tra i caratteri '«' e '»'). Con la split come lo fai?
Con l'automa a stati finiti basta aggiungere un paio di stati e il gioco è fatto.

C'è, inoltre, nella versione C# con 'split', il problema del conteggio errato. Per esempio, per la parola 'rivoluzione' dà 48 occorrenze quando in realtà, come riporta giustamente la versione C, dovrebbe dare 52.
Ho controllato manualmente con il comando "Trova" di Blocco Note.
Puoi verificare di persona scaricando il romanzo da qui:

http://www.liberliber.it/biblioteca/d/de_roberto/index.htm

[DanieleC88]

Guardate, non conosco il C#, ma la cosa da fare sarebbe controllare il valore di ogni carattere: se è alfabetico è parte di una parola, quando è un qualsiasi altro valore lo si interpreta come "separatore" e stop, altrimenti bisognerebbe passare un'infinità di separatori alla split() per avere un funzionamento corretto...

[Vincenzo1968]

Guardate, non conosco il C#, ma la cosa da fare sarebbe controllare il valore di ogni carattere: se è alfabetico è parte di una parola, quando è un qualsiasi altro valore lo si interpreta come "separatore" e stop, altrimenti bisognerebbe passare un'infinità di separatori alla split() per avere un funzionamento corretto...

Quello che hai descritto è, bene o male, il funzionamento di un automa a stati finiti. È il metodo più efficace e non per niente è quello utilizzato dai compilatori per effettuare l'analisi lessicale del codice sorgente.

Ho portato la dimensione del file di testo a 13.5 MB (circa dieci volte copia e incolla). I risultati sono i seguenti:

C# con LINQ:
http://img163.imageshack.us/img163/4873/csharplinq.jpg

C# con Dictionary:
http://img72.imageshack.us/img72/485/csharpdictionary.jpg

C con automa a stati finiti e hash table:
http://img525.imageshack.us/img525/460/chashtable.jpg

C con automa a stati finiti e albero binario di ricerca:
http://img833.imageshack.us/img833/319/cbst.jpg

L'implementazione con albero binario di ricerca è ulteriormente migliorabile utilizzando un albero Red-Black( o AVL) ;)

[gugoXX]

Guardate, non conosco il C#, ma la cosa da fare sarebbe controllare il valore di ogni carattere: se è alfabetico è parte di una parola, quando è un qualsiasi altro valore lo si interpreta come "separatore" e stop, altrimenti bisognerebbe passare un'infinità di separatori alla split() per avere un funzionamento corretto...

Dici facile.
I seguenti sono caratteri da tenere o no?
éÉ (che fra l'altro p.es. in Inglese non ci sono)

E questi?
âäåèéíîñąĀúýąćœǼǻ
Sono forse meno nobili?

E questi?
ڝڠڬںڛڝ
Ancora meno nobili?

che facciamo? Una lista? :D

comunque al posto di un automa per un problema come questo preferirei una RegularExpression, che alla fine e' un automa, ma ridotto dal compilatore di regular expression.
Resta che dalla lista secondo me non ci si esce.
Se volete i caratteri [A-Za-z0-9] e' semplicissimo, ma appunto leviamo via le lettere accentate, le dieresi, le y rovesciate, etc.etc.

Prima di fare i confronti di tempistiche occorre essere certi che il dominio delle parole su cui si sta cercando sia lo stesso.

[DanieleC88]

E infatti quelli in Unicode sono tutti caratteri "alfabetici" (che sia o no il nostro alfabeto). :O

:D

Hmm comunque sì, è un problemuccio più vasto della portata che prevedevo... :what:
Vado a ripassarmi un po' di codifica dei caratteri... :)

[gugoXX]

A me il risultato in C# con LINQ viene in 2 secondi.
Di tutto questo tempo, solo 135ms sono la costruzione il filtro e l'ordinamento.
Tutti i restanti 1.8secondi sono sulla Split.

E' difficile confrontare gli algoritmi cosi'.
a meno che il nuovo problema sia
"Trovare il modo piu' efficiente di spaccare un testo in parole", mettendo pero' bene in chiaro cosa voglia dire.

[^TiGeRShArK^]

Se devi veramente trovare l'algoritmo piu' efficiente, allora voto per una hashtable (classica, non ordinata), in cui la chiave e' la singola parola, mentre il valore e' l'occorrenza di tale parola.
Alla fine ordini una sola volta per occorrenza e prendi le prime 10 parole.

Se e' un'implementazione che ti serve per lavoro ok, altrimenti in C gestire una hashtable mi sa che e' proprio scomodo.

vuoi un assaggio di C# che faccia proprio la stessa cosa?
La hashtable in questione e' nascosta nel codice linq nell'istruzione Group By.
La manipolazione di "gruppi", come liste, hastable, code, stack, etc. e' quello che e' considerato il secondo punto forte del C#, dopo l'introduzione della Garbage Collection in un linguaggio C++ style.


string text = new WebClient().DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt"); // Great Expectations
string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);

var res = from word in words
group word by word into gruppo
select new {parola = gruppo.Key, occorrenza = gruppo.Count()};

var first10 = res.OrderByDescending(t => t.occorrenza).Take(10);

first10.ForEach(Console.WriteLine);

ma il metodo .ForEach() cos'è? :mbe:
un extension method che hai creato tu o l'hai preso da qualche libreria? :fagiano:

[gugoXX]

Sisi... e' un extension method che oramai mi porto dietro da quando le extension method esistono.
L'ho attaccato alla templeate degli IEnumerable, cosi' in pratica qualsiasi collezione ne puo' beneficiare (anche gli array)

Ne ho due versioni, analoghe.
La prima e' la piu' vecchia e fa uso della ForEach sulle liste, gia' presente sul C#2.0, da preferirsi quando ci sono lavori remoti in ballo da finire il piu' presto possibile (es: database). Essa infatti prende tutti i dati dell'enumerazione e POI appica l'azione per ciascuno di essi.
La seconda invece scoda in stile pipeline, da preferire negli altri casi perche' fa uso di meno memoria.


public static void Foreach<T>(this IEnumerable<T> domain, Action<T> action)
{
domain.ToList().ForEach(action);
}


public static void Foreach<T>(this IEnumerable<T> domain, Action<T> action)
{
foreach (T elem in domain) action(elem);
}

[^TiGeRShArK^]

tnx :p

[Vincenzo1968]

A me il risultato in C# con LINQ viene in 2 secondi.
Di tutto questo tempo, solo 135ms sono la costruzione il filtro e l'ordinamento.
Tutti i restanti 1.8secondi sono sulla Split.

E' difficile confrontare gli algoritmi cosi'.
a meno che il nuovo problema sia
"Trovare il modo piu' efficiente di spaccare un testo in parole", mettendo pero' bene in chiaro cosa voglia dire.

Non si tratta di spaccare alcunché. Il problema è quello di suddividere correttamente le parole del testo(e fornire il numero di occorrenze esatto). Per 'parole', anche se l'esercizio non lo specifica, dovrebbe intendersi 'parole della lingua italiana'. Ora, ti sembra che '?Eccellenza' appartenga all'insieme delle parole della lingua italiana?

Vogliamo fornire una versione corretta in C#?
Altrimenti, che conclusioni potrebbe trarre il neofita che capitasse da queste parti e leggesse la mia prima implementazione in C, e la seconda in C#, pure piu' lenta? ...

... che in C# si scrive molto meno codice ma che il risultato ottenuto non è corretto? :cool:

La soluzione che propongo è questa:


using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.InteropServices;
using System.IO;
using System.Diagnostics;

namespace ContaParole2
{
class Program
{
static private ArrayList words = new ArrayList();

enum Stati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
}

static private Stati DFA(string FileName)
{
Stati stato = Stati.S0;
string buffer;
StringBuilder strTemp = new StringBuilder();
string strKey;
char c;
int k = 0;

StreamReader sr = new StreamReader(FileName);

if (!File.Exists(FileName))
return Stati.S_ERROR;

buffer = File.ReadAllText(FileName);

words.Capacity = buffer.Length / 100;

for (; ; )
{
if (k == buffer.Length)
break;

c = buffer[k++];

switch (stato)
{
case Stati.S0:
if (char.IsLetterOrDigit(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò')
{
strTemp.Append(c);
stato = Stati.S1;
}
else
{
stato = Stati.S0;
}
break;

case Stati.S1:
if (char.IsLetterOrDigit(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò')
{
strTemp.Append(c);
stato = Stati.S1;
}
else
{
strKey = strTemp.ToString();
strTemp = new StringBuilder();

if ( strKey.Length > 10)
words.Add(strKey);

stato = Stati.S0;
}
break;
}
}

return stato;
}

static void Main(string[] args)
{
Stati stato;
int nMax = 10;
string FileName = "romanzoOld.txt";
string text = File.ReadAllText(FileName);

Console.WriteLine();

Stopwatch watch = new Stopwatch();
watch.Start();

stato = DFA(FileName);
if (stato == Stati.S0 || stato == Stati.S1)
{

var res = from word in words.ToArray()
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(nMax);

var finale = first10.ToList();

watch.Stop();

finale.ForEach(Console.WriteLine);
Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);
}
}
}
}


Utilizzo un automa a stati finiti per splittare le parole del file di testo.

questo è il risultato(considerando il file originale di circa 1.22 MB e filtrando le parole con lunghezza > 10):

http://img825.imageshack.us/img825/5176/dfacsharp.jpg

Come vedi, rispetto alla tua versione, per implementare l'automa bisogna scrivere qualche riga di codice in più. Ma i risultati sono corretti(per la parola 'rivoluzione', per esempio, si ottiene un conteggio di 52, che è quello giusto).

;)

[gugoXX]

Hai circoscritto e descritto meglio il problema.
Il problema del codice da me utilizzato prima e' che non funziona con file che non sono in ASCII puro, come il testo di prova. L'ASCII puro prevede caratteri solo nel range 0-127

Comunque lo stile C# e' diverso, sembra molto simile al C quello.
Come detto avrei comunque usato una RegularExpression per questo problema, e non avrei riscritto l'automa a mano.

Un codice equivalente al tuo io lo scriverei cosi'


static void Main(string[] args)
{
string text = File.ReadAllText(@"C:\temp\i_vice_t.txt");

Stopwatch watch = new Stopwatch();

watch.Start();
string[] words = Regex.Split(text, "[^a-zA-Z0-9èéìàùò]+");
watch.Stop();
Console.WriteLine("Spaccare: Time - {0}", watch.ElapsedMilliseconds);
watch.Reset();

watch.Start();
var res = from word in words.ToArray()
where word.Length>10
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(10);

var finale = first10.ToList();

watch.Stop();

finale.ForEach(Console.WriteLine);
Console.WriteLine();
Console.WriteLine("Filtrare: Time - {0}", watch.ElapsedMilliseconds);
Console.ReadLine();
}



Spaccare: Time - 214

Filtrare: Time - 10
{ parola = principessa, occorrenza = 307 }
{ parola = Baldassarre, occorrenza = 117 }
{ parola = Francalanza, occorrenza = 100 }
{ parola = specialmente, occorrenza = 68 }
{ parola = rivoluzione, occorrenza = 52 }
{ parola = amministrazione, occorrenza = 40 }
{ parola = primogenito, occorrenza = 37 }
{ parola = naturalmente, occorrenza = 35 }
{ parola = opposizione, occorrenza = 29 }
{ parola = Benedettini, occorrenza = 26 }

[Vincenzo1968]

Perfetto!

L'implementazione con automa è tuttavia più veloce(89 ms contro 214). Forse vale la pena scrivere un po' di codice a mano?

Ciao.

[DanieleC88]

Forse vale la pena scrivere un po' di codice a mano?
Certo. Se ce n'è il bisogno, perché no? Anche io ho provato a ripetere il problema in C e mi sono fatto il parser a mano. Ma se ci sono modi già pronti e contesti, come questo, dove i millesecondi non ti condizionano più di tanto, perché arrischiarsi in una implementazione che potrebbe essere non corretta? :)

[gugoXX]

Come detto il C# non e' fatto per andare veloci, ma per sbagliare meno.
E poi spesso si va anche piu' veloci perche' si guardano di piu' gli algoritmi piuttosto che perdersi in minuzie tecniche.

Comunque se venisse qualcuno a dirmi che la regular expression e' troppo lenta, allora io scriverei cosi'.


static void Main(string[] args)
{
string text = File.ReadAllText(@"C:\temp\i_vice_t.txt");

Stopwatch watch = new Stopwatch();
watch.Start();

var res = from word in SpaccoAMano(text)
where word.Length>10
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(10);

var finale = first10.ToList();

watch.Stop();
Console.WriteLine();
Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);
finale.ForEach(Console.WriteLine);

Console.ReadLine();
}

public static IEnumerable<string> SpaccoAMano(string text)
{
int len = text.Length;
int startword = -1;
for (int t = 0; t < len; t++)
{
char c = text[t];
if (char.IsLetterOrDigit(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò')
{
if (startword == -1) startword = t;
}
else
{
if (startword != -1)
{
int wordlength = t - startword;
string ret = text.Substring(startword, wordlength);
yield return ret;
startword = -1;
}
}
}
}




Time - 45
{ parola = principessa, occorrenza = 307 }
{ parola = Baldassarre, occorrenza = 117 }
{ parola = Francalanza, occorrenza = 100 }
{ parola = specialmente, occorrenza = 68 }
{ parola = rivoluzione, occorrenza = 52 }
{ parola = amministrazione, occorrenza = 40 }
{ parola = primogenito, occorrenza = 37 }
{ parola = naturalmente, occorrenza = 35 }
{ parola = opposizione, occorrenza = 29 }
{ parola = Benedettini, occorrenza = 26 }

[Vincenzo1968]

Nel calcolo dei tempi metterei anche il tempo necessario per la lettura del file altrimenti il confronto non è valido:


string FileName = "romanzoOld.txt";

Console.WriteLine();

Stopwatch watch = new Stopwatch();
watch.Start();

string text = File.ReadAllText(FileName);

var res = from word in SpaccoAMano(text)
where word.Length > 10
group word by word into gruppo
select new { parola = gruppo.Key, occorrenza = gruppo.Count() };

var first10 = res.OrderByDescending(t => t.occorrenza).Take(10);

var finale = first10.ToList();

watch.Stop();
Console.WriteLine();
finale.ForEach(Console.WriteLine);

Console.WriteLine("Time - {0}", watch.ElapsedMilliseconds);


ottengo, sulla mia macchina:

http://img51.imageshack.us/img51/2238/dfacsharp2.jpg

I tempi adesso si equivalgono ;) La versione C rimane imbattibile con i suoi 31 millisecondi :)

[gugoXX]

Certo, si sa che il C e' piu' veloce.
Passiamo all'assembly allora :D

Se pero' nel conteggio metti anche il tempo necessario per scrivere e soprattutto debuggare il codice...
(E su questo oggi punzecchiano sempre di piu')
Per questo preferisco il codice con RegularExpression. Davvero difficile sbagliare, e una volta scritto lo provi un paio di volte, scrivi un paio di test (meglio prima direi) e hai finito.

PS: sai perche' in C# la ReadAllText e' cosi' lenta?
Perche' e' in Unicode. Ogni carattere in memoria occupa infatti 2byte non 1 solo.
Ma questo significa che passare dalla versione "Italiana" alla versione "Araba", "Russa" o "Israeliana" e' praticamente gratis...

PS: Nel codice del tuo automa C# il tempo di lettura del file non sembra essere incluso...

[Vincenzo1968]

PS: Nel codice del tuo automa C# il tempo di lettura del file non sembra essere incluso...

È incluso. All'interno della funzione DFA leggo il file con questa riga di codice:


buffer = File.ReadAllText(FileName);


Nella funzione Main, copiando e incollando da una versione all'altra, mi sono dimenticato di togliere la riga


string text = File.ReadAllText(FileName);


che non serve a niente.

Per quanto riguarda Unicode, la stessa cosa si può ottenere in C utilizzando le macro del file tchar.h.

[Rigo007]

ma il metodo .ForEach() cos'è? :mbe:
un extension method che hai creato tu o l'hai preso da qualche libreria? :fagiano:

Dopo aver giustamente avuto un errore di compilazione, smattendando un po', visual studio me l'ha definito al volo così.
Qualcuno sa spiegarmi come è possibile?!? :confused:

[gugoXX]

Dopo aver giustamente avuto un errore di compilazione, smattendando un po', visual studio me l'ha definito al volo così.
Qualcuno sa spiegarmi come è possibile?!? :confused:

Ciao.
Il metodo ForEach e' un metodo gia' presente dal C#2.0 applicabile ad una IList. Lo stai infatti applicando ad una List<qualcosa>, essendo che precedentemente hai eseguito la ToList() sul risultato ottenuto.
Il Qualcosa nel C#3.0 puo' essere una classe incognita, dinamicamente generata a tuo uso e consumo, della quale non sai il nome (ne' ti serve saperlo, anche se l'intellisense ti sta dicendo che si chiama 'a), proprio come questo caso.

Il metodo Foreach accetta in input la descrizione di un'azione "tipizzata", che sara' da eseguirsi per ciascun elemento della lista.
Un'azione "tipizzata" e' una qualsiasi funzione che ha come ingresso un parametro unico, esattamente del tipo ospitato dalla lista, e che non restituisce nulla.
Una funzione che in questo caso soddisfa questo requisito e' per esempio Console.WriteLine, che accetta in ingresso un qualsiasi parametro che possa essere stampato, ovvero che possieda il metodo ToString(), come di fatto tutti gli oggetti.

In pratica stai eseguendo Console.WriteLine(elemento); per ciascun elemento della lista.

[Rigo007]

Capito. :)
Grazie della spiegazione.