CODEWITHSUNDEEP
pythonmemoization
Noob Coder
Noob Coder

Reputation: 949

Implementing Memoization

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?

Upvotes: 1

Views: 129

Answers (1)

Madison May
Madison May

Reputation: 2753

Definitely check out functools.lru_cache, the Python stdlib's memoization implementation: http://docs.python.org/dev/library/functools.html#functools.lru_cach

Upvotes: 1

Related Questions