Подтвердить что ты не робот

Нужна помощь в оптимизации решения проблемы Project Euler №12

Я снова развлекаюсь с проблемами Project Euler, и я заметил, что мое решение для числа 12 является одним из моих самых медленных в ~593.275 ms за прохождение. Это второе решение для числа 10 при ~1254.593 ms за прохождение. Все мои другие ответы занимают меньше 3 ms, чтобы работать с наилучшим образом в 1 ms.

Мое решение Java для Проблема 12:

Основной():

int index = 1;
long currTriangleNum = 1;

while (numDivisors(currTriangleNum) <= 500) {
    index++;
    currTriangleNum += index;
}

System.out.println(currTriangleNum);

numDivisors():

public static int numDivisors(long num) {  
    int numTotal = 0;

    if (num > 1)
        if (num % 2 == 0) {
            for (long i = 1; i * i <= num; i++)
                if (num % i == 0)
                    numTotal+=2;
        } else {
            // halves the time for odd numbers
            for (long i = 1; i * i <= num; i+=2)
                if (num % i == 0)
                    numTotal+=2;
    }
    else if (num == 0)
        return 0;
    else if (num == 1)
        return 1;
    else (num < 0)
        return numDivisors(num *= -1);

    return numTotal;
 }

.

Оглядываясь на форум решений, некоторые люди обнаружили, что эти формулы (n = (p ^ a) (q ^ b) (r ^ c)... и d (n) = (a + 1) (b + 1) (c + 1)...) работал для них, но лично я не вижу, как это будет быстрее; возможно, быстрее, но не в программе.

.

Основной мыслительный процесс выглядит следующим образом:

Мы хотим рассчитать число делителей в 48. Посмотрев на дерево факторов ниже, мы можем заключить, что 48 = (2^4)(3^1) [n = (p ^ a) (q ^ b) (r ^ c)... ].

  48
 /  \
2   24
   /  \
  2   12
     /  \
    2   06
       /  \
      2    3

Зная это, мы строим формулу d(48) = (4+1)(1+1) [d (n) = (a + 1) (b + 1) (c + 1)...], чтобы определить, что 48 имеет 10 факторов.

d(n)  = (a+1)(b+1)(c+1)...
d(48) = (4+1)(1+1)
d(48) = (5)(2)
d(48) = 10

.

Как я могу оптимизировать свой код? Являются ли эти формулы лучшим решением? Я считаю, что найти все основные факторы, а затем реализовать формулы займет больше времени, чем программа, которую я уже имел.

Большое спасибо,

Жюстьян

EDIT:

Прежде чем кто-нибудь начнет размещать ссылки, я просмотрел похожие вопросы в SO без везения - я просто не могу придумать реализации своих методов, которые будут работать быстрее, чем то, что у меня уже есть.

EDIT2:

Моя вторая попытка на сите Эратосфена (для задачи 10):

int p = 3, n = 2000000;
long total = 0;
boolean[] sieve = new boolean[n];

for (int i = 3; i < n; i += 2)
    sieve[i] = true;

sieve[2] = true;

while (p * p < n) {
    for (int i = p; i < n; i++)
        if (sieve[i] && (i % p) == 0)
            sieve[i] = false;
    p++;

    while (!sieve[p])
        p++;
}

for (int i = 0; i < n; i++)
    if (sieve[i])
        total += i;

System.out.println(total);

Работает в ~985.399 ms - не намного быстрее, чем другой метод, но пока не оптимизирован. Он работает, однако.

4b9b3361

ОТВЕТЫ

Ответ 1

Используйте базовую математическую структуру, это значительно изменит время работы вашей программы. Кстати, это относится и к проблеме 10; если вы не можете сделать это за несколько миллисекунд, вы использовали широкомасштабный неэффективный алгоритм. На самом деле, я советую вам сначала работать над проблемой 10, потому что на ней строится проблема 12.

Я собираюсь дать лучший алгоритм для проблемы 12 ниже, но сначала это замечание, которое должно значительно ускорить вашу программу. Если два числа x и y взаимно простые (т.е. Они не имеют общего делителя, отличного от 1), то d (x · y) = d (x) · d (y). В частности, для треугольного числа d (n · (n + 1)) = d (n) · d (n + 1). Поэтому вместо повторения по номерам треугольников n · (n + 1), итерация по n: это значительно уменьшит размер аргументов, переданных в d (n).

Если вы выполните эту оптимизацию, вы заметите, что вы вычисляете d (n) дважды в строке (один раз как d ((n-1) +1) и один раз в качестве d (n)). Это говорит о том, что кэширование результата d является хорошей идеей. Алгоритм ниже делает это, но также вычисляет d снизу вверх, а не сверху вниз, что более эффективно, потому что умножение происходит намного быстрее, чем факторинг.

Проблема 10 может быть решена простым применением сита Эратосфен. Заполните массив логических элементов (например, бит-вектора) размером 2000000, так что sieve[i]==true, если i является простым; затем суммируем числа, для которых sieve[i]==true.

Проблема 12 может быть решена путем обобщения решета Эратосфена. Вместо того, чтобы сделать sieve[i] логическим, указывающим, является ли i простым, сделайте его числом, указывающим количество способов, в которых оно не является простым, т.е. Число делителей i. Для этого легко изменить основное сито Eratosthenes: вместо того, чтобы установить sieve[x*y] в false, добавьте 1 к нему.

Несколько последующих проблем проекта Эйлера пользуются аналогичным подходом.

Одна из проблем, которые могут возникнуть, заключается в том, что в задаче 12 неясно, когда прекратить вычислять сито. Вы можете пойти двумя способами:
1. вычислить сито по кускам по требованию, само стоящее программирование (это потребует более сложного кода, второго метода)
2. или начните с переоценки привязки: найдите номер треугольника, который содержит более 500 делителей, вы знаете, что остановитесь до или после этого номера.

Вы можете получить больше времени, если поймете, что вам нужно только заботиться о нечетных числах, так как d (2 ^ k · n) = (k + 1) · d (n), если n нечетно, и нахождение k и n задано только (2 ^ k · n) быстро на двоичном компьютере. Я оставлю детали этой оптимизации в качестве упражнения.

Ответ 2

Рассматривали ли вы нарушение основных факторов и отслеживание простых чисел, поэтому вам не нужно их пересчитывать?

Ответ 3

Я сделал это некоторое время назад, поэтому не помню всех оптимизаций, вот некоторые из них:

  • использовать формулу суммирования для суммы (1... n)
  • найти основные факторы с методами описанные в задаче 7 и проблема 10
  • определить, сколько дивизоров n основано на его простой факторизации *

* Рассматривайте это как вероятный вопрос, если вы не знаете "правило". Например, у вас есть четыре аромата, которые вы можете добавить к своему кофе, сколько у вас вариантов?