Intersection efficace Set - Décidez si l'intersection est plus grande que k

Une optimisation possible, qui est plus efficace, plus la gamme de valeurs contenues dans chaque ensemble:

• Créez une liste de tous les ensembles, triés par leur élément kth-plus grand (c'est facile à trouver, car vous avez déjà chacun ensemble avec ses éléments dans l'ordre). Appelez cette liste l.
• Pour les deux ensembles A et B, leur intersection ne peut pas avoir autant que k éléments de ks si l'élément kth-plus grand de A est inférieur au moindre élément de b.
• Donc, pour chaque ensemble à son tour, calculez son intersection uniquement avec les ensembles de la partie correspondante de L.

  Vous pouvez utiliser le même fait pour sortir tôt du calcul de l'intersection de deux ensembles - s'il n'y a que des éléments N-1 laissés à comparer dans l'un des ensembles et l'intersection contient jusqu'à présent sur la plupart des éléments KN, puis arrêter. La procédure ci-dessus est simplement cette règle appliquée à tous les ensembles de L à la fois, avec N = K, au point où nous examinons le moins d'élément de l'ensemble B et le plus grand élément de A.

Considérez un mappage avec tous les ensembles de taille K comme clés et valeurs correspondantes des listes de tous les ensembles de votre collection qui contiennent la clé comme un sous-ensemble. Compte tenu de cette mappage, vous n'avez pas besoin d'effectuer des tests d'intersection: Pour chaque touche, toutes les paires d'ensembles de la liste auront une intersection de la taille au moins k. Cette approche peut produire la même paire d'ensembles plus d'une fois, de sorte que cela devra être vérifié.

La cartographie est suffisamment facile pour calculer. Pour chaque ensemble dans la collection, calculez tous les sous-ensembles Taille-K et appendez l'original défini sur la liste pour cet ensemble de touches. Mais est-ce réellement plus rapide? En général, non. La performance de cette approche dépendra de la distribution des tailles des ensembles de la collection et de la valeur de k. Avec D éléments distincts dans les ensembles, vous pourriez avoir autant que D choisissez K Keys, qui peut être très grande.

Cependant, l'idée de base est utilisable pour réduire le nombre d'intersections. Au lieu d'utiliser des ensembles de taille K, utilisez des plus petits de la taille fixe Q en tant que touches. Les valeurs sont à nouveau des listes de tous les ensembles qui ont la clé en tant que sous-ensemble. Maintenant, testez chaque paire d'ensembles de la liste pour l'intersection. Ainsi, avec q = 1, vous ne testez que ces paires d'ensembles qui ont au moins un élément en commun, avec q = 2, vous ne teste que ces paires d'ensembles qui ont au moins deux éléments en commun, etc. La valeur optimale pour Q dépendra de la distribution de tailles des ensembles, je pense.

Pour les ensembles en question, un bon choix peut être Q = 2. Les clés sont alors juste des bords du graphique, donnant une taille prévisible à la cartographie. Étant donné que la plupart des ensembles devraient être disjoints, Q = 2 devrait éliminer de nombreuses comparaisons sans trop de frais généraux supplémentaires.

La stratégie suivante devrait être assez efficace. J'ai utilisé des variantes de ceci pour intersecter des séquences ascendantes à plusieurs reprises.

Je suppose d'abord que vous avez une sorte de queue prioritaire em> disponible (sinon, rouler votre propre tas est assez facile. ). Et une recherche de clé / valeur rapide (BTREE, hachage, peu importe). P>

avec qui dit, voici pseudocode pour un algorithme qui devrait faire ce que vous voulez de manière assez efficace. P>

# Initial setup
sets = array of all sets
intersection_count = key/value lookup with keys = (set_pos, set_pos) and values are counts.
p_queue = priority queue whose elements are (set[0], 0, set_pos), organized by set[0]

# helper function
def process_intersections(current_sets):
    for all pairs of current_sets:
        if pair in intersection_count:
            intersection_count[pair] += 1
        else:
            intersection_count[pair] = 1

# Find all intersections
current_sets = []
last_element = first element of first thing in p_queue
while p_queue is not empty:
    (element, ind, set_pos) = get top element from p_queue
    if element != last_element:
        process_intersections(current_sets)
        last_element = element
        current_sets = []
    current_sets.append(set_pos)
    ind += 1
    if ind < len(sets[set_pos]):
        add (sets[set_pos][ind], ind, set_pos) to p_queue
# Don't forget the last one!
process_intersections(current_sets)

final answer = []
for (pair, count) in intersection_count.iteritems():
    if k-1 < count:
        final_answer.append(pair)

Et si vous utilisiez un sous-ensemble prédictif en tant que préqualificateur. Prétraitement, mais utilisez une intersection sous-ensemble comme condition de seuil. Si l'intersection des sous-ensembles> N% complète ensuite l'intersection, sinon abandonnez. n devient alors l'inverse de votre niveau de confort avec la perspective d'un faux positif.

Vous pouvez également trier par les intersections de sous-ensemble (M) calculées précédemment et commencer à exécuter l'intersection complète commandée par M décroissant. Donc, vraisemblablement, la majorité de vos intersections de M les plus hautes seraient probablement franchiront probablement votre seuil K sur le sous-ensemble complet et que le seuil de frappe de votre K pourrait diminuer continuellement.

Cela commence vraiment à traiter le problème comme NP-complet.