After viewing code samples from RosettaCode and Literate Programming I am still confused at how to implement memoization for a problem I am doing.
In the problem, I perform a magic() formula, similar to a Collatz Sequence on the number, and eventually the sequence either yields 1,2,or 3.
for example it might go:
123849 -> 2342453 -> 1233453 ->3
I would like to store the values after I calculate them, so that as I perform magic() on increasingly big numbers, the run time is reduced. So for instance, after doing magic(123849), I would like to store 123849, 2342453, and 1233453. If any of these numbers comes up in the future, instead of having to perform the magic function, it will immediately output 3.
ones=[]
twos=[]
threes=[]
def magic(x):
# Memoization
if ones.count(x)>0: return 1
if twos.count(x)>0: return 2
if threes.count(x)>0: return 3
sequence=[]
<generate magic sequence, add each value to sequence>
# Add each sequence to the appropriate list
if final_value==1: ones.extend(sequence)
if final_value==2: twos.extend(sequence)
if final_value==3: threes.extend(sequence)
return final_value
My question: is there a better (more efficient/faster) way of implementing this memoization? Can I use lists instead of dicts?
- I have read this: What is memoization and how can I use it in Python? and understand that you are normally supposed to use dicts. I was just wondering if there is a big difference between using lists and dicts for memoization.
