Независимо от того, какой язык программирования вы изучаете, вычисление чисел Фибоначчи слишком классическое, чтобы его пропустить. Это кажется очень простым в реализации, но также может быть достаточно глубоким, чтобы его можно было догнать, особенно когда число очень велико. Думал ли ты об этом раньше?
Это может быть очень легко реализовать с помощью рекурсии всего в одной строке кода, даже с использованием Java.
|
1
2
3
|
int fib(int n) { return n <= 2 ? 1 : (fib(n - 1) + fib(n - 2));} |
И чтобы вы поняли основную идею оптимизации, механизм монетизации будет введен с помощью целочисленного массива или HashMap, но идея та же: рассчитать один раз и только один раз, чтобы эти бедные кролики чувствовали жизнь намного проще.
Добавьте еще одну строку кода, и благодаря функции Lambdas, предоставленной начиная с JDK8, жизнь стала намного проще в наши дни.
|
1
2
3
4
5
|
private static Map<Integer, Integer> CACHE = new HashMap<>();int fib(int n) { return CACHE.computeIfAbsent(n, k -> (k <= 2 ? 1 : (fib(k - 1) + fib(k - 2))));} |
Всегда есть кто-то, кто боится знаменитой ошибки StackOverflowError, и он скажет вам не использовать рекурсию, а делать итеративный способ, например так:
|
01
02
03
04
05
06
07
08
09
10
|
int fib(int n) { if (n <= 2) return 1; int[] cache = new int[n]; cache[0] = cache[1] = 1; for (int i = 2; i < n; i++) { cache[i] = cache[i - 1] + cache[i - 2]; } return cache[n - 1];} |
Очевидно, что целочисленного массива можно избежать, вы можете просто сохранить три значения и обновить их до конца, но это не та проблема, которую мы хотим обсудить здесь. Вы, вероятно, обнаружили бы, что результат очень легко может быть намного больше, чем верхний предел int, long, double. Например, если мы введем n как 2048, каков будет точный результат?
|
1
|
454153044374378942504557144629068920270090826129364442895118239027897145250928343568434971 803477173043320774207501029966396250064078380187973638077418159157949680694899576625922604 895968605634843621876639428348247300097930657521757592440815188064651826480022197557589955 655164820646173515138267042115173436029259905997102292769397103720814141099147144935820441 85153918055170241694035610145547104337536614028338983073680262684101 |
Сейчас 4,54 * 10 ^ 427. Что касается Java, для такого рода проблем у вас нет другого выбора, кроме BigInteger , и он очень прост в использовании.
|
1
2
3
4
5
|
private static Map<Integer, BigInteger> CACHE = new HashMap<>();BigInteger fib(int n) { return CACHE.computeIfAbsent(n, k -> (k <= 2 ? BigInteger.ONE : (fib(k - 1).add(fib(k - 2)))));} |
Поздравляем! Вы получите БОМБУ, взрывающуюся так:
|
1
2
3
|
Exception in thread "main" java.lang.StackOverflowError at java.util.HashMap.hash(HashMap.java:339) at java.util.HashMap.computeIfAbsent(HashMap.java:1099) |
Вы можете использовать -Xss4m чтобы закрыть его, или разрешить его итеративным способом, немного оптимизированным, в котором мы не будем тратить пространство на создание массива. Да, это правильно, рекурсию легко продумать и реализовать, но она слишком близка к StackOverflowError.
|
01
02
03
04
05
06
07
08
09
10
11
12
|
BigInteger fib(int n) { if (n <= 2) return BigInteger.ONE; BigInteger prev = BigInteger.ONE, prevOfPrev = BigInteger.ONE; BigInteger curr = null; for (int i = 2; i < n; i++) { curr = prev.add(prevOfPrev); prevOfPrev = prev; prev = curr; } return curr;} |
BigInteger, в чем секрет того, что он может представлять число за верхним пределом всех примитивных типов данных Java?
Идея все еще проста, но реализация может быть сложной, особенно когда необходима высокая оптимизация. Bigint в Github даст вам больше информации о том, как Тимоти Букту подходит и оптимизирует его.
Есть знаменитая цитата Сэма «Властелин колец»: «Я не могу нести это для тебя, но я могу нести тебя», что касается BigInteger, кажется, это должно быть «Я не могу нести это для тебя, и Я не могу нести тебя, но я могу нести часть вас.
Да, целое число слишком велико, но если мы разделим его на множество частей, то мы обнаружим, что каждая часть может находиться в пределах верхнего предела, если мы сохраним каждую из них в массиве и выполним вычисления на двоичном уровне, а также хорошо обращайтесь с переносящей частью, тогда контейнер для хранения большого количества станет возможным.
Довольно круто и умно, правда? Но что именно находится под капотом? Давайте проверим это в следующем посте.
ПРОДОЛЖЕНИЕ СЛЕДУЕТ
|
Опубликовано на Java Code Geeks с разрешения Натанаэля Янга, партнера нашей программы JCG . Смотреть оригинальную статью здесь: Фибоначчи и BigInteger: секрет под капотом Мнения, высказанные участниками Java Code Geeks, являются их собственными. |