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
Answers:
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
Method 1
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']}
Method 2
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.
Method 3
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
Method 4
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.
Method 5
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)
Method 6
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.
All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0