C 프로그램의 계산 속도를 향상

Question

나는 다음과 같은 문제가 있습니다 : 같은 N 번호

을 감안할 때이 개 파일을

FILE1.DAT : 1,2,3,4,5,6,7 , 8,9,0

FILE2.DAT : 나는 얼마나 많은 시간을 알고 싶은 2,5,4,7,6,9,8,1,0,3

두 개의 연속 번호의 순서 첫 번째 파일의 두 번째 파일에서 변경된 파일 (동일한 번호 포함). 예를 들어, 파일 1에서 우리는 1과 2를 찾고, 두 번째 파일에서 2는 1 앞에옵니다. 따라서 순서가 변경되었습니다. 첫 번째 파일에는 9와 0이 있고 두 번째 파일에는이 순서가 유지됩니다.

#include <stdio.h> 
#include <stdlib.h> 
#define N 32421 

int main() { 
    int A[N], B[N]; 
    int i,j,k=0,count=0; 
    FILE *fp; 

    if ((fp = fopen ("file1.dat", "r")) == NULL) { 
    printf ("Error opening file 1\n"); 
    exit (EXIT_FAILURE); 
    } 
    for (i = 0; i < N; i++) 
    fscanf (fp, "%d", &A[i]); 
    fclose (fp); 

    if ((fp = fopen ("file2.dat", "r")) == NULL) { 
    printf ("Error opening file 2\n"); 
    exit (EXIT_FAILURE); 
    } 
    for (i = 0; i < N; i++) 
    fscanf (fp, "%d", &B[i]); 
    fclose (fp); 

    for(i=0; i<N-1; i++) 
    for(j=0; j<N; j++) 
     for(k=0 ; k<N; k++) 
     if(B[j]==A[i] && B[k]==A[i+1] && k < j) 
    count++; 


    printf("The number of inversion is: %d\n",count); 

    return 0; 
} 

내가 다루고있어있는 파일을 사용하면 프로그램 (각 파일에 대한 32421 개 번호)의 3 번째 줄에서 볼 수 있듯이 매우 큰, 그래서 시간 :

나는 다음과 같은 프로그램을 작성 찍은 것이 너무 큽니다. 누구나 계산 속도를 향상시킬 수있는 제안이 있습니까?

---

나는 휴식이 다음과 같은 방법으로 루프에 추가로도 시도 :

int a; 

    for(i=0;i<N-1;i++){ 
    a=0; 
    for(j=0;j<N;j++){ 
     for(k=0;k<N;k++){ 
    if(A[i]==B[j] && A[i+1]==B[k] && k<j) { 
     count++; 
     break; 
     a=1; 
    } if(A[i]==B[j] && A[i+1]==B[k] && j<k){ 
     break; 
     a=1; 
    } 
     } 
     if(a==1){ 
     break; 
     } 
    } 
    } 

하지만 여전히 5 시간 이상 소요됩니다. 어떻게 속도를 높일 수 있습니까?

Answer 1

for(i=0; i<N-1; i++) { 
    //looking for the position of B[i] in A 
    j=-1; 
    while (A[++j] != B[i]) {} 

    //now A[j] is B[i] 

    for (k= 0 ; k < j; k++) { 
     //is the next in B in a previous position in A ? 
     if (B[i+1] == A[k]) { 
      count++; 
      break; 
     } 
    } 
} 

는 또한, 여기에 또 다른 솔루션의 핵심은 여기에 "첫 번째 파일에 두 개의 연속 번호"입니다

int pos1, pos2; 
for(i=0; i<N-1; i++) { 
    pos2=-1; 
    for(j=-1; j<N && pos1 != -1 && pos2 != -1; j++) { //will stop if both are found 
     if (pos1 == -1 && B[i]==A[j]) pos1 = j; //found the position of a num 
     if (B[i+1]==A[j]) pos2 = j; //found the position of the next num 
     if (pos2 < pos1) { 
      count++; 
     } 
    } 
    pos1 = pos2; //useful for next loop.. 
} 

Answer 2

에게 있습니다.

O (N^2) 루프를 수행 할 필요가 없습니다. 사실, 당신은 다음과 같은 기준을 사용하는 동적 프로그래밍 접근 방식을 사용할 수 있습니다

• 숫자는 N 숫자의 집합의

• 별개을, 숫자 값 (이 나의 가정이다)

  0..N-1 있습니다

• 첫 번째 파일에 두 개의 연속 번호 A 및 B이있는 경우 B이 발생했을 때 이미 A이 발생한 경우 두 번째 파일에 순서가 유지됩니다.

필자의 가정에 유의하십시오. 그 가정이 거짓이라면, 현재 받아 들여지는 O (N^2) -ish 응답을 사용할 수도 있습니다 (인덱스 값을위한 트리를 만들 수는 있지만 최악의 경우는 O (N.log (N)).

색인 수 있다면 값 바로 다음이 문제는 선형된다.

Answer 3

N 인 길이의 두 어레이 사이의 반전 횟수 ...

N이 1이면 반전 수는 0
입니다. 그렇지 않으면 첫 번째 배열의 마지막 N-1 요소와 첫 번째 배열의 첫 번째 요소를 제외한 두 번째 배열 사이의 반전 수입니다. 두번째 배열 재귀

만세 :)

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

static int find(int a, int *b, size_t n) { 
    size_t k = 0; 
    while (k < n) { 
    if (b[k] == a) return k; 
    k++; 
    } 
    return -1; 
} 

int ninversions(int *a, int *b, size_t n) { 
    if (n == 1) return 0; 
    size_t pos = find(*a, b, n); 
    if (pos == (size_t)-1) exit(EXIT_FAILURE); 
    int *newb = malloc((n - 1) * sizeof *newb); 
    memcpy(newb, b, pos * sizeof *b); 
    memcpy(newb + pos, b + pos + 1, (n - pos - 1) * sizeof *b); 
    int retval = pos + ninversions(a + 1, newb, n - 1); 
    free(newb); 
    return retval; 
}