Restar matrices

Question

¿Cuál es la forma más rápida de implementar una matriz de sustracción? Por ejemplo:

array a1 = [1, 3, 4, 5, 8]; 
array a2 = [2, 4, 5]; 

array a3 = a1 - a2; /* [1, 3, 8] */ 

Aquí array sería el tipo de mi programa utiliza para representar una estructura que se utiliza como un contenedor. El resto es pseudocódigo, por supuesto que no estoy creando las matrices ni restando.

La solución más simple que puedo pensar implica bucles anidados:

/* a1 - a2 */ 
for (i = 0; i < a1.size; ++i) { 
    int is_the_same = 0; 
    for (j = 0; i < a2.size; ++j) 
     if (a1[i] == a2[j]) { 
      is_the_same = 1; 
      break; 
     } 
    } 
    if (!is_the_same) 
     a3.push a1[i]; 
} 

Pero esto no parece muy eficiente. ¿Cuál sería otro enfoque?

Answer 1

Si sus matrices no están ordenadas, la peor complejidad de tiempo para una exclusión de matriz con una solución intuitiva es O (n) (aunque puede mejorar esto si ordena las matrices primero), ya que necesita para verificar la matriz completa si un elemento existe o no.

Ejemplo de peor de los casos:

array a1 = [1, 3, 4, 5, 8]; 
array a2 = [8, 5, 4, 3, 1]; 

Si se ordenan las matrices, a continuación, el peor complejidad de tiempo caso es O (n + m) (pseudo-código):

int i = 0; 
for(int j = 0; i < a1.size && j < a2.size;){ 
    if(a1[i] == a2[j]) 
     ++i, ++j; // exclude this element 
    if(a1[i] < a2[j]){ 
     a3.push(a1[i]); // include this element 
     ++i; 
    } 
    if(a1[i] > a2[j]) 
     ++j; // ignore lesser elements 
} 
while(i < a1.size) 
    a3.push(a1[i]); 

ACTUALIZACIÓN código-Wall -Wextra -pedantic C:

#include <stdio.h> 
#include <malloc.h> 

/** 
* The following function excludes values from an array using another arrays values. 
* Note that this version won't exclude multiple values, for this you have to drop 
* '++j' in line 25. 
* 
* \param[in] from Original sorted array 
* \param[in] from_length Original array length 
* \param[in] what Sorted array including the excluding values 
* \param[in] what_length self describing 
* \param[out] result_length the lenght of the new array - a value lesser 0 indicates an error. 
*/ 

int* exclude(int* from, int from_length, int* what, int what_length, int* result_length){ 
    int i,j,k; 
    int* result = (int*) malloc(sizeof(int)*from_length); 
    if(result == NULL){ 
     *result_length = -1; 
     return NULL; 
    } 
    for(i = j = k = 0; i < from_length && j < what_length;){ 
     if(from[i] == what[j]) 
      ++i, ++j; /* exclude this element - to enable multiple exclusion drop '++j' 
         4,4,5,6 /4 --> 5,6 */ 
     if(from[i] < what[j]) 
      result[k++] = from[i++]; 
     if(from[i] > what[j]) 
      ++j; /* ignore lesser elements */ 
    } 
    while(i < from_length) 
     result[k++] = from[i++]; 

    if(k < from_length){ 
     int* tmp = (int*) realloc(result,sizeof(int)*k); 
     if(tmp == NULL){ 
      /* either error handling or returning result */ 
     }else{ 
      result = tmp; 
     } 
    } 
    *result_length = k; 
    return result; 
} 

int main(){ 
    int a[6] = {1,2,3,4,5,6}; 
    int b[3] = {2,4,5}; 
    int result_length; 
    int i; 
    int *c = exclude(a,6,b,3,&result_length); 
    for(i = 0; i < result_length; ++i) 
     printf("%i ",c[i]); 
    free(c); 
    return 0; 
} 

Esta voluntad r esult en la peor complejidad de tiempo de O(n+m) para matrices ordenadas y O(n log n + m log m) para matrices no ordenadas (ordena ambas, usa la función provista anteriormente).

Answer 2

se puede hacer en O(nlogm + m) donde m es la matriz que está restando de, utilizando binary search (*) Si la matriz no está ordenada, se necesitará una especie primero que se traducirá en O(mlogm + nlogm + m)
pseudo código:

remove(a1,a2): //a1-a2 
    for each element x in a2: 
     i <- binarySearch(a1,x) 
     if x is in a1: 
     a1[x] <- NOT_VALID 
    remove all elements in a1 marked NOT_VALID 

(*) Usted tendrá que dar NOT_VALID un valor especial para la búsqueda binaria para seguir trabajando, o incluso más simple: mantener una nueva matriz de elementos marcados como NOT_VALID en lugar de los elementos de hecho marcado.

Answer 3

Si a1 no contiene duplicados, puede usar una estructura de datos configurada en hash, p. desde pblSet. Algo como esto:

PblSet* pSet = pblSetNewHashSet(); 

pblSetAddAll(pSet, a1); 
pblSetRemoveAll(pSet, a2); 

int** ppResult = (int**) pblSetToArray(pSet); 

// use *ppResult 
... 

free(ppResult); 
pblSetFree(pSet); 

El rendimiento debe ser O (n + m) y las matrices no necesita ser resuelto.

Answer 4

Porque, en que pidió la más rápido y más simple voy a introducir algunos supuestos:

• enteros
• finitos
• positivo
• única
• pequeña
• orden no es importante.

e.g. no tienes más de 10 números. A continuación, vamos a tratarlos como conjuntos para un O (n) solución (donde n representa el tamaño finito máximo del conjunto):

// Initialize array1 to [1, 3, 4, 5, 8]. 
unsigned char array1[10]; 
memset(array1, 0, 10); 
array1[1] = 1; 
array1[3] = 1; 
array1[4] = 1; 
array1[5] = 1; 
array1[8] = 1; 

// Initialize array2 to [2,4,5]. 
unsigned char array2[10]; 
memset(array2, 0, 10); 
array2[2] = 1; 
array2[4] = 1; 
array2[5] = 1; 

// Implement array3 = array1 - array2. 
unsigned char array3[10]; 
memset(array3, 0, 10); 
for (int i = 0; i < 10; i++) 
    array3[i] = array1[i] & ~array2[i]; 

Para una respuesta aún más cheekier, si los números en la matriz no exceda 0-31, sólo puede simplificar lo anterior usando unsigned int:

// array1 = 1, 3, 4, 5, 8 
    unsigned int array1 = (1 << 1) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 8); 
    // array2 = 2, 4, 5 
    unsigned int array2 = (1 << 2) | (1 << 4) | (1 << 5); 
    // array3 = array1 - array2; 
    unsigned int array3 = array1 &~ array2;