アルゴリズムの計算量を求める。

アルゴリズムの計算量は以下の様に
O(n)
O(n²)
と記述を行う。

アルゴリズムの計算量を計算できると、処理の速度の比較を行うことが出来る。 計算量を計算することで、アルゴリズムの比較を大雑把に行うことが可能になる。

具体的なことに関しては以下に具体的にまとめられていおり、かなり分かりやすい。

qiita.com

ざっくり言えば、

• forやwhileの繰り返しの分だけnが階乗されていく。
• i = i * 2の場合はO(log x)となる。

bash on ubuntu on windows でCドライブを扱うには

Cドライブの場所

bash on ubuntu on windows では起動時した状態ではCドライブの場所が分からなかった。 しかし、/mntにCドライブをマウントしているようだ。

qiita.com

そのため、cd /mnt/cと打てばCドライブに移動が出来る。

Windows上で簡易に操作を行うにはlnでリンクを作成しておけばいい。

Lessen6-7:Extend Prefix

ポイント

・再帰検索時の検索結果の格納 　再帰を用いた検索で、各末端での検索結果を最上段の関数に返す場合は、基本的にreturnを使用して値の返しを行う。

def foo(x):
   if x > 100:
      return x
   else:
      return x + foo(x + 1)

しかし、ひとつの関数で複数の結果を生成し、それを最上段に返さなければいけない時「参照渡し」を利用すれば簡単に行える。

def find_words(letters):
    extend_prefix(letters)

def extend_prefix(letters, w='', results=None):
    if results: results = set()
    if w in WORDS: results.add(w)
    if w in PREFIXES:
        for L in letters: extend_prefix(w + L, letters.replace(L, '', 1))
    return results

resultがset()なので、extend_prefix()で参照渡しされる。 よって、結果は最上段のresultに格納される。

Lesson1-25:Allmax

ポイント

keyでFunctionを指定する際に、初期入力がNoneの時の対象法

Key指定時の注意点

pythonにおいてmax(a, key=function)など、基準として関数を指定することが可能。 このような関数を独自で実装するとき、key指定がない場合のfunctionをどうするかが問題になる。 この時lambda関数をデフォルト指定にしたい場合の実装をまとめる。

def allmax(iterable, key=None):
    "Return a list of all items equal to the max of the iterable."
    result, maxval = [], None
    key = key or (lambda x: x) # keyがNoneの場合、lambdaを指定する。
    for x in iterable:
        xval = key(x)
        if not result or xval > maxval:
            result, maxval = [x], xval
        elif xval == maxval:
            result.append(x)
    return result

Lesson1-7:UsingMax

今回のポイント

MaxはKeyにFunctionを指定することが出来る。指定されたFunctionは最大値算出時にMapのように一つずつ値を算出し、比較をしすることで最大値を算出する。

例

def poker(hands):
    "Return the best hand; poker([hand, ...]) => hand"
    return max(hands, key=hand_rank) # hand_rankを評価基準にして最大値を算出する。

def hand_rank(hand):
    pass

Lesson1-3:Outlining The Problem

はじめに

Design of Computer ProgramsのLesson1-3についてまとめる。

ここでの目標

今回作成するのは、ポーカーの手札を複数引数として取り込んで、そのなかから一番いい手を返すプログラム。

Dependency Injection

はじめに

---

Dependency Injectionについて自分なりにまとめてみる。 (Dependency Injection コンテントにつていは記述していません。) 修正箇所があれば、Updateをしていく。

そもそも

---

Dependency Injection(DI)をWikiで調べてみると…

コンポーネント間の依存関係をプログラムのソースコードから排除し、外部の設定ファイルなどで注入できるようにするソフトウェアパターンである。英語の頭文字からDIと略される。 依存性の注入 - Wikipedia

簡単に言うと、下記の様にクラス内でインスタンス発行（定数など）をせずに、引数として渡しましょうと言っているだけ。 なのに名前が仰々しすぎる…

非DIコード

import random

possible_moves = ['roll', 'hold']
other = {1: 0, 0: 1}
goal = 50


def clueless(state):
    "A strategy that ignores the state and chooses at random from possible moves."
    return random.choice(possible_moves)


def hold(state):
    """Apply the hold action to a state to yield a new state:
    Reap the 'pending' points and it becomes the other player's turn."""
    (p, me, you, pending) = state
    return (other[p], you, me + pending, 0)


def roll(state, d):
    """Apply the roll action to a state (and a die roll d) to yield a new state:
    If d is 1, get 1 point (losing any accumulated 'pending' points),
    and it is the other player's turn. If d > 1, add d to 'pending' points."""
    (p, me, you, pending) = state
    if d == 1:
        return (other[p], you, me + 1, 0)  # pig out; other player's turn
    else:
        return (p, me, you, pending + d)  # accumulate die roll in pending


def play_pig(A=clueless, B=clueless):
    """Play a game of pig between two players, represented by their strategies.
    Each time through the main loop we ask the current player for one decision,
    which must be 'hold' or 'roll', and we update the state accordingly.
    When one player's score exceeds the goal, return that player."""
    # your code here
    strategies = [A, B]
    state = (0, 0, 0, 0)

    while True:
        (p, me, you, _) = state
        if me >= goal:
            return strategies[p]
        elif you >= goal:
            return strategies[other[p]]
        elif strategies[p](state) == 'roll':
            state = roll(state, random.randint(1, 6)) #randomが毎回変わるのでテストができない・・・
        else:
            state = hold(state)

def always_roll(state):
    return 'roll'


def always_hold(state):
    return 'hold'

DIにする。 変更部分のみを記述。

def dierolls():
    "Generate die rolls."
    while True:
        yield random.randint(1, 6)

def play_pig(A=clueless, B=clueless, die=dierolls()): # generaterは、dierolls()の様に括弧付きでよい。
    """Play a game of pig between two players, represented by their strategies.
    Each time through the main loop we ask the current player for one decision,
    which must be 'hold' or 'roll', and we update the state accordingly.
    When one player's score exceeds the goal, return that player."""
    # your code here
    strategies = [A, B]
    state = (0, 0, 0, 0)

    while True:
        (p, me, you, _) = state
        if me >= goal:
            return strategies[p]
        elif you >= goal:
            return strategies[other[p]]
        elif strategies[p](state) == 'roll':
            state = roll(state, next(die))
        else:
            state = hold(state)