Last active
December 21, 2022 12:01
-
-
Save dwy6626/ca70c57da3b79daae1bd8df05e98d0c2 to your computer and use it in GitHub Desktop.
Timeit!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import time | |
| from functools import lru_cache | |
| import numpy as np | |
| from matplotlib import pyplot as plt | |
| from decimal import Decimal, getcontext | |
| getcontext().prec = 250 | |
| def fib_binet(n): | |
| sqrt5 = Decimal(5) ** Decimal('0.5') | |
| golden_ratio = (1 + sqrt5) / Decimal(2) | |
| golden_ratio_alt = (1 - sqrt5) / Decimal(2) | |
| return round((golden_ratio ** Decimal(n) - golden_ratio_alt ** Decimal(n)) / sqrt5) | |
| def fib_fast_double(n): | |
| def recursive(n): | |
| if n == 0: | |
| return 1, 0 | |
| q, r = divmod(n, 2) | |
| f2, f1 = recursive(q) | |
| f2, f1 = f1 ** 2 + f2 ** 2, f1 * (2 * f2 - f1) | |
| if r == 0: | |
| return f2, f1 | |
| return f1 + f2, f2 | |
| return recursive(n)[1] | |
| def fib_fast_double_iter(n): | |
| tracker = [] | |
| while n > 1: | |
| tracker.append(n) | |
| n //= 2 | |
| f1, f2 = 1, 1 | |
| while tracker: | |
| n = tracker.pop() | |
| f1, f2 = f1 * (2 * f2 - f1), f1 ** 2 + f2 ** 2 | |
| if n % 2 == 1: | |
| f1, f2 = f2, f1 + f2 | |
| return f1 | |
| def fib_matrix(n): | |
| A = [[1, 1], [1, 0]] | |
| def power(A, n): | |
| if n < 2: | |
| return A | |
| q, r = divmod(n, 2) | |
| power(A, q) | |
| multiply(A, A) | |
| if r != 0: | |
| multiply(A, [[1, 1], [1, 0]]) | |
| def multiply(A, B): | |
| x = A[0][0] * B[0][0] + A[0][1] * B[1][0] | |
| y = A[0][0] * B[0][1] + A[0][1] * B[1][1] | |
| z = A[1][0] * B[0][0] + A[1][1] * B[1][0] | |
| w = A[1][0] * B[0][1] + A[1][1] * B[1][1] | |
| A[0][0] = x | |
| A[0][1] = y | |
| A[1][0] = z | |
| A[1][1] = w | |
| power(A, n-1) | |
| return A[0][0] | |
| def fib_iterative(n): | |
| f1, f2 = 1, 1 | |
| for _ in range(2, n): # 當 n < 3 時不會進入迴圈 | |
| f1, f2 = f2, f1 + f2 | |
| return f2 | |
| @lru_cache(maxsize=2) | |
| def fib_lru(n): | |
| if n < 3: | |
| return 1 | |
| return fib_lru(n-2) + fib_lru(n-1) | |
| functions = [fib_binet, fib_fast_double, fib_fast_double_iter, fib_matrix, fib_iterative, fib_lru] | |
| # unittest | |
| for i in [1, 10, 100, 1000]: | |
| res = [] | |
| for f in functions: | |
| res.append(f(i)) | |
| assert all(x == res[0] for x in res[1:]) | |
| # time measurement | |
| xx = list(range(10, 1001, 20)) | |
| repeat = 1000 | |
| res = [] | |
| for i in xx: | |
| for j in range(repeat): | |
| res_j = [0 for _ in range(len(functions))] | |
| for k, f in enumerate(functions): | |
| time1 = time.time() | |
| f(i) | |
| time2 = time.time() | |
| res_j[k] += time2 - time1 | |
| if f.__name__ == 'fib_lru': | |
| f.cache_clear() | |
| res.append(res_j) | |
| res = np.array(res).T * 1000 | |
| # plot | |
| for k, f in enumerate(functions): | |
| plt.plot(xx, res[k], label=f.__name__) | |
| plt.legend() | |
| plt.xlabel('n') | |
| plt.ylabel('time/1000 run (ms)') | |
| plt.savefig('res.png') |
I was thinking of binet algo to be the fastest possible, but with some practical code whom you write, I found my self in a wrong position 🍡
glad it helped!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Awesome work, :)