[Algoritmi] Trovare l'elemento non comune a due liste

[Patras]

Ciao a tutti! Ho la consegna di un esercizio ma non la soluzione quindi vi chiedo cortesemente di suggerirmi qualcosa se avete idee.
Consegna:
Date due liste A e B (non ordinate), ciascuna delle quali contiene elementi interi distinti,
si vuole determinare se esiste un elemento che compare in A ma non in B. Fornire un
algoritmo efficiente, scriverne lo pseudocodice e discuterne la complessità (ne esiste uno che
richiede tempo nel caso medio, dove n è il numero di elementi della lista più lunga).

Due soluzioni che mi vengono in mente (ma che non sembrano O(n) nel caso medio)
- Scandire una lista nel frattempo controllando la presenza dell'elemento nell'altra
- Creare un array dimensione (quella dell'array più grande) e fare un MergeSort e scandirlo per verificare la presenza di duplicati prendendo ogni volta un elemento dall'altro facendo una ricerca binaria. Ma anche in questo caso abbiamo.. con dimensione dell'altro array, che se è molto piccola è circa

Con una funzione hash si può fare O(M) dove M è il massimo dei due array. Ma non mi sembra nel caso medio

Qualcuno ha qualche idea?

[IlGuru]

Verrebbe più semplice ordinando prima le due liste

[Patras]

Grazie per la risposta. Credo che l'ordinamento in se fatto per confronti , che sia prima o dopo aver fuso le liste, comunque non possa dar origine a prestazioni mediamente

[GuidoB]

Date due liste A e B (non ordinate), ciascuna delle quali contiene elementi interi distinti,
si vuole determinare se esiste un elemento che compare in A ma non in B. Fornire un
algoritmo efficiente, scriverne lo pseudocodice e discuterne la complessità (ne esiste uno che
richiede tempo nel caso medio, dove n è il numero di elementi della lista più lunga).

Potresti inserire gli elementi della lista B in una tabella hash ( se si generano poche collisioni) e poi controllare, per ogni elemento della lista A, se è già presente o no nella tabella (ancora se si generano poche collisioni).

Per generare poche collisioni, la tabella non deve essere troppo piena (non più del 75%, normalmente), e la funzione di hash deve essere "buona". Come farla "buona" è un po' complicato da spiegare qui...

[Patras]

Posso ottimizzare la funzione hash traslando il range dopo aver trovato il minimo. Nel caso peggiore avrò comunque dove è il massimo e è il minimo. Cosa posso fare di meglio? Non conosco il "passo" tra due valori consecutivi per dividere. Posso trovare il massimo però. E così come dico io non credo che mediamente venga , (N-M) può essere molto più grande di n. Però di sicuro è

[GuidoB]

Posso ottimizzare la funzione hash traslando il range dopo aver trovato il minimo.

Non è necessario trovare il minimo (e il massimo). Si può fare in modo più efficiente.

Nel caso peggiore avrò comunque dove è il massimo e è il minimo.

Nooo... La complessità di inserimento o ricerca di un elemento in una tabella hash non dipende dalle sue dimensioni ma dal grado di riempimento. Se non è troppo piena, è , cioè costante e indipendente dal numero di elementi già presenti.
Se devi inserire o ricercare elementi, la complessità sarà .

Se ne parla un po' qui e in questo PDF.

Suggerimento di un possibile algoritmo:

1) trova quanti elementi contiene la lista B (complessità: ). Chiamiamo questo numero nElementiB.
2) dimensioneTabellaHash = nElementiB * 1.5 // Il riempimento in questo esempio sarà 1/1.5 = 67%.
3) allochi memoria per la tabella hash, con le dimensioni appena calcolate, e la inizializzi con elementi "vuoti".
4) Inserisci nella tabella, uno per uno, gli elementi della lista B (complessità: ). In caso di collisione, la risolvi in uno dei soliti modi: salti avanti o indietro di un certo numero di posizioni (magari variabile), oppure modifichi la funzione di hash a ogni collisione, oppure memorizzi gli elementi in liste concatenate...
5) Cerchi nella tabella, uno per uno, gli elementi della lista A (complessità: ), e vedi se ce n'è qualcuno non presente.

La complessità totale è .

La funzione di hash può essere semplicemente (per quest'uso la ritengo sufficientemente "buona"):

hash = valElemento % dimensioneTabellaHash (dove valElemento è il valore dell'intero da inserire, e % è il simbolo del modulo, ovvero il resto della divisione intera).


Se usi la standard library del C++, puoi dichiarare una unordered_map e hai già pronta tutta la classe che gestisce la tua tabella hash.

Ma mi sembra che a te basti lo pseudocodice...

[Patras]

Grazie mille! Si sapevo che l'inserimento avvenisse in tempo costante però al passaggio finale che come lo considerato io avrei avuto anche celle vuote. Per quello mi toccava verificare più di n valori in generale.

hash = valElemento % dimensioneTabellaHash (dove valElemento è il valore dell'intero da inserire, e % è il simbolo del modulo, ovvero il resto della divisione intera).

Così invece l'array può essere un po' più riempito ma sempre dagli elementi e seguendo i passaggi indicati è perfetto.