Un algoritmo di ricerca efficiente

[natasha]

Buongiorno a tutti,
trovandomi di fronte al problema di dover trovare tutti i nominativi di un elenco A che non fossero presenti in un elenco B, ho implementato con una query in Access il più stupido degli algoritmi: confrontare ogni elemento di A con tutti gli elementi di B... Il mio professore di Fondamenti di Informatica ne sarebbe più che soddisfatto: complessità esponenziale, roba da crocefissione in sala mensa.
Qualcuno conosce un algoritmo più efficiente?
Kisses,

Nat

[xegallo]

se gli elementi sono ordinati ti conviene usare una ricerca dicotomica

[natasha]

non sono ordinati... comunque cos'è?

[xegallo]

Originariamente inviato da natasha
non sono ordinati... comunque cos'è?

se non sono ordinati non la puoi usare

[cik]

se non sono ordinati puoi ordinarli con un algoritmo quicksort (o uno dei suoi derivati) e usare la ricerca dicotomica.

La ricerca dicotomica è quella che confronta l'elemento da trovare con l'elemento centrale di un insieme ordinato. Se è maggiore ripete l'operazione nella seconda metà dell'array, se è minore la ripete nella prima.

Il quicksort è uno degli algoritmi di ordinamento più veloci.

[MaverickNumber1]

Bella comunque quella della crocifissione in sala mensa

[caralu]

Se devi ricercare un pattern in un'altra stringa (ho capito bene?)potresti utilizzare anche l'algoritmo di knuth, Morris e Pratt che ha complessità lineare. Ti scrivo il codice in C, dagli un'occhiatina:

/*Il ciclo while viene ripetuto finchè non viene raggiunta la fine di una delle due stringhe (stringa e pat). Poichè la variabile i non viene mai diminuita, le righe che aumentano (i) non possono essere eseguite più di m=strlen(stringa) volte. Il ripristino di j a insuccesso[j-1]+1 riduce il valore di j. Pertanto questa operazione non può essere fatta più volte di quanto j non sia incrementato dall'istruzione j++, altrimenti j andrebbe fuori dal limite di pat. Ogni volta che l'istruzione j++ viene eseguita, j viene incrementato. Pertanto j non può essere incrementato più di m volte. */

int pmatch(char *stringa, char *pat)
{
int i=0, j=0;

int lens = strlen(stringa);
int lenp = strlen(pat);

insucc(pat); //Inizializza l'array "insuccesso" per ottimizzare l'algoritmo

while(i<lens && j<lenp)
{
if(stringa[i] == pat[j])
{i++; j++;}
else
if(j==0)
i++;
else
j = insuccesso[j-1]+1;
}
return( (j==lenp) ? (i-lenp) : -1); /*questa istruzione verifica se pat è stata trovata oppure no. Se pat non è ststa trovata, l'indice j non è uguale alla lunghezza di pat e l'istruzione fornisce il valore -1. Se la stringa pat viene trovata, allora la posizione di partenza è pari a i meno la lunghezza di pat.*/
}

//-------------------------------------------------------------------

FUNZIONE insucc(): //Calcola la funzione di insuccesso per un pattern di caratteri da ricercare (pat)

/*Ad ogni iterazione del ciclo while il valore di i diminuisce secondo la definizione di f (descritta sotto). La variabile i viene ripristinata all'inizio di ogni iterazione del ciclo for. Questa variabile può essere impostata a -1 (inizialmente o quando la precedente iterazione del ciclo for passa attrverso la clausola else) oppure ad un valore maggiore di 1 rispetto al suo valore finale nella precedente iterazione (cioè quando viene eseguita l'istruzione "insuccesso[j] = i+1"). */

void insucc(char *pat)
{
int i, j;

int n = strlen(pat);

insuccesso[0] = -1;

for(j=1; j<n; j++)
{
i = insuccesso[j-1];
while((pat[j] != pat[i+1]) && (i>=0))
i = insuccesso[i];

if(pat[j] == pat[i+1])
insuccesso[j] = i+1;
else
insuccesso[j] = -1;
}
}

Spero ti sia utile... bye bye