提高C程序的計算速度

鑑於2個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個多小時。我如何加快速度？

來源

2013-01-09 Valerio D. Ciotti

是否所有的號碼不同的第一陣列的第一個元素的位置？ – pmg

你可以在你的循環中做一些'break'ing – pmg

@pmg，這個中斷可能是一個解決方案，但我不知道如何在程序中編寫它們。這些數字都是截然不同的 –

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-09 23:29:50

不客氣:) –

不錯。你也可以查找（B [i + 1] == A [k]），其中k從N開始，當j接近N時停止在k> j。 – pfnuesel

@pfnuesel是的，這是一種改進方法:) –

這裏的關鍵是「第一文件中的兩個連續號」。

沒有必要做一個O（N^2）循環。事實上，你可以使用動態規劃方法採用以下標準：

的數字是不同的
對於任何一組N數字，該數值是0..N-1（這是我的假設）
對於第一個文件中的任何兩個連續號碼A和B，如果您在遇到B時已遇到A，則順序將保留在第二個文件中。

請注意我對數值的假設。如果這個假設是錯誤的，那麼你可以使用當前被接受的O（N^2）-ish答案（儘管你可以建立一個樹來索引值，最壞的情況變成O（N.log（N））。

如果可以索引的值直接，那麼這個問題變爲線性。

來源

2013-01-09 23:47:09 paddy

但是我應該如何修改我的cicle？ –

'cicle'是什麼意思？ – paddy

對不起，我做了一個不好的翻譯。我的意思是循環 –

長度的兩個陣列，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; 
}

來源

2013-01-09 23:57:23 pmg

提高C程序的計算速度

回答

相關問題