27

I've been using the following memoizing decorator (from the great book Python Algorithms: Mastering Basic Algorithms in the Python Language ... love it, btw).

def memo(func):
    cache = {}
    @ wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

The problem with this decorator is that the dictionary-based cache means that all of my arguments must be hashable.

Does anyone have an implementation (or a tweak to this one) that allows for unhashable arguments (e.g. dictionaries)?

I know that the lack of a hash value means that the question of "is this in the cache?" becomes non-trivial, but I just thought I'd ask.

===EDITED TO GIVE CONTEXT===

I am working on a function that returns a Parnas-style "uses hierarchy" given a dictionary of module: dependencies. Here's the setup:

def uses_hierarchy(requirements):
    """
    uses_hierarchy(requirements)

    Arguments:
    requirements - a dictionary of the form {mod: list of dependencies, }

    Return value:
    A dictionary of the form {level: list of mods, ...}

    Assumptions:
    - No cyclical requirements (e.g. if a requires b, b cannot require a).
    - Any dependency not listed as a mod assumed to be level 0.

    """

    levels = dict([(mod, _level(mod, requirements))
                   for mod in requirements.iterkeys()])
    reversed = dict([(value, []) for value in levels.itervalues()])
    for k, v in levels.iteritems():
        reversed[v].append(k)
    return reversed


def _level(mod, requirements):
    if not requirements.has_key(mod):
        return 0
    dependencies = requirements[mod]
    if not dependencies:
        return 0
    else:
        return max([_level(dependency, requirements)
                    for dependency in dependencies]) + 1

So that:

>>> requirements = {'a': [],
...                 'b': [],
...                 'c': ['a'],
...                 'd': ['a','b'],
...                 'e': ['c','d'],
...                 'f': ['e']
...                 }

>>> uses_hierarchy(requirements)
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']}

_level is the function I want to memoize to make this setup more scalable. As implemented without memoization, it calculates the level of dependencies multiple times (e.g. 'a' is calculated 8 times I think in the example above).

Thanks,

Mike

MikeRand
  • 4,788
  • 9
  • 41
  • 70
  • 1
    Well, just store them in a list as tuples of `(args, result)`, and iterate over it. As you say, though, it won't be fast. – Thomas K Jan 12 '11 at 13:51
  • 1
    @Thomas K: A cache that gets slower the more items it has sounds really counterproductive indeed. – Jochen Ritzel Jan 12 '11 at 13:59
  • @THC4k: That depends what you want it for. If you're going to be hitting the same few possibilities many times, and the function is a big calculation, or a slow network request, it could well be more than good enough. And on a modern computer, it can get pretty big before it's a problem. – Thomas K Jan 12 '11 at 15:29

6 Answers6

16

Here is the example in Alex Martelli Python Cookbook that show how to create a memoize decorator using cPickle for function that take mutable argument (original version) :

import cPickle

class MemoizeMutable:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args, **kwds):
        import cPickle
        str = cPickle.dumps(args, 1)+cPickle.dumps(kwds, 1)
        if not self.memo.has_key(str): 
            print "miss"  # DEBUG INFO
            self.memo[str] = self.fn(*args, **kwds)
        else:
            print "hit"  # DEBUG INFO

        return self.memo[str]

Here is a link.

EDIT: Using the code that you have given and this memoize decorator :

_level = MemoizeMutable(_level)

equirements = {'a': [],
               'b': [],
               'c': ['a'],
               'd': ['a','b'],
               'e': ['c','d'],
               'f': ['e']
                 }

print uses_hierarchy(equirements)

i was able to reproduce this:

miss
miss
hit
miss
miss
hit
miss
hit
hit
hit
miss
hit
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']}
mouad
  • 67,571
  • 18
  • 114
  • 106
  • @MikeRand: i have just edited my answer with your example, hope it can help – mouad Jan 12 '11 at 14:59
  • 3
    +1: Pickling is an interesting way to hash mutable objects. I guess this would win over iterating a list for many possibilities (because of the lookup time), but the simpler solution has less overhead for a few possible cases. – Thomas K Jan 12 '11 at 15:18
  • Seems to work, thanks much. Just for my understanding: is cPickle effectively serializing the arguments to make the serialization the hashable key? – MikeRand Jan 12 '11 at 15:27
  • @MikeRand: you're welcome :), yes exactly cPickle just pickle the function argument to a string that can be placed as a key in the cache dictionary , the thing with cPickle is that it's very fast. – mouad Jan 12 '11 at 15:33
  • Isn't it more efficient, performance-wise, to only have the `import` statement on the top of the module, i.e., remove it from `__call__`? – ElRudi Mar 25 '20 at 22:45
7

Technically you can solve this problem by turning the dict (or list or set) into a tuple. For example:

 key = tuple(the_dict.iteritems())
 key = tuple(the_list)
 key = tuple(sorted(the_set))

 cache[key] = func( .. )

But I wouldn't do this in memo, I'd rather change the functions you want to use memo on - for example, instead of accepting a dict they should only accept (key, value) pairs, instead of taking lists or sets they should just take *args.

Jochen Ritzel
  • 104,512
  • 31
  • 200
  • 194
2

Since no one else has mentioned it, the Python Wiki has a Decorator Library which includes a number of memoizing decorator patterns.

My personal preference is the last one, which lets calling code simply treat the method as a lazily-evaluated property, rather than a method. But I like the implementation here better.

class lazy_property(object):
    '''Decorator: Enables the value of a property to be lazy-loaded.
    From Mercurial's util.propertycache

    Apply this decorator to a no-argument method of a class and you
    will be able to access the result as a lazy-loaded class property.
    The method becomes inaccessible, and the property isn't loaded
    until the first time it's called.  Repeated calls to the property
    don't re-run the function.

    This takes advantage of the override behavior of Descriptors - 
    __get__ is only called if an attribute with the same name does
    not exist.  By not setting __set__ this is a non-data descriptor,
    and "If an instance's dictionary has an entry with the same name
    as a non-data descriptor, the dictionary entry takes precedence."
     - http://users.rcn.com/python/download/Descriptor.htm

    To trigger a re-computation, 'del' the property - the value, not
    this class, will be deleted, and the value will be restored upon
    the next attempt to access the property.
    '''
    def __init__(self,func):
        self.func = func
        self.name = func.__name__
    def __get__(self, obj, type=None):
        result = self.func(obj)
        setattr(obj, self.name, result)
        return result

In the same file linked above there's also a lazy_dict decorator, which lets you treat a function as a dictionary with lazily-evaluated values.

dimo414
  • 47,227
  • 18
  • 148
  • 244
2

Not heavily tested, but seems to work:

from functools import wraps

def memo(func):
    cache = []
    argslist = []
    @ wraps(func)
    def wrap(*args):
        try:
            result = cache[argslist.index(args)]
            print 'cache hit'
            return result
        except ValueError:
            argslist.append(args)
            cache.append(func(*args))
            print 'cache miss'
            return cache[-1]
    return wrap

d1 = { 'a':3, 'b':42 }
d2 = { 'c':7, 'd':19 }
d3 = { 'e':34, 'f':67 }

@memo
def func(d):
    return sum(d.values())

print func(d1)
# cache miss
# 45
print func(d2)
# cache miss
# 26
print func(d3)
# cache miss
# 101
print func(d2)
# cache hit
# 26
martineau
  • 119,623
  • 25
  • 170
  • 301
  • Returns a different answer than what I was expecting. When run on example above, the result is {0: ['a', 'b'], 1: ['c'], 2: ['e', 'd', 'f']}. Not sure why 'd' moves from level 1 to level 2. – MikeRand Jan 12 '11 at 14:44
  • @MikeRand: I don't know -- thought it might be because the args being stored were mutable, so tried making deepcopies of them, but that had no effect. Will look into it more and will let you know and/or will modify my answer. – martineau Jan 12 '11 at 15:12
0

I've searched and have found a good python package.

https://pypi.org/project/memoization/

  • easy to use
  • possible to use unhashable arguments
  • other useful option (time to live)
pakira79
  • 111
  • 2
  • 5
0

I was trying to solve the problem myself and came across this question, because this site is prominent in Google search results, but very unfortunately none of the answers are satisfying, so I developed a method myself and I want to share.

I know this question is old but my solution is very new.

So how do you memoize functions that take mutable unhashable objects?

Short answer: You DON'T. I know you are thinking what this answer is about, then?

Well, to memoize the functions that process unhashable objects and gain maximum performance out of it, you absolutely can't pass the objects themselves, but instead some hashable pointer to that object that guarantees the pointer will point to that object.

Let me explain, Python memoization is based on dictionaries, and dict is based on hashmaps, in short keys must be hashable. Mutable objects are unhashable so in order to memoize functions that take mutable arguments you must make the arguments immutable.

Now is the crucial part, any attempt to immutabilize mutable objects will reduce performance because of conversion overhead. So you must not try to make them immutable.

Now comes the hack. Python rebinds names to objects, Python creates objects and maps a string to that object, reassigning a new variable just adds a new name to that object, and literal immutable objects once created will not be created again.

In [12]: ('omo', 114) is ('omo', 114)
<>:1: SyntaxWarning: "is" with a literal. Did you mean "=="?
<ipython-input-12-5fa552d1d69b>:1: SyntaxWarning: "is" with a literal. Did you mean "=="?
  ('omo', 114) is ('omo', 114)
Out[12]: True

In [18]: b'\1' is b'\1'
<>:1: SyntaxWarning: "is" with a literal. Did you mean "=="?
<ipython-input-18-b65ac271a853>:1: SyntaxWarning: "is" with a literal. Did you mean "=="?
  b'\1' is b'\1'
Out[18]: True

In [19]: b'\x01' is b'\1'
<>:1: SyntaxWarning: "is" with a literal. Did you mean "=="?
<ipython-input-19-33adabcdabac>:1: SyntaxWarning: "is" with a literal. Did you mean "=="?
  b'\x01' is b'\1'
Out[19]: True

And what name is guaranteed to be unique and unchangeable to each and every object? Their id, which is just the memory address of that object, concurrent objects will have different memory addresses but objects with non-overlapping lifespans can potentially have the same address, but that possibility is very very small.

So in short, in order to memoize functions that processes immutable objects you can't pass the objects directly, but their current ids.

But how do you get the objects back from id? Use ctypes.

Example:

tree = {('ana',
  224): {('nat', 26): {('ate', 108): {('ted', 573): 0, ('ter', 84): 0},
   ('ati', 383): {('tic', 255): 0, ('tin', 28): 0},
   ('ator', 108): 0}, ('naced', 31): 0, ('nage', 23): {('ged', 31): 0,
   ('ger', 45): 0}, ('nalic', 43): 0},
 ('ani', 87): {('nimal', 39): 0, ('nison', 28): 0},
 ('ave',
  49): {('ven', 20): {('enal', 40): 0,
   ('ene', 152): {('ned', 50): 0, ('ner', 57): 0},
   ('enic', 44): 0}, ('ver',
   23): {('era', 70): {('ral', 73): 0, ('ran', 28): 0}, ('ere',
    86): {('red', 165): 0, ('rer', 155): 0}, ('eri', 69): {('ric', 75): 0,
    ('rin', 24): 0}}},
 ('cal',
  290): {('ala', 31): {('lace', 67): 0,
   ('lane', 65): 0,
   ('lary', 31): 0,
   ('late', 58): 0}, ('ale', 24): {('lene', 90): 0, ('lery', 26): 0}, ('ali',
   36): {('lide', 26): 0,
   ('lify', 36): 0,
   ('line', 88): 0,
   ('lise', 417): 0,
   ('lit', 262): {('ite', 209): 0, ('ity', 698): 0},
   ('lize', 259): 0}, ('alogy', 23): 0},
 ('can',
  244): {('ana', 24): {('nade', 26): 0,
   ('nage', 59): 0,
   ('nary', 28): 0,
   ('nate', 103): 0}, ('anomy', 25): 0},
 ('car',
  427): {('ara', 41): {('rac', 84): {('ace', 33): 0, ('acy', 60): 0},
   ('rade', 47): 0,
   ('rage', 56): 0,
   ('rate', 76): 0}, ('are', 22): {('rely', 26): 0, ('rene', 72): 0}, ('ari',
   24): {('rice', 30): 0,
   ('ride', 25): 0,
   ('rify', 24): 0,
   ('rily', 63): 0,
   ('rin', 156): {('ina', 24): 0, ('ine', 168): 0},
   ('rise', 146): 0,
   ('rit', 119): {('ite', 174): 0, ('ity', 118): 0},
   ('rize', 56): 0}, ('aro', 25): {('rome', 24): 0, ('rone', 35): 0}},
 ('cat',
  226): {('ate', 50): {('tely', 117): 0,
   ('tene', 74): 0,
   ('ter', 153): {('era', 35): 0, ('ery', 72): 0}}, ('atary', 88): 0},
 ('cer',
  155): {('era', 31): {('rac', 63): {('ace', 33): 0, ('acy', 60): 0},
   ('rage', 39): 0,
   ('rary', 36): 0,
   ('rate', 472): 0}, ('erene', 41): 0},
 ('col', 294): {('ole', 21): {('lene', 60): 0, ('lery', 39): 0},
  ('olo', 65): {('logy', 825): 0, ('lose', 23): 0},
  ('olute', 34): 0},
 ('cor',
  422): {('ora', 34): {('rac', 50): {('ace', 33): 0, ('acy', 60): 0},
   ('rage', 23): 0,
   ('rary', 20): 0,
   ('rate', 221): 0}, ('oro', 34): {('rone', 29): 0, ('rose', 40): 0}},
 ('dec', 350): {('eca', 70): {('case', 22): 0, ('cate', 41): 0},
  ('ecide', 50): 0,
  ('ecul', 28): {('ula', 29): 0, ('ule', 41): 0}},
 ('del', 166): {('ela', 20): {('lane', 72): 0, ('late', 111): 0},
  ('eli', 86): {('lide', 23): 0,
   ('line', 126): 0,
   ('lise', 44): 0,
   ('lit', 43): {('ite', 209): 0, ('ity', 698): 0}},
  ('elene', 20): 0},
 ('dem',
  187): {('ema', 23): {('mary', 23): 0,
   ('mat', 208): {('ata', 37): 0, ('ate', 111): 0}}, ('emi',
   44): {('mine', 109): 0, ('mit', 58): {('ite', 64): 0,
    ('ity', 45): 0}}, ('emo',
   79): {('mony', 133): 0,
   ('more', 62): 0,
   ('mose', 29): 0,
   ('mote', 35): 0}, ('emer', 21): {('ere', 24): 0, ('ery', 20): 0}},
 ('dep', 181): {('epo', 28): {('pore', 32): 0, ('pose', 50): 0},
  ('epery', 21): 0},
 ('dis', 1259): {('isa', 115): {('sary', 24): 0, ('sate', 78): 0},
  ('isi', 49): {('sine', 79): 0,
   ('sit', 53): {('ite', 61): 0, ('ity', 128): 0}},
  ('iso', 44): {('some', 26): 0, ('sory', 37): 0},
  ('isely', 83): 0},
 ('div', 116): {('ive', 52): {('vely', 175): 0, ('very', 107): 0},
  ('ivi', 39): {('vine', 51): 0, ('vity', 55): 0}},
 ('epi',
  260): {('pid', 27): {('idal', 34): 0,
   ('ide', 40): {('ded', 20): 0, ('der', 40): 0, ('des', 38): 0},
   ('idic', 26): 0}, ('pit', 36): {('ital', 80): 0,
   ('iti', 27): {('tic', 142): 0, ('tis', 108): 0},
   ('itor', 22): 0}, ('pica', 39): {('cal', 1198): 0,
   ('can', 25): 0}, ('piped', 37): 0},
 ('eve',
  60): {('ven', 26): {('enal', 40): 0,
   ('ene', 152): {('ned', 50): 0, ('ner', 57): 0},
   ('enic', 44): 0}, ('ver',
   27): {('era', 70): {('ral', 73): 0, ('ran', 28): 0}, ('ere',
    86): {('red', 165): 0, ('rer', 155): 0}, ('eri', 69): {('ric', 75): 0,
    ('rin', 24): 0}}},
 ('gen', 150): {('ene', 56): {('nery', 118): 0, ('nese', 644): 0},
  ('eni', 25): {('nine', 59): 0,
   ('nit', 112): {('ite', 200): 0, ('ity', 93): 0},
   ('nize', 33): 0}},
 ('hem',
  139): {('ema', 45): {('mary', 23): 0,
   ('mat', 208): {('ata', 37): 0, ('ate', 111): 0}}, ('emi',
   56): {('mine', 109): 0, ('mit', 58): {('ite', 64): 0, ('ity', 45): 0}}},
 ('hom',
  193): {('omo', 114): {('mony', 35): 0,
   ('more', 99): 0,
   ('mote', 49): 0}, ('omer', 45): {('ere', 24): 0, ('ery', 20): 0}},
 ('lat',
  106): {('ate', 27): {('tely', 117): 0,
   ('tene', 74): 0,
   ('ter', 153): {('era', 35): 0, ('ery', 72): 0}}, ('ati',
   39): {('tice', 187): 0,
   ('tify', 43): 0,
   ('til', 25): {('ile', 79): 0, ('ily', 37): 0},
   ('tin', 230): {('ina', 22): 0, ('ine', 134): 0},
   ('tise', 129): 0,
   ('tite', 52): 0,
   ('tive', 517): 0,
   ('tize', 59): 0}},
 ('mal',
  213): {('ala', 64): {('lace', 67): 0,
   ('lane', 65): 0,
   ('lary', 31): 0,
   ('late', 58): 0}, ('ale', 37): {('lene', 90): 0, ('lery', 26): 0}},
 ('mar',
  286): {('ara', 21): {('rac', 84): {('ace', 33): 0, ('acy', 60): 0},
   ('rade', 47): 0,
   ('rage', 56): 0,
   ('rate', 76): 0}, ('ari', 30): {('rice', 30): 0,
   ('ride', 25): 0,
   ('rify', 24): 0,
   ('rily', 63): 0,
   ('rin', 156): {('ina', 24): 0, ('ine', 168): 0},
   ('rise', 146): 0,
   ('rit', 119): {('ite', 174): 0, ('ity', 118): 0},
   ('rize', 56): 0}},
 ('mel', 159): {('ela', 55): {('lane', 72): 0, ('late', 111): 0},
  ('eli', 26): {('lide', 23): 0,
   ('line', 126): 0,
   ('lise', 44): 0,
   ('lit', 43): {('ite', 209): 0, ('ity', 698): 0}}},
 ('met', 291): {('eta', 154): {('tary', 46): 0, ('tate', 45): 0},
  ('ete', 37): {('tene', 65): 0,
   ('ter', 212): {('era', 35): 0, ('ery', 72): 0}}},
 ('min', 141): {('ine', 22): {('nery', 80): 0, ('nese', 536): 0},
  ('ini', 49): {('nify', 40): 0,
   ('nine', 66): 0,
   ('nit', 112): {('ite', 200): 0, ('ity', 93): 0},
   ('nize', 41): 0}},
 ('mis', 512): {('isa', 49): {('sary', 24): 0, ('sate', 78): 0},
  ('isely', 28): 0},
 ('mon',
  393): {('ona', 49): {('nade', 27): 0,
   ('nage', 28): 0,
   ('nary', 118): 0,
   ('nate', 156): 0}, ('one', 30): {('nery', 30): 0, ('nese', 54): 0}, ('oni',
   23): {('nide', 27): 0,
   ('nify', 35): 0,
   ('nine', 62): 0,
   ('nit', 108): {('ite', 200): 0, ('ity', 93): 0},
   ('nize', 113): 0}, ('ono', 220): {('nomy', 160): 0, ('nose', 33): 0}},
 ('mor',
  187): {('ora', 25): {('rac', 50): {('ace', 33): 0, ('acy', 60): 0},
   ('rage', 23): 0,
   ('rary', 20): 0,
   ('rate', 221): 0}, ('ori', 20): {('rice', 57): 0,
   ('ride', 48): 0,
   ('rify', 54): 0,
   ('rily', 36): 0,
   ('rin', 71): {('ina', 24): 0, ('ine', 168): 0},
   ('rise', 91): 0,
   ('rit', 63): {('ite', 174): 0, ('ity', 118): 0},
   ('rize', 68): 0}},
 ('non',
  306): {('ona', 29): {('nade', 27): 0,
   ('nage', 28): 0,
   ('nary', 118): 0,
   ('nate', 156): 0}, ('one', 26): {('nery', 30): 0, ('nese', 54): 0}, ('oni',
   21): {('nide', 27): 0,
   ('nify', 35): 0,
   ('nine', 62): 0,
   ('nit', 108): {('ite', 200): 0, ('ity', 93): 0},
   ('nize', 113): 0}},
 ('pal',
  263): {('ala', 43): {('lace', 67): 0,
   ('lane', 65): 0,
   ('lary', 31): 0,
   ('late', 58): 0}, ('ale', 62): {('lene', 90): 0, ('lery', 26): 0}, ('ali',
   25): {('lide', 26): 0,
   ('lify', 36): 0,
   ('line', 88): 0,
   ('lise', 417): 0,
   ('lit', 262): {('ite', 209): 0, ('ity', 698): 0},
   ('lize', 259): 0}},
 ('par',
  570): {('ara', 236): {('rac', 84): {('ace', 33): 0, ('acy', 60): 0},
   ('rade', 47): 0,
   ('rage', 56): 0,
   ('rate', 76): 0}, ('are', 39): {('rely', 26): 0, ('rene', 72): 0}, ('ari',
   31): {('rice', 30): 0,
   ('ride', 25): 0,
   ('rify', 24): 0,
   ('rily', 63): 0,
   ('rin', 156): {('ina', 24): 0, ('ine', 168): 0},
   ('rise', 146): 0,
   ('rit', 119): {('ite', 174): 0, ('ity', 118): 0},
   ('rize', 56): 0}, ('aro', 38): {('rome', 24): 0, ('rone', 35): 0}},
 ('ped',
  107): {('edi', 35): {('dine', 32): 0,
   ('dit', 73): {('ite', 50): 0, ('ity', 89): 0}}, ('edate', 29): 0},
 ('per',
  649): {('eri', 198): {('rice', 121): 0,
   ('ride', 56): 0,
   ('rify', 37): 0,
   ('rily', 26): 0,
   ('rin', 268): {('ina', 24): 0, ('ine', 168): 0},
   ('rise', 158): 0,
   ('rit', 173): {('ite', 174): 0, ('ity', 118): 0},
   ('rize', 51): 0}, ('erene', 20): 0},
 ('pol',
  384): {('ola', 22): {('lane', 27): 0,
   ('lary', 48): 0,
   ('late', 165): 0}, ('ole', 22): {('lene', 60): 0, ('lery', 39): 0}, ('oli',
   35): {('lide', 36): 0,
   ('lify', 24): 0,
   ('line', 72): 0,
   ('lise', 79): 0,
   ('lit', 234): {('ite', 209): 0, ('ity', 698): 0},
   ('lize', 22): 0}},
 ('rec', 342): {('eca', 24): {('case', 22): 0, ('cate', 41): 0},
  ('ecide', 28): 0,
  ('ecul', 35): {('ula', 29): 0, ('ule', 41): 0}},
 ('red',
  145): {('edi', 23): {('dine', 32): 0,
   ('dit', 73): {('ite', 50): 0, ('ity', 89): 0}}, ('edery', 29): 0, ('educe',
   22): 0},
 ('rel', 113): {('ela', 28): {('lane', 72): 0, ('late', 111): 0},
  ('eli', 47): {('lide', 23): 0,
   ('line', 126): 0,
   ('lise', 44): 0,
   ('lit', 43): {('ite', 209): 0, ('ity', 698): 0}}},
 ('rem',
  125): {('emi', 32): {('mine', 109): 0,
   ('mit', 58): {('ite', 64): 0, ('ity', 45): 0}}, ('emo',
   35): {('mony', 133): 0, ('more', 62): 0, ('mose', 29): 0, ('mote',
    35): 0}, ('emer', 26): {('ere', 24): 0, ('ery', 20): 0}},
 ('rep', 241): {('epo', 25): {('pore', 32): 0, ('pose', 50): 0},
  ('epate', 32): 0,
  ('epery', 40): 0},
 ('res',
  299): {('esi', 53): {('side', 44): 0,
   ('sine', 22): 0,
   ('sit', 25): {('ite', 61): 0, ('ity', 128): 0}}, ('esome', 37): 0},
 ('ret', 180): {('eta', 21): {('tary', 46): 0, ('tate', 45): 0},
  ('eti', 47): {('tice', 150): 0,
   ('tin', 71): {('ina', 22): 0, ('ine', 134): 0},
   ('tise', 60): 0,
   ('tite', 38): 0,
   ('tive', 24): 0,
   ('tize', 34): 0}},
 ('rev', 156): {('eve', 76): {('vely', 36): 0, ('very', 139): 0},
  ('evity', 44): 0},
 ('sal',
  178): {('ala', 20): {('lace', 67): 0,
   ('lane', 65): 0,
   ('lary', 31): 0,
   ('late', 58): 0}, ('ali', 47): {('lide', 26): 0,
   ('lify', 36): 0,
   ('line', 88): 0,
   ('lise', 417): 0,
   ('lit', 262): {('ite', 209): 0, ('ity', 698): 0},
   ('lize', 259): 0}},
 ('sol',
  154): {('ola', 21): {('lane', 27): 0,
   ('lary', 48): 0,
   ('late', 165): 0}, ('ole', 36): {('lene', 60): 0, ('lery', 39): 0}, ('oli',
   46): {('lide', 36): 0,
   ('lify', 24): 0,
   ('line', 72): 0,
   ('lise', 79): 0,
   ('lit', 234): {('ite', 209): 0, ('ity', 698): 0},
   ('lize', 22): 0}},
 ('uni', 217): {('nimal', 31): 0,
  ('nine', 62): {('ned', 88): 0, ('ner', 74): 0, ('net', 25): 0},
  ('niver', 25): 0},
 ('abor', 53): {('oral', 49): 0,
  ('ore', 35): {('red', 42): 0, ('rer', 28): 0},
  ('oric', 35): 0},
 ('acanic', 67): 0,
 ('acet', 75): {('etal', 23): 0, ('etic', 25): 0, ('eton', 22): 0},
 ('acid', 42): {('idal', 43): 0,
  ('ide', 43): {('ded', 20): 0, ('der', 40): 0, ('des', 38): 0},
  ('idic', 49): 0},
 ('adular', 37): 0,
 ('amen', 67): {('enal', 29): 0,
  ('ene', 23): {('ned', 50): 0, ('ner', 57): 0},
  ('enic', 40): 0},
 ('amor', 48): {('oral', 77): 0,
  ('ore', 23): {('red', 42): 0, ('rer', 28): 0},
  ('oric', 47): 0},
 ('aneman', 64): 0,
 ('anom', 78): {('oman', 71): 0, ('omer', 101): 0, ('omic', 115): 0},
 ('apos', 147): {('ose', 47): {('sed', 28): 0, ('ser', 26): 0},
  ('osis', 124): 0},
 ('aris', 60): {('ise', 24): {('sed', 42): 0, ('ser', 42): 0},
  ('ison', 43): 0},
 ('bala', 146): {('lace', 67): 0,
  ('lane', 65): 0,
  ('lary', 31): 0,
  ('late', 58): 0},
 ('baro', 236): {('rome', 24): 0, ('rone', 35): 0},
 ('basi', 125): {('sile', 22): 0,
  ('sine', 39): 0,
  ('sit', 24): {('ite', 61): 0, ('ity', 128): 0}},
 ('bene', 114): {('nery', 118): 0, ('nese', 644): 0},
 ('bili', 86): {('lify', 23): 0,
  ('line', 101): 0,
  ('lise', 47): 0,
  ('lit', 562): {('ite', 209): 0, ('ity', 698): 0},
  ('lize', 53): 0},
 ('camer', 119): {('ere', 24): 0, ('ery', 20): 0},
 ('comer', 549): {('ere', 24): 0, ('ery', 20): 0},
 ('coni', 1359): {('nide', 27): 0,
  ('nify', 35): 0,
  ('nine', 62): 0,
  ('nit', 108): {('ite', 200): 0, ('ity', 93): 0},
  ('nize', 113): 0},
 ('cove', 42): {('vely', 34): 0, ('very', 624): 0},
 ('cyanic', 28): 0,
 ('deno', 144): {('nomy', 43): 0, ('nose', 26): 0},
 ('desi', 262): {('side', 44): 0,
  ('sine', 22): 0,
  ('sit', 25): {('ite', 61): 0, ('ity', 128): 0}},
 ('dete', 122): {('tene', 65): 0,
  ('ter', 212): {('era', 35): 0, ('ery', 72): 0}},
 ('devity', 102): 0,
 ('dila', 59): {('lane', 54): 0, ('lary', 27): 0, ('late', 117): 0},
 ('dimi', 53): {('mine', 90): 0,
  ('mit', 62): {('ite', 64): 0, ('ity', 45): 0}},
 ('direly', 45): 0,
 ('domi', 56): {('mine', 149): 0,
  ('mit', 37): {('ite', 64): 0, ('ity', 45): 0}},
 ('evanic', 54): 0,
 ('fami', 31): {('mide', 42): 0,
  ('mine', 146): 0,
  ('mit', 36): {('ite', 64): 0, ('ity', 45): 0}},
 ('fili', 82): {('lify', 23): 0,
  ('line', 101): 0,
  ('lise', 47): 0,
  ('lit', 562): {('ite', 209): 0, ('ity', 698): 0},
  ('lize', 53): 0},
 ('firely', 69): 0,
 ('forely', 469): 0,
 ('habite', 35): 0,
 ('heli', 132): {('lide', 23): 0,
  ('line', 126): 0,
  ('lise', 44): 0,
  ('lit', 43): {('ite', 209): 0, ('ity', 698): 0}},
 ('herene', 192): 0,
 ('hete', 97): {('tene', 65): 0,
  ('ter', 212): {('era', 35): 0, ('ery', 72): 0}},
 ('holo', 96): {('logy', 825): 0, ('lose', 23): 0},
 ('hone', 48): {('nery', 30): 0, ('nese', 54): 0},
 ('humat', 98): {('ata', 37): 0, ('ate', 111): 0},
 ('hypery', 246): 0,
 ('icon', 26): {('onal', 20): 0, ('onic', 100): 0},
 ('iner', 181): {('era', 134): {('ral', 73): 0, ('ran', 28): 0},
  ('ere', 24): {('red', 165): 0, ('rer', 155): 0},
  ('eri', 34): {('ric', 75): 0, ('rin', 24): 0},
  ('eron', 27): 0},
 ('iron', 30): {('onal', 44): 0,
  ('one', 47): {('ned', 86): 0,
   ('ner', 85): 0,
   ('nes', 26): 0,
   ('net', 20): 0},
  ('onic', 94): 0},
 ('labite', 70): 0,
 ('lacele', 128): 0,
 ('lamer', 117): {('ere', 24): 0, ('ery', 20): 0},
 ('legate', 76): 0,
 ('lepine', 69): 0,
 ('levity', 57): 0,
 ('line', 113): {('nery', 80): 0, ('nese', 536): 0},
 ('lite', 157): {('tely', 34): 0,
  ('tene', 37): 0,
  ('ter', 89): {('era', 35): 0, ('ery', 72): 0}},
 ('live', 34): {('vely', 175): 0, ('very', 107): 0},
 ('magite', 115): 0,
 ('mani', 315): {('nify', 32): 0,
  ('nine', 34): 0,
  ('nit', 98): {('ite', 200): 0, ('ity', 93): 0},
  ('nize', 86): 0},
 ('mate', 139): {('tely', 117): 0,
  ('tene', 74): 0,
  ('ter', 153): {('era', 35): 0, ('ery', 72): 0}},
 ('medi', 100): {('dine', 32): 0,
  ('dit', 73): {('ite', 50): 0, ('ity', 89): 0}},
 ('megate', 61): 0,
 ('memo', 37): {('mony', 133): 0,
  ('more', 62): 0,
  ('mose', 29): 0,
  ('mote', 35): 0},
 ('meri', 125): {('rice', 121): 0,
  ('ride', 56): 0,
  ('rify', 37): 0,
  ('rily', 26): 0,
  ('rin', 268): {('ina', 24): 0, ('ine', 168): 0},
  ('rise', 158): 0,
  ('rit', 173): {('ite', 174): 0, ('ity', 118): 0},
  ('rize', 51): 0},
 ('mesome', 145): 0,
 ('mili', 127): {('lify', 23): 0,
  ('line', 101): 0,
  ('lise', 47): 0,
  ('lit', 562): {('ite', 209): 0, ('ity', 698): 0},
  ('lize', 53): 0},
 ('modery', 70): 0,
 ('moto', 77): {('tom', 169): {('oma', 22): 0, ('ome', 50): 0, ('omy', 99): 0},
  ('tone', 35): 0,
  ('tory', 32): 0},
 ('myri', 56): {('rin', 25): {('ina', 24): 0, ('ine', 168): 0},
  ('rit', 25): {('ite', 174): 0, ('ity', 118): 0}},
 ('nati', 66): {('tice', 187): 0,
  ('tify', 43): 0,
  ('til', 25): {('ile', 79): 0, ('ily', 37): 0},
  ('tin', 230): {('ina', 22): 0, ('ine', 134): 0},
  ('tise', 129): 0,
  ('tite', 52): 0,
  ('tive', 517): 0,
  ('tize', 59): 0},
 ('nema', 37): {('mary', 23): 0,
  ('mat', 208): {('ata', 37): 0, ('ate', 111): 0}},
 ('odon', 38): {('onal', 31): 0, ('onic', 39): 0},
 ('oper', 49): {('era', 149): {('ral', 73): 0, ('ran', 28): 0},
  ('ere', 69): {('red', 165): 0, ('rer', 155): 0},
  ('eri', 346): {('ric', 75): 0, ('rin', 24): 0},
  ('eron', 59): 0},
 ('opin', 52): {('inal', 38): 0,
  ('ine', 43): {('ned', 88): 0, ('ner', 74): 0, ('net', 25): 0},
  ('inic', 54): 0},
 ('over', 504): {('era', 70): {('ral', 73): 0, ('ran', 28): 0},
  ('ere', 86): {('red', 165): 0, ('rer', 155): 0},
  ('eri', 69): {('ric', 75): 0, ('rin', 24): 0}},
 ('pate', 159): {('tely', 117): 0,
  ('tene', 74): 0,
  ('ter', 153): {('era', 35): 0, ('ery', 72): 0}},
 ('peni', 247): {('nine', 59): 0,
  ('nit', 112): {('ite', 200): 0, ('ity', 93): 0},
  ('nize', 33): 0},
 ('peta', 124): {('tary', 46): 0, ('tate', 45): 0},
 ('pipery', 36): 0,
 ('pota', 80): {('tary', 32): 0, ('tate', 52): 0},
 ('puri', 117): {('rice', 23): 0,
  ('rify', 27): 0,
  ('rin', 71): {('ina', 24): 0, ('ine', 168): 0},
  ('rise', 89): 0,
  ('rit', 50): {('ite', 174): 0, ('ity', 118): 0},
  ('rize', 22): 0},
 ('radi', 73): {('dine', 58): 0,
  ('dit', 21): {('ite', 50): 0, ('ity', 89): 0}},
 ('rati', 71): {('tice', 187): 0,
  ('tify', 43): 0,
  ('til', 25): {('ile', 79): 0, ('ily', 37): 0},
  ('tin', 230): {('ina', 22): 0, ('ine', 134): 0},
  ('tise', 129): 0,
  ('tite', 52): 0,
  ('tive', 517): 0,
  ('tize', 59): 0},
 ('regen', 119): {('ene', 20): 0, ('eny', 35): 0},
 ('romat', 41): {('ata', 37): 0, ('ate', 111): 0},
 ('rosely', 66): 0,
 ('rubi', 60): {('bine', 24): 0, ('bite', 20): 0},
 ('sati', 63): {('tice', 187): 0,
  ('tify', 43): 0,
  ('til', 25): {('ile', 79): 0, ('ily', 37): 0},
  ('tin', 230): {('ina', 22): 0, ('ine', 134): 0},
  ('tise', 129): 0,
  ('tite', 52): 0,
  ('tive', 517): 0,
  ('tize', 59): 0},
 ('secul', 95): {('ula', 29): 0, ('ule', 41): 0},
 ('selene', 69): 0,
 ('semi', 211): {('mine', 109): 0,
  ('mit', 58): {('ite', 64): 0, ('ity', 45): 0}},
 ('sepate', 104): 0,
 ('seve', 22): {('vely', 36): 0, ('very', 139): 0},
 ('sidery', 39): 0,
 ('sili', 107): {('lify', 23): 0,
  ('line', 101): 0,
  ('lise', 47): 0,
  ('lit', 562): {('ite', 209): 0, ('ity', 698): 0},
  ('lize', 53): 0},
 ('supery', 351): 0,
 ('telene', 122): 0,
 ('terene', 155): 0,
 ('unaced', 205): 0,
 ('uranic', 42): 0,
 ('vale', 78): {('lene', 90): 0, ('lery', 26): 0},
 ('vapo', 25): {('poda', 36): 0, ('pore', 40): 0, ('pose', 35): 0},
 ('vari', 67): {('rice', 30): 0,
  ('ride', 25): 0,
  ('rify', 24): 0,
  ('rily', 63): 0,
  ('rin', 156): {('ina', 24): 0, ('ine', 168): 0},
  ('rise', 146): 0,
  ('rit', 119): {('ite', 174): 0, ('ity', 118): 0},
  ('rize', 56): 0},
 ('vene', 111): {('nery', 118): 0, ('nese', 644): 0},
 ('visi', 58): {('sine', 79): 0,
  ('sit', 53): {('ite', 61): 0, ('ity', 128): 0}},
 ('volute', 92): 0,
 ('wate', 56): {('tely', 117): 0,
  ('tene', 74): 0,
  ('ter', 153): {('era', 35): 0, ('ery', 72): 0}},
 ('xylogy', 50): 0}

from ctypes import cast, py_object
from functools import lru_cache
                                                   
@lru_cache(maxsize=None)                           
def remap_key(addr):                               
    d = dict()                                     
    obj = cast(addr, py_object).value
    for k, v in obj.items():                       
        if isinstance(v, dict):                    
            v = remap_key(id(v))                   
        d[f'{k!r}'] = v                            
    return d                                       

def remap_key_(obj):           
    d = dict()                 
    for k, v in obj.items():   
        if isinstance(v, dict):
            v = remap_key_(v)  
        d[f'{k!r}'] = v        
    return d                   

In [20]: %timeit remap_key_(tree)
767 µs ± 35.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [21]: %timeit remap_key(id(tree))
184 ns ± 2.84 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [22]: remap_key(id(tree)) == remap_key_(tree)
Out[22]: True

Obviously if the object changes then the result will be wrong, but then all other techniques of memoizing mutable objects suffer the same problem.

Ξένη Γήινος
  • 2,181
  • 1
  • 9
  • 35