7-33. Quiz: Cache Management

目次

• MEMO化について
• MEMOのデコレータ
• Hash TableにListは入れられない？？

MEMO化について

C101においても、プログラムの高速化にメモ化を使用する場面があった。コードは下記のようである。

memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    else:
        memo[n] = result = n * fib(n - 1)
        return result

このようなメモ化はfibの様に再帰処理を行う関数において高速化を行う事が可能であるため、よく用いられる。 再帰がある度にこのコードが書かれるのだ。ここでDRYの法則違反していることが分かる。 DRYの法則を満たすために、デコレーターを作成することにする。

MEMOのデコレータ

---

メモのデコレータを作成してみる。

@decorater
def memo(f):
    """
  Decorator that caches the return value for each call to f(args).
  Then when called again with same args, we can just look it up.
  """
    cache = {} #->cacheは宣言を外でしていてもよい。
    def _f(*args):
        try:
            return cache[args]
        except KeyError:
            cache[args] = result = f(*args)
            return result
        except TypeError:
            return f(args)
    return _f

Hash TableにListは入れられない？？

Hash Tableに数字が入っているかを評価する場合には通る。 しかし、listがHash上にあるかを評価すると、Errorとなる。

a = {}
x = 42
x in d #->False

y = [1,2,3,4]
y in d #-> TypeError: unhashable type:list

これは、listが変更可能なオブジェクトであるためHash TableのKeyとすることができないため。 listでなくTupleならば問題ない。

しかし、([1,2,3,4], 5)はエラーとなる。

a = {}
b = ([1,2,3,4], 5)
a[b] = 'c' # => TypeError: unhashable type:list

なぜなら、TupleにListが入っているように見えるが実際Tupleが保持しているのは Listの参照メモリ。よって、書き換えが可能。

a = {}
b = ([1,2,3,4], 5)
# a[b] = 'c'
b[0][1] = 100
print(b)# => ([1,100,3,4], 5)

ちょうどこんなイメージ