Есть ли еще место для оптимизации в этой части кода?

Question

void HappyTest()
{
    for (int i = 0; i < 2100000000; i++) {
        int n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 10 ? m % 10 : m;
                sum += t * t;
                m /= 10;
            }
            n = sum;
        }
        //return n == 1 || n == 7;
        //if (i % 10000000 == 0) {
        //  cout << i << endl;
    }
}

VS2017 Режим отладки Анализатор производительности

Я использовал инструмент анализа производительности vs2017, чтобы получить данные на рисунке, и обнаружил, что потребление производительности в основном составляет% и * операции. Есть ли место для оптимизации в этой части кода?

Answer 1

Да, есть место для большей эффективности, но я не уверен, что на самом деле делает код, потому что он не ищет повторяющиеся циклы, найденные с счастливыми числами. Тем не менее:

• Избавьтесь от ненужного int m

• Вы избежали m % 10 модуля для значений <10 <strong>, но не m / 10 деление. Последняя цифра может быть вычислена вне цикла

• Используйте кеш: вы будете проверять одни и те же значения снова и снова внутри цикла (см. Ниже).

Модифицированный код, хотя он не был понятен из-за отсутствующей скобки и комментария кода

void HappyTest(void)
{
    for (int i = 0; i < 2100000000; i++) {
        int n = i;
        while (n >= 10) {
            int sum = 0;
            while (n >= 10) {       // while(m != 0)
                int t = n % 10;
                n /= 10;
                sum += t * t;
            }
            sum += n * n;           // final digit moved out of loop
            n = sum;
        }
        if(n == 1 || n == 7) {
            printf("%d\n", i);
        }
    }
}

---

Возвращаясь к идее кеша. Обратите внимание, что при первом разборе 10-значного числа сумма квадратов его цифр не может быть больше, чем 9 * 9 * 10 = 810 (на самом деле меньше, для 32-битного int), который возвращается во второй разбор. Таким образом, первые 810 числа могут обрабатываться по-разному - их результат сохраняется в массиве. Из оставшихся чисел требуется только один разбор цифр, после чего можно посмотреть результат.

#define LIMIT       2100000000
#define CACHE_SZ    810

void HappyTest(void)
{
    char cached[CACHE_SZ] = { 0 };

    // the first part also sets up the cache
    for (int i = 0; i < CACHE_SZ; i++) {
        int n = i;
        while (n >= 10) {
            int sum = 0;
            while (n >= 10) {       // while(m != 0)
                int t = n % 10;
                n /= 10;
                sum += t * t;
            }
            sum += n * n;           // final digit moved out of loop
            n = sum;
        }
        if(n == 1 || n == 7) {
            //printf("%d\n", i);
            cached[i] = 1;
            results++;
        }
    }

    // the second part continues more simply
    for (int i = CACHE_SZ; i < LIMIT; i++) {
        int n = i;
        int sum = 0;
        // only one parse of the number
        while (n >= 10) { 
            int t = n % 10;
            n /= 10;
            sum += t * t;
        }
        sum += n * n;
        // then look it up
        if(cached[sum]) {
            //printf("%d\n", i);
            results++;
        }
    }
}

Это выполняется примерно в 1/3 времени, которое занимает ваша функция (оба без printf).

Answer 2

Давайте начнем с небольшой переписки вашего кода, например:

int HappyTest()
{
    int n;
    for (int i = 0; i < 210000000; i++) {  // Reduced by a factor 10 compared to OP code
        n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 10 ? m % 10 : m;
                sum += t * t;
                m /= 10;
            }
            n = sum;
        }
    }
    return n;
}

int main(void) {
  printf("%d\n", HappyTest());
}

Выполнение этого в моей системе занимает 10,7 секунды.

Ваш код примерно такой: возьмите число и вычислитесумма всех его цифр в квадрате.

Таким образом, ваши умножения ограничены 10 различными умножениями, т. Е. 0 * 0, 1 * 1, ..., 9 * 9

Таким образом, одной из идей оптимизации может быть помещение результатов втаблицу и сделать поиск таблицы вместо умножения.Например:

int mul_tab_10[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};

int HappyTest()
{
    int n;
    for (int i = 0; i < 210000000; i++) {
        n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 10 ? m % 10 : m;
                sum += mul_tab_10[t];
                m /= 10;
            }
            n = sum;
        }
    }
    return n;
}

Выполнение этого в моей системе занимает 12,9 секунды.Так что это медленнее .

Но что, если мы сделаем этот шаг еще дальше?Вместо того, чтобы просто использовать таблицу с 10 элементами, мы могли бы использовать таблицу с 100 элементами.Как:

int mul_tab_100[100] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 4, 5, 8, 13, 20, 29, 40, 53, 68, 85, 9, 10, 13, 18, 25, 34, 45, 58, 73, 90, 16, 17, 20, 25, 32, 41, 52, 65, 80, 97, 25, 26, 29, 34, 41, 50, 61, 74, 89, 106, 36, 37, 40, 45, 52, 61, 72, 85, 100, 117, 49, 50, 53, 58, 65, 74, 85, 98, 113, 130, 64, 65, 68, 73, 80, 89, 100, 113, 128, 145, 81, 82, 85, 90, 97, 106, 117, 130, 145, 162};

int HappyTest()
{
    int n;
    for (int i = 0; i < 210000000; i++) {
        n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 100 ? m % 100 : m;  // Notice this change
                sum += mul_tab_100[t];
                m /= 100;                        // Notice this change
            }
            n = sum;
        }
    }
    return n;
}

Выполнение этого в моей системе занимает 6,9 секунды.Таким образом, производительность улучшена .

Если сделать еще один шаг вперед (т. Е. 1000 элементов), результат составит 5,3 секунды - опять же улучшение .

Такда, вы можете улучшить производительность во время выполнения.