[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]

Originariamente inviato da 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.

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]

Originariamente inviato da 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).

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]

Originariamente inviato da 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?

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]

Originariamente inviato da 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).

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]

Originariamente inviato da Vincenzo1968

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]

Originariamente inviato da kingal

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 .