Trovare in modo efficiente l'intersezione di un numero variabile di insiemi di stringhe

Question

Ho un numero variabile di ArrayList di cui ho bisogno per trovare l'intersezione di. Un limite realistico al numero di serie di stringhe è probabilmente intorno ai 35 ma potrebbe essere più. Non voglio alcun codice, solo idee su ciò che potrebbe essere efficiente. Ho un'implementazione che sto per iniziare a programmare ma voglio ascoltare altre idee.

Attualmente, solo pensando alla mia soluzione, sembra che dovrei avere un runtime asintotico di Θ (n).

Grazie per qualsiasi aiuto!

tshred

Edit: Per chiarire, io in realtà voglio solo sapere c'è un modo più veloce per farlo. Più veloce di Θ (n).

Answer 1

Set.retainAll() è come si trova l'intersezione di due set. Se si utilizza HashSet, la conversione dei numeri da ArrayList a Set e l'uso di retainAll() in un ciclo su tutti loro è in realtà O (n).

Answer 2

Ordinarli (n lg n) e quindi eseguire ricerche binarie (lg n).

Answer 3

L'opzione migliore sarebbe utilizzare HashSet per archiviare il contenuto di questi elenchi anziché ArrayList. Se puoi farlo, puoi creare un HashSet temporaneo a cui aggiungi gli elementi da intersecare (usa il metodo putAll (..)). Do tempSet.retainAll (storedSet) e tempSet conterrà l'intersezione.

Answer 4

Un'ultima idea: se i tuoi array/set sono di dimensioni diverse, ha senso iniziare con il più piccolo.

Answer 5

È possibile utilizzare un singolo Hashset. Il suo metodo add() restituisce false quando l'oggetto è già presente nel set. l'aggiunta di oggetti dalle liste e il conteggio dei conteggi di valori di ritorno falsi ti daranno l'unione nel set + i dati per l'istogramma (e gli oggetti che hanno un conteggio + 1 uguale al conteggio delle liste sono l'intersezione). Se si lanciano i conteggi a TreeSet, è possibile rilevare l'intersezione vuota in anticipo.

Answer 6

C'è anche il metodo statico Sets.intersection(set1, set2) in Google Guava che restituisce una vista non modificabile dell'intersezione di due insiemi.

Answer 7

La risposta accettata va bene; come aggiornamento: da Java 8 c'è un modo leggermente più efficiente per trovare l'intersezione di due Set s.

Set<String> intersection = set1.stream() 
    .filter(set2::contains) 
    .collect(Collectors.toSet()); 

Il motivo è leggermente più efficiente è perché l'approccio originale aveva per aggiungere elementi di set1 poi dovuto togliere di nuovo se non fossero in set2. Questo approccio aggiunge solo al risultato impostato ciò che deve essere presente.

Strettamente parlando si potrebbe fare questo pre Java 8 pure, ma senza Stream s il codice sarebbe stato un po 'più laborioso.

Se entrambi i set differiscono notevolmente in termini di dimensioni, si preferisce lo streaming su quello più piccolo.