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)

ちょうどこんなイメージ

【Python】複数代入について

複数代入とは下記のようなことを言っているつもりです。

>>a, b = 1, 2
>>a
1
>>b
2

複数の変数に一行の式で代入が行えること。

スワイプが一行で書ける！！

int a = 1;
int b = 2;

int temp = a;
a = b;
b = temp;

System.out.print(a + "," + b)

と記述する必要があったスワイプ処理、 Pythonだと下記のように記述可能。

t, s = 1, 2 
print(t, s) # 1, 2
t, s = s, t # ※
print(t, s) # 2, 1

このように、スワイプ処理を１行で記述可能。 (※)の部分でスワイプ処理を行う前に、t, sの値を評価しているため t, s = 2, 1となっている。 かなり手抜きができるのがいいね。

Pythonでのメモリ使用状況をリアルタイムで表示（初級）

Pythonプログラムのメモリ使用方法（初級）をurseraの講座で解説していたので、メモしておく。

使用サイト

・ Python Tutor - Visualize Python, Java, JavaScript, TypeScript, Ruby, C, and C++ code execution　-> リアルタイムでメモリの使用状況が分かるサイト

使用スクリプト

def convert_to_minutes(num_hours):
    '''(int) -> int
    Reteurn the number of minutes there are in number
    >>> convert_to_minutes(2)
    120
    '''
    
    result = num_hours * 60
    return result
    
minutes_2 = convert_to_minutes(2)
minutes_3 = convert_to_minutes(3)

講座ので使用していたスクリプトと全く同じです。

実行してみる。

起動

Frame -> stack領域の状況を示しています。現在は、convert_to_minutes(2)のみがスタックされています(Global Frame)。
Object -> heap領域の状況。Function:convert_to_minutesのソース情報、引数情報などが格納されています。
※FrameとObjectはid（番地）によって関連づけられています。

関数の計算

num_hours、result、return valueが変数としてスタック領域に用意さる(Local Frame)。 この時それぞれの数値本体は、heap領域に存在します。変数のみがstackにあるイメージです。

数値が返る

convert_to_minutes(2)の計算が終了したことで、Local Frameが解放され、返り値のみがminutes_2に渡される。 この時、数値本体はheap領域にある。

まとめ

・stack領域は変数を用意する場所。呼び出し順を保持している。（Stackなので当たり前） ・それに対して、数値自体はheap領域に存在する。 ・stack領域の変数とheap領域の数値は別途idで結び付けられている。

これまでよく理解できていなかった、アプリ実行中にメモリの利用方法が少しわかった。