c - 提高C程序的计算速度

Question

我有以下问题:

给定 N 个数字的 2 个文件，例如

文件1.dat: 1,2,3,4,5,6,7,8,9,0

file2.dat: 2,5,4,7,6,9,8,1,0,3

我想知道第一个文件中两个连续数字的顺序在第二个文件中发生了多少次更改(包含相同的数字)。例如，在第一个文件中，我们开始查找 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;
}

我正在处理的文件非常大，从程序的第 3 行可以看出(每个文件 32421 个数字)，所以花费的时间太大了。有人对提高计算速度有什么建议吗？

---

我还尝试通过以下方式在循环中添加中断:

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