Qu'est-ce qu'une structure de données pour trouver rapidement des intersections non vides d'une liste d'ensembles?

Question

J'ai un ensemble de N éléments, qui sont des ensembles d'entiers, supposons qu'il est commandé et appelez-le I[1..N]. Étant donné un ensemble candidate, j'ai besoin de trouver le sous-ensemble de I qui ont des intersections non vides avec le candidate.

Ainsi, par exemple, si:

I = [{1,2}, {2,3}, {4,5}] 

Je cherche à définir valid_items(items, candidate), tel que:

valid_items(I, {1}) == {1} 
valid_items(I, {2}) == {1, 2} 
valid_items(I, {3,4}) == {2, 3} 

Je suis en train d'optimiser pour un ensemble donné I et une variable candidate ensembles. Actuellement, je le fais en mettant en cache items_containing[n] = {the sets which contain n}. Dans l'exemple ci-dessus, ce serait:

items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}] 

C'est, 0 est contenu dans aucun élément, 1 est contenue dans l'article 1, 2 est contenu dans itmes 1 et 2, 2 est contenue dans l'article 2, 3 est contenu dans l'article 2, et 4 et 5 sont contenues dans l'article 3.

De cette façon, je peux définir valid_items(I, candidate) = union(items_containing[n] for n in candidate).

Existe-t-il une structure de données plus efficace (d'une taille raisonnable) pour mettre en cache le résultat de cette union? L'exemple évident de l'espace 2^N n'est pas acceptable, mais N ou N*log(N) serait.

Answer 1

Je pense que votre solution actuelle est optimisée, même si des techniques de micro-optimisation peuvent améliorer ses performances actuelles. Telles que l'utilisation des opérations au niveau du bit lors de la fusion de l'ensemble choisi dans item_containing avec l'ensemble d'éléments valide.

-à-dire que vous items_containing stocker comme ceci:

items_containing = [0x0000, 0x0001, 0x0011, 0x0010, 0x0100, 0x0100] 

et vos valid_items pouvez utiliser le bit-sage ou de fusionner comme ceci:

int valid_items(Set I, Set candidate) { 
    // if you need more than 32-items, use int[] for valid 
    // and int[][] for items_containing 
    int valid = 0x0000; 
    for (int item : candidate) { 
     // bit-wise OR 
     valid |= items_containing[item]; 
    } 
    return valid; 
} 

mais ils ne changent pas vraiment le Big-O performance.

Answer 2

Une représentation qui pourrait aider est de stocker les ensembles I comme vecteurs V de taille n dont les entrées V (i) sont 0 quand i n'est pas dans V et positif sinon. Ensuite, pour prendre l'intersection de deux vecteurs, vous multipliez les termes, et pour prendre l'union, vous ajoutez les termes.