是否可以改進此陣列交集代碼

這是在最終陣列中沒有任何重復的情況下獲得陣列交集的最少代碼。可以改進嗎？我認為它不能，因為它使用了最少的迭代次數，這要歸功于內部回圈中的中斷，而且由于 if 子句中的臨界區，它無法并行化，我錯了嗎？我嘗試嘗試使用此函式和具有相同輸出的 Matlab 函式（相交），后者要快得多，這怎么可能？

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

PS大小在len1和len2之間最大

uj5u.com熱心網友回復：

你的演算法是 O(N ³ )，考慮到它可以在 O(N) 中快速完成，這是非常糟糕的。

下面對陣列進行排序（使用 base2基數排序），然后使用類似于歸并排序的方法來查找已排序陣列的交集。

（我用過uint32_t。我留給你去適應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;
}

uj5u.com熱心網友回復：

它可以改進。你有 O(n ³ )。如果對兩個陣列進行排序，則可以在 O(max(len1, len2)) 中獲得交集。對它們進行排序是 O(len*log(len))。

另一個想法是通過二元決策圖將每個陣列編碼為一個無序集。使用 BDD 進行交叉是線性時間。

uj5u.com熱心網友回復：

最后，根據對這個問題的評論，我使用基數排序對兩個陣列進行排序，并使用 O(n m) 的經典交集演算法。可能這段代碼比@ikegami 發布的代碼慢一點，但比問題中的代碼快得多。

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

標籤：C 集合交集

上一篇：找到正確的“演算法”來確定給定月份的第一天

下一篇：陣列洗掉問題angular8