Огромная разница в производительности, когда параметр функции изменил типы с int на unsigned - PullRequest
Новая
       45

Огромная разница в производительности, когда параметр функции изменил типы с int на unsigned

0 голосов
/ 03 октября 2019

У меня есть функция, которая должна суммировать все натуральные числа, делимые на 3 и 5. Я не хотел соглашаться на самое очевидное решение и пытался придумать что-то, что работает лучше, чем просто одноцикл с оператором if.

Я придумал функцию ниже. Сначала был только один параметр, limit, но затем я хотел попытаться распределить вычисления по нескольким потокам, поэтому я ввел второй параметр по умолчанию, lowerLimit. Если я запускаю и тестирую следующий код с лимитом 99999999999999 (leftLimit left со значением по умолчанию), программа занимает около 3,5 секунд. Однако , когда я изменил тип с int на unsigned, запуск кода занял так много времени, что я решил остановить его и не ждать вывода. Откуда эта разница?

TLDR: Почему следующий код занимает больше времени для запуска, когда тип lowerLimit меняется с int на unsigned? 

unsigned long sumNaturalNumbersDivisibleBy3And5UpToNumber(unsigned long limit, int lowerLimit = 0)
{
    unsigned long sum = 0;
    for (auto threes = lowerLimit + 3; threes <= limit; threes += 3)
    {
        sum += threes;
    }
    for (auto fives = lowerLimit + 5; fives <= limit; fives += 5)
    {
        sum += fives;
    }
    for (auto fifteens = lowerLimit + 15; fifteens <= limit; fifteens += 15)
    {
        sum -= fifteens;
    }
    return sum;
}

ОБНОВЛЕНИЕ: Как предположил PaulMcKenzie, вероятно, существует ошибка переполнения при назначении значений по трем, пятеркам и пятнадцати. Я до сих пор не уверен, почему это приведет к разрыву в производительности.

Ответы [ 2 ]

1 голос
/ 04 октября 2019

У меня есть функция, которая должна суммировать все натуральные числа, делимые на 3 и 5. Я не хотел соглашаться на самое очевидное решение и пытался придумать что-то, что работает лучше, чем простоодиночный цикл for с оператором if.

Это даже не близко к быстрому.

"Fast" будет выглядеть примерно так: 

int thingy1[] = 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6;

int thingy2[] = 0, 0, 0, 3, 3, 3+5, 3+5+6, 3+5+6, 3+5+6, 3+5+6+9, 3+5+6+9+10, 3+5+6+9+10, 3+5+6+9+10+12, 3+5+6+9+10+12, 3+5+6+9+10+12;

unsigned long getSumOfNaturalNumbersDivisibleBy3Or5UpToNumber(unsigned long limit) {
    unsigned long sum = 0;
    unsigned long i;

    for(i = 0; i < limit/15; i++) {
        sum += i*15*7 + 3+5+6+9+10+12+15;
    }
    return sum + (limit/15) * thingy1[limit % 15] * 15 + thingy2[limit % 15];
}


unsigned long getCountOfNaturalNumbersDivisibleBy3Or5UpToNumber(unsigned long limit) {
    return (limit / 15) * 7 + thingy1[limit % 15];
}
1 голос
/ 04 октября 2019

Если ваша версия с int lowerLimit фактически заканчивается, это потому, что она переполняется, и то, что происходит, является неопределенным поведением (для целых чисел со знаком). С таким же успехом он может обернуться вокруг 2^31-1 до -2^31 и продолжить цикл навсегда - или сделать что-то совершенно другое (посмотрите « носовые демоны »).

Если вы попытаетесьэто внутри вашей int lowerLimit версии: 

auto threes = lowerLimit + 3;
for(; threes <= limit; threes += 3) {
    sum += threes;
}
std::cout << threes << " " << limit << "\n";

Один возможный вывод, если вам случится скомпилировать с опцией g++ -fsanitize=undefined:

runtime error: signed integer overflow: 2147483646 + 3 cannot be represented in type 'int'
-2147483647 99999999999999

Он фактически завершил цикл с threes, являющимся отрицательным числом, которое, конечно, меньше, чем limit. Это выглядит невозможным, но компилятор может делать все, что захочет - поведение не определено. Это носовой демон своего рода.

Если I скомпилировать то же самое без -fsanitize=undefined - он будет работать вечно. Это все еще неопределенное поведение, так что это может не произойти для вас.

Если вы переключитесь на unsigned int, то, что происходит в 2^32-1, на самом деле хорошо определено. Для 32-битного unsigned int результата 2^32-1 + 1 == 0.

Такая программа должна выполняться вечно (поскольку threes никогда не достигнет 99999999999999), пока она имеет некоторыепобочные эффекты. Бесконечный цикл без побочных эффектов также имеет неопределенное поведение - поэтому, даже если каждая отдельная операция в функции имеет определенное поведение, реализация, способная понять, что цикл бесконечный и не имеет побочных эффектов, может привести к чему-либо.

Решение состоит в том, чтобы использовать тот же тип для threes, fives и fifteens, что и limit - но с limit, установленным на 99999999999999, будьте готовы ждать действительно действительнодолгое время.

...