Нужна помощь в оптимизации решения проблемы 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 - не намного быстрее, чем другой метод, но пока не оптимизирован. Он работает, однако.
Ответы
Ответ 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 основано на его простой факторизации *
* Рассматривайте это как вероятный вопрос, если вы не знаете "правило". Например, у вас есть четыре аромата, которые вы можете добавить к своему кофе, сколько у вас вариантов?
