26

私は次のメモ化デコレータを使用しています（すばらしい本Python Algorithmsから：Python言語で基本的なアルゴリズムをマスターする...それが大好きです、ところで）。

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

これは、可変引数を取る関数のcPickleを使用してメモ化デコレータを作成する方法を示すAlex Martelli Python Cookbookの例です（元のバージョン）：

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]

ここにリンクがあります。

編集：あなたが与えたコードとこれをメモ化するデコレータを使用して：

_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技術的には、 （またはlistまたはset）をタプルに変換することでこの問題を解決できます。例えば：

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

 cache[key] = func( .. )

しかし、私はこれを行いません。memoメモを使用する関数を変更したいと思います。たとえば、リストやセットを取得する代わりに、ペアdictのみを受け入れる必要があります。(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

他の誰もそれについて言及していないので、PythonWikiには多くのメモ化デコレータパターンを含むデコレータライブラリがあります。

私の個人的な好みは最後のものです。これにより、コードを呼び出すと、メソッドがメソッドではなく、遅延評価されたプロパティとして扱われるようになります。しかし、私はここでの実装の方が好きです。

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パッケージを見つけました。

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

  • 使いやすい
  • ハッシュできない引数を使用することが可能
  • その他の便利なオプション（存続時間）
于 2020-01-01T11:58:26.230 に答える
0

このサイトはグーグルの検索結果で目立つので、自分で問題を解決しようとしてこの質問に出くわしましたが、残念ながらどれも満足のいくものではなかったので、自分で方法を開発して共有したいと思います。

私はこの質問が古いことを知っていますが、私の解決策は非常に新しいものです。

では、変更可能でハッシュ化できないオブジェクトを受け取る関数をどのようにメモ化するのでしょうか。

簡単な答え：あなたはしません。では、あなたはこの答えが何であるかを考えているのを知っていますか？

ハッシュ不可能なオブジェクトを処理して最大のパフォーマンスを得る関数をメモ化するために、オブジェクト自体を渡すことは絶対にできませんが、代わりに、ポインターがそのオブジェクトを指すことを保証する、そのオブジェクトへのハッシュ可能なポインターがあります。

説明させてください。Pythonのメモ化は辞書にdict基づいており、sに基づいていhashmapます。つまり、キーはハッシュ可能でなければなりません。可変オブジェクトはハッシュできないため、可変引数を取る関数をメモ化するには、引数を不変にする必要があります。

これが重要な部分です。可変オブジェクトを不変化しようとすると、変換のオーバーヘッドが原因でパフォーマンスが低下します。したがって、それらを不変にしようとしてはなりません。

今ハックが来ます。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 に答える