主页 / 问题 / 1229599
Accepted
videxerion
Asked:2022-01-11 04:39:14 +0000 UTC2022-01-11 04:39:14 +0000 UTC

如何使代码尽可能快？

  • 772

我有一个 C 代码，可以将一个数字分解成对（蛮力）。有什么方法可以加快代码速度，尽管提高了 1 毫秒（除了多线程）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

clock_t start, end;

void main() {
    int first = 1;
    int userInput;

    scanf_s("%d", &userInput);
    int Two = userInput;
    start = clock();
    while (first != userInput){
        Two = userInput;
        while (Two != 0) {
            if (Two != 1){
                if (first * Two == userInput) {
                    printf("%d %d\n", first, Two);
                }
            }
            Two--;
        }
        first++;
    }
    end = clock();
    printf("The above code block was executed in %.4f second(s)\n", ((double)end - start) / ((double)CLOCKS_PER_SEC));
    system("PAUSE");
}
c

3 个回答

  1. Best Answer

    可以改进的地方：

    1. 该函数clock的分辨率非常低，似乎是16ms。这对你的任务来说太粗糙了。

    2. 内循环是多余的。在外循环中，将数字除以第一个除数，如果余数为零，则找到一对除数。

    3. 从最小到最大开始搜索除数是合乎逻辑的。寻找范围内的第一个除数[1, sqrt(N)]。

    4. 找到一个除数后，您可以寻找下一对除数，而不是原始数字，而是已经被除数的数字。尽管需要恢复原始数字的除数对，但这将大大加快该过程。

    5. 除数通常不会成对搜索。一个数被分解为素数：整数分解。然后，从简单的开始，您可以构建所有必要的对。这是最快的方法。

    例子

    f1

    原来的videx程序。工作缓慢，因为它会检查直到N（我们分解的数字）的所有数字对。复杂性O(N^2)。几乎所有对都打印了两次。如果N > 46340 (= sqrt(2^31))由于溢出是错误的。

    f2

    由user419509建议。除以N所有数字，最高为sqrt(N)。复杂性O(sqrt(N))。N < 2^31.

    f3

    哈利建议。除以N所有奇数直到sqrt(N)。如果找到一个除数，则按它减少N并继续搜索。最糟糕的复杂性O(sqrt(N))。N < 2^32. 因式分解是在单独的通道中从因式分解进行的。

    f4

    包含最多为 的素数表2^16。除以N所有素数，直到sqrt(N). N < 2^32.

    f5

    轮子分解是否简单2, 3, 5, 7, 11, 13。除以N从“轮”到 的所有数字sqrt(N)。N < 2^64.

    N该表显示了分解为两个大致相等的素数的乘积时的最差运行时间：

    营业时间

    • 7

  2. 那么它不会起作用吗？

    #include <stdlib.h>
#include <stdio.h>

typedef struct Item_
{
    unsigned int p, k;
} Item;

Item f[11];

void factors(unsigned int n)
{
    memset(f,0,sizeof(f));
    int idx = 0;
    while(n > 1 && n%2 == 0)
    {
        f[idx].p = 2;
        f[idx].k++;
        n /= 2;
    }
    if (f[idx].p) idx++;

    if (n > 1)
        for(unsigned int i = 3; i*i <= n; i += 2)
        {
            while(n%i == 0)
            {
                f[idx].p = i;
                f[idx].k++;
                n /= i;
            }
            if (f[idx].p) idx++;
        }
    if (n > 1)
    {
        f[idx].p = n;
        f[idx].k = 1;
    }
}

void outpairs(unsigned int N, unsigned int p, int m )
{
    if (f[m].p == 0)
    {
        printf("%u * %u = %u\n",p,N/p,p*(N/p));
        return;
    }
    unsigned int k = 1, i = 0;
    do {
        if (p*k > sqrt(N)) return;
        outpairs(N,p*k,m+1);
        k *= f[m].p;
    } while(++i <= f[m].k);
}

int main()
{
    unsigned int N;
    scanf("%u",&N);
    factors(N);
    outpairs(N,1,0);
}

    的确，在我的情况下，与您的代码不同， a*b 和 b*a 是相同的扩展，并且显示一次。

    • 1

  3. 给你（改变了获取执行时间的方式，因为时钟（）不是很准确）

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#ifndef WIN32
void scanf_s(char * s, int *pInt) { scanf(s, pInt); }
#endif

void main() {
    int userInput;

    scanf_s("%d", &userInput);

    struct timespec begin, end;
    clock_gettime(CLOCK_REALTIME, &begin);


    int counter = 2;
    int max = (int)ceil(sqrt(userInput)) + 1;
    printf("%d %d\n", 1, userInput);
    while (counter < max) {
        if ((userInput % counter) == 0) {
            printf("%d %d\n", counter, userInput/counter);
        }
        counter++;
    }

    clock_gettime(CLOCK_REALTIME, &end);

    long seconds = end.tv_sec - begin.tv_sec;
    long nanoseconds = end.tv_nsec - begin.tv_nsec;
    double elapsed = seconds + nanoseconds*1e-9;

    printf("The above code block was executed in %.5f second(s)\n", elapsed);
    system("PAUSE");
}
    • 0

相关问题