Без рекурсии, дающей ошибку памяти

Question

Я узнал, что memoization лучше подходит для игры с сериями Фибоначчи. Сегодня я написал программу таким образом -

private void printFibonacci(int lengthOfSeries) { 

    int lastNumb = 1; 
    int secondLastNumb = 1; 

    List<Integer> fabArray = new ArrayList<Integer>(); 

    if (lengthOfSeries == 0) { 
     System.out.println("Please enter number to print series."); 

    } else { 

     fabArray.add(secondLastNumb); 
     fabArray.add(lastNumb); 

     while (fabArray.size() < lengthOfSeries) { 

      lastNumb = fabArray.get(fabArray.size() - 1); 
      secondLastNumb = fabArray.get(fabArray.size() - 2); 

      fabArray.add(lastNumb + secondLastNumb); 
     } 
    } 
    System.out.println(fabArray); 
} 

Это прекрасно работает. Но когда входной номер высок (скажем, 100 000 000), его бросание outOfMemoryerror. И его ошибка бросания в строке, где печатает список.

Может кто-нибудь, пожалуйста, дайте какое-нибудь предложение сделать его мощным.

Answer 1

Это рост ArrayList, который вызывает OutOfMemoryError, и вам не нужно либо распечатать список или завершить цикл. У данного кода не возникает проблем с памятью:

private void printFibonacci(int lengthOfSeries) { 

    int lastNumb = 1; 
    int secondLastNumb = 1; 
    int count = 2; 

    if (lengthOfSeries == 0) { 
     System.out.println("Please enter number to print series."); 

    } else { 

     System.out.print("1, 1"); 

     while (count < lengthOfSeries) { 
      int next = lastNumb + secondLastNumb; 
      System.out.print(", " + next); 
      secondLastNumb = lastNumb; 
      lastNumb = next; 
      //Updated 
      count = count+1; 
     } 
     System.out.println(); 
    } 

} 

Answer 2

Это характер такого рода алгоритмов, они очень голодны. Также, используя int/Integer, это очень плохая идея, так как вы быстро исчерпаете емкость Integer (2 * 10^32 -1). Возможно, вы хотите удваивать, но все же есть предел того, как далеко вы можете идти.

Answer 3

100 миллионов Целых занимает около 400 миллионов байт.

Это может быть больше размера вашего куча JVM по умолчанию. Попробуйте добавить ключи командной строки, чтобы выделить больше памяти.

Некоторые указания здесь: http://publib.boulder.ibm.com/infocenter/realtime/v2r0/index.jsp?topic=%2Fcom.ibm.rt.doc.20%2Fdiag%2Fappendixes%2Fdefaults.html

Answer 4

После моего комментария, тривиальная реализация будет:

int[] fabArray = new int[] {1, 1, 0}; 
for (int i = 0; i < lengthOfSeries; i++) { 
    fabArray[2] = fabArray[1] + fabArray[0]; 
    System.out.print(fabArray[0] + ", "); 
    fabArray[0] = fabArray[1]; 
    fabArray[1] = fabArray[2]; 
} 
// End of line 
System.out.println();