Возможная оптимизация в моем коде?

Question

Чтобы решить проблему Проекта Эйлера № 5 , я написал следующую программу:

class p5
{
    const int maxNumber = 20;
    static void Main(string[] args)
    {
        Job(); // First warm-up call to avoid Jit latency

        var sw = Stopwatch.StartNew();
        var result = Job();
        sw.Stop();

        Debug.Assert(result == 232792560);
        Console.WriteLine(result);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }

    private static int Job()
    {
        var result = Enumerable.Range(1, int.MaxValue - 1)
            .Where(
                n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
            ).First();
        return result;
    }
}

Однако я обнаружил, что это немного долго (17 секунд, врежим релиза), даже если он работает.

Есть ли какая-либо возможная оптимизация?

К вашему сведению, я пробовал с помощью метода AsParallel, но, как и ожидалось, кусок работ слишком мал ипереключение контекста было тяжелее преимуществ (более 1 минуты):

    var result = Enumerable.Range(1, int.MaxValue - 1).AsParallel()
        .Where(
            n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
        ).First();
    return result;

[Редактировать] Согласно предложению Мартина, эта версия делится на 10 времени:

    private static int Job()
    {
        var n =2;
        bool result;
        do
        {
            result = true;
            for (int c = maxNumber / 2; c <= maxNumber; c++)
            {
                if (n % c > 0)
                {
                    result = false;
                    break;
                }
            }
            n ++;//= 2;
        } while (!result);
        return n;
    }

[Edit] Подводя итог всем моим тестам, приблизительное время выполнения:

• Моя первая реализация: 20 секунд
• Удален внутренний вызов enumerable.Range (заменен напросто для цикла): 3 секунды
• Удалены внешние и внутренние перечислимые. Вызов диапазона: 1,5 секунды
• Только взятие четных чисел: (только с циклами, без перечисления. Диапазон): меньше 1second
• Использование евклидовых алгоритмов Gcd / LCm в соответствии с предложением drhirsch: 0,004 мс

Последнее предложение, безусловно, является хорошим ответом.Я благодарю drhirsch за то, что он предложил другой подход вместо простой оптимизации цикла

Answer 1

Хорошая оптимизация - использование лучшего алгоритма.

Это запрашивает наименьшее общее кратное чисел 1..20, которое можно вычислить последовательно, найдя lcm (1,2), затем lcm (lcm (1,2), 3) и т. д. до 20.

Простой алгоритм нахождения lcm делит произведение двух чисел на наибольший общий делитель . gcd может быть найден с помощью хорошо известного евклидова алгоритма за очень короткое время.

#include <iostream>

long gcd(long a, long b) {
    if (!b) return a;
    return gcd(b, a-b*(a/b));
}

long lcm(long a, long b) {
    return (a*b)/gcd(a, b);
}

int main(int argc, char** argv) {
    long x = 1;
    for (long i=2; i<20; ++i) 
        x = lcm(x, i);
    std::cout << x << std::endl;
}

Это мгновенно выплевывает решение.

Answer 2

Ну, во-первых, вам нужно только проверить четные числа, поэтому начните с 0 и увеличьте до 2. это связано с тем, что четное число никогда не будет равномерно делиться на нечетное число. Вы также можете начать поиск с факториала 10, так 10 * 9 * 8 * 7 .. и так далее, так что другие слова начинаются с 10! что составляет 3 628 800 . это может помочь запустить его быстрее. Кроме того, в среднем моя скорость на C составляла 10 секунд, так что код на самом деле в порядке.

Answer 3

Использование Enumerable является медленным (см. this для сравнения Enumerable.Repeat и цикла for для инициализации массива).Попробуйте выполнить простой цикл while / for следующим образом:

        int maxNumber = 21;
        int n = 1;
        bool found = false;
        while(!found)
        {
            found = true;
            for(int i = 1; i < maxNumber; i++)
            {
                if(n % i != 0)
                {
                    found = false;
                    break;
                }
            }
            n++;
        }
        return n-1;

Это выполняется в течение 4 секунд на моем компьютере при отладке.

EDIT

При рассмотрении дальнейшей оптимизации этоЛучше начать тестирование по модулю больших чисел, поэтому, когда я изменил цикл for на:

for (int i = maxNumber; i > 1; i--)

, время сократилось до 2 секунд.

Математическое понимание состоит в том, что мы имеем толькопроверить делимость на числа, которые не кратны числам, которые мы уже тестировали.В нашем случае мы можем написать:

    private int[] p = { 19, 17, 16, 13, 11, 9, 7, 5, 4, 3, 2 };
    int Job()
    {
        int n = 1;
        bool found = false;
        while (!found)
        {
            found = true;
            foreach (int i in p)
            {
                if (n % i != 0)
                {
                    found = false;
                    break;
                }
            }
            n++;
        }
        return n - 1;
    }

Однако на самом деле это медленнее, около 2,5 секунд.