Join GitHub today
GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.
Sign upCreate fibonacci_sequence_recursion_with_memoization.py #2619
Conversation
SamueldaCostaAraujoNunes
changed the title
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: 6d896530-0414-11eb-b614-dd2b96524a99 |
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: 6972fd20-0415-11eb-b614-dd2b96524a99 |
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: 8bec1310-0419-11eb-b614-dd2b96524a99 |
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: 3ce5bfd0-041b-11eb-b614-dd2b96524a99 |
| Return number of index n in sequence fibonacci | ||
| >>> [fibonacci(i) for i in range(12)] | ||
| [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] | ||
| """ |
dhruvmanila
Oct 2, 2020
Member
Please have multiple doctest.
Please have multiple doctest.
|
|
||
| if aux in cache: | ||
| return cache[aux] |
dhruvmanila
Oct 2, 2020
Member
Please check whether the input is of type int, if not then raise TypeError and for negative numbers raise ValueError.
Please check whether the input is of type int, if not then raise TypeError and for negative numbers raise ValueError.
| if aux in cache: | ||
| return cache[aux] | ||
|
|
||
| if (n == 0) or (n == 1): |
dhruvmanila
Oct 2, 2020
Member
Suggested change
if (n == 0) or (n == 1):
if n in {0, 1}:
set are hashed, so fast lookup.
$ python -m timeit -s "n = 1" "(n == 0) or (n == 1)"
10000000 loops, best of 5: 32.5 nsec per loop
$ python -m timeit -s "n = 1" "n in {0, 1}"
10000000 loops, best of 5: 21 nsec per loop
$ python -m timeit -s "n = 1" "n in (0, 1)"
10000000 loops, best of 5: 27.4 nsec per loop
| if (n == 0) or (n == 1): | |
| if n in {0, 1}: |
set are hashed, so fast lookup.
$ python -m timeit -s "n = 1" "(n == 0) or (n == 1)"
10000000 loops, best of 5: 32.5 nsec per loop
$ python -m timeit -s "n = 1" "n in {0, 1}"
10000000 loops, best of 5: 21 nsec per loop
$ python -m timeit -s "n = 1" "n in (0, 1)"
10000000 loops, best of 5: 27.4 nsec per loop|
|
||
|
|
||
| def main() -> None: | ||
| number = int(input("Enter an integer greater than or equal to 0: ")) |
dhruvmanila
Oct 2, 2020
Member
Suggested change
number = int(input("Enter an integer greater than or equal to 0: "))
try:
number = int(input("Enter an integer greater than or equal to 0: "))
except ValueError:
print("Error: Input value should be an integer greater than or equal to 0")
| number = int(input("Enter an integer greater than or equal to 0: ")) | |
| try: | |
| number = int(input("Enter an integer greater than or equal to 0: ")) | |
| except ValueError: | |
| print("Error: Input value should be an integer greater than or equal to 0") |
NumberPiOso
Oct 2, 2020
Contributor
This try does not assert that the value is greater than or equal to 0, so the message of error is misleading.
This try does not assert that the value is greater than or equal to 0, so the message of error is misleading.
Co-authored-by: Dhruv <[email protected]>
|
A simpler approach is to use the decorator This uses the memoization technique withouth the overhead of having to implement the dictionary and looking for values. There is a example of this for Fibonacci numbers in the Python documentation. |
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: d5a554f0-04c6-11eb-a4bc-1b94c014fd22 |
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: 5ce50cd0-04c7-11eb-a4bc-1b94c014fd22 |
Travis tests have failedHey @SamueldaCostaAraujoNunes, TravisBuddy Request Identifier: 01cb2440-04c9-11eb-a4bc-1b94c014fd22 |
I really agree that it would be much simpler to implement, but my intention with this code was to be more didactic, applying memoization directly within the Fibonacci sequence! I liked to know that there is a native solution within Python itself, but I chose to keep the logic of my algorithm in this way, thank you! |
|
Thanks. Did you take a look at the existing implementation in |
My program is in the application of memoization in the fibonacci sequence using a single recursive function. The fast_fibonacci example applies recursion, but does not apply any algorithm focused on saving data, as is done in the memoizationtechnique. In the fibonacci example, an array is used that will be generated at the beginning of the program execution, with the size defined by the user and only after that, that the user can request the desired fibonacci value! My program uses a dictionary to store the corresponding values of the fibonacci sequence, only when necessary! So, my program allows you to find the desired value in O (1), right on the first run, and it is possible to save this same dictionary for future runs! The limitation of this program is due to the amount of memory available in the system! |
Yes, but is it still, classified as |
My algorithm relates the application of the Fibonacci sequence (using Recursion) to the Memoization technique. Thus, it is possible to reach the complexity O (1), to calculate the Fibonacci value of very high numbers and in an incredibly shorter time interval than using only the common recursion.
Checklist:
Fixes: #{$ISSUE_NO}.