c - 超几何分布的 C 代码优化

Question

我必须优化给定的 C 代码:-

#include<sys/time.h>
#include<stdio.h>
#define GAP(start, end) ((end.tv_usec-start.tv_usec)+(end.tv_sec-start.tv_sec)*1000000)
void main(){
    struct timeval start_time, end_time;
    gettimeofday(&start_time, NULL);
    /* START OF BLOCK */
    long int n, N, e, E, e_choose_i, E_e_choose_N_i, E_choose_N;
    float p_value = 0;
    long int i, var1, var2, var3, var4; // Temporary variables
    fscanf(stdin, "%ld%ld%ld%ld", &n, &N, &e, &E);
    for(i = n; i <= N; i++){
        for(var1 = 1, var4 = 2; var4 <= e; var4++)
            var1 = var1 * var4; // Computes e!
        for(var2 = 1, var4 = 2; var4 <= i; var4++)
            var2 = var2 * var4; // Computes i!
        for(var3 = 1, var4 = 2; var4 <= e-i; var4++)
            var3 = var3 * var4; // Computes (e-i)!
        e_choose_i = var1/(var2*var3); // Computes (e choose i)
        for(var1 = 1, var4 = 2; var4 <= (E-e); var4++)
            var1 = var1 * var4; // Computes (E-e)!
        for(var2 = 1, var4 = 2; var4 <= (N-i); var4++)
            var2 = var2 * var4; // Computes (N-i)!
        for(var3 = 1, var4 = 2; var4 <= ((E-e)-(N-i)); var4++)
            var3 = var3 * var4; // Computes ((E-e)-(N-i))!
        E_e_choose_N_i = var1/(var2*var3); // Computes ((E-e) choose (N-i))
        p_value += e_choose_i*E_e_choose_N_i;
    }
    for(var1 = 1, var4 = 2; var4 <= E; var4++)
        var1 = var1 * var4; // Computes E!
    for(var2 = 1, var4 = 2; var4 <= N; var4++)
        var2 = var2 * var4; // Computes N!
    for(var3 = 1, var4 = 2; var4 <= E-N; var4++)
        var3 = var3 * var4; // Computes (E-N)!
    E_choose_N = var1/(var2*var3); // Computes (E choose N)
    p_value /= E_choose_N;
    /* END OF BLOCK */
    gettimeofday(&end_time, NULL);
    printf("p-value = %f (%d microseconds)", p_value, (int) GAP(start_time, end_time));
}

我使用动态规划方法来查找二项式系数，并将代码修改为:-

#include<sys/time.h>
#include<stdio.h>
#define GAP(start, end) ((end.tv_usec-start.tv_usec)+(end.tv_sec-start.tv_sec)*1000000)
void main(){
    struct timeval start_time, end_time;
    gettimeofday(&start_time, NULL);
    /* START OF BLOCK */
    long int n, N, e, E, e_choose_i, E_e_choose_N_i, E_choose_N;
    float p_value = 0;
    long int i; //var1, var2, var3, var4; // Temporary variables
    int p,q,r;
    fscanf(stdin, "%ld%ld%ld%ld", &n, &N, &e, &E);
    for(i = n; i <= N; i++){
        long int C[e+1][i+1];
        for(p=0;p<=e;p++)
        {
            r=(p<i)?p:i;
            for(q=0;q<=r;q++)
            {
                if(q==0 || q==p)
                    C[p][q]=1;
                else
                    C[p][q]=C[p-1][q-1]+C[p-1][q];
            }
        } 
        e_choose_i=C[e][i];
        long int C1[E-e+1][N-i+1];
        for(p=0;p<=E-e;p++)
        {
            r= (p<N-i)?p:N-i ;
            for(q=0;q<=r;q++)
            {
                if(q==0 || q==p)
                    C1[p][q]=1;
                else
                    C1[p][q]=C1[p-1][q-1]+C1[p-1][q];
            }
        } 
        E_e_choose_N_i = C1[E-e][N-i]; // Computes ((E-e) choose (N-i))
        p_value += e_choose_i*E_e_choose_N_i;
       }
     long int C2[E+1][N+1];
        for(p=0;p<=E;p++)
        {
            r= (p<N)?p:N ;
            for(q=0;q<=r;q++)
            {
                if(q==0 || q==p)
                    C2[p][q]=1;
                else
                    C2[p][q]=C2[p-1][q-1]+C2[p-1][q];
            }
        }   
    E_choose_N = C2[E][N]; // Computes (E choose N)
    p_value /= E_choose_N;
    /* END OF BLOCK */
    gettimeofday(&end_time, NULL);
    printf("p-value = %f (%d microseconds)", p_value, (int) GAP(start_time, end_time));
}

对于较小的值，例如 n=2、N=3、e=3 和 E=7，花费的时间较少，但对于较大的值，例如 n=3、N=8、e=10 和 E=7，花费更多的时间E=15。如何针对大值对其进行优化。请帮忙。

Answer 1

正如 dmuir 所指出的

You are including the fscanf in your timed sequence. This will take most of the time! It is always a good idea to time many calls of a function rather than one.

除此之外，您还可以尝试不同的方法来评估二项式系数:

double binomial(long n, long k)
{
    double result = 1.0;
    if ( k > n/2 )
        k = n - k;
    ++n;
    for (int i = 1; i <= k; ++i)
        result *= (double)(n - i) / i;
    return result;
}

这样计算(如果我正确的话)可以减少到

for(int i = n; i <= N; i++)
{       
    p_value += binomial(e, i) * binomial(E - e, N - i);
}
p_value /= binomial(E, N);

可测试here .