Calcul de la différence entre deux grands ensembles

14

J'ai deux grands ensembles d'entiers et B . Chaque ensemble contient environ un million d'entrées et chaque entrée est un entier positif de 10 chiffres au maximum. AB

Quel est le meilleur algorithme pour calculer et B A ? En d'autres termes, comment puis-je calculer efficacement la liste des entrées de A qui ne sont pas dans B et vice versa? Quelle serait la meilleure structure de données pour représenter ces deux ensembles, pour rendre ces opérations efficaces?ABBAAB

La meilleure approche que je puisse trouver consiste à stocker ces deux ensembles sous forme de listes triées et à comparer chaque élément de avec chaque élément de B , de manière linéaire. Pouvons-nous faire mieux?AB

user917279
la source
Si vous souhaitez le stocker différemment, vous pourrez peut-être obtenir de meilleurs résultats.
Realz Slaw
En outre, si vous souhaitez obtenir les résultats sous forme de structure de données implicite; vous pouvez simplement créer une telle structure qui interroge les deux ensembles pour répondre à chacune de ses propres requêtes.
Realz Slaw
1
@ user917279 Un point important est que vous pouvez généralement comparer le temps de prétraitement / construction, le temps de requête et l'utilisation de la mémoire. Modifiez-vous rarement la structure, mais interrogez-vous beaucoup? L'inverse? La mémoire est-elle une préoccupation ou non? De telles questions peuvent être répondues d'un point de vue pratique et éclairer le choix de la construction «correcte» «théorique».
Raphael
1
@Raphael Suggérez-vous que l'on pourrait faire mieux que les ensembles persistants convergents (en termes de complexité) en utilisant plus de mémoire et / ou en consacrant plus de temps à la préparation. Je suis juste curieux de savoir si c'est possible. Je ne vois pas les tables de recherche comme une option pour les ensembles d'entrée de cette taille.
smossen
1
@ user917279 Si vous considérez l'exemple de deux énormes ensembles identiques, alors toute structure de données créée à l'aide de la fonction de hachage prendrait en charge les tests d'égalité dans O (1) car des structures égales seront fusionnées lors de leur création et partageront ainsi le même emplacement mémoire. Les ensembles persistants confluents profitent également du hachage lorsque deux structures sont presque égales. La complexité est la meilleure que j'ai vue jusqu'à présent pour les ensembles ordonnés.
smossen

Réponses:

9

Si vous êtes prêt à stocker les ensembles dans une structure de données spécialisée, vous pouvez éventuellement obtenir des complexités intéressantes.

Soit I=O(min(|A|,|B|,|AΔB|))

Ensuite, vous pouvez définir les opérations et A Δ B , chacune dans O ( I log | A | + | B |AB,AB,ABAΔBtemps prévu. Donc, essentiellement, vous obtenez la taille minimale des deux ensembles, ou la taille de la différence symétrique, la plus petite des deux. C'est mieux que linéaire, si la différence symétrique est petite; c'est à dire. s'ils ont une grande intersection. En fait, pour les deux opérations de différence d'ensemble que vous souhaitez, cela est pratiquement sensible à la sortie, car ensemble, elles constituent la taille de la différence symétrique.O(Ilog|A|+|B|I)

Voir Confluently Persistent Sets and Maps par Olle Liljenzin (2013) pour plus d'informations.

Realz Slaw
la source
Les tracés du papier sont des arbres de recherche ordonnés. Je ne les compterais pas comme des structures de données non triées.
smossen
@smossen c'est vrai, j'ai édité ça.
Realz Slaw
6

Un balayage linéaire est le meilleur que je sais faire, si les ensembles sont représentés sous forme de listes chaînées triées. Le temps d'exécution est .O(|A|+|B|)

Notez que vous n'avez pas besoin de comparer chaque élément de à chaque élément de B , par paire. Cela conduirait à un temps d'exécution de O ( | A | × | B | ) , ce qui est bien pire. Au lieu de cela, pour calculer la différence symétrique de ces deux ensembles, vous pouvez utiliser une technique similaire à l'opération de "fusion" dans mergesort, modifiée de manière appropriée pour omettre les valeurs communes aux deux ensembles.ABO(|A|×|B|)

Plus en détail, vous pouvez créer un algorithme récursif comme le suivant pour calculer , en supposant que A et B sont représentés sous forme de listes liées avec leurs valeurs dans l'ordre trié:ABAB

difference(A, B):
    if len(B)=0:
        return A # return the leftover list
    if len(A)=0:
        return B # return the leftover list
    if A[0] < B[0]:
        return [A[0]] + difference(A[1:], B)
    elsif A[0] = B[0]:
        return difference(A[1:], B[1:])  # omit the common element
    else:
        return [B[0]] + difference(A, B[1:])

J'ai représenté cela en pseudo-Python. Si vous ne lisez pas Python, A[0]est la tête de la liste liée A, A[1:]est le reste de la liste et +représente la concaténation des listes. Pour des raisons d'efficacité, si vous travaillez en Python, vous ne voudrez probablement pas l'implémenter exactement comme ci-dessus - par exemple, il serait préférable d'utiliser des générateurs, pour éviter de créer de nombreuses listes temporaires - mais je voulais vous montrer les idées sous la forme la plus simple possible. Le but de ce pseudo-code est juste d'illustrer l'algorithme, pas de proposer une implémentation concrète.

Je ne pense pas qu'il soit possible de faire mieux, si vos ensembles sont représentés sous forme de listes triées et que vous souhaitez que la sortie soit fournie sous forme de liste triée. Vous avez fondamentalement regarder tous les éléments de et B . Croquis informel de justification: s'il y a un élément que vous n'avez pas regardé, vous ne pouvez pas le produire, donc le seul cas où vous pouvez omettre de regarder un élément est si vous savez qu'il est présent à la fois dans A et B , mais comment pourriez-vous savoir qu'il est présent si vous n'avez pas regardé sa valeur?ABAB

DW
la source
fantastique, avons-nous d'autres options si la contrainte que les ensembles doivent être stockés sous forme de listes triées est supprimée?
user917279
2

Si A et B sont de taille égale, disjoints et entrelacés (par exemple, les nombres impairs dans A et les nombres pairs dans B), alors la comparaison par paire d'éléments en temps linéaire est probablement optimale.

Si A et B contiennent des blocs d'éléments qui se trouvent exactement dans l'un ou l'autre de A ou B, ou dans les deux, il est possible de calculer la différence, l'union et l'intersection définies en temps sous-linéaire. Par exemple, si A et B diffèrent dans exactement un élément, alors la différence peut être calculée dans O (log n).

http://arxiv.org/abs/1301.3388

étouffer
la source
1
Il dit que les ensembles sont ordonnés, ce qui pourrait signifier qu'ils sont stockés sous forme de listes, d'arbres de recherche ou d'autre chose. Si les données doivent être stockées sous forme de listes, il est assez peu intéressant de demander "le meilleur algorithme pour calculer AB" alors qu'aucun algorithme ne pourrait faire mieux que de parcourir les listes en temps linéaire (pour lequel il a déjà trouvé un algorithme).
smossen
1
mon dieu, vous avez lié le même papier que moi (moi, comme vous, plutôt) ... nommez vos liens la prochaine fois: D
Realz Slaw
@smossen fantastique, à ma connaissance (?), je les ai représentées sous forme de listes triées, mais j'aimerais aussi humblement accueillir d'autres suggestions.
user917279
2

une option consiste à utiliser des vecteurs de bits pour représenter les ensembles (où lenCette position représente la présence ou l'absence d'un élément) et les opérations de type ensemble se réduisent ensuite à des opérations binaires qui peuvent être effectuées rapidement (et sur plusieurs bits en parallèle) sur des ordinateurs numériques. dans ce casUNE-B = uneb¯une,bsont les vecteurs de bits. l'efficacité relative de cette technique par rapport à d'autres techniques dépend également de la rareté. pour les ensembles plus denses, il peut être plus efficace que d'autres approches. bien sûr, toute l'opération est également embarrassante en parallèle, de sorte que les opérations définies peuvent être effectuées en parallèle.

vzn
la source
Avec dixdixentrées possibles, les vecteurs bits ne sont pas du tout pratiques.
Raphael
1
R., manque le point. un seul longpeut stocker 32 éléments ou 1 byte, 8 éléments. donc 1M d'entrées peuvent être stockées dans seulement ~ 125 Ko de RAM! le stockage peut être significativement plus efficace que les autres représentations selon la façon dont le problème est implémenté ...
vzn
Vous auriez donc besoin de plus de 12 Mo pour les ensembles qui intéressent l'OP. Cela fait exploser tous les caches (actuellement) et sera horrible pour les ensembles clairsemés. En particulier, la création d'un ensemble vide domine toutes les autres opérations (pour les ensembles clairsemés). Soit dit en passant, Knuth résout ce problème dans TAoCP.
Raphael
12 Mo? hein? l'affiche dit qu'il n'a que 2 sets. l'affiche n'a pas précisé la densité / densité de son ensemble. cela est souligné dans ma réponse. supposez-vous qu'il a des ensembles clairsemés? il n'y a pas de réponse unique, l'approche est présentée comme une option alternative qui peut être utile selon les circonstances. il n'est pas inhabituellement utilisé dans ce contexte ...
vzn
Je vous suggère de relire la question: "Chaque ensemble contient environ un million d'entrées, et chaque entrée est un entier positif de 10 chiffres au maximum." Il y adixdix différents nombres qui peuvent se produire, et il y a environ dix6ceux de la liste. Cela signifie que seulement 0,01% de toutes les entrées de votre vecteur de bits sont égales à 1 - j'appellerais cela très clairsemé. (Il s'avère que mes 12 Mo étaient trop faibles; vous devez bien sûrdixdixb1,15gB.)
Raphael