This is the minimum code to obtain arrays intersection without any repetition in the final array. Can it be improved ? I think it can't because it uses the minimum number of iteration thanks to the break in the inner loop and also that it can't be parallelized due to a critical section inside the if clause, am I wrong ? I tried to try this function and the Matlab one (intersect) with the same output and the latter is much faster, how is it possible ?
int intersection(int* array1, int* array2, int len1, int len2, int size) {
int j, k, t, intersectC = 0;
int* tmp = (int*)malloc(sizeof(int) * size);
for (j = 0; j < len1; j ) {
for (k = 0; k < len2; k ) {
if (array1[j] == array2[k]) {
for (t = 0; t < intersectC; t ) {
if (tmp[t] == array1[j]) {
break;
}
}
if (t == intersectC) {
tmp[intersectC ] = array1[j];
}
}
}
}
free(tmp);
return intersectC;
}
P.S. size is the greatest between len1 and len2
CodePudding user response：
It can be improved. You have O(n3). If you sort both arrays, you can get the intersection in O(max(len1, len2)). Sorting both of them is O(len*log(len)).
Other idea is to encode each array as an unordered set via binary decision diagrams. Doing intersections is linear time using BDD.
CodePudding user response：
Your algorithm is O(N3), which is insanely bad considering it can be done quickly in O(N).
The following sorts the arrays (using a base2 radix sort), and then uses an approach akin to merge sort to find the intersection of the sorted arrays.
(I used uint32_t. I leave it to you to adapt to int.)
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_LEN(a) ( sizeof(a) / sizeof(*a) )
#define MALLOC(t, n) ( (t*)malloc(sizeof(t) * n) )
#define REALLOC(p, t, n) ( (t*)realloc(p, sizeof(t) * n) )
static void _sort_uint32s(uint32_t *a, size_t n, uint32_t mask) {
if ( n <= 1 )
return;
uint32_t *p = a;
uint32_t *q = a n;
while (1) {
while (1) {
if ( ( *p & mask ) != 0 )
break;
if ( p == q )
goto DONE_GROUPING;
}
while (1) {
if ( p == --q )
goto DONE_GROUPING;
if ( ( *q & mask ) == 0 )
break;
}
uint32_t tmp = *p;
*p = *q;
*q = tmp;
}
DONE_GROUPING:
mask >>= 1;
if ( !mask )
return;
if ( q > a )
_sort_uint32s(a, q-a, mask);
if ( q < a n )
_sort_uint32s(q, a n-q, mask);
}
static void sort_uint32s(uint32_t *a, size_t n) {
_sort_uint32s(a, n, 0x80000000);
}
static size_t min_size_t(size_t a, size_t b) {
return a < b ? a : b;
}
// Returns 0 on success.
// Returns -1 and sets errno on error.
// Will modify (sort) a1 and a2.
// Note that *set_p == NULL is possible on success.
static int intersect(uint32_t *a1, size_t n1, uint32_t *a2, size_t n2, uint32_t **set_p, size_t *n_p) {
size_t n = min_size_t(n1, n2);
uint32_t *set = MALLOC(uint32_t, n);
if (!set) {
*set_p = NULL;
*n_p = 0;
return -1;
}
sort_uint32s(a1, n1);
sort_uint32s(a2, n2);
n = 0;
while ( n1 && n2 ) {
if ( *a1 < *a2 ) {
while ( --n1 && *( a1) < *a2 );
}
else if ( *a2 < *a1 ) {
while ( --n2 && *( a2) < *a1 );
}
else {
uint32_t v = *a1;
set[n ] = v;
while ( --n1 && *( a1) == v );
while ( --n2 && *( a2) == v );
}
}
if ( !n ) {
free(set);
*set_p = NULL;
*n_p = 0;
return 0;
}
uint32_t *tmp = REALLOC(set, uint32_t, n);
*set_p = tmp ? tmp : set;
*n_p = n;
return 0;
}
int main(void) {
uint32_t a1[] = { 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15 };
size_t n1 = ARRAY_LEN(a1);
uint32_t a2[] = { 12, 1, 5, 2, 2 };
size_t n2 = ARRAY_LEN(a2);
uint32_t *set;
size_t n;
if ( intersect(a1, n1, a2, n2, &set, &n) < 0 ) {
perror(NULL);
exit(1);
}
printf("Intersection:");
for (size_t i=0; i<n; i)
printf(" %" PRIu32, set[i]);
printf("\n");
free(set);
return 0;
}
CodePudding user response：
In the end, following comments to this question, I used the radix sort to sort the two arrays and a classic intersection algorithm with O(n m). Probably, this code is a bit slower than the one posted by @ikegami but much faster than the one in the question.
int getMax(int* arr, int n){
int mx = arr[0];
for (int i = 1; i < n; i )
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void countSort(int* arr, int* output, int n, int exp){
int i, count[10] = { 0 };
for (i = 0; i < n; i )
count[(arr[i] / exp) % 10] ;
for (i = 1; i < 10; i )
count[i] = count[i - 1];
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i )
arr[i] = output[i];
}
void radixsort(int* arr, int n){
int m = getMax(arr, n);
int* output = (int*)malloc(sizeof(int) * n);
for (int exp = 1; m / exp > 0; exp *= 10) {
countSort(arr, output, n, exp);
}
free(output);
}
int intersection(int* arr1, int* arr2, int len1, int len2, int size){
int t, intersectC = 0;
int* tmp = (int*)malloc(sizeof(int) * size);
radixsort(arr1, len1);
radixsort(arr2, len2);
int i = 0, j = 0;
while (i < len1 && j < len2) {
if (arr1[i] < arr2[j])
i ;
else if (arr2[j] < arr1[i])
j ;
else /* if arr1[i] == arr2[j] */
{
for (t = 0; t < intersectC; t ) {
if (tmp[t] == arr1[j]) {
break;
}
}
if (t == intersectC) {
tmp[intersectC ] = arr1[j];
}
i ;
}
}
free(tmp);
return intersectC;
}