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

Question

Я снова получаю удовольствие от испытаний 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 - не намного быстрее, чем другой метод, но еще не оптимизирован. Это работает, однако.

Answer 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 можетбыть решена с помощью простого применения сита Eratosthenes .Заполните массив логических значений (т. Е. Битовый вектор) размером 2000000 так, чтобы sieve[i]==true, если i было простым числом;затем суммируйте числа, для которых sieve[i]==true.

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

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

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

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

Answer 2

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

1. используйте формулу суммирования для суммы (1 ... n)
2. найдите простые множители с помощью методов, описанных в задаче 7, а задача 10
3. определяет, сколько делителей n имеет на основе своей простой факторизации *

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

Answer 3

Рассматривали ли вы разбиение на основные факторы и отслеживание простых чисел, чтобы вам не приходилось пересчитывать их?