Có cách nào tốt hơn (hiệu suất) tính toán giá trị hơn cái này không?

Question

Tôi đã thực hiện mã này .. Và tôi cần để có được tốt nhất của nó .. Tôi thực sự cần hiệu suất tốt nhất của tính số lượng .. xin vui lòng giúp đỡ được ..

Tôi đã đọc một số mã của loại tính toán và tôi nghĩ rằng tôi đã là tốt nhất trong số họ ..

Avaliate này cho tôi .. plz ..

ps: và tôi thực sự cần sự BigInteger .. tôi sẽ tính toán Fibonacci số khổng lồ

ps2: Tôi đã tính toán một số lượng lớn với thuật toán này và tôi có thời gian phản hồi tuyệt vời .. nhưng tôi cần biết liệu nó có thể là tốt hơn

ps3: để chạy mã này, bạn sẽ cần phải sử dụng lập luận này VM -Xss16384k (STACKSIZE)

public class Fibonacci { 

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) }; 

    public static BigInteger fibonacci(long v) { 

     BigInteger fib = BigInteger.valueOf(0); 

     if (v == 1) { 

      fib = BigInteger.valueOf(1); 

     } else if (v == 0) { 

      fib = BigInteger.valueOf(0); 

     } else { 

      BigInteger v1 = fibonacci(v - 1); 
      BigInteger v2 = fibTmp[(int) (v - 2)]; 

      fib = v1.add(v2); 
     } 

     synchronized (fibTmp) { 

      if (fibTmp.length - 1 < v) 
       fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10)); 

      fibTmp[(int) v] = fib; 
     } 

     return fib; 
    } 
} 

Answer 1

thực hiện của bạn không làm việc cho bất kỳ số lượng phong nha vì nó làm cho stack overflow .

Tôi không thấy lý do nào để sử dụng tính đệ quy tại đây. Độ đệ quy khá đẹp nhưng thường nặng hơn (phụ thuộc vào ngôn ngữ). Dưới đây là một việc thực hiện làm việc với một for vòng lặp đơn giản:

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE}; 
private static int maxCached = 1; 
public static BigInteger fibonacci(int v) { 
    if (fibTmp.length<=v) { 
     fibTmp = Arrays.copyOf(fibTmp, v*5/4); 
    } 
    for (; maxCached<v;) { 
     maxCached++; 
     BigInteger v1 = fibTmp[maxCached - 1]; 
     BigInteger v2 = fibTmp[maxCached - 2]; 
     fibTmp[maxCached] = v1.add(v2); 
    } 
    return fibTmp[v]; 
} 

Đó là một thực hiện trực tiếp mà không cần tìm kiếm một thuật toán Fibonacci hiệu quả trong các tài liệu. Bạn nên tìm kiếm chúng.

Cũng lưu ý rằng việc triển khai dựa trên bộ nhớ cache này là bộ nhớ tốn kém và chỉ có ý nghĩa nếu bạn gọi hàm đó nhiều lần.

Answer 2

Trước hết, bạn đang sử dụng đệ quy, điều này không hiệu quả về mặt phức tạp về thời gian và không gian. Bạn nên sử dụng phương pháp lặp lại. Sau đó, nếu thêm bộ nhớ hoặc không gian không phải là đối phó breaker và nếu hiệu suất là rất quan trọng, bạn có thể muốn precompute tất cả các số mà bạn muốn tính toán sau đó và lưu trữ chúng trong một mảng hoặc trên đĩa của bạn nếu nó quá nhiều cho trí nhớ của bạn. Sau đó bạn có thể nhận được giá trị trong thời gian không đổi.

Answer 3

Có, có cách tốt hơn. Đây là log(n) được thử nghiệm và rất hiệu quả để tính giá trị của Fibonacci với độ chính xác tùy ý, được cho một số nguyên dương làm đầu vào. Thuật toán được chuyển thể từ một giải pháp cho SICP 's exercise 1.19:

public static BigInteger fibonacci(int n) { 

    int count = n; 
    BigInteger tmpA, tmpP; 
    BigInteger a = BigInteger.ONE; 
    BigInteger b = BigInteger.ZERO; 
    BigInteger p = BigInteger.ZERO; 
    BigInteger q = BigInteger.ONE; 
    BigInteger two = new BigInteger("2"); 

    while (count != 0) { 

     if ((count & 1) == 0) { 
      tmpP = p.multiply(p).add(q.multiply(q)); 
      q = two.multiply(p.multiply(q)).add(q.multiply(q)); 
      p = tmpP; 
      count >>= 1; 
     } 

     else { 
      tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p))); 
      b = b.multiply(p).add(a.multiply(q)); 
      a = tmpA; 
      count--; 
     } 

    } 

    return b; 

} 

Trong chương liên kết của cuốn sách có một giải thích về cách thức hoạt động (di chuyển xuống để thực hiện 1,19), và nó nói rằng:

Đây là một thuật toán thông minh để tính toán số Fibonacci trong một số bước logarit ... Bài tập này được đề xuất bởi Joe Stoy, dựa trên một ví dụ ở Kaldewaij, Anne. 1990. Lập trình: Nguồn gốc của thuật toán.

Tất nhiên, nếu các giá trị giống nhau cần được tính lặp đi lặp lại, các kết quả có thể đạt được bằng kết quả đã được tính toán, ví dụ như sử dụng bản đồ để lưu trữ các giá trị trước đó.