DSUとメモ化

Python

DSUは結局、valueからkeyを取り出すfoo(value) ⇒ keyという関数があり、それをメモ化しているのと同じ意味だと思った。同じになるか実験してみた。

import time

def memoize(func):
    D = {}
    def f(*args):
        if args in D:
            return D[args]
        res = func(*args)
        D[args] = res
        return res
    return f

class Elem(object):
    def __init__(self, id):
        self.__id = id
    def __getattr__(self, attr):
        if attr == 'id':
            time.sleep(1)
            return self._Elem__id

@memoize
def getId(el):
    return el.id

e1, e2, e5, e10 = Elem(1), Elem(2), Elem(5), Elem(10)
L = [e1, e5, e10, e2]

t = time.time()
L.sort(lambda e1, e2: cmp(e1.id, e2.id))          # 工夫なし
print time.time() - t, 'sec'

t = time.time()
L.sort(key=lambda el: el.id)                      # DSU
print time.time() - t, 'sec'

t = time.time()
L.sort(lambda e1, e2: cmp(getId(e1), getId(e2)))  # メモ化
print time.time() - t, 'sec'

実行結果:

10.0 sec
4.0 sec
4.0 sec

結果は当然DSUとメモ化で同じ(くらいの)パフォーマンスになった。この最初に初期化するという考え方は実際のコーディングでもよく使うが、このテクニック自体にも名前があれば分かりやすい。存在しないのだろうか？メモ化は、結局「関数と引数 ⇒ 返値」のハッシュであると思うが、用語の範囲としては以外と狭い気がする…。