26

我一直在使用以下 memoizing 装饰器（来自伟大的书 Python Algorithms: Mastering Basic Algorithms in the Python Language ... 喜欢它，顺便说一句）。

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

这个装饰器的问题是基于字典的缓存意味着我所有的参数都必须是可散列的。

有没有人有允许不可散列参数（例如字典）的实现（或对此进行调整）？

我知道缺少哈希值意味着“这是在缓存中吗？”的问题。变得不平凡，但我只是想我会问。

===已编辑以提供上下文===

我正在研究一个函数，它返回一个 Parnas 风格的“使用层次结构”，给定一个模块字典：依赖项。这是设置：

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

以便：

>>> 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 是我想记住的功能，以使此设置更具可扩展性。在没有记忆的情况下实现，它会多次计算依赖级别（例如，在上面的示例中，我认为“a”计算了 8 次）。

谢谢，

麦克风

4

6 回答 6

16

这是 Alex Martelli Python Cookbook中的示例，该示例展示了如何使用cPickle为采用可变参数的函数创建 memoize 装饰器（原始版本）：

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]

这是一个链接。

编辑：使用您给出的代码和这个 memoize 装饰器：

_level = MemoizeMutable(_level)

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

print uses_hierarchy(equirements)

我能够重现这个：

miss
miss
hit
miss
miss
hit
miss
hit
hit
hit
miss
hit
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']}
于 2011-01-12T14:12:25.443 回答
7

从技术上讲，您可以通过将dict(or listor set) 转换为元组来解决此问题。例如：

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

 cache[key] = func( .. )

但我不会在 中这样做memo，我宁愿更改您要在备忘录上使用的功能 - 例如，与其接受 adict他们应该只接受(key, value)对，而不是接受他们应该只接受的列表或集合*args。

于 2011-01-12T14:09:43.673 回答
2

没有经过大量测试，但似乎有效：

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
于 2011-01-12T14:17:58.533 回答
2

由于没有人提到它，Python Wiki 有一个装饰器库，其中包含许多记忆装饰器模式。

我个人的偏好是最后一个，它让调用代码简单地将方法视为延迟评估的属性，而不是方法。但我更喜欢这里的实现。

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

在上面链接的同一个文件中，还有一个lazy_dict装饰器，它允许您将函数视为具有延迟评估值的字典。

于 2015-08-20T13:35:18.740 回答
0

我试图自己解决这个问题并遇到了这个问题，因为这个网站在谷歌搜索结果中很突出，但很遗憾没有一个答案令人满意，所以我自己开发了一个方法，我想分享一下。

我知道这个问题很老，但我的解决方案很新。

那么你如何记忆那些采用可变的、不可散列的对象的函数呢？

简短的回答：你不知道。我知道你在想这个答案是关于什么的，那么？

好吧，要记住处理不可散列对象并从中获得最大性能的函数，您绝对不能传递对象本身，而是一些指向该对象的可散列指针，以保证该指针将指向该对象。

让我解释一下，Python memoization 是基于字典的，并且dict是基于hashmaps 的，简而言之，键必须是可散列的。可变对象是不可散列的，因此为了记忆带有可变参数的函数，您必须使参数不可变。

现在是关键部分，任何使可变对象不可变的尝试都会因为转换开销而降低性能。所以你不能试图让它们不可变。

现在是黑客攻击。Python 将名称重新绑定到对象，Python 创建对象并将字符串映射到该对象，重新分配一个新变量只是为该对象添加一个新名称，并且一旦创建的文字不可变对象将不会再次创建。

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

什么名称可以保证对每个对象都是唯一且不可更改的？它们id，这只是该对象的内存地址，并发对象将具有不同的内存地址，但具有非重叠生命周期的对象可能具有相同的地址，但这种可能性非常小。

简而言之，为了记忆处理不可变对象的函数，您不能直接传递对象，而是传递它们的当前 ID。

但是如何从 id 中取回对象呢？使用ctypes.

例子：

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

显然，如果对象发生变化，那么结果将是错误的，但是所有其他记忆可变对象的技术都会遇到同样的问题。

于 2021-11-06T08:05:25.577 回答
0

我已经搜索并找到了一个很好的 python 包。

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

  • 便于使用
  • 可以使用不可散列的参数
  • 其他有用的选项（生存时间）
于 2020-01-01T11:58:26.230 回答