Je recherche une structure de données abstraite qui représente une collection d'ensembles tels qu'aucun défini dans la collection est un sous-ensemble d'un autre ensemble dans la collection.
Cela signifie que sur l'insertion des conditions suivantes sera remplie:
a. Insertion d'un élément qui est déjà un sous-ensemble d'un autre élément retournera la collection d'origine.
b. Insertion d'un élément qui est un superset de tout autre élément entraînera une collection avec la superset ajoutée et les sous-ensembles supprimés.
En supposant une commande sur les éléments de l'ensemble, puis un arbre de préfixe peut être utilisé pour représenter la collection. Cela permet de conserver la condition d'être traitée très rapidement (c'est-à-dire qu'il ne faut plus de vérifier la condition que de insérer le sous-ensemble) mais que la condition de réunion B prend du temps.
Je me demande s'il y a une structure de données qui permet à B de se rencontrer rapidement.
4 Réponses :
une idée triviale, qui fonctionnera dans O (k) où k est la taille de l'élément ajouté.
A et B sont O (k).
Notez qu'un objet peut être membre de plusieurs ensembles, comme dans {{A, B}, {B, C}, {A, C}}.
L'approche triviale consisterait à conserver une liste de jeux et à effectuer une recherche linéaire à travers celle de chaque ensemble entrant (test si l'entrant est un sous-ensemble).
Ceci fonctionne évidemment dans O (n) temps pour la recherche linéaire et éventuellement O (m) la taille de la taille de l'ensemble entrant. Ainsi, o (n * m) temps total (nombre d'ensembles contre taille de chaque ensemble).
L'optimisation la plus évidente, bien sûr, est d'indexer sur les tailles de jeu. Ensuite, vous ne testez que chaque ensemble entrant contre ceux qui ont une taille égale ou supérieure. (Un ensemble ne peut pas être un sous-ensemble d'un ensemble plus petit, duh!).
L'optimisation suivante qui me vient à l'esprit est de créer dans l'index des éléments. Ainsi, pour chaque ensemble entrant, vous trouverez l'intersection de chaque ensemble contenant chacun des éléments. En d'autres termes si, pour un ensemble entrant {A, B, C}, nous trouvons cet élément {A} dans les ensembles A, B et D, élément {b} existe dans B, E et F, et {C} Existe dans A, B et Z ... alors le jeu entrant est un sous-ensemble de B (l'intersection de {A, B, D}, {B, E, F} et {A, B, Z}).
Donc, cela ressemble à une complexité de O (m * log (n)) pour moi. (Nous devons effectuer des recherches hachées sur chaque élément de chaque ensemble entrant). Les insertions doivent également être sur le même ordre (insérer le nouvel identifiant de l'ensemble dans chacun des cartes de l'élément). (Dans l'analyse Big-o 2 * O (m log (n)) diminue vers O (m journal (n)), bien sûr).
Si les membres individuels de vos ensembles A, B, sont mappés sur des nombres distincts (et relativement) premiers, et à côté de chaque ensemble, vous stockez le produit de tous les membres comme p (A), P (B) etc. puis les sous-ensembles et les supersets peuvent être trouvés selon que p (x) est un facteur de p (y) ou inversement.
Vous pouvez vous retrouver avec de très grands nombres, je suppose, mais cela fonctionne en théorie.
Par exemple:
Si [A B C D] -> [2 3 5 7], P (ABC) = 30, P (ABD) = 42, P (BC) = 15, P (ABCD) = 210
Le problème des numéros d'affacturage n'est-il pas terminé?
Pas si vous utilisez une bibliothèque de grand nombre avec une fonction de division!
J'aurais dû ajouter que dans ce cas, le problème est juste une division, pas l'affacturage.
@Stephen C: Trouver les facteurs d'un nombre arbitraire est NP complet. Le problème est que le plus petit des deux chiffres divise exactement la plus grande, une simple opération de module. Par exemple, p (BC) = 15 est un diviseur de P (ABCD) = 210, alors la BC est un sous-ensemble d'ABCD. L'ajout d'un nouvel ensemble S à l'ensemble existant de N ensembles nécessite jusqu'à n opérations de module; moins si S est un duplicata. Pour chaque entrée existante E dans l'ensemble des ensembles, si S est inférieur à E, vérifiez si S divise e et ignore si elle le fait. Si S est plus grand que E, vérifiez si E divise S et supprimer E si elle le fait (et ajoutez S). Un tableau de Bignums fonctionnerait.
À moins que vos ensembles soient assez clairsemés, ne serait-il pas plus efficace de simplement utiliser un Bitfield pour les représenter? Au lieu de mapper chaque élément à une prime, carapez-la à une position de bit, puis définissez ce bit dans le champ Bitfield si l'élément existe. A est un sous-ensemble de B Si A & B == A. Vous pouvez arrêter la comparaison à tout moment A n'est ni une superset ni un sous-ensemble de B.
C'est mieux encore - il est difficile de voir comment quelque chose pourrait être plus efficace que cela. Je pense que vous devez vérifier un nouvel ensemble contre tous les ensembles existants, ce qui ne l'ajoute qu'à la fin.
Quel site Dorky! Je suis maintenant inscrit, alors peut-être en temps utile pour pouvoir commenter des choses d'hier. Jusque-là, cependant, ...
@stephen C: Bien que je pense que mon anglais soit adéquat, je semble avoir acquis un explicatrice: il a raté les morceaux manqués, cependant, et son commentaire devrait être lu comme suit:
@StEphen C: Trouver les facteurs d'un Le nombre arbitraire est en effet complet NP, mais pas pertinent ici. le question est de savoir si le plus petit de deux chiffres divise exactement le plus grand, a Opération de modulus simple. Par example, p (BC) = 15 est un diviseur de P (ABCD) = 210, alors BC est un sous-ensemble d'ABCD (comme les ensembles ABD et abc).
Ajout d'un nouvel ensemble S à la collection existante de N ensembles est O (n), en supposant que la comparaison et la division des grands nombres prend à peu près au même moment, sans distinction de n.
Pour chaque entrée existante E dans la collection d'ensembles, arrêtez-vous si p (s)
p (e) et p (e) divise les p) pb exactement. Ajoutez S si vous arrivez à la fin de la collection. Un tableau de Bignums travaillerait.
@JL: Si vous souhaitez être mon harceleur sur site, veuillez s'efforcer de 1) Ajouter une valeur 2) avec précision.
Est-ce que le "permet à B de se rencontrer rapidement" exigeant le problème? Il semble que vous puissiez imaginer ce que la solution directe serait. Je voudrais simplement coder la solution directe, puis voir si elle répond à mes besoins de performance de l'espace / temps. Peut-être que la solution directe sera assez bonne.
J'ai bien peur de ne pas voir comment un arbre de préfixe aiderait beaucoup. Tous les sous-ensembles ne sont pas des préfixes.