C : 큰 배열을 효율적으로 루핑하기

Question

나는 약 500 개의 숫자를 가진 마스터리스트 정수 배열을 가지고있다. 그리고, 나는 잃어버린 숫자를 찾기 위해 마스터 목록에서 선택한 무작위 100 개 세트를 가지고 있습니다. 이제 마스터 목록에 대해이 임의 번호 목록을 검토해야합니다. 프로그램을 매달지 않고 C 프로그래밍을 진행하는 가장 좋은 방법은 무엇입니까? 만약 내가 500 개 요소에 대한 간단한 'for'루프를 살펴보면, 전체 목록을 살펴볼 필요가 있기 때문에 멈출 것이다. 누군가 이걸 내게 지시 할 수 있니?

감사합니다.

Answer 1

먼저 프로필을 만들어야합니다. 우리가 말하는 최대치에서 500 * 100 = 50,000 작업 만입니다. 평균적인 최신 컴퓨터는 코드를 매우 비효율적으로 코딩하지 않는 한 1/1 초 만에 끝낼 수 있습니다.

어쨌든 최적화하려는 경우 마스터 배열을 정렬하고 무작위 배열의 각 요소에 대해 binary search을 실행해야합니다. 이렇게하면 500 개의 숫자를 이원 검색하면 최대 9 개의 비교가 필요하기 때문에 연산 수를 50,000 개에서 900 개로 줄일 수 있습니다. 여기

int less_int(const void* left, const void* right) { 
    return *((const int*)left) - *((const int*)right); 
} 

int main(void) { 
    size_t num_elements = 500; 
    int* a = malloc(num_elements*sizeof(int)); 
    for(size_t i=0 ; i<num_elements ; i++) { 
     a[i] = rand() % num_elements; 
    } 
    qsort(a, num_elements, sizeof(int), less_int); 
    size_t num_rand = 100; 
    int* r = malloc(num_rand*sizeof(int)); 
    for(size_t i=0 ; i < num_rand ; i++) { 
     r[i] = rand() % num_rand; 
    } 

    for (size_t i = 0 ; i != num_rand ; i++) { 
     int *p = (int*) bsearch (&r[i], a, num_elements, sizeof(int), less_int); 
     if (p) { 
      printf ("%d is in the array.\n", *p); 
     } else { 
      printf ("%d is not in the array.\n", r[i]); 
     } 
    } 

    free(a); 
    free(r); 
    return 0; 
} 

가 link to this running program on ideone이다 : 여기

내장 사용하는 표준 C 라이브러리의 선별 및 이진 검색 기능 ( qsort 및 bsearch)을 구현 한 것이다.

Answer 2

n - 무작위 배열 길이입니다.

m - 마스터리스트 배열 길이.

1. 무작위로 정렬합니다. n * log (n)
2. 마스터 목록의 모든 요소에 대해 정렬 된 배열의 이진 검색. 따라서 모든 누락 된 요소가 있습니다. (m) * 로그 (N)

= "(m + N) * 로그 (N) 전체 동작. N = 100 및 m = 500으로 우리는

600 * 로그 (100) 로그 원시 코딩 50,000 반복에 비해 약 3986

2 반복의 기준으로했다.

추신 : 두 배열을 모두 정렬하면 O (m)만으로도 충분합니다.