Lesson 4- 17: Calculating Costs
下記の定義のようなTupleがあり、最後から２眼目のtotal_costが欲しい。 この場合、一旦変数にいれてやると、可読性が上がる。
tupleの定義
path = [state, (action, total_cost), state, ....]
コード
def path_cost(path) if len(path) < 3: return 0 else: action, total_cost = path[-2] return total_cost
Lesson4-4: Pouring Problem
目次
問題のイメージ
良くありがちな、二つの容器を使用して特定の分量を測定してくださいという問題。
問題を解く方向性としては、探索問題となる。
既に探索した領域を記憶し、新たな領域を探索するイメージ
実装
def pour_problem(X, Y, goal, start=(0, 0)): """ X and Y are the capacity oc glasses; (x, y) is current fill levels and represents a state. Hte goal is a level that can be in either glass. Start at start state and follow successors until we reach the goal. Keep track of frontier and previously explored; fail when no frontier """ if goal in start: return [start] explored = set() # set of states we have visited frontier = [[start]] # ordered list of paths we have blazed while frontier: path = frontier.pop(0) (x, y) = path[-1] for (state, action) in successors(x, y, X, Y).items(): if state not in explored: # the successors state has not be explored(don't re-explored) explored.add(state) path2 = path + [action, state] if goal in path2: return path2 else: frontier.append(path2) return Fail Fail = [] def successors(x, y, X, Y): assert x <= X and y <= Y return {(0, x + y) if x + y < Y else (x - (Y - y), y + (Y - y)) : 'x => y', (x + y, 0) if x + y < X else (x + (X - x), y - (X - x)) : 'x <= y', (x, Y): 'fill up y', (X, y): 'Fill up x', (0, y): 'empty y', (x, 0): 'empty x'} print(pour_problem(10, 12, (10, 6)))
Problem set 3: 2_Quiz_Inverse_Function
目次
- Inverse Functionとは
- 実装
- 逆算法
- ２分探査
Inverse Functionとは
まずは、関数の定義から見てみる。
あるy = f(x)に対して、xを求めるようなf'(y)のことである。
ex) f(x) = x ** 2 f'(x) = sqrt(y)
こんな関数を実装していく。
実装
逆算方
f(x)を0から順番に計算していき、yに近似するまでループする。
def Inverse(f ,delta=1/285.): """ Given a function y = f(x) that is monotonically increasing function on no-negative numbers, return the function x = f_1(y) that is an approximate inverse """ def _f(y): x = 0 while f(x) < y: x = x + delta return x if (f(x) - y < y - f(x-delta)) else x-delta return _f
この場合、検索のポインタｘがdeltaずつしか増加しないため、yの数を大きくすると検索回数が増大する。
２分探査
逆算出は単純に０から順に検索していたので、検索に時間を要した。
そのため、目的の値(x)を挟む２つの値から2分探査を用いて検索することで時間短縮をすることが可能。
def Inverse_quick(f, delta=1/285): def _f(y): lo, hi = find_bounds(f, y) return binary_search(lo, hi, f, y, delta) return _f def find_bounds(f, y): x = 1 while f(x) <= y: x *= 2 return (0, 1) if x == 1 else (x/2, x) def binary_search(lo, hi, f, y, delta): while lo < hi: mid = (lo + hi) / 2 if y > f(mid): lo = mid + delta elif y < f(mid): hi = mid - delta else: return mid return lo if (y - f(lo) < f(hi) - y) else hi def square(x): return x * x sqrt = Inverse_quick(square) print(sqrt(100))
7-35. Trace_Tool
目次
これまでに作成したデコレータ
- DEBUGGING TOOL
- countcall
- trace <- New!!
- PERFORMANCE TOOL
- memo
- EXPRESSION TOOL
- n_ary
Trace Tool
関数の実行のされ方がVisualizeされるデコレータ。
--> fib(6) --> fib(5) --> fib(4) --> fib(3) --> fib(2) --> fib(1) <-- fib(1) == 1 --> fib(0) <-- fib(0) == 1 <-- fib(2) == 2 --> fib(1) <-- fib(1) == 1 <-- fib(3) == 3 --> fib(2) --> fib(1) <-- fib(1) == 1 --> fib(0) <-- fib(0) == 1 <-- fib(2) == 2 <-- fib(4) == 5 --> fib(3) --> fib(2) --> fib(1) <-- fib(1) == 1 --> fib(0) <-- fib(0) == 1 <-- fib(2) == 2 --> fib(1) <-- fib(1) == 1 <-- fib(3) == 3 <-- fib(5) == 8 --> fib(4) --> fib(3) --> fib(2) --> fib(1) <-- fib(1) == 1 --> fib(0) <-- fib(0) == 1 <-- fib(2) == 2 --> fib(1) <-- fib(1) == 1 <-- fib(3) == 3 --> fib(2) --> fib(1) <-- fib(1) == 1 --> fib(0) <-- fib(0) == 1 <-- fib(2) == 2 <-- fib(4) == 5 <-- fib(6) == 13
# --------------- # User Instructions # # Modify the function, trace, so that when it is used # as a decorator it gives a trace as shown in the previous # video. You can test your function by applying the decorator # to the provided fibonnaci function. # # Note: Running this in the browser's IDE will not display # the indentations. from functools import update_wrapper def decorator(d): "Make function d a decorator: d wraps a function fn." def _d(fn): return update_wrapper(d(fn), fn) update_wrapper(_d, d) return _d @decorator def trace(f): indent = ' ' def _f(*args): signature = '%s(%s)' % (f.__name__, ', '.join(map(repr, args))) print ('%s--> %s' % (trace.level*indent, signature)) trace.level += 1 try: result = f(*args) #->関数はここで呼ばれる。再帰なので末尾に到着するまでreturnはなし。 print ('%s<-- %s == %s' % ((trace.level-1)*indent, signature, result)) finally: trace.level -= 1 return result trace.level = 0 return _f @trace def fib(n): if n == 0 or n == 1: return 1 else: return fib(n-1) + fib(n-2) fib(6) #running this in the browser's IDE will not display the indentations!
trace.level += 1しているが、f(*args)にてエラーになった際に元の位置に戻れるようにTry-Finallyにしている。
7-33. Quiz: Cache Management
目次
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で結び付けられている。
これまでよく理解できていなかった、アプリ実行中にメモリの利用方法が少しわかった。
