Memoized just saves the previous calculations when using a formula recusivley. Caching actually saves the previous results as well, which makes it really quick to caluclate a values that is incresed.
This was run on my really old Lenovo X220.
Last active
May 17, 2018 20:12
-
-
Save olikami/b44edf89a57f98dbcedd9b4bad110f91 to your computer and use it in GitHub Desktop.
Speed comparison of fibonacci implementations in Python
This file contains 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
| from functools import lru_cache | |
| import time | |
| def fib_recursive(n): | |
| """ | |
| Calculate the n-th fibonacci number recursively | |
| :param n: Fibonacci number to calculate | |
| :return: The n-th fibonacci number | |
| """ | |
| if n < 2: | |
| return n | |
| return fib_recursive(n - 1) + fib_recursive(n - 2) | |
| @lru_cache(maxsize=None) | |
| def fib_memoized(n): | |
| """ | |
| Calculate the n-th fibonacci number basically recursively, but using some caching or memoization. | |
| :param n: Fibonacci number to calculate | |
| :return: The n-th fibonacci number | |
| """ | |
| if n < 2: | |
| return n | |
| return fib_memoized(n - 1) + fib_memoized(n - 2) | |
| def fib_iterative(n): | |
| """ | |
| Calculate the n-th fibonacci number iteratively. | |
| :param n: Fibonacci number to calculate | |
| :return: The n-th fibonacci number | |
| """ | |
| a, b = 1, 1 | |
| for i in range(n-1): | |
| a, b = b, a+b | |
| return a | |
| values = range(0, 51) | |
| for value in values: | |
| print("fib({:02d}) = {}".format(value, fib_memoized(value))) | |
| # Recursion | |
| start = time.time() | |
| fib_recursive(value) | |
| end = time.time() | |
| print("Recursive: {:010.6f}s".format(end - start)) | |
| # Memoization | |
| start = time.time() | |
| fib_memoized(value) | |
| end = time.time() | |
| print("Memoized: {:010.6f}s".format(end - start)) | |
| # Iteration | |
| start = time.time() | |
| fib_iterative(value) | |
| end = time.time() | |
| print("Iteration: {:010.6f}s".format(end - start)) | |
| print() |
This file contains 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
| fib(00) = 0 | |
| Recursive: 000.000002s | |
| Memoized: 000.000002s | |
| Caching: 000.000001s | |
| Iteration: 000.000003s | |
| Direct: 000.000112s | |
| fib(01) = 1 | |
| Recursive: 000.000002s | |
| Memoized: 000.000002s | |
| Caching: 000.000001s | |
| Iteration: 000.000004s | |
| Direct: 000.000021s | |
| fib(02) = 1 | |
| Recursive: 000.000003s | |
| Memoized: 000.000005s | |
| Caching: 000.000002s | |
| Iteration: 000.000005s | |
| Direct: 000.000013s | |
| fib(03) = 2 | |
| Recursive: 000.000003s | |
| Memoized: 000.000005s | |
| Caching: 000.000001s | |
| Iteration: 000.000004s | |
| Direct: 000.000014s | |
| fib(04) = 3 | |
| Recursive: 000.000005s | |
| Memoized: 000.000006s | |
| Caching: 000.000001s | |
| Iteration: 000.000004s | |
| Direct: 000.000009s | |
| fib(05) = 5 | |
| Recursive: 000.000016s | |
| Memoized: 000.000008s | |
| Caching: 000.000001s | |
| Iteration: 000.000005s | |
| Direct: 000.000009s | |
| fib(06) = 8 | |
| Recursive: 000.000009s | |
| Memoized: 000.000008s | |
| Caching: 000.000002s | |
| Iteration: 000.000004s | |
| Direct: 000.000006s | |
| fib(07) = 13 | |
| Recursive: 000.000008s | |
| Memoized: 000.000005s | |
| Caching: 000.000000s | |
| Iteration: 000.000002s | |
| Direct: 000.000004s | |
| fib(08) = 21 | |
| Recursive: 000.000012s | |
| Memoized: 000.000005s | |
| Caching: 000.000000s | |
| Iteration: 000.000002s | |
| Direct: 000.000004s | |
| fib(09) = 34 | |
| Recursive: 000.000018s | |
| Memoized: 000.000005s | |
| Caching: 000.000000s | |
| Iteration: 000.000002s | |
| Direct: 000.000004s | |
| fib(10) = 55 | |
| Recursive: 000.000029s | |
| Memoized: 000.000009s | |
| Caching: 000.000001s | |
| Iteration: 000.000003s | |
| Direct: 000.000012s | |
| fib(11) = 89 | |
| Recursive: 000.000055s | |
| Memoized: 000.000019s | |
| Caching: 000.000002s | |
| Iteration: 000.000005s | |
| Direct: 000.000006s | |
| fib(12) = 144 | |
| Recursive: 000.000114s | |
| Memoized: 000.000014s | |
| Caching: 000.000001s | |
| Iteration: 000.000005s | |
| Direct: 000.000005s | |
| fib(13) = 233 | |
| Recursive: 000.000179s | |
| Memoized: 000.000018s | |
| Caching: 000.000001s | |
| Iteration: 000.000006s | |
| Direct: 000.000008s | |
| fib(14) = 377 | |
| Recursive: 000.000252s | |
| Memoized: 000.000011s | |
| Caching: 000.000000s | |
| Iteration: 000.000004s | |
| Direct: 000.000009s | |
| fib(15) = 610 | |
| Recursive: 000.000412s | |
| Memoized: 000.000019s | |
| Caching: 000.000001s | |
| Iteration: 000.000007s | |
| Direct: 000.000012s | |
| fib(16) = 987 | |
| Recursive: 000.000814s | |
| Memoized: 000.000027s | |
| Caching: 000.000002s | |
| Iteration: 000.000021s | |
| Direct: 000.000052s | |
| fib(17) = 1597 | |
| Recursive: 000.000986s | |
| Memoized: 000.000017s | |
| Caching: 000.000000s | |
| Iteration: 000.000006s | |
| Direct: 000.000013s | |
| fib(18) = 2584 | |
| Recursive: 000.001306s | |
| Memoized: 000.000013s | |
| Caching: 000.000001s | |
| Iteration: 000.000003s | |
| Direct: 000.000005s | |
| fib(19) = 4181 | |
| Recursive: 000.002072s | |
| Memoized: 000.000011s | |
| Caching: 000.000000s | |
| Iteration: 000.000003s | |
| Direct: 000.000004s | |
| fib(20) = 6765 | |
| Recursive: 000.003258s | |
| Memoized: 000.000012s | |
| Caching: 000.000000s | |
| Iteration: 000.000003s | |
| Direct: 000.000004s | |
| fib(21) = 10946 | |
| Recursive: 000.005498s | |
| Memoized: 000.000016s | |
| Caching: 000.000000s | |
| Iteration: 000.000005s | |
| Direct: 000.000009s | |
| fib(22) = 17711 | |
| Recursive: 000.008994s | |
| Memoized: 000.000018s | |
| Caching: 000.000001s | |
| Iteration: 000.000005s | |
| Direct: 000.000010s | |
| fib(23) = 28657 | |
| Recursive: 000.014053s | |
| Memoized: 000.000019s | |
| Caching: 000.000001s | |
| Iteration: 000.000006s | |
| Direct: 000.000009s | |
| fib(24) = 46368 | |
| Recursive: 000.022631s | |
| Memoized: 000.000021s | |
| Caching: 000.000001s | |
| Iteration: 000.000006s | |
| Direct: 000.000011s | |
| fib(25) = 75025 | |
| Recursive: 000.037127s | |
| Memoized: 000.000019s | |
| Caching: 000.000001s | |
| Iteration: 000.000006s | |
| Direct: 000.000010s | |
| fib(26) = 121393 | |
| Recursive: 000.062554s | |
| Memoized: 000.000041s | |
| Caching: 000.000002s | |
| Iteration: 000.000011s | |
| Direct: 000.000020s | |
| fib(27) = 196418 | |
| Recursive: 000.106930s | |
| Memoized: 000.000036s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000014s | |
| fib(28) = 317811 | |
| Recursive: 000.159737s | |
| Memoized: 000.000026s | |
| Caching: 000.000001s | |
| Iteration: 000.000007s | |
| Direct: 000.000015s | |
| fib(29) = 514229 | |
| Recursive: 000.265797s | |
| Memoized: 000.000027s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(30) = 832040 | |
| Recursive: 000.420143s | |
| Memoized: 000.000026s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(31) = 1346269 | |
| Recursive: 000.661506s | |
| Memoized: 000.000034s | |
| Caching: 000.000001s | |
| Iteration: 000.000007s | |
| Direct: 000.000015s | |
| fib(32) = 2178309 | |
| Recursive: 001.364184s | |
| Memoized: 000.000030s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000016s | |
| fib(33) = 3524578 | |
| Recursive: 001.768754s | |
| Memoized: 000.000030s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000016s | |
| fib(34) = 5702887 | |
| Recursive: 002.737444s | |
| Memoized: 000.000030s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000016s | |
| fib(35) = 9227465 | |
| Recursive: 004.420574s | |
| Memoized: 000.000036s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(36) = 14930352 | |
| Recursive: 007.161705s | |
| Memoized: 000.000031s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(37) = 24157817 | |
| Recursive: 011.560133s | |
| Memoized: 000.000033s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000016s | |
| fib(38) = 39088169 | |
| Recursive: 018.742245s | |
| Memoized: 000.000031s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(39) = 63245986 | |
| Recursive: 030.789896s | |
| Memoized: 000.000032s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(40) = 102334155 | |
| Recursive: 049.485875s | |
| Memoized: 000.000033s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(41) = 165580141 | |
| Recursive: 079.902681s | |
| Memoized: 000.000034s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000015s | |
| fib(42) = 267914296 | |
| Recursive: 134.800153s | |
| Memoized: 000.000036s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000015s | |
| fib(43) = 433494437 | |
| Recursive: 212.036552s | |
| Memoized: 000.000055s | |
| Caching: 000.000001s | |
| Iteration: 000.000015s | |
| Direct: 000.000027s | |
| fib(44) = 701408733 | |
| Recursive: 341.782828s | |
| Memoized: 000.000035s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(45) = 1134903170 | |
| Recursive: 551.241700s | |
| Memoized: 000.000036s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000015s | |
| fib(46) = 1836311903 | |
| Recursive: 896.829807s | |
| Memoized: 000.000037s | |
| Caching: 000.000001s | |
| Iteration: 000.000008s | |
| Direct: 000.000015s | |
| fib(47) = 2971215073 | |
| Recursive: 1438.007968s | |
| Memoized: 000.000037s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000014s | |
| fib(48) = 4807526976 | |
| Recursive: 2324.525913s | |
| Memoized: 000.000037s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000015s | |
| fib(49) = 7778742049 | |
| Recursive: 3757.213618s | |
| Memoized: 000.000039s | |
| Caching: 000.000001s | |
| Iteration: 000.000009s | |
| Direct: 000.000015s |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment