Fibonacciアルゴリズムの3つの実装と性能の比較


コードは次のとおりです.
import java.util.ArrayList;
import java.util.List;

public class Fibonacci {

	/**
	 *     :            
	 * @param n
	 * @return
	 */
	public static Long recursiveCompute(int n) {
		if (n <= 2)
			return 1L;
		else
			return recursiveCompute(n - 1) + recursiveCompute(n - 2);
	}

	/**
	 *    cache  :   List     1~n Fibonacci 
	 * @param n
	 * @return
	 */
	public static Long cacheCompute(int n) {
		if (n <= 2)
			return 1L;

		List<Long> results = new ArrayList<Long>();
		results.add(1L);
		results.add(1L);

		int length = -1;
		while ((length = results.size()) < n)
			results.add(results.get(length - 2) + results.get(length - 1));
		return results.get(n - 1);
	}

	/**
	 *    swap  :      l1、l2   Fibonacci ,  update swap
	 * @param n
	 * @return
	 */
	public static Long swapCompute(int n) {
		if (n <= 2)
			return 1L;

		long l1 = 1;
		long l2 = 1;

		int index = 2;
		while (index < n - 1) {
			long l = l2;
			l2 = l1 + l2;
			l1 = l;
			index++;
		}
		return l1 + l2;
	}

	public static void testTime(int n) {
		Long result = 0L;

		long start = System.nanoTime();
		result = recursiveCompute(n);
		long end = System.nanoTime();
		System.out.println("Recursive Compute: " + result + "\tUse Time: " + (end - start));

		start = System.nanoTime();
		result = cacheCompute(n);
		end = System.nanoTime();
		System.out.println("Cache Compute: " + result + "\tUse Time: " + (end - start));

		start = System.nanoTime();
		result = swapCompute(n);
		end = System.nanoTime();
		System.out.println("Swap Compute: " + result + "\tUse Time: " + (end - start));
	}

	public static void main(String[] args) {
		System.out.println("Compute Fibonacci(10):");
		testTime(10);
		System.out.println("
Compute Fibonacci(20):"); testTime(20); System.out.println("
Compute Fibonacci(30):"); testTime(30); System.out.println("
Compute Fibonacci(40):"); testTime(40); System.out.println("
Compute Fibonacci(50):"); testTime(50); } }

テスト結果:
Compute Fibonacci(10):
Recursive Compute: 55	Use Time: 26944
Cache Compute: 55	Use Time: 52444
Swap Compute: 55	Use Time: 4330

Compute Fibonacci(20):
Recursive Compute: 6765	Use Time: 1528093
Cache Compute: 6765	Use Time: 26463
Swap Compute: 6765	Use Time: 1443

Compute Fibonacci(30):
Recursive Compute: 832040	Use Time: 17896390
Cache Compute: 832040	Use Time: 48595
Swap Compute: 832040	Use Time: 1924

Compute Fibonacci(40):
Recursive Compute: 102334155	Use Time: 2385636507
Cache Compute: 102334155	Use Time: 54850
Swap Compute: 102334155	Use Time: 1924

Compute Fibonacci(50):
Recursive Compute: 12586269025	Use Time: 287928822445
Cache Compute: 12586269025	Use Time: 76501
Swap Compute: 12586269025	Use Time: 2887

再帰アルゴリズムを削除し、テストします.
Compute Fibonacci(100):
Cache Compute: 3736710778780434371	Use Time: 274730
Swap Compute: 3736710778780434371	Use Time: 10104

Compute Fibonacci(1000):
Cache Compute: 817770325994397771	Use Time: 1330826
Swap Compute: 817770325994397771	Use Time: 44746

Compute Fibonacci(10000):
Cache Compute: -2872092127636481573	Use Time: 4596307
Swap Compute: -2872092127636481573	Use Time: 326211

Compute Fibonacci(50000):
Cache Compute: -806788626697678875	Use Time: 14161801
Swap Compute: -806788626697678875	Use Time: 1218240
  • Recursiveアルゴリズムは自身を呼び出し続けるため、深さ計算が多すぎて、性能が非常に低下し、n>=50の場合、Recursiveアルゴリズムにかかる時間はもう我慢できない.
  • CacheアルゴリズムとSwapアルゴリズムはwhileサイクルで絶えず計算と更新されているだけで、Cacheアルゴリズムは毎回計算値をリストに保存し、消費メモリが多すぎて、性能もSwapの良いものではありません.