java - java中的内存错误

Question

我正在尝试使用 Java 素数算法进行编码。我试图面对整数和长尺寸的问题。我的简单代码如下，直到达到 n 的限制为止:

public static long f(int n) {
  if (n == 1 || n == 2) 
    return 1;
  else { 
    long value = f(n-2) + f(n-1); 
    return value;
  }
}

如果在我的 main 中我给 50 例如我的代码将被压碎，我猜测是由于结果的大小。我还有另一种我很难理解的方法，如下所示:

private static long[] cache = new long[60]; 

public static long f(int n) {
  if (n == 1 || n == 2) 
    return 1;
  else if (cache[n] > 0) 
    return cache[n]; 
  else { 
    long value = f(n-2) + f(n-1); 
    cache[n] = value; 
    return value;
  }
}

通过这种方法，无论 n 是什么，一切都正常，我的问题是我无法区分。

Answer 1

“粉碎”是指计算运行时间很长。原因是多次调用相同的调用。如果将此添加到您的方法中:

static long count;
public static long f(int n) {
    count++;
    ...

您将看到该方法执行了多少次。对于 f(50)，它实际上调用了方法 25,172,538,049 次，它在我的机器上运行了 41 秒。

当您缓存先前调用的结果时，称为 memoization ，您消除了所有冗余调用，例如f(40) = f(39) + f(38)，但是 f(39) = f(38) + f(37)，所以 f (38) 被调用了两次。记住 f(38) 的结果意味着后续调用会立即得到答案，而无需重做递归。

没有内存，我得到这个:

 n           f(n)           count       time(ns)
== ============== =============== ==============
 1              1               1          6,273
 2              1               1            571
 3              2               3            855
 4              3               5          1,141
 5              5               9          1,425
 6              8              15          1,140
 7             13              25          1,996
 8             21              41          2,851
 9             34              67          7,413
10             55             109         16,536
11             89             177          8,839
12            144             287         19,103
13            233             465         21,098
14            377             753         11,405
15            610           1,219          5,703
16            987           1,973          9,979
17          1,597           3,193         21,099
18          2,584           5,167         32,788
19          4,181           8,361         35,639
20          6,765          13,529         57,307
21         10,946          21,891         91,521
22         17,711          35,421        147,687
23         28,657          57,313        237,496
24         46,368          92,735        283,970
25         75,025         150,049        331,583
26        121,393         242,785        401,720
27        196,418         392,835        650,052
28        317,811         635,621      1,053,483
29        514,229       1,028,457      1,702,679
30        832,040       1,664,079      2,750,745
31      1,346,269       2,692,537      4,455,137
32      2,178,309       4,356,617     12,706,520
33      3,524,578       7,049,155     11,714,051
34      5,702,887      11,405,773     19,571,980
35      9,227,465      18,454,929     30,605,757
36     14,930,352      29,860,703     51,298,507
37     24,157,817      48,315,633     84,473,965
38     39,088,169      78,176,337    127,818,746
39     63,245,986     126,491,971    208,727,118
40    102,334,155     204,668,309    336,785,071
41    165,580,141     331,160,281    543,006,638
42    267,914,296     535,828,591    875,782,771
43    433,494,437     866,988,873  1,429,555,753
44    701,408,733   1,402,817,465  2,301,577,345
45  1,134,903,170   2,269,806,339  3,724,691,882
46  1,836,311,903   3,672,623,805  6,010,675,962
47  2,971,215,073   5,942,430,145  9,706,561,705
48  4,807,526,976   9,615,053,951 15,715,064,841
49  7,778,742,049  15,557,484,097 25,427,015,418
50 12,586,269,025  25,172,538,049 41,126,559,697