[C] Trovare gli elementi comuni ad una serie di array (in meno di O(n^2)...)

[m0n4c0]

Salve a tutti, è il mio primo post in questa sezione.
Il mio problema è il seguente. Ho una serie di array di interi, non necessariamente ordinati e non necessariamente della stessa lunghezza. Avrei bisogno di ricavare i numeri che compaiono in tutti gli array. Ad esempio, dati 3 array:

A = { 2, 6, 3, 12, 7 }
B = { 11, 5, 3, 2, 8, 34 }
C = { 7, 2, 3 }

devo ottenere la sequenza {3, 2} (non importa in che ordine). Gli array in questione sono allocati dinamicamente.

Sapreste consigliarmi un metodo efficiente? Grazie a tutti in anticipo.

[cionci]

C'è un modo, ma l'applicabilità o meno dipende da quanto è grande il numero maggiore fra quelli presenti nei tre vettori.

I primo passo da fare è trovare il massimo.
A questo punto ti allochi un vettore di interi di dimensione pari al massimo (ecco qui a cosa è dovuto il limite di applicabilità) e ne azzeri il contenuto (o usi la calloc).

Scorrendo ogni vettore vai ad incrementare di 1 l'elemento della posizione corrispondente all'elemento corrente...quando arrivi al terzo vettore se trovi già il contatore a 2 ti metti da parte l'elemento in un altro vettore dei risultati.

Questo è O(n), anche se per dimensioni del vettore troppo grandi diventa inefficiente. Comunque suppongo che si possa fare anche in O(n*log n), anche perché mi sembra equivalente al problema dell'ordinamento.

[m0n4c0]

Intanto grazie per la risposta.

Mi sono dimenticato di aggiungere una cosa. Come ho detto i vettori sono allocati dinamicamente, tuttavia tramite un altra variabile che mi porto dietro posso sapere la dimensione di ciascuno di essi. Non so se questo puo rendere le cose piu semplici...

Spiego anche da dove nasce questo problema. Sto realizzando un semplice indicizzatore di file di testo. In risposta ad una certa query, ad esempio "pippo paperino", ottengo un array di interi per ogni parola che contiene gli indici dei file in cui la parola si trova.
Ad esempio:

pippo: 2, 4, 6 (la parola "pippo" si trova nei file 2, 4, 6)
paperino: 7, 2, 5, 9 (la parola "pippo si trova nei file 7, 2, 5, 9)

In riposta alla query devo ottenere il file che contiene entrambe le parole, in questo caso il file 2 soltanto.

In linea di massima la dimensione massima di questi array di interi, che corrsiponde al numero totale dei file indicizzati, è dell'ordine di qualche migliaio.
Di conseguenza ognuno di questi interi è < numero file indicizzati.

Visto che i numeri da esaminare non sono poi così tanti, preferire non dover allocare altra memoria per l'operazione di ricerca, anche a costo di una complessità n(log n) piuttosto che n.

[k0nt3]

mmm non sono sicuro che sia l'argoritmo più efficiente, comunque i tuoi array sono:
A = { 2, 6, 3, 12, 7 }
B = { 11, 5, 3, 2, 8, 34 }
C = { 7, 2, 3 }

se sai quanto sono lunghi gli array in partenza ti conviene ordinarli dal meno lungo al più lungo.. quindi nell'esempio sarebbe:
A = { 7, 2, 3 }
B = { 2, 6, 3, 12, 7 }
C = { 11, 5, 3, 2, 8, 34 }

provi a confrontare A[0] con gli elementi dell'array B, finchè non trovi un valore uguale a A[0]. in questo caso ti fermerai a B[4]. ora fai la stessa cosa tra B[4] e l'array C, e in questo caso non troverai l'elemento e passerai a esaminare A[1] e così via.. quando trovi l'elemento nell'array C sai che hai trovato una terna di valori uguali.
una piccola ottimizzazione potrebbe essere quella di eliminare gli elementi che fanno già parte di una terna dagli array, ma nel caso in cui le terne sono rare non conviene un granchè

certo se non ti costa molto ordinare l'array in fase di costruzione magari si può pensare a qualcosa di ancora meglio

[fabianoda]

Beh...

(1) Con un costo O(n log n) [in-place mergesort, senza altre strutture dati] ti ordini i tuoi vettori, ognuno per ogni parola.

(2) Poi inizi a scorrere i tuoi m vettori dall'inizio alla fine, usando m cursori e confrontando i valori. Ad ogni step aumenti il cursore del vettore il cui elemento è il minore degli m.

(3) Quando tutti gli m cursori sono su valori uguali, allora inserisci in un nuovo array il risultato.

Esempio
ORIGINALE:
pippo: 3 5 1 4
paperino: 4 1
pluto: 4 3 5

DOPO L'ORDINAMENTO:
pippo: 1 3 4 5
paperino: 1 3
pluto: 3 4 5

PASSO 1:
pippo: 1 3 4 5
paperino: 1 3
pluto: 3 4 5
uguali: -
PASSO 2:
pippo: 1 3 4 5
paperino: 1 3
pluto: 3 4 5
uguali: -

PASSO 3:
pippo: 1 3 4 5
paperino: 1 3
pluto: 3 4 5
uguali: 3
Qui addirittura puoi alzare tutti e tre i cursori, dato che l'uguaglianza già c'è

Spero di essermi spiegato, e di avere capito il problema.
Costo dell'approccio: O(n log n) + O(n) = O(n log n)

[m0n4c0]

Grazie a tutti per la vostra disponibilità. E' la prima volta che chiedo aiuto nella sezione di programmazione, e sono rimasto impressionato dalla rapidità e dalla completezza delle vostre risposte.

Adesso provo le soluzioni che mi avete proposto, grazie di nuovo.

[cionci]

Originariamente inviato da m0n4c0

In linea di massima la dimensione massima di questi array di interi, che corrsiponde al numero totale dei file indicizzati, è dell'ordine di qualche migliaio.
Di conseguenza ognuno di questi interi è < numero file indicizzati.

Visto che i numeri da esaminare non sono poi così tanti, preferire non dover allocare altra memoria per l'operazione di ricerca, anche a costo di una complessità n(log n) piuttosto che n.

Mi sembra che tu sia nella condizione migliore per adottare la soluzione che ti ho proposto in quanto mi immagino che tu conosca a priori il numero di file.
Non credo che allocare 1 byte di RAM per ogni file possa essere una soluzione inaccettabile. Fossero stati qualche milione i byte da allocare allora un pensierino ce l'avrei fatto, ma si tratta di pochi KB
Ram che poi tra l'atro ti si libererebbe appena hai finito di fare il conteggio...

[m0n4c0]

Dici che si tratta di allocare 1 byte.. ma allora forse non ho capito il tuo metodo.. scusa ma sono un po' "duro"...
Quando dici trovare il massimo intendi il massimo fra tutti gli array o il massimo di ogni array?
Poi se non ho capito male devo allocare un array di dimensione pari al massimo... ma questo non mi occupa n*sizeof(int) bytes? Poi scusa se io ad esempio ho questi 4 array:

(2, 4, 189)
(2, 1)
(4, 8, 2, 1)
(1, 2)

dovrei allocare un array di 189 elementi? Mi sa che non c'ho capito una mazza eh... Ma forse intendi il massimo nel senso della dimensione dell'array... non il massimo elemento... cioè in questo caso un array di 4 elementi?

Grazie ancora per l'aiuto...

Un altra cosa che forse non ho spiegato bene... gli array non è che sono per forza esattamente tre... può darsi che una volta ne venga fuori uno solo come un'altra volta ne vengano fuori 50, dipende dalla query. Certo non saranno 2.000... anche perchè la query viene passata da linea di comando.

[cionci]

Sì, il numero di elementi da allocare è 189.

Mi hai detto che quei numeri variano fra 0 (oppure 1 ?) ed il numero di file indicizzati, giusto ? Quindi non importa trovare il massimo, visto che il massimo numero possibile che ti può ritornare lo conosci già.
Puoi anche allocare dei char, quindi 1 byte, visto che ti servono solo per contare da 0 a 2

Ti faccio l'esempio del caso che hai postato prima...

char *v = (char *) calloc(number_of_indexed_files, sizeof(char)); /* quindi 1 byte per ogni file indicizzato*/

v[v1[0]]++;
v[v1[1]]++;
v[v1[2]]++;

v[v2[0]]++;
v[v2[1]]++;

v[v3[0]]++;
v[v3[1]]++;
v[v3[2]]++;
v[v3[3]]++;

Per l'ultimo vettore:
se v[v4[0]] == 3 allora metto da parte v4[0]
se v[v4[1]] == 3 allora metto da parte v4[1]

free(v);

Quindi il numero di byte da allocare è uguale al numero di file indicizzati, se sono qualche migliaio allochi qualche KByte...mi sembra una quantità decente.
Se i file fossero diversi milioni mi verrebbe da pensare che la complessità di spazio è troppo superiore a quella computazionale, allora non varrebbe la pena utilizzare questo metodo
Ma qualche KB, se non hai vincoli di memoria, mi sembra un compromesso più che accettabile

[Furla]

per allocare meno spazio puoi usare, con il metodo di cionci, il minimo tra i massimi di ogni vettore. in questo modo si riduce la dimensione dell'array di contatori, ma bisogna inserire un controllo per evitare che si tenti di incrementare il contatore di un file di indice maggiore del "minimo dei massimi".
la complessità resta O(n).

(2, 4, 189)
(2, 1)
(4, 8, 2, 1)
(1, 2)

in questo caso il massimo è 2, quindi ti basta un array di due elementi.

comunque se il massimo è noto senza doverlo cercare ed è un numero ragionevole, forse non conviene introdurre la ricerca (che comunque potrebbe non essere efficace, se tutti gli array hanno un massimo alto, ad esempio quando uno dei file contenente tutte le parole ha un indice alto), perché il tempo di esecuzione dell'algoritmo è breve e il tempo di vita dell'array di contatori lo è altrettanto

[cionci]

Originariamente inviato da Furla

per allocare meno spazio puoi usare, con il metodo di cionci, il minimo tra i massimi di ogni vettore. in questo modo si riduce la dimensione dell'array di contatori, ma bisogna inserire un controllo per evitare che si tenti di incrementare il contatore di un file di indice maggiore del "minimo dei massimi".

Vero
Ed in teoria si potrebbe anche trovare il "massimo dei minimi" e sottrarlo come offset per indicizzare il vettore dei contatori

[m0n4c0]

Grazie ancora...

Certo che casino.... io all'inizio invece di una lista di interi per ogni parola avevo fatto in questo modo: ad ogni parola anchè una lista di interi associavo una maschera di bit (un array di char) dove il bit corrispondente ad ogni indice di file veniva messo a uno... Alla fine era molto piu semplice perchè a quel punto bastava mettere in AND le maschere di bit delle varie parole, e la maschera risultante mi dava gli indici di file dove si trovano tutte le parole... il professore però mi ha detto che in questo modo c'era un eccessivo spreco di bit a 0...
Citando dalla sua mail:

La soluzione e' fattibile, e il trucco standard consiste nell'usare un array
di char. Il bit x sara' l'x%8 bit dell'x/8 elemento nell'array. Ovviamente,
stiamo parlando di una codifica di K parole per N file, e la
rappresentazione esplicita a bit NON conviene se la matrice e' sparsa
(cioe', se la grande maggioranza dei bit e' 0). In effetti, si guadagna un
fattore (costante) 8 rispetto a una matrice di "booleani", che puo' non
controbilanciare lo spreco dei bit a 0.
Si puo' assumere che il numero dei file sia dell'ordine 100-1000, e che ogni
file contenga forse 15000 parole distinte (il 10% dell'intero dizionario),
seguendo l'idea che un documento, per quanto lungo, difficilmente parlera'
di tutto: se e' un trattato di storia, non compariranno i nomi di tutte le
specie di marsupiali, e cosi' via.

... secondo me è un po' esagerato... però se me lo dice lui che devo fare

[cionci]

Originariamente inviato da m0n4c0

... secondo me è un po' esagerato... però se me lo dice lui che devo fare

Eh sì...è sicuramente esagerato
A quel punto ne usi un algoritmo di ordinamento con complessità O(n * log n) e scorri il risultato contando quanto ci sono N (con N pari al numero di parole) numeri uguali.

Comunque magari proponi al professore questo algoritmo, magari potrebbe raggiungere un trade off fra prestazioni e memoria occupata che gli può andare a genio. Ovviamente digli anche la soluzione O(n * log n).