Блог

Эта функция f предназначена для поиска общих элементов в массиве и возврата результирующего массива, и я использую 4 четырех цикла для выполнения этой задачи, которая, по моему мнению, не является лучшим использованием циклов, другая проблема заключается в том, как я могу определить размер возвращаемого массива, чтобы мой цикл находился в пределах

вот код

 #include <stdio.h>
#include <stdlib.h>

int *f(int first[], int second[], int size_first, int size_second);
int main(void) {
  int arr1[]={1, 8, 3, 2, 6};
  int arr2[]= {2, 6, 1};
  int size1 = sizeof(arr1)/sizeof(arr1[0]);
  int size2 = sizeof(arr2)/sizeof(arr2[0]);
  int *intersection = f(arr1, arr2, size1, size2); 
  for(int i=0;i<3; i  ){
    printf("%d ", intersection[i]);
  }
  return 0;
}

 // function to find common elements in 2 arrays
 int *f(int first[], int second[], int size_first, int size_second){
  int k=0, count=0;

   //loop through the array to find the number common elements and store in count for dynamic memory allocation in future
   for(int i=0;i<size_first;i  ){
     for(int j=0;j<size_second;j  ){
       if(first[i]==second[j]){
        count   ;
       }
     }
   }


  // allocate memory for the common elements by making use of count
  int * common_elements = (int*)malloc(count*sizeof(int));

  // store the common elements in the new memory location
  for(int i=0;i<size_first;i  ){
     for(int j=0;j<size_second;j  ){
       if(first[i]==second[j]){
        common_elements[k]=first[i];
        k  ;
       }
     }
   }
  
  return common_elements;
  free(common_elements);
 }
 

Если вам разрешено тратить немного памяти, обратите внимание, что пересечение не может иметь мощность больше, чем количество элементов в меньшем наборе. Таким образом, вы можете выделить больше памяти, чем вам может понадобиться, и избежать необходимости сначала считать, а затем выделять.

Или вы можете realloc по ходу дела.

В общем, вам нужна хорошая структура данных для проверки принадлежности к множеству быстрее, чем для сканирования всего массива, хотя для небольших размеров, которые помещаются в различные кэши, линейное сканирование также не будет работать слишком плохо.

Однако для больших наборов вам нужно загрузить больший из наборов в дерево AVL или дерево козлов отпущения.

Для действительно больших наборов данных вам нужно изучить фильтры Блума и связанные структуры данных в зависимости от варианта использования.

Я включаю ниже самое наивное улучшение в вашем коде, которое все еще имеет вложенный цикл и тратит память до размера меньшего набора, чтобы избежать подсчета общих элементов в первую очередь.

 #include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

// TODO: What about duplicates in smaller set?
int *
int_set_intersection(
        const int *first,
        const int *second,
        const size_t size_first,
        const size_t size_second,
        size_t *n
        )
{
    size_t K = 0; // number of common elements
    const int is_first_smaller = (size_first < size_second);
    // Done this way so I can declare variables as consts
    const int *set_smaller = is_first_smaller ? first : second;
    const int *set_larger  = is_first_smaller ? second : first;
    const size_t size_smaller   = is_first_smaller ? size_first : size_second;
    const size_t size_larger    = is_first_smaller ? size_second : size_first;

    int *common = malloc(size_smaller * sizeof(*common));

    if (!common) {
        fprintf(stderr, "Failed to allocate memory for %z intsn", size_smaller);
        perror("Cannot allocate memory for common elements");
        exit(EXIT_FAILURE);
    }

    for (size_t i = 0; i < size_smaller;   i) {
        for (size_t j = 0; j < size_larger;   j) {
            if (set_smaller[i] == set_larger[j]) {
                common[K] = set_smaller[i];
                  K;
                break;
            }
        }
    }

    *n = K;
    return common;
}

void
int_set_print(const int *set, size_t n, FILE *f)
{
    FILE *out = f ? f : stdout;
    size_t i = 0;

    fputs("{ ", out);

    for (i = 0; i < n - 1;   i) {
        fprintf(out, "%d, ", set[i]);
    }

    fprintf(out, "%d }n", set[i]);
}

int
main(void) {
  int arr1[] = {1, 8, 3, 2, 6};
  int arr2[] = {2, 5, 1};
  size_t n = 0;

  const int *intersection = int_set_intersection(
          arr1,
          arr2,
          sizeof(arr1)/sizeof(arr1[0]),
          sizeof(arr2)/sizeof(arr2[0]),
          amp;n
          );

  int_set_print(intersection, n, NULL);

  free(intersection); // not really needed, but good hygiene

  return 0;
}
 

Для больших массивов одним из вариантов является сортировка содержимого, чтобы упростить проверку на наличие общих элементов, как показано в приведенном ниже коде. Если исходное содержимое массива не может быть изменено, сначала скопируйте их в динамически выделяемую память. Динамически выделяемая память также необходима для хранения списка общих элементов, но для этого может использоваться то же хранилище, что и для одной из копий.

Исходная функция OP возвращает указатель на динамически выделяемую память, содержащую массив общих элементов, но не указывает длину массива. Я добавил параметр для возврата длины.

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int *f(int first[], int second[], int size_first, int size_second, int *size_common);
int main(void) {
  int arr1[]={1, 8, 3, 2, 6};
  int arr2[]= {2, 6, 1};
  int size1 = sizeof(arr1)/sizeof(arr1[0]);
  int size2 = sizeof(arr2)/sizeof(arr2[0]);
  int size_common;
  int *intersection = f(arr1, arr2, size1, size2, amp;size_common); 
  for(int i=0;i<size_common; i  ){
    printf("%d ", intersection[i]);
  }
  free(intersection);
  return 0;
}

static int cmp_int(const void *ap, const void *bp) {
  int a = *(const int *)ap;
  int b = *(const int *)bp;
  return (a > b) - (a < b);
}

// function to find common elements in 2 arrays
int *f(int first[], int second[], int size_first, int size_second,
       int *size_common) {
  int *copy1;
  int *copy2;
  int idx1;
  int idx2;
  int count;

  // allocate memory local copies of the arrays
  copy1 = malloc(size_first * sizeof (int));
  copy2 = malloc(size_second * sizeof (int));
  if (!copy1 || !copy2) {
    // allocation error
    free(copy1);
    free(copy2);
    *size_common = -1;  // use -1 to report error
    return NULL;
  }

  // copy the arrays
  memcpy(copy1, first, size_first * sizeof (int));
  memcpy(copy2, second, size_second * sizeof (int));

  // sort the copies in ascending order
  qsort(copy1, size_first, sizeof (int), cmp_int);
  qsort(copy2, size_second, sizeof (int), cmp_int);

  // find common elements
  idx1 = 0;
  idx2 = 0;
  count = 0;
  while (idx1 < size_first amp;amp; idx2 < size_second) {
    if (copy1[idx1] < copy2[idx2]) {
      idx1  ;
    } else if (copy1[idx1] > copy2[idx2]) {
      idx2  ;
    } else {
      // common element found!
      // use copy1[] to store common elements
      copy1[count] = copy1[idx1];
      count  ;
      idx1  ;
      idx2  ;
    }
  }

  // common elements are in copy1[].
  // finished with copy2, so free it.
  free(copy2);

  if (count == 0) {
    // no common elements
    free(copy1);  // free the memory
    copy1 = NULL; // and make the function return NULL
  } else {
    // try to reduce memory for common elements
    copy2 = realloc(copy1, count * sizeof (int));
    if (copy2) {
      // reallocation successful
      copy1 = copy2;
    } // else, never mind, copy1 is still valid
  }

  // return the common elements
  *size_common = count;
  return copy1;
}
 

Если ваши массивы состоят из сопоставимых элементов (вы используете сопоставимые целые числа), на мой взгляд, лучший способ — отсортировать оба массива и пройти оба параллельно, рассматривая обе стороны и сравнивая элементы с обеих сторон. Если есть самый низкий элемент, переместите его указатель, оставив другой в ожидании …. если есть совпадение (они равны), вы можете пометить его (подробнее об этом позже) и перемещать оба указателя, пока не дойдете до конца в одном массиве (самом сортированном). Вы получите отметки на совпадающих позициях, но если вы измените порядок массива, заменив найденный элемент первым из еще не совпадающих элементов, у вас будут все совпадающие элементы в первых позициях обоих массивов, что позволит вам возвращать только количество совпадений из функции и совпадений себя на первых позициях обоих массивов.

Сложность этого алгоритма должна составлять O (n * log (n)) (из-за быстрой сортировки), если вы используете быструю сортировку, плюс O (n) (что не влияет на конечное O) для сопоставления, поэтому O (n * log (n)) должно быть большим Oсложность, как общий случай. Ниже приведен пример кода с выполнением:

комп.c

 #include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

#define N(arr) (sizeof(arr)/sizeof((arr)[0]))

void swap(int *ref_a, int *ref_b)
{
    if (ref_a == ref_b)
        return; /* nothing to do. */
    int temp = *ref_a;
    *ref_a = *ref_b;
    *ref_b = temp;
}

int int_cmp(const void *_a, const void *_b)
{
    const int *a = _a, *b = _b;
    return *a - *b;
}

void print(int v[], int v_sz, const char *fmt, ...)
{
    va_list p;
    va_start(p, fmt);
    vprintf(fmt, p);
    va_end(p);
    char *sep = "[";
    for (int i = 0; i < v_sz; i  ) {
        printf("%s%d", sep, v[i]);
        sep = ", ";
    }
    printf("]n");
}

int find_matches(int a[], int b[], int a_sz, int b_sz)
{
    print(a, a_sz, "a(unsorted)");
    print(b, b_sz, "b(unsorted)");
    qsort(a, a_sz, sizeof a[0], int_cmp);
    qsort(b, b_sz, sizeof b[0], int_cmp);
    print(a, a_sz, "a(sorted)");
    print(b, b_sz, "b(sorted)");
    int i = 0;
    for (int i_a = 0, i_b = 0; i_a < a_sz amp;amp; i_b < b_sz;) {
        if (a[i_a] < b[i_b]) {
            i_a  ;
            continue;
        } else if (a[i_a] > b[i_b]) {
            i_b  ;
            continue;
        }
        /* a[i_a] == b[i_b] */
        swap(amp;a[i_a], amp;a[i]);
        swap(amp;b[i_b], amp;b[i]);
        print(a, a_sz, "after #%d, a:", i);
        print(b, b_sz, "after #%d, b:", i);
        i_a  ; i_b  ; i  ;
    }
    return i;
}

int main()
{
    int arr1[] = {1, 8, 3, 2, 6, 7};
    int arr2[] = {2, 6, 1, 7, 4, 1, 9, 6};
    int size1 = N(arr1);
    int size2 = N(arr2);

    int match = find_matches(arr1, arr2, size1, size2);

    for (int i = 0; i < match; i  ) {
        printf("Match #%d: %dn", i, arr1[i]);
    }
}

 

Это приведет к:

 $ comp
a(unsorted)[1, 8, 3, 2, 6, 7]
b(unsorted)[2, 6, 1, 7, 4, 1, 9, 6]
a(sorted)[1, 2, 3, 6, 7, 8]
b(sorted)[1, 1, 2, 4, 6, 6, 7, 9]
after #0, a:[1, 2, 3, 6, 7, 8]
after #0, b:[1, 1, 2, 4, 6, 6, 7, 9]
after #1, a:[1, 2, 3, 6, 7, 8]
after #1, b:[1, 2, 1, 4, 6, 6, 7, 9]
after #2, a:[1, 2, 6, 3, 7, 8]
after #2, b:[1, 2, 6, 4, 1, 6, 7, 9]
after #3, a:[1, 2, 6, 7, 3, 8]
after #3, b:[1, 2, 6, 7, 1, 6, 4, 9]
Match #0: 1
Match #1: 2
Match #2: 6
Match #3: 7
$ _
 

Хорошим интерфейсом является переключение в обоих алгоритмах сопоставленных элементов с первым из еще не сопоставленных элементов в обоих массивах, поэтому таким образом вы можете вернуть целое число (то, которое вы используете, чтобы узнать начало еще не сопоставленных элементов), которое сообщает вам количество совпадающих элементов.сопоставленные элементы, и вы получите их из любого из двух массивов.

Если элементы несопоставимы, и их можно просто сравнить для равенства, тогда вам нужно сравнить каждый элемент с любым другим для соответствия, удалить их из массивов (это можно сделать, заменив их первым из еще не сопоставленных элементов и продвинув указатели),и начните снова с их уменьшенных версий. Некоторый способ сделать это — когда вы находите совпадение, обменять их на первый, второй, третий элементы каждого массива и использовать вариант вышеупомянутого алгоритма (вы переупорядочиваете по мере совпадения) В этом случае вы сравниваете в первый раз n * m (но не все),когда вы получаете совпадение, (n-1) * (m-1), … и так до последнего сравнения, в котором вы не выполняете все сравнения с (m-k) * (n-k) . В среднем это m* n/2 (m-1)*(n-1)/2 … (m-k)* (n-k). что-то в диапазоне m (m-1) * n (n-1) / k ^ 2, что равно O (m ^ 2 * n ^ 2):

comp2.c

 #include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

#define N(arr) (sizeof(arr)/sizeof((arr)[0]))

void swap(int *ref_a, int *ref_b)
{
    if (ref_a == ref_b)
        return; /* nothing to do. */
    int temp = *ref_a;
    *ref_a = *ref_b;
    *ref_b = temp;
}

int int_cmp(const void *_a, const void *_b)
{
    const int *a = _a, *b = _b;
    return *a - *b;
}

void print(int v[], int v_sz, const char *fmt, ...)
{
    va_list p;
    va_start(p, fmt);
    vprintf(fmt, p);
    va_end(p);
    char *sep = "[";
    for (int i = 0; i < v_sz; i  ) {
        printf("%s%d", sep, v[i]);
        sep = ", ";
    }
    printf("]n");
}



int find_matches(int a[], int b[], int a_sz, int b_sz)
{
    print(a, a_sz, "a(unsorted)");
    print(b, b_sz, "b(unsorted)");
    int i = 0;
    loop:
    for (int i_a = 0; i_a   i < a_sz; i_a  ) {
        for (int i_b = 0; i_b   i < b_sz; i_b  ) {
            /* we can only compare for equality */
            if (a[i   i_a] == b[i   i_b]) {
                swap(amp;a[i   i_a], amp;a[i]);
                swap(amp;b[i   i_b], amp;b[i]);
                i  ;
                goto loop;
            }
        }
    }
    print(a, a_sz, "a(final)");
    print(b, b_sz, "b(final)");
    return i;
}

int main()
{
    int arr1[] = {1, 8, 3, 2, 6, 7};
    int arr2[] = {2, 6, 1, 7, 4, 1, 9, 6};
    int size1 = N(arr1);
    int size2 = N(arr2);

    int match = find_matches(arr1, arr2, size1, size2);

    for (int i = 0; i < match; i  ) {
        printf("Match #%d: %dn", i, arr1[i]);
    }
}
 

который выдает при запуске следующий вывод:

 $ comp2
a(unsorted)[1, 8, 3, 2, 6, 7]
b(unsorted)[2, 6, 1, 7, 4, 1, 9, 6]
a(final)[1, 2, 6, 7, 3, 8]
b(final)[1, 2, 6, 7, 4, 1, 9, 6]
Match #0: 1
Match #1: 2
Match #2: 6
Match #3: 7
$ _
 

Вы можете изменить порядок значений, разницы нет, в этом случае у вас был двухуровневый for цикл, смешанный с третьим уровнем, вернитесь к началу и начните цикл заново. Цикл гарантированно завершается, так как, когда вы возвращаетесь к началу, вы увеличили i , что означает, что вложенные for циклы будут короче каждый раз. find_matches В этом случае мы можем переписать процедуру, настроив начальные точки массива следующим образом:

comp3.c

 /* ... as before */
int find_matches(int a[], int b[], int a_sz, int b_sz)
{
    print(a, a_sz, "a(unsorted)");
    print(b, b_sz, "b(unsorted)");
    int i = 0;
    loop:
    for (int i_a = 0; i_a < a_sz; i_a  ) {
        for (int i_b = 0; i_b < b_sz; i_b  ) {
            /* we can only compare for equality */
            if (a[i_a] == b[i_b]) {
                swap(amp;a[i_a], amp;a[0]);
                swap(amp;b[i_b], amp;b[0]);
                i  ;
                print(a  , a_sz--, "a(after match)");
                print(b  , b_sz--, "b(after match)");
                goto loop;
            }
        }
    }
    print(a, a_sz, "a(final)");
    print(b, b_sz, "b(final)");
    return i;
}
/* ... as before */
 

это приведет к такому результату (я изменил начальный порядок сортировки, чтобы посмотреть, как это влияет на конечный результат):

 $ comp3
a(unsorted): [7, 8, 2, 3, 6, 1]
b(unsorted): [2, 6, 1, 7, 4, 1, 9, 6]
a(after match): [7, 8, 2, 3, 6, 1]
b(after match): [7, 6, 1, 2, 4, 1, 9, 6]
a(after match): [2, 8, 3, 6, 1]
b(after match): [2, 1, 6, 4, 1, 9, 6]
a(after match): [6, 3, 8, 1]
b(after match): [6, 1, 4, 1, 9, 6]
a(after match): [1, 8, 3]
b(after match): [1, 4, 1, 9, 6]
a(final): [8, 3]
b(final): [4, 1, 9, 6]
Match #0: 7
Match #1: 2
Match #2: 6
Match #3: 1
$ _