C++ Différence entre deux vecteurs <MyType*> A et B

Question

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

concerne Kind, Pollux

Answer 1

L'approche non ordonnée aura typiquement 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 beaucoup d'opérations. Cela a son propre surcoût (être un arbre) mais si vous trouvez vraiment que c'est un problème d'efficacité, vous pouvez implémenter un allocateur de mémoire rapide pour insérer et supprimer des éléments très rapidement (note: ne faites cela que si vous définissez un goulot d'étranglement).

Avertissement: entrer dans un territoire un peu compliqué.

Il existe une autre solution qui peut être très rapide si applicable et vous n'avez jamais à vous soucier du tri des données. Fondamentalement, faire en sorte que tout groupe d'objets MyType partageant le même ID stocke un compteur partagé (ex: pointeur vers un entier non signé). Cela nécessitera la création d'une carte d'ID pour les compteurs et nécessitera l'extraction du compteur de la carte chaque fois qu'un objet MyType est créé en fonction de son ID. Puisque vous avez des objets MyType avec des ID en double, vous ne devriez pas avoir à insérer sur la carte aussi souvent que vous créez des objets MyType (la plupart ne peuvent probablement récupérer qu'un compteur existant). En plus de cela, avoir un compteur global 'traversal' qui est incrémenté chaque fois qu'il est récupéré.

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 revenons à l'endroit où vous avez des vecteurs A et B qui stockent MyType *. Pour récupérer les éléments dans A qui ne sont pas dans B, nous appelons d'abord traversal_counter(). En supposant que c'est la première fois que nous l'appelons, cela nous donnera une valeur de traversée de 0.

Maintenant parcourir tous les objets MyType * dans B et définir le compteur partagé pour chaque objet de 0 à la valeur de traversée, 1.

itérez chaque MyType * objet A. ceux qui ont une valeur de compteur qui ne correspond pas à la valeur actuelle traversal (1) sont les éléments a qui ne figurent pas dans B.

Qu'est-ce qui se passe lorsque vous débordez le compteur de parcours? Dans ce cas, nous parcourons tous les compteurs stockés dans la carte d'ID et les remettons à zéro avec le compteur de parcours lui-même. Cela n'aura besoin de se produire qu'une fois dans environ 4 milliards de traversées si c'est un entier non signé de 32 bits.

Il s'agit de la solution la plus rapide que vous pouvez appliquer à votre problème. Il peut effectuer n'importe quelle opération en complexité linéaire sur des données non triées (et toujours, pas seulement dans les meilleurs cas, comme une table de hachage), mais cela introduit de la complexité, ne le considérez que si vous en avez vraiment besoin.

Answer 2

Trier les deux vecteurs (std::sort) selon l'ID, puis utiliser 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

Regardez d'abord le problème. Vous voulez "tout dans A pas dans B". Cela signifie que vous allez devoir visiter "tout en A". Vous devrez également tout visiter en B pour avoir une connaissance de ce qui est ou n'est pas en B. Donc cela suggère qu'il devrait y avoir une solution O(n) + O(m), ou en prenant la liberté d'élider la différence entre n et m, O(2n).

Considérons l'approche std::set_difference. Chaque tri est O(n log n) et set_difference est O(n). L'approche sort-sort-set_difference est donc O(n + 2n log n). Appelons cela O(4n).

Une autre approche consisterait à placer d'abord les éléments de B dans un ensemble (ou une carte). L'itération sur B pour créer l'ensemble est O(n) plus l'insertion O(log n) de chaque élément, suivie de l'itération sur A O (n), avec une recherche pour chaque élément de A (log n), donne un total: O(2n log n). Appelons cela O(3n), ce qui est légèrement mieux.

Enfin, en utilisant un unordered_set (ou unordered_map), et en supposant que nous obtenons un cas moyen d'insertion et O(1)O(1) recherche, nous avons une approche qui est O(2n). A-ha! La vraie victoire ici est que unordered_set (ou map) est probablement le le choix le plus naturel pour représenter vos données en premier lieu, c.-à-d., La bonne conception donne l'implémentation optimisée. Cela n'arrive pas toujours, mais c'est sympa quand c'est le cas!

Answer 4

Si B préexiste à A, vous pouvez tenir un code C dans le fichier A.