Implementing Memoization

Question

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.

Madison May · Accepted Answer · 2014-01-03 22:46:28Z

1

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

answered Jan 3, 2014 at 22:46

Madison May

2,7833 gold badges24 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Implementing Memoization

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related