1

次の問題があります。

次のようなN個の数値の2つのファイルが与えられた場合

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

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

最初のファイルの 2 つの連続する数字の順序が 2 番目のファイル (同じ数字を含む) で何回変更されたかを知りたいです。たとえば、ファイル 1 では 1 と 2 の検索を開始し、2 番目のファイルでは 2 が 1 の前に来るため、順序が変更されました。最初のファイルには 9 と 0 があり、2 番目のファイルではこの順序が維持されます。

次のプログラムを書きました。

#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時間以上かかります。どうすればこれをスピードアップできますか?

4

3 に答える 3

4 
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..
}
于 2013-01-09T23:29:50.313 に答える
1

ここでポイントとなるのが、「最初のファイルの連続した 2 つの数字」です。

O(N^2) ループを実行する必要はありません。実際、次の基準を利用する動的計画法のアプローチを使用できます。

  • 数字が違う

  • 数値の任意のセットについて、N数値は次のとおりです0..N-1（これは私の仮定です）

  • 任意の 2 つの連続する番号についてA、最初のファイルで、 に遭遇した時点でBすでに遭遇していた場合、順序は 2 番目のファイルに保持されます。AB

値に関する私の仮定に注意してください。その仮定が間違っている場合は、現在受け入れられている O(N^2) っぽい回答を使用することもできます (ただし、値にインデックスを付けるためにツリーを作成すると、最悪の場合は O(N.log(N) になります) ）。

値に直接インデックスを付けることができる場合、この問題は線形になります。

于 2013-01-09T23:47:09.880 に答える
0

長さ N の 2 つの配列間の反転の数は ...

N が 1 の場合、反転の数は 0 です。
それ以外の場合は、最初の配列の最後の N-1 要素と、最初の配列の最初の要素を除いた 2 番目の配列との間の反転の数に、最初の要素の位置を加えたものです。 2 番目の配列内の最初の配列

再帰万歳:)

#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;
}
于 2013-01-09T23:57:23.703 に答える