Diferencia entre dos vector A y B

Question

Tengo dos objetos llamados vector<MyType*> A y B. La clase tiene una MyType ID campo y quiero conseguir el MyType* que están en A pero no en B. Estoy trabajando en una aplicación de análisis de imagen y que estaba esperando encontrar una solución rápida / optimizado.

Answer 1

El enfoque no ordenada típicamente tiene complejidad cuadrática a menos que los datos se clasifican de antemano (por el campo ID), en cuyo caso sería lineal y no requeriría búsquedas repetidas a través de 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) );

Otra solución es utilizar un recipiente ordenado como std :: set con CompareId utiliza para el argumento de plantilla StrictWeakOrdering. Creo que esto sería mejor si es necesario aplicar una gran cantidad de operaciones de conjuntos. Que tiene su propia cabeza (al ser un árbol), pero si realmente encuentra que ser un problema de eficiencia, se podría implementar un asignador de memoria rápida de poner y quitar elementos súper rápido (Nota: sólo hacer esto si perfil y determinar que se trata de un cuello de botella).

Advertencia:. Entrar en el territorio un tanto complicado

Hay otra solución se puede considerar que podría ser muy rápido si es aplicable y que nunca tenga que preocuparse por la ordenación de datos. Básicamente, hacer que cualquier grupo de objetos MyType que comparten el mismo ID de la tienda de un contador compartido (por ejemplo: puntero a int sin signo).

Esto requerirá la creación de un mapa de identificadores de contadores y requieren ir a buscar el contador del mapa cada vez que un objeto MyType se crea basándose en su ID. Puesto que usted tiene objetos MyType con identificadores duplicados, que no debería tener que insertar al mapa con la frecuencia que crea objetos MyType (más probablemente puede ir a buscar un contador existente).

Además de esto, tiene un contador global 'transversal' que consigue incrementa cada vez que es inverosímil.

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;
}

Ahora vamos a volver a donde usted tiene vectores A y B que almacenan MyType *. Para obtener los elementos de A que no están en B, primero traversal_counter llamada (). Asumiendo que es la primera vez que lo llamamos, que nos dará un valor transversal de 1.

Ahora iterar a través de cada MyType * objeto en B y poner el contador compartida para cada objeto desde 0 al valor de recorrido, 1.

Ahora iterar a través de cada MyType * objeto en A. Los que tienen un valor de contador que no coincide con el valor de recorrido de corriente (1) son los elementos de A que no están contenidos en B.

¿Qué pasa cuando se desborde el contador de recorrido? En este caso, iterar a través de todos los contadores almacenados en el mapa ID y los establecidos en cero, junto con la propia contador de recorrido. Esto sólo tendrá que ocurrir una vez en cerca de 4 mil millones recorridos si es un 32-bit unsigned int.

Se trata de la solución más rápida se puede aplicar a su problema dado. Se puede hacer cualquier operación en conjunto complejidad lineal en los datos no clasificados (y siempre, no sólo en los mejores casos, como una tabla hash), pero sí introduce cierta complejidad por lo que sólo tienen en cuenta que si realmente lo necesita.

Answer 2

Ordenar ambos vectores ( std::sort ) de acuerdo con ID y luego usar std::set_difference . Usted tendrá que definir un comparador personalizado para pasar al tanto de estos algoritmos, por ejemplo

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

Answer 3

En primer vistazo al problema. Que desea "todo en un no en B". Eso significa que vas a tener que visitar "todo en una". Usted también tiene que visitar todo en B a tener conocimiento de lo que es y no es en B. Para que sugiere que debería ser una solución O(n) + O(m), o teniendo libertad para eludir la diferencia entre n y m, O(2n).

Vayamos de tener en cuenta el enfoque std::set_difference. Cada especie es O(n log n) y set_difference es O(n). Por lo que el enfoque de especie-tipo-set_difference es O(n + 2n log n). la llamada de Let que O(4n).

Otro enfoque sería primer lugar los elementos de B en un conjunto (o mapa). La iteración a través de B para crear el conjunto es O(n) más O(log n) inserción de cada elemento, seguido de iteración a través de un O (n), con una búsqueda para cada elemento de A (log n), da un total: O(2n log n). la llamada de Let que O(3n), que es un poco mejor.

Finalmente, utilizando un unordered_set (o unordered_map), y suponiendo que obtenemos caso medio de la inserción O(1) y la búsqueda O(1), tenemos un enfoque que es O(2n). A-ha!

La verdadera victoria aquí es que unordered_set (o mapa) es probablemente la opción más natural para representar los datos en el primer lugar, es decir, el diseño adecuado se obtiene la implementación optimizada. Eso no siempre sucede, pero es bueno cuando lo hace!

Answer 4

Si B preexiste a A, entonces al rellenar A, puede bookkeep en un vector C.