Как сделать код максимально быстрым?

Question

есть у меня код на си который раскладывает число на множители в пары(перебором). Какие есть способы ускорить код пускай и на 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");
}

Answer 1

Что можно улучшить:

Функция clock имеет очень низкое разрешение, кажется 16ms. Это слишком грубо для вашей задачи.
Внутренний цикл лишний. Во внешнем цикле делите число на первый делитель, если остаток нулевой, вы нашли пару делителей.
Поиск делителей логично начинать от меньших к большим. Первый делитель ищите в диапазоне [1, sqrt(N)].
Найдя один делитель можно искать следующие пары делителей не для исходного числа, а для числа уже разделённого. Это сильно ускорит процесс, хотя пары делителей для оригинального числа надо будет восстанавливать.
Обычно делители не ищут парами. Число разлагают на простые: факторизация целых чисел. Затем из простых можно сконструировать все нужные пары. Это самый быстрый способ.

Примеры

f1

Оригинальная программа videx. Работает медленно, так как проверяет все пары чисел до N (число, которое факторизуем). Сложность O(N^2). Почти все пары печатаются два раза. Если N > 46340 (= sqrt(2^31)) из-за переполнения ошибается.

f2

Предложена user419509. Делит N на все числа до sqrt(N). Сложность O(sqrt(N)). N < 2^31.

f3

Предложена Harry. Делит N на все нечетные числа до sqrt(N). Если делитель найден, то сокращает на него N и продолжает поиск. Сложность в худшем случае O(sqrt(N)). N < 2^32. Разложения на множители делаются из факторизации отдельным проходом.

f4

Содержит таблицу простых чисел до 2^16. Делит N на все простые числа до sqrt(N). N < 2^32.

f5

Делает wheel factorization для простых 2, 3, 5, 7, 11, 13. Делит N на все числа из "колеса" до sqrt(N). N < 2^64.

В таблице приведены худшие времена работы, когда N разлагается в произведение двух примерно равных простых чисел:

Answer 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 - одинаковые разложения, и выводятся один раз.

Answer 3

Вот держи (изменил способ получения времени выполнения так как clock() не очень точен)

#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");
}

БЛОГ НА HUSL

Как сделать код максимально быстрым?

Ответы (3 шт):

Примеры