Différence entre deux vecteur A et B

Question

J'ai deux objets vector<MyType*> appelés A et B. La classe MyType a un ID sur le terrain et je veux obtenir le MyType* qui sont en A mais pas dans B. Je travaille sur une application d'analyse d'image et j'espérais trouver une solution rapide / optimisé.

Answer 1

L'approche non ordonnée aura généralement la complexité quadratique, sauf si les données sont triées à l'avance (par votre champ ID), auquel cas il serait linéaire et ne nécessiterait pas des recherches répétées par B.

struct CompareId
{
    bool operator()(const MyType* a, const MyType* b) const
    {
        return a>ID < b->ID;
    }
};
...
sort(A.begin(), A.end(), CompareId() );
sort(B.begin(), B.end(), CompareId() );

vector<MyType*> C;
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C) );

Une autre solution consiste à utiliser un conteneur ordonné comme std :: set avec CompareId utilisé pour l'argument modèle de StrictWeakOrdering. Je pense que ce serait mieux si vous avez besoin d'appliquer un grand nombre d'opérations ensemble. Qui a sa propre tête (étant un arbre) mais si vous trouvez vraiment être un problème d'efficacité, vous pourriez mettre en œuvre un allocateur de mémoire rapide pour insérer et supprimer des éléments super rapide (note: seulement faire cela si vous profil et déterminer ce pour être un goulot d'étranglement).

Attention:. Entrer dans un territoire un peu compliqué

Il y a une autre solution, vous pouvez envisager ce qui pourrait être très rapide le cas échéant et vous ne jamais avoir à vous soucier de tri des données. En gros, faire un groupe d'objets MyType qui partagent le même magasin d'identité, un compteur partagé (ex: pointeur vers unsigned int).

Cela nécessitera la création d'une carte d'ID de compteurs et aller chercher le compteur nécessitent de la carte à chaque fois qu'un objet MyType est créé sur la base de son ID. Puisque vous avez MyType objets avec ID en double, vous ne devriez pas avoir à insérer à la carte aussi souvent que vous créez des objets MyType (la plupart peuvent probablement chercher un compteur existant).

En plus de cela, ont un compteur global « traversal » qui s'incrémente chaque fois qu'il est tiré par les cheveux.

static unsigned int counter = 0;
unsigned int traversal_counter()
{
    // make this atomic for multithreaded applications and
    // needs to be modified to set all existing ID-associated
    // counters to 0 on overflow (see below)
    return ++counter;
}

Maintenant, nous allons revenir à l'endroit où vous avez des vecteurs A et B * stockage MyType. Pour récupérer les éléments de A qui ne sont pas en B, nous avons d'abord traversal_counter d'appel (). En supposant que c'est la première fois que nous l'appelons, qui nous donnera une valeur de 1. traversal

Maintenant itérer à travers chaque MyType * objet B et régler le compteur partagé pour chaque objet de 0 à la valeur de traversée, 1.

Maintenant itérer à travers chaque MyType * objet A. Ceux qui ont une valeur de compteur qui ne correspond pas à la valeur de traversée de courant (1) sont les éléments de A qui ne sont pas contenus dans B.

Qu'est-ce qui arrive quand vous déborder le compteur traversal? Dans ce cas, nous itérer à travers tous les compteurs stockés dans la carte d'identité et les remises à zéro, le compteur de traversal lui-même. Cela ne doit se produire une fois dans environ 4 milliards traversals si c'est un 32 bits unsigned int.

Ceci est de la solution la plus rapide, vous pouvez appliquer à votre problème donné. Il peut faire toute opération de jeu en complexité linéaire sur des données non triées (et toujours, non seulement dans les meilleurs scénarios comme une table de hachage), mais elle introduit une certaine complexité donc considérer que si vous avez vraiment besoin.

Answer 2

Classer les deux vecteurs ( std::sort ) selon l'ID, puis utilisez std::set_difference . Vous devez définir un comparateur personnalisé pour passer à ces deux algorithmes, par exemple

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};

Answer 3

Tout d'abord regarder le problème. Vous voulez « tout en A non B ». Cela signifie que vous allez avoir à visiter « tout en un ». Vous aurez également à tout séjour en B d'avoir connaissance de ce qui est et n'est pas en B. Donc, qui suggère qu'il devrait y avoir une solution O(n) + O(m), ou de prendre la liberté de elide la différence entre n et m, O(2n).

Considérons l'approche std::set_difference. Chaque espèce est O(n log n) et set_difference est O(n). Ainsi, l'approche genre tri-set_difference est O(n + 2n log n). L'appel Let que O(4n).

Une autre approche serait d'abord les éléments de B dans un ensemble (ou la carte). Itération à travers B pour créer le jeu est O(n) ainsi insertion O(log n) de chaque élément, suivi par itération à travers un O (n), avec une recherche pour chaque élément de A (log n), donne un total: O(2n log n). L'appel de Let que de O(3n), ce qui est légèrement mieux.

Enfin, l'utilisation d'un unordered_set (ou unordered_map), et en supposant que nous obtenons en moyenne cas d'insertion de O(1) et O(1) recherche, nous avons une approche qui est O(2n). A-ha!

La vraie victoire ici est que unordered_set (ou la carte) est probablement le choix le plus naturel pour représenter vos données en premier lieu, à savoir la conception appropriée cède la mise en œuvre optimisée. Cela ne se produit pas toujours, mais il est agréable quand il fait!

Answer 4

Si B préexiste à A, puis en A peuplant, vous pouvez bookkeep dans un vecteur C.