#java #algorithm
#java #алгоритм
Вопрос:
Проблема:
Каждый новый член в последовательности Фибоначчи генерируется путем добавления двух предыдущих членов.
Начиная с 1 и 2, первые 10 терминов будут:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...Рассматривая члены в последовательности Фибоначчи, значения которых не превышают четырех миллионов, найдите сумму четных членов.
Мой код: (который работает нормально)
public static void main(String[] agrs){
int prevFirst=0;
int prevSecond=1;
int bound=4_000_000;
int evenSum=0;
boolean exceed=false; //when fib numbers > bound
while(!exceed){
int newFib=prevFirst prevSecond;
prevFirst = prevSecond;
prevSecond = newFib;
if(newFib > bound){
exceed=true;
break;
}
if(newFib % 2 == 0){
evenSum = newFib;
}
}
System.out.println(evenSum);
}
Я ищу более эффективный алгоритм для решения этого вопроса. Какие-нибудь подсказки?
Комментарии:
1. Если у вас есть рабочий код, который вы хотели бы улучшить, рассмотрите возможность публикации / переноса этого в Code Review SE . Некоторые могут счесть общий вопрос «Как я могу это улучшить» слишком широким для переполнения стека.
2.
while(true)Достаточно A, поскольку выbreakвсе равно выходите из цикла.3. @laune: да, но a
breakне рекомендуется. Большинство компиляторов плохо оптимизируют такой код. Например, в цикле компилятор будет учитывать вероятность повторения цикла выше, чем разрыв цикла (поскольку в большинстве случаев цикл повторяется при переборе массивов и т. Д.). Вifинструкции -некоторые компиляторы утверждают, что вероятность выполнения тела выше, чем нет… Это влияет на то, как компиляторы структурируют код, а также на некоторые процессоры.4. @CommuSoft переходы в любой форме чаще всего являются плохим стилем кодирования. Я просто хотел указать, что превышение является излишним.
5. @user262945 после избавления от модуля (путем amp; или путем вычисления 3 чисел на сумму) это слишком просто для современных машин. Я получаю время вычисления 2-3 us, если я увеличу N в 100 раз, я все равно получу то же время (поэтому накладные расходы на измерение времени, системные вызовы и движок C больше, чем само вычисление)… поэтому я не вижу смысла в дальнейшем улучшении (если вы не вычисляете очень большое N, что не относится к проблеме 2). PS Я использую старый 32-разрядный компилятор от Borland / Embarcadero с отключенной оптимизацией для этого!
Ответ №1:
При учете следующих правил:
четный четный = четный
четный нечетный = нечетный
нечетное четное = нечетное
нечетное нечетное = четное
Четность первых чисел Фибоначчи равна:
o o e o o e o o e …
Таким образом, по сути, вам просто нужно выполнить шаги из трех. Что:
(1,1,2)
(3,5,8)
(13,21,34)
Учитывая (a,b,c) это (b c,b 2*c,2*b 3*c) .
Это означает, что нам нужно только сохранить два последних числа и вычислить заданное (a,b) , (a 2*b,2*a 3*b) .
Таким образом (1,2) -> (5,8) -> (21,34) -> ... , и всегда возвращайте последнее.
Это будет работать быстрее, чем подход с «фильтром», потому что в нем используется оператор if, который сокращает конвейерную обработку.
Результирующий код:
int b = 1;
int c = 2, d;
long sum = 0;
while(c < 4000000) {
sum = c;
d = b (c<<0x01);
c = d b c;
b = d;
}
System.out.println(sum);
Или jdoodle (с бенчмаркингом, занимает 5 микросекунд при холодном запуске и в среднем 50 наносекунд, исходя из среднего значения 1M раз). Конечно, количество инструкций в цикле больше. Но цикл повторяется в трети случаев.
Комментарии:
1. «Это будет работать быстрее, чем подход «фильтра», потому что в нем используется оператор if, который сокращает конвейерную обработку» ? вам все равно придется вычислять a, b, c на каждой итерации, чтобы иметь возможность вычислять следующую итерацию. как это более эффективно?
2. Ну, оператор if нарушит конвейер в процессоре. В большинстве случаев процессор имеет конвейер длиной шесть. Как следствие, пропускная способность будет уменьшена с помощью оператора
if— . Вот почему, например, графические программы пытаются решить многие вещи с помощью битовых манипуляций вместо использованияifоператоров. За исключением интерпретируемых языков,if-инструкции выполняются медленно по сравнению с другими инструкциями.3. 1 — Мне нравятся небольшие математические рассуждения, прежде чем просто штамповать код 😉
4. @laune Обычно так работает Project Euler; особенно когда вы начинаете переходить на более высокие уровни
5. ну, вы получите от меня 1, потому что вы сохранили проверку по модулю!
Ответ №2:
Вы не можете улучшить его намного больше, любое улучшение, которое вы сделаете, будет незначительным, а также зависит от ОС, на которой вы работаете.
Пример:
Запуск вашего кода в цикле 1 м раз на моем Mac тоже 73-75 мс (запускал его несколько раз).
Изменение условия:
if(newFib % 2 == 0){
Для:
if((newFib amp; 1) == 0){
и, запустив его снова несколько раз, я получил 51-54 мс.
- Если вы запустите то же самое на другой ОС, вы можете (и, вероятно, получите) разные результаты.
- даже если мы рассмотрим вышеизложенное как улучшение, разделите ~ 20 мс на 1 м, и «улучшение», которое вы получите за один запуск, не имеет смысла (~ 20 нанометров).
Ответ №3:
предполагая последовательные числа Фибоначчи
a, b,
c = a b,
d = a 2b,
e = 2a 3b,
f = 3a 5b,
g = 5a 8b = a 4(a 2b) = a 4d,
казалось бы, более эффективно использовать
ef 0 = 0, ef 1 = 2, ef n = ef n-2 4 ef n-1
Комментарии:
1. Умно, очень умно! : D
Ответ №4:
как я упоминал в своем комментарии, на самом деле нет необходимости в дальнейшем улучшении. Я провел некоторые измерения
- зацикливается на 1000000 раз все это
- измерьте время в [мс]
- мс / 1000000 = ns
-
итак, время одного прохода [ns] таково:
- [176 ns] — использует, что четные числа — каждое третье
- [179 ns] — amp;1 вместо %2
- [169 ns] — amp;1 вместо %2 и устраняется, если с помощью -,^,amp;
[edit1] новый код - [105 ns] — использование того, что четные числа являются каждой третьей производной двойной итерацией fibonaci [edit2] новый код
- [76 ns] — уменьшенное количество операндов для снижения накладных расходов и разгрома кучи
-
последний явно выигрывает на моей машине (хотя я ожидаю, что первый будет лучшим)
- все было протестировано на Win7 x64 AMD A8-5500 3.2GHz
-
Приложение без потоков 32-разрядный компилятор BDS2006 Trubo C
-
1,2 уже упоминаются в ответах здесь, поэтому я комментирую только 3:
s =aamp;(-((a^1)amp;1)); -
(a ^ 1) отрицает бит лавеста
- ((a ^ 1)amp; 1) равно 1 для четных и 0 для нечетных a
- -((a ^ 1) amp; 1)) равно -1 для четных и 0 для нечетных a
- -1 равно 0xFFFFFFFF, поэтому число по нему не изменит его
- 0 равно 0x00000000, поэтому число по нему будет равно 0
- следовательно, нет необходимости в if
- также вместо xor (^) вы можете использовать отрицание (!), Но это намного медленнее на моей машине
Хорошо, вот код (не читайте дальше, если вы хотите закодировать его самостоятельно):
//---------------------------------------------------------------------------
int euler002()
{
// Each new term in the Fibonacci sequence is generated by adding the previous two terms.
// By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
int a,a0=0,a1=1,s=0,N=4000000;
/*
//1. [176 ns]
a=a0 a1; a0=a1; a1=a; // odd
a=a0 a1; a0=a1; a1=a; // even
for (;a<N;)
{
s =a;
a=a0 a1; a0=a1; a1=a; // odd
a=a0 a1; a0=a1; a1=a; // odd
a=a0 a1; a0=a1; a1=a; // even
}
//2. [179 ns]
for (;;)
{
a=a0 a1; a0=a1; a1=a;
if (a>=N) break;
if ((aamp;1)==0) s =a;
}
//3. [169 ns]
for (;;)
{
a=a0 a1; a0=a1; a1=a;
if (a>=N) break;
s =aamp;(-((a^1)amp;1));
}
//4. [105 ns] // [edit1]
a0 =a1; a1 =a0; a=a1; // 2x
for (;a<N;)
{
s =a; a0 =a1; a1 =a0; // 2x
a=a0 a1; a0=a1; a1=a; // 1x
}
*/
//5. [76 ns] //[ edit2]
a0 =a1; a1 =a0; // 2x
for (;a1<N;)
{
s =a1; a0 =a1; a1 =a0; // 2x
a=a0; a0=a1; a1 =a; // 1x
}
return s;
}
//---------------------------------------------------------------------------
[edit1] добавление более быстрого кода
- CommuSoft предложила повторять более 1 числа за итерацию fibonaci, чтобы минимизировать операции.
- хорошая идея, но код в его комментарии не дает правильных ответов
- Я немного изменил свой, так что вот результат:
- [105 ns] — использует, что четные числа являются каждой третьей производной двойной итерацией fibonaci
- это почти в два раза быстрее, чем 1. из которого он получен
- найдите [edit1] в коде или найдите //4 .
[edit2] добавление еще более быстрого кода — просто измените порядок некоторых переменных и операций для увеличения скорости — [76 нс] уменьшенное количество операндов для снижения накладных расходов и кучи
Комментарии:
1. Я определенно согласен, что эта проблема слишком проста для современных машин, но вопрос интересен, чтобы узнать, как оптимизировать код. 🙂
2. @CommuSoft да, но Project Euler делает это постепенно, там возникает много проблем не один раз, но с гораздо большей полезной нагрузкой и, как правило, после того, как все требуемые методы представлены в предыдущих задачах. Я прекращаю оптимизацию, если решение выполняется быстрее или около 1 мс во время выполнения. Итак, я хочу сказать, что не тратьте время на ненужную оптимизацию, для этого будет гораздо больше времени в будущих задачах, где без оптимизации код не будет работать за «конечное» время…
3. Что происходит, когда вы заменяете девять инструкций в случае один на
a=a0 (a1<<0x01); a1 = a a0; a0 = a;? Можно было бы ожидать, что количество примитивных инструкций в цикле будет уменьшено.4. @CommuSoft возможно, ваш способ может быть быстрее (если вы хотите сделать это в коде 1.) был слишком ленив, чтобы оценить это уравнение. Кстати, как вы получили форматирование кода в комментарии?
5. @CommuSoft после небольшой настройки, я думаю
[edit2], является окончательным. [76 ns] время выполнения.
Ответ №5:
если вы проверите ряд Фибоначчи, для четных чисел 2 8 34 144 610 вы можете увидеть, что существует фантастическая связь между четными числами, например:
34 = 4*8 2,
144 = 34*4 8,
610 = 144*4 34;
это означает, что следующий четный в Фибоначчи может быть выражен следующим образом
Even(n)=4*Even(n-1) E(n-2);
в Java
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0 ){
long n = in.nextLong();
long a=2;
long b=8;
long c=0;
long sum=10;
while(b<n)
{
sum =c;
c=b*4 a;
a=b;
b=c;
}
System.out.println(sum);
}
}
Ответ №6:
F (n) — n-е число Фибоначчи, т.е. F (n) = F (n-1) F (n-2)
Допустим, что F (n) четно, тогда
F (n) = F (n-1) F (n-2) =F(n-2) F (n-3) F (n-2)
F (n) = 2F (n-2) F (n-3)
— это доказывает, что каждый третий член четный (если F (n-3) четный,тогда F(n) тоже должно быть четным)
F(n) = 2[F (n-3) F (n-4)] F(n-3)
= 3F (n-3) 2F (n-4)
= 3F (n-3) 2F (n-5) 2F (n-6)
Из уравнения 1:
F(n-3) = 2F(n-5) F (n-6)
2F(n-5) = F (n-3) — F (n-6)
F(n) = 3F(n-3) [F(n-3) — F (n-6)] 2F(n-6)
= 4F (n-3) F(n-6)
Если последовательность четных чисел состоит из каждого третьего числа (n, n-3, n-6, …)
Четная последовательность Фибоначчи:
E (k) = 4E (k-1) E (k-2)
Последовательность Фибоначчи F= {0,1,1,2,3,5,8…..}
Четная последовательность Фибоначчи E={0,2,8,…..}
код:
public static long findEvenFibSum(long n){
long term1=0;
long term2=2;
long curr=0;
long sum=term1 term2;
while((curr=(4*term2 term1))<=n){
sum =curr;
term1=term2;
term2=curr;
}
return sum;
}
Комментарии:
1. (с опозданием почти на два года)
2. @greybeard разве это не поможет другим пользователям??
3. Поздно представлять эту последовательность без четных элементов — на мой взгляд, полезные ответы никогда не опаздывают. Если вы не думаете, что это портит удовольствие, разработайте последовательность, дающую результат напрямую.
Ответ №7:
Ответ на проблему project Euler 2 (на Java):
int x = 0;
int y = 1;
int z = x y;
int sumeven = 0;
while(z < 4000000){
x = y;
y = z;
z = x y;
if(z % 2 == 0){
sumeven = z; /// OR sumeven = sumeven z
}
}
System.out.printf("sum of the even-valued terms: %d n", sumeven);
Это самый простой ответ.
Комментарии:
1. Если это самое простое решение проблемы Project Euler # 2, как оно отвечает
More efficient solution?