Archives of learned topics

Lesson 4- 17: Calculating Costs

下記の定義のようなTupleがあり、最後から2眼目の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

目次


問題のイメージ


良くありがちな、二つの容器を使用して特定の分量を測定してくださいという問題。 問題を解く方向性としては、探索問題となる。 Imgur
既に探索した領域を記憶し、新たな領域を探索するイメージ

実装

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とは
  • 実装
    • 逆算法
    • 2分探査

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

この場合、検索のポインタxがdeltaずつしか増加しないため、yの数を大きくすると検索回数が増大する。

2分探査

逆算出は単純に0から順に検索していたので、検索に時間を要した。 そのため、目的の値(x)を挟む2つの値から2分探査を用いて検索することで時間短縮をすることが可能。 Imgur

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)

ちょうどこんなイメージ f:id:jsakusan:20170512223730p:plain

【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

このように、スワイプ処理を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)

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

実行してみる。

起動

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

関数の計算

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

数値が返る

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

まとめ

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

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