ラベル Python の投稿を表示しています。 すべての投稿を表示
ラベル Python の投稿を表示しています。 すべての投稿を表示

2012年9月21日金曜日

Pythonで独自ソートの実装

Pythonのリストにあるsortメソッドは、自然な順序でソートしてくれるものであるが、そうではないソートを行いたいときがある。そのようなソートを行うには、sortメソッドに比較のための関数を渡してやればよい。まずは、比較によく用いられる関数を見てみよう。

>>> help(cmp)
Help on built-in function cmp in module __builtin__:

cmp(...)
    cmp(x, y) -> integer
    
    Return negative if xy.
>>> help(list.sort)
Help on method_descriptor:

sort(...)
    L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
    cmp(x, y) -> -1, 0, 1
>>> help(sorted)
Help on built-in function sorted in module __builtin__:

sorted(...)
    sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list

cmp関数は2つの引数を評価した結果を返すというものである。第1引数が第2引数より小さければ負、同じなら0、大きければ正の値を返すようになっている。

リストのsortメソッドには3つの引数を与えることができる。cmpは比較のための関数である。keyはソートの基準となる対象を指定するものである。例えば文字列のソートで2文字目以降でソートしたいという場合にはlambda x:x[1:]とすることになる。この場合、xはソート対象となるオブジェクトに相当する。reverseは昇順・降順を指定するものである。デフォルトでは昇順に並べることになる。

sortedは反復可能なオブジェクトであれば、ソートすることができる。例えば、辞書のvalueで辞書をソートするときにはこれを利用するとよい。cmpなどのオプションはlist.sortと同様の意味を持つ。

これを踏まえて、以前Javaでも書いた文字列の長さ順にソートするということを行ってみる。なお、sortメソッドはstable sort(安定なソート)なので、同じ値(=文字列の長さが同じ)が複数ある場合は、先に出てきたものが先に並べられるようになっている。

# -*- encoding: utf-8 -*-

def cmp_len(s1, s2):
    return cmp(len(s1), len(s2)) # 文字列の長さで比較するための関数

langs = ["Python", "LISP", "Haskell", "C", "Java"]

langs.sort(cmp=cmp_len, reverse=True)
print langs #徐々に文字列の長さが短くなっていくリストになる

dic = {"NumPy":"numerical analysis",
       "sphinx":"documentation generator",
       "django":"web"}

sdic = sorted(dic.items(), cmp=cmp_len, key=lambda x:x[1])
# 説明文が短い順に並べ替えられている
print sdic

表示される結果は次の通り。

['Haskell', 'Python', 'LISP', 'Java', 'C']
[('django', 'web'), ('NumPy', 'numerical analysis'), ('sphinx', 'documentation generator')]

2012年9月16日日曜日

ウォリスの公式

PythonでWallisの公式を書いてみました。Wallisの公式は円周率を多項式を利用して近似するものです。元ネタはPython Scientific lecture noteの英語版(2012年8月リリース)19ページの練習問題になります。実行結果を見てみると、引数の値を大きくするにつれて、円周率に近づいている様子が確認できます。ちなみにnumは数字というよりもnumerator(分子)のつもりです、念のため。

def wallis_formula(n):
    mypi = 1
    for i in range(1, n):
        num = 4*(i**2)
        mypi *= float(num)/(num-1)
    return 2 * mypi

'''
>>> wallis_formula(1000)
3.1408069608284657
>>> wallis_formula(10000)
3.1415141108281714
>>> wallis_formula(100000)
3.141584799578707
>>> wallis_formula(1000000)
3.1415918681913633
'''

2012年9月13日木曜日

Pythonでクイックソート実装

Scipyを学習するためのノートPython Scientific lecture notesというものが公開されています。英語版pdfはこちらの右上にあるDownloadsのところにあるpdfへのリンクを、日本語版pdfはこちらの上部にある印刷用のダウンロード書かれた横のpdfへのリンクをクリックすると読むことができます。ただし、(記事執筆時点では)日本語版は最新版ではないようです。

本日は英語版のノート24ページにある、Wikipediaのクイックソートの説明文(擬似コード)を実際のプログラムに変換せよという問題を解いてみました。以下、私の解答です。

# -*- encoding: utf-8 -*-

def quick_sort(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot = array.pop(len(array)/2)
    less = []
    greater = []
    for x in array:
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

ピボットの選び方は簡単のため、リストの中央の位置にある値にしていますが、それ以外にも方法があります。例えば、中央の位置と両端の3つの値に対する中央値をピボットにするという方法があります。これは、クイックソートの性能はピボットの選び方に依存するためです。

極端ではありますが、毎回ピボット以下の値になるグループのデータ数が0、ピボットより値が大きいグループのデータが残り全部となった場合に効率が悪くなります。この場合、ソートのオーダはデータ数をnとしたときO(n^2)になります(1個ずつソート済になるため、バブルソートなどのソートと同じ程度の計算量になる)。クイックソートのオーダは平均してO(n*log(n))となるので、nが大きいとき非効率になってしまいます。

データを大きいもの、小さいもので半分ずつに分けられるようなピボットを選ぶのが理想的なのですが、データを大量に利用してピボット選択の計算をすること自体にも時間がかかってしまいます。このようなときは、ソートしたいデータの性質に依存したピボット選択を考えましょう。例えば、ほぼ昇順であるが、数パーセントのノイズが入ってくるデータの場合は、数パーセントのノイズには目をつぶって、中央の位置にある値(=ほぼ中央値と期待される)をピボットにするという方針を選ぶことが考えられます。

2012年9月14日追記

データの破壊はないほうがよいということなので、popメソッドを利用しない方針で書き直してみました。

# -*- encoding: utf-8 -*-

def quick_sort2(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot_pos = len(array)/2
    pivot = array[pivot_pos]
    less = []
    greater = []
    for idx, x in enumerate(array):
        if idx == pivot_pos: continue
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

2012年8月29日水曜日

ニュートン法による極値計算

テキスト「これなら分かる最適化数学」の86ページにあるニュートン法をPythonで実装した。通常のニュートン法は関数f(x)に対し、f(x)=0なるxを求める反復計算を行うものであるが、反復の式を少し変更するだけで、極値(f'(x)=0なるx)を求めることができる。詳しい理論はテキストに譲るが、x <- x - f'(x)/f''(x)とし、収束するまで繰り返せば、極値にたどり着くことができる。

ニュートン法で極値を求めるにあたり、注意しなければならないのは、コードの更新式からも見当がつくが、途中で2回微分が0にならないようにすることである。

以下、f(x)=x^3-2*x^2+x+3に対して、極値が求まるか試してみた。なお、f(x)が極値をとるxの値は解析的に解くこともでき、x=1、1/3の2つとなる。

# -*- encoding: utf-8 -*-

'''
ニュートン法による極値の計算
2回微分が存在する場合、勾配法よりも効率よく極値を計算できる
'''

from sympy import * # 微分操作のために必要
import itertools as it # mapで複数の引数を与えたいので利用する

def newton(init, vari, func, delta=10**-6):
    '''
    funcは極値を探す対象の関数、variは微分する変数、deltaは収束判定のための定数
    返す値は見つかった極値の1つである
    '''
    df = diff(func, vari)
    d2f = diff(df, vari)
    x = init
    while True:
        xvar = x
        # 2回微分の微分係数が0にならないように注意が必要
        x = xvar - float(limit(df, vari, xvar)) / float(limit(d2f, vari, xvar))
        if abs(x - xvar) < delta:
            break
    return round(x, 5) # deltaの値によって有効桁数が変わるが、簡単のため5で決めうち

x = Symbol('x')
f = x**3 - 2*x**2 + x + 3
start_num = range(-5, 5) # 初期値を複数設定しておく
print map(newton, start_num, it.repeat(x, len(start_num)),
          it.repeat(f, len(start_num)))

最後のmapを利用することで、一度に複数の結果を実行、表示することができるようになる。mapに与える引数については、繰り返し実行できる形式にしておく必要がある。

実行結果は、[0.33333, 0.33333, 0.33333, 0.33333, 0.33333, 0.33333, 1.0, 1.0, 1.0, 1.0]となる。それぞれ初期値を-5、-4、...、4に変更しながら実行した結果である。すべて1/3と1のうち、近いほうの極値に収束していることが確認できる。

2012年8月28日火曜日

勾配法を用いた最適化計算

テキスト「これなら分かる最適化数学」の81ページにある勾配法(gradient method)アルゴリズムをpythonで実装した。勾配法とは、関数f(x)を最大にするxの値に近いと思われる値を初期値とし、必ず関数値f(x)が増加するようにし、かつステップ幅をなるべく大きくなるようその幅を調整することにより、できるだけ高速に関数を最大にするxを求めるというものである。

なお、今回扱う勾配法においては、変数の値がとりうる範囲について、関数の微分係数が0になるのは1箇所であると仮定する(複数極値があると、どこに向かうか分からないため)。また、微分できない箇所がある関数では不都合が生じるので、これも考えないことにする(例えばf(x)=|x|のx=0の点のように、尖っている状況下などがある)。

関数の最大値を求めるにあたっては、微分係数が0になるという性質を利用している。このため、微分という操作を行う必要であるが、この問題はsympyモジュールを利用することによって解決できる。sympyモジュールはこちらからダウンロードできる。なお、記事執筆時点のsympyのバージョンは0.7.1である。

以下、「2次関数f(x)」と「正規分布の確率変数と関係がある部分のみ取り出した関数g(x)」の2つの例を用いて、勾配法で正しく関数を最大化するようなxを推定できるか試してみた。結果としては、(制約が強いこともあるが)ほぼ正確に推定できているということになった。

# -*- encoding: utf-8 -*-

from sympy import *

# 符号関数
def sign(value):
    if value > 0: return 1
    if value < 0: return -1
    return 0

# 勾配法を計算するメインルーチン
# initは初期推定値、funcは最大値を求めたい関数、stepは初期移動量、
# epsは収束した(ほぼf'(x)が0となった)と判定する閾値である。
# 返り値は最大値となるxの値に相当する。
def gradient_method(init, func, step = 10**-7, eps = 10**-6):
    # diffは微分の関数、これで第一引数の関数をxで微分したことになる
    # 事前にxをSymbol関数でシンボル化しておく必要がある
    df = diff(func, x)
    xx, h = init, step
    while True:
        h = sign(limit(df, x, xx)) * abs(h)
        X, Xdash = xx, xx + h
        # 関数に値を入れるという方法が見つからないので
        # 極限の値を求めている
        if limit(func, x, X) < limit(func, x, Xdash):
            while limit(func, x, X) < limit(func, x, Xdash):
                h *= 2.0
                X, Xdash = Xdash, X + h
            xx, h = X, h / 2.0
        else:
            while limit(func, x, X) > limit(func, x, Xdash):
                h /= 2.0
                Xdash -= h
            xx, h = Xdash, 2.0 * h
        if abs(limit(df, x, xx)) <= eps:
            break
    return xx

x = Symbol('x') # xを記号として扱う
f = -x**2 + 2*x + 3
g = exp(-(x-2)**2)
print gradient_method(0, f) # 1.0000002、なお正解は1である
print gradient_method(0.5, g) # 2.0000002、なお正解は2である

2012年6月26日火曜日

初めてのコンピュータサイエンス解答まとめ

章ごとに解答の記事があるので、以下にリンクでまとめました。1章、13章は問題がないので、解答はありません。英語版テキストはこちらをご覧ください。日本語版のpdfはありませんので、必要があれば購入しましょう。なお、英語版と日本語版では一部の問題が異なっていますのでご注意ください。

2012年6月22日金曜日

初めてのコンピュータサイエンス第15章解答

いよいよ最終章、第15章練習問題の解答です。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず(英語版はpdfで公開されている模様)。日本語版が必要なら買いましょう。その前にこの章の個人的なメモ。

  • Pythonの標準ライブラリにはSQLite3というSQLiteというDBを操作するためのライブラリがある。SQLiteは大規模なものには向かないが、小規模なものであれば十分利用に耐えうる。
  • データベースにプログラムが直接手を加えるということはなく、DBMSが操作の仲介の役割を果たす。
  • データベースのキーにID(つまり整数)を持たせることには重要な意味がある。整数の方がソートが高速であるということ、同じ名前の物、人物の区別に便利だからである。
  • NULLの取り扱いはデータベースによって異なる。データベースはSQLite以外にもMySQL、OrableDB、Accessなどがある。
  • クエリーはネストできる。特定の条件Aに合うものだけ抽出し、その抽出したものに対し、別の条件Bに合うものだけを抽出するといったことができる。
SQLの基本的な決まり文句の一覧には以下のようなものがある。
コマンド 意味
CREATE TABLE Men(Name TEXT, Age INTEGER)Name(人物名)という文字列型の列、Age(年齢)という整数型の列からなるMenというデータベースを作成する
INSERT INTO Men VALUES("Taro", 30)MenというDBに("Taro", 30)という値のレコードを挿入する
SELECT Name FROM Men WHERE Age >= 25年齢が25歳以上の人物の名前を抽出する
SELECT Name FROM Men WHERE Age >= 25 AND Age <=40年齢が25歳以上40歳以下の人物の名前を抽出する
SELECT * FROM Men WHERE Name="Taro"名前が"Taro"という人をすべて抽出する
UPDATE Men SET Age=31 WHERE Name="Taro"TaroのAgeを31に更新する
DELETE FROM Men WHERE Name="Taro"NameがTaroというレコードを削除する。TaroというNameのものがすべて消える
CREATE TABLE Men(Name TEXT NOT NULL, Age INTEGER)NameがNULLのレコードを認めないデータベースを作成する。
INNER JOIN直積を作成する(クエリー間で比較するときに使える)
PRIMARY KEY一意になるキー列を設定する(キーを複数入れないようにするエラーチェックに使える)
SELECT AVG(Age) FROM Men平均年齢を計算する
SELECT MAX(Age) FROM Men GROUP BY NameNameごとに年齢の最大値を計算する
SELECT DISTINCT Name FROM MenNameの重複を排除してNameを抽出

では解答に移ることにする。

1

a)~c)の解答。DBへのデータの挿入はFor文とタプルを利用した方法でもよいでしょう。

# -*- encoding: utf8 -*-
import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

cur.execute('CREATE TABLE Density(State TEXT, Population INTEGER, Area REAL)')

cur.execute('INSERT INTO Density VALUES("Newfoundland and Labrador", 512930, 370501.69)')
cur.execute('INSERT INTO Density VALUES("Prince Edward Island", 135294, 5684.39)')
cur.execute('INSERT INTO Density VALUES("Nova Scotia", 908007, 52917.43)')
cur.execute('INSERT INTO Density VALUES("New Brunswick", 729498, 71355.67)')
cur.execute('INSERT INTO Density VALUES("Quebec", 7237479, 1357743.08)')
cur.execute('INSERT INTO Density VALUES("Ontario", 11410046, 907655.59)')
cur.execute('INSERT INTO Density VALUES("Manitoba", 1119583, 551937.87)')
cur.execute('INSERT INTO Density VALUES("Saskatchewan", 978933, 586561.35)')
cur.execute('INSERT INTO Density VALUES("Alberta", 2974807, 639987.12)')
cur.execute('INSERT INTO Density VALUES("British Columbia", 3907738, 926492.48)')
cur.execute('INSERT INTO Density VALUES("Yukon Territory", 28674, 474706.97)')
cur.execute('INSERT INTO Density VALUES("Northwest Territories", 37360, 1141108.37)')
cur.execute('INSERT INTO Density VALUES("Nunavut", 26745, 1925460.18)')

con.commit()

d)~j)の解答はこちら。基本的なSQL文の練習問題です。j)の計算結果を列として並べて表示するという方法は調べて納得。

# -*- encoding: utf8 -*-

import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

con.text_factory = str

# d)の解答
cur.execute('SELECT * FROM Density')
ans_d = cur.fetchall()
print ans_d

# e)の解答
cur.execute('SELECT Population FROM Density')
ans_e = cur.fetchall()
print ans_e # リストの中身は要素1のタプルである

# f)の解答
cur.execute('SELECT State FROM Density WHERE Population < 1000000')
ans_f = cur.fetchall()
print ans_f

# g)の解答
cur.execute('SELECT State FROM Density WHERE \
             Population < 1000000 OR Population > 5000000')
ans_g = cur.fetchall()
print ans_g

# h)の解答
cur.execute('SELECT State FROM Density WHERE \
             NOT(Population < 1000000 OR Population > 5000000)')
ans_h = cur.fetchall()
print ans_h

# i)の解答
cur.execute('SELECT Population FROM Density WHERE Area > 200000')
ans_i = cur.fetchall()
print ans_i

# j)の解答 州の名前と人口密度を表示
cur.execute('SELECT State, Population / Area FROM Density')
ans_j = cur.fetchall()
print ans_j

2

1のDBも使って解答します。まずは次のコードで、データを挿入します。

# -*- encoding: utf8 -*-

import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

con.text_factory = str

cur.execute('CREATE TABLE Capitals(State TEXT, Capital TEXT, Population INTEGER)')

# Province/Territory Capital Population
data =(
("Newfoundland and Labrador", "St. John’s", 172918),
("Prince Edward Island", "Charlottetown", 58358),
("Nova Scotia", "Halifax", 359183),
("New Brunswick", "Fredericton", 81346),
("Quebec", "Quebec", 682757),
("Ontario", "Toronto", 4682897),
("Manitoba", "Winnipeg", 671274),
("Saskatchewan", "Regina", 192800),
("Alberta", "Edmonton", 937845),
("British Columbia", "Victoria", 311902),
("Yukon Territory", "Whitehorse", 21405),
("Northwest Territories", "Yellowknife", 16541),
("Nunavut", "Iqaluit", 5236)
)

for d in data:
    cur.execute('INSERT INTO Capitals VALUES(?, ?, ?)', (d[0], d[1], d[2]))

con.commit()

以下、a)~i)までの解答です。

# -*- encoding: utf8 -*-

import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

con.text_factory = str

cur.execute('SELECT * FROM Capitals')
ans_a = cur.fetchall()
print ans_a

cur.execute('SELECT Density.Population, Capitals.Population \
FROM Density INNER JOIN Capitals WHERE Density.State = Capitals.State')
ans_b = cur.fetchall()
print ans_b

cur.execute('SELECT Density.Area FROM Density INNER JOIN Capitals \
WHERE Capitals.Population > 100000 AND Density.State = Capitals.State')
ans_c = cur.fetchall()
print ans_c

cur.execute('SELECT Density.Area FROM Density INNER JOIN Capitals \
WHERE Capitals.Population > 500000 AND \
Density.Population *1.0 / Density.Area < 2.0 AND \
Density.State = Capitals.State')
ans_d = cur.fetchall()
print ans_d

cur.execute('SELECT SUM(Area) FROM Density')
ans_e = cur.fetchall()
print ans_e

cur.execute('SELECT AVG(Population) FROM Capitals')
ans_f = cur.fetchall()
print ans_f

cur.execute('SELECT MIN(Capitals.Population) FROM Capitals')
ans_g = cur.fetchall()
print ans_g

# 著者による解答は間違ってそうな気がします。著者はもっとも多い人口の値を求めていますが、
# 求める必要があるのは、人口最大の州の名前です。
cur.execute('SELECT Density.State FROM Density \
WHERE Density.Population IN \
    (SELECT MAX(Population) FROM Density)')
ans_h = cur.fetchall()
print ans_h

cur.execute('SELECT A.State, B.State FROM \
Density A INNER JOIN Density B WHERE \
ABS(A.Population * 1.0 / A.Area - B.Population * 1.0 / B.Area) < 0.5 \
AND A.State < B.State')
ans_i = cur.fetchall()
print ans_i

3

SELECT文の結果を表示すると、空のリストになる。Pythonで1/0を含めるとZeroDivisionErrorになる。

>>> 1/0
Traceback (most recent call last):
  File "<interactive input>"line 1, in <module>
ZeroDivisionError: integer division or modulo by zero
>>> 1 > 0 and 1 / 0
Traceback (most recent call last):
  File "<interactive input>"line 1, in <module>
ZeroDivisionError: integer division or modulo by zero
>>> 1 / 0 and 1 > 0
Traceback (most recent call last):
  File "<interactive input>"line 1, in <module>
ZeroDivisionError: integer division or modulo by zero

4

デフォルト引数を利用することで、外部からパラメータを渡すことができるようになる。もっとチェックするのであれば、query中の?の数とタプルの要素数が一致していることを確認するということが挙げられます。問題文の趣旨から外れていきそうなので、そこまではしませんが。

# -*- encoding: utf8 -*-

def run_query(db, query, param=None):
    '''データベースdbに対してqueryを実行して結果を返す '''

    con = sqlite.connect()
    cur = con.cursor()
    if param != None:
        cur.execute(query)
    else:
        if type(param) == tuple: # タプルのみを受け付ける
            cur.execute(query, param)
    data = cur.fetchall()
    cur.close()
    con.close()
    return data

# example
run_query(db, 'SELECT * FROM Precipitation')
run_query(db, 'SELECT City, Temp FROM Precipitation \
    WHERE Snow >= (?) and Temp > (?)', (s, t))

2012年6月18日月曜日

初めてのコンピュータサイエンス第14章解答

第14章練習問題の前半の解答です。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず(英語版はpdfで公開されている模様)。日本語版が必要なら買いましょう。

1

このコードは実行すると、ボタンが出てきます。ボタンを押すとアプリケーションが終了するようになっています。

import Tkinter as tk

class Goodbye:
    def __init__(self, parent):
        self.parent = parent
        self.frame = tk.Frame()
        self.frame.pack()

        self.bye = tk.Button(self.frame, text='Good-bye', command=self.byebye)
        self.bye.pack()

    def byebye(self):
        self.parent.destroy()


if __name__ == '__main__':
    window = tk.Tk()
    myapp = Goodbye(window)
    window.mainloop()

2

このコードを実行すると数字が入ったボタンが出てきます。ボタンをクリックすると、表示される値が1ずつ大きくなります。

import Tkinter as tk

class CountUp:
    def __init__(self, parent):
        self.parent = parent
        self.frame = tk.Frame(parent)
        self.frame.pack()

        self.state = tk.IntVar()
        self.state.set(0)

        self.button = tk.Button(parent, text=self.state.get(),
                                command=self.count)
        self.button.pack()

    def count(self):
        self.state.set(self.state.get() + 1)
        self.button.config(text=self.state.get())

if __name__ == '__main__':
    window = tk.Tk()
    app = CountUp(window)
    window.mainloop()

3

x = lambda(): 3を読みやすくせよということなのですが、このコードを実行するとエラーになります。読みやすくする以前の問題で、何がしたいのでしょうか?

4

# -*- encoding: utf8 -*-

import Tkinter as tk

class CountDNA:
    def __init__(self, parent):
        self.parent = parent
        self.frame = tk.Frame()
        self.frame.pack()

        # モデルはATGCの数
        self.dic = {'A' : 0, 'T' : 0, 'G' : 0, 'C' : 0}
        self.message = tk.StringVar()

        # DNAの文字列を表示する
        self.textbox = tk.Text(self.frame, width=30, height=10)
        self.textbox.pack()

        # 数えるボタンを表示する
        self.bt = tk.Button(self.frame, text="数える",
                  command=lambda: self.countATGC(self.dic, self.message))
        self.bt.pack()

        # 数えた結果を表示する
        self.label = tk.Label(self.frame, textvariable=self.message)
        self.label.pack()


    # 出現回数を計算する
    def countATGC(self, dic, msg):
        for (key, value) in dic.iteritems():
            dic[key] = 0

        for c in self.textbox.get('0.0', tk.END):
            if c in dic.keys():
                dic[c] = dic.get(c, 0) + 1
        # print dic
        msg.set(self.printATGC(dic))

    def printATGC(self, dic):
        msg =  u'Aの数:%d Tの数:%d Cの数:%d Gの数:%d' % \
               (dic['A'], dic['T'], dic['C'], dic['G'])
        return msg

if __name__ == '__main__':
    window = tk.Tk()
    app = CountDNA(window)
    window.mainloop()

5

練習ということで、敢えてクラスを使わないで書いてみました。ちなみにこのコードをとあるWebエンジニアに見せたところ、__init__に何もかも押し込むのは、Cで言うところのmainに1000行書くようなものだということで、あまり良い作法でないということを教わりました。機能自体は実現できましたが、更によい書き方を知る必要もありそうです。

# -*- encoding: utf8 -*-

import Tkinter as tk

window = tk.Tk()
frame = tk.Frame(window)
frame.pack()
label = tk.Label(frame, text="華氏表現の温度")
label.pack()

var = tk.DoubleVar()

entry = tk.Entry(frame, textvariable=var) # 数値入力部
entry.pack()

svar = tk.StringVar()

msg = tk.Label(frame, textvariable=svar)
msg.pack()

bt_trans = tk.Button(frame, text="変換", command=lambda: click_trans(var,svar))
bt_trans.pack()

bt_end = tk.Button(frame, text="終了", command=lambda: click_end(window))
bt_end.pack()

def to_celsius(t):
    return (t - 32.0) * 5.0 / 9.0

def click_trans(var,svar):
    try:
        # var.get()が文字列だと例外が発生する
        s_temp = "%.10f" % to_celsius(var.get())
        svar.set(s_temp)
    except:
        svar.set("???")

def click_end(window):
    window.destroy()

window.mainloop()

2012年6月12日火曜日

初めてのコンピュータサイエンス第12章解答(後半)

第12章練習問題の後半10問の解答です。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず(英語版はpdfで公開されている模様)。日本語版が必要なら買いましょう。

11

one_item_listというリストが2回使われているが、1回目の利用でリストの内容を取り除いているので、2回目の利用時に要素数が空になっているため、assert len(one_item_list)==1で失敗してしまう。これを避けるためには、リストのコピーなどしておけばよいであろう。

12

文字列をファイルのように扱うことができる点においてテストを簡単にできる(テキストファイルをいちいち用意しなくても良いから)。詳しくはオンラインドキュメントのこちらを参照してほしい。

def count_lines(f):
    nLine = 0
    for line in f:
        nLine += 1
    return nLine
import cStringIO
import nose
from file_util import count_lines

def test_str_to_file():
    data = 'this\nis\na\npen'
    s = cStringIO.StringIO(data)
    assert count_lines(s) == 4

if __name__ == '__main__':
    nose.runmodule()

13

毎回各要素がこれまでに探索した要素の最大値より大きいか、あるいは最小値より小さいかを調べて更新している。最初にmax = None、min = Noneとしているが、不等式で評価する際、Noneは0扱いされている。そのため、すべて正の値、あるいはすべて負の値からなるリストが入力されるとおかしな挙動になる。従って、次のように書き換える。

def find_min_max(values):
    min = None
    max = None

    if len(values):
        min = values[0]
        max = values[0]
        for value in values:
            if value > max:
                max = value
            if value < min:
                min = value

    print 'min = %s' % min
    print 'max = %s' % max

if __name__ == '__main__':
    find_min_max([])
    find_min_max([6])
    find_min_max([-1, 1, 3, 5])

14

a)、b)の解答は、limitに負の値を与えたとき、終了条件のcurrent==0が満たされず、無限ループになるということである。

c)の解答としては、current != 0でループを続けるのではなく、current > 0でループを続けるようにすればよい。正の数を入力すればいずれ0になって止まるし、0以下であれば、ループに入らず終了する。

15

valueが0の時に0で割るため、例外が発生する。0で割るとZeroDivisionErrorが発生するので、これを捕捉し、Noneを返すことにする。ここでは、問題文中のコードのコメントに従い、値が逆数を持たない場合はリストにNoneを入れるというルールに従う。

def compute_reciprocals(values):
    reciprocals = []
    for value in values:
        try:
            reciprocals.append(1/value)
        except ZeroDivisionError:
            reciprocals.append(None)
    return reciprocals

val = [-1.0, 0, 1.0, 2.0, 3.0]
print compute_reciprocals(val) # [-1.0, None, 1.0, 0.5, 0.3333333333333333]

16

find_last関数について。v0は行数をカウントしている。v1は文字列の含まれる最終行の行番号と、その行に含まれる内容になる。v2はファイル、v3はファイルの各行を収める変数である。変数名を書き換えるのであれば、v0=num_line、v1=last_line、v2=filename、v3=lineなどが考えられる。

一方、standard_deviation関数について。v0はリストに含まれる数値の合計、v1はvaluesの各要素を格納する一時的な変数を表している。v2はリストの要素から計算される平均、v3は分散、v5は標本分散の平方根、すなわち標準偏差になる。変数名を書き換えるのであれば、v0=total、v1=val、v2=mean、v3=var、v4=val(v1と同じリストを使うループなのでv1に合わせた)、v5=sd(standard deviationの略語)などが考えられる。

17

まさかもう一度中央値、平均の実装を行うことになるとは...最頻値の導出については、C言語だったらさぞ面倒だろうなと思った次第。

# -*- encoding: utf8 -*-

def mean(values):
    total = 0 # 要素の合計を格納
    for val in values:
        if not type(val) in (int, float):
            raise ValueError
        total += val

    # floatにキャストするのはvaluesが
    # 全部整数だったときに切り捨てが発生するから
    return float(total)/len(values)

def median(values):
    for val in values:
        if not type(val) in (int, float):
            raise ValueError

    L = sorted(values[:]) # valuesの書き換えはしないことにする
    length = len(L)
    if length % 2 == 0:
        return (L[length/2-1]+L[length/2]) / 2.0
    else:
        return L[length/2]

def mode(values):
    for val in values:
        # 1/3のような実数は辞書のキーにしないものとする
        # 細かい丸め誤差があるときに同一か判別するのは厄介なので
        if type(val) != int:
            raise ValueError

    dic = {} # 整数の出現回数をカウント
    for val in values:
        dic[val] = dic.get(val, 0) + 1
    max_val = max(dic.values()) # 出現回数の最大値
    ret = []
    for key in dic.keys():
        if dic[key] == max_val: # 出現回数の最大値に一致するキーのみ抽出
            ret.append(key)
    return ret

if __name__ == '__main__':
    print mean([1, 3, 5, 7]) # 4.0
    try:
        print mean([1, 'a', 6])
    except ValueError:
        print "ValueError was caught in mean!"
    print median(range(10)) # 0~9なので4.5
    print median(range(10)) # 0~10なので5
    try:
        print median([1, 'a', 6])
    except ValueError:
        print "ValueError was caught in median!"

    print "key =", mode([0, 1, 0, 3, 2, 4, 1])
    try:
        print mode([1, 3.14, 6])
    except ValueError:
        print "ValueError was caught in mode!"

18

def process_file(filename):
    try:
        f = open(filename, 'r')
        for line in f:
            line = line.strip()
            print line
    except:
        pass

    f.close()

19

問題文には「アサーションを追加し、フォーマットに誤りがあればエラーメッセージを出力して終了するようにしてください」とあるのですが、アサーションというのはテスト、デバッグのために使うものであり、リリースする製品には含めてはいけないようなコードである。従って「アサーションを追加」するのではなく、「エラー処理を追加」するのが正しいはず。エラーが発生するとすれば、splitとその周辺の処理に限られるはずなので、そこにtryをかけて例外を補足すればよい。

# -*- encoding: utf8 -*-

def read_molecule(r):
    line = r.readline()
    if not line:
        return None

    try:
        key, name = line.split()
    except: # 例えばsplitの結果、引数が3つになるとここにくる
        print "Error in COMPND Name"
        return None # 例外発生時の返り値は要検討だが、Noneとする

    molecule = [name]
    reading = True

    while reading:
        line = r.readline()
        if line.startswith('END'):
            reading = False
        else:
            try:
                key, num, type, x, y, z = line.split()
                molecule.append((type, x, y, z))
            except: # ENDがない、あるいはsplitの結果が6つでないなどの原因で例外が発生する
                print "Error in reading"
                return None

    return molecule

20

a)~d)の解答があるのだが、まとめて解答する。a)、b)はdocstringが解答になる。c)はテストケースの作成、d)はテストケースに通る関数の作成である。

# -*- encoding: utf8 -*-

import nose

def findButNotAfter(source, prefix, pattern):
    '''sourceの中で最初にpatternが現れた位置(ただし直前がprefixに
    なってはなりません)の添え字を返す。例えば、
    findButNotAfter('abcdcd', 'ab', 'cd')は4を返す。最初のcdは
    直前にabがあるので不適切。以下、仕様があいまいな箇所を修正
    1)
    findButNotAfter('abcdcd', 'bc', 'cd')とした場合、2を返すものとする。
    1回目のcdの前にはabしかないと考える(abcを探索範囲としない)。
    2)
    pattern、source、prefixのいずれかが空、あるいはNoneの場合、-1を返す。
    3)
    patternがsourceにない場合、例えば
    findButNotAfter('abcdcd', 'bc', 'de')は-2を返す。
    4)
    patternはあるが、prefixが常に前にある場合は-3を返す
    '''

    if not pattern or not source or not prefix:
        return -1
    pos = source.find(pattern, 0)
    if pos < 0:
        return -2
    while pos >= 0:
        if not source[:pos].endswith(prefix): # 1番目の仕様はここに効く
            return pos
        pos = source.find(pattern, pos+1)

    return -3 # 常にpatternの直前にprefixがある場合

def test_pattern_is_null():
    ''' patternが空 '''
    assert findButNotAfter('abcdcd', 'bd', '') == -1

def test_no_prefix():
    ''' prefixが空の場合 '''
    assert findButNotAfter('abcdcd', '', 'cd') == -1

def test_no_source():
    ''' sourceが空の場合 '''
    assert findButNotAfter('', 'cd', 'ab') == -1

def test_no_pattern_in_source():
    ''' patternがsourceの中にない '''
    assert findButNotAfter('abcdcd', 'bd', 'ef') == -2

def test_theres_always_prefix_previously():
    ''' いつもpatternの直前にprefixがある場合 '''
    assert findButNotAfter('abcdabcd', 'ab', 'cd') == -3

def test_prefix_pattern_is_the_same():
    ''' prefixとpatternが一致する場合 '''
    assert findButNotAfter('abcdefg', 'd', 'd') == 3

def test_all_the_same_chars():
    ''' 全部文字が同じ場合 '''
    assert findButNotAfter('aaaaaaaaaaa', 'aa', 'aa') == 0

def test_match_at_first_char():
    ''' 先頭でマッチした場合 '''
    assert findButNotAfter('abcdcd', 'bc', 'abcd') == 0

def test_pattern_and_source_are_the_same():
    ''' patternとsourceが一致する場合 '''
    assert findButNotAfter('abcdcd', 'ab', 'abcdcd') == 0

def test_two_valid_pattern_pos():
    ''' 複数箇所条件にあう場合は先に出現した位置を返す '''
    assert findButNotAfter('abcdabcd', 'ef', 'c') == 2

if __name__ == '__main__':
    nose.runmodule()

2012年6月10日日曜日

初めてのコンピュータサイエンス第12章解答(前半)

第12章練習問題の前半の解答です。本章は問題が20問とかなり多いので、可読性の向上を目的に10問ずつに分けて公開します。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず(英語版はpdfで公開されている模様)。日本語版が必要なら買いましょう。その前にこの章の個人的なメモ。

  • デフォルト引数も、可変長引数も仮引数の右に置かなければならない。可変長引数は1つだけ設定することが許されている。
  • 可変長引数リストを呼び出すと、実引数はタプルとして関数定義に渡される
  • 例外はtry~except構文で書く。tryで例外が発生しない場合、exceptの後ろにelseをつけておくと、その内容を実行することができる。
  • 例外を生成する場合はraise 例外名(メッセージ)という書き方をするとよい。
  • 低いところからスロー、高いところからキャッチする。つまり例外を投げられる可能性がある関数で逐一キャッチするのではなく、関数を呼んでいる側でまとめてキャッチするとよいということである。エラーの処理場所を減らすことで、エラーの処理方法を変えることが容易にできる。

テスト駆動開発(TDD)のメリット

  • テストを必ず書かされることになる
  • プログラマにとって全部のケースに通ればOKという目安が与えられる
  • 文章よりも仕様を正確に与えられる
  • テストコードを書いている最中に設計について考えることができる

では解答にうつります。

1

Pythonの名前つき引数が利用される場面は引数が大量にある場合である。順番を気にするよりも、引数名と値を与えるほうが楽だからである。逆に、本来の順序が分からなくなる恐れがあるので、名前を省略した書き方をした際にバグを引き起こすというリスクが発生する。

2

-1は有効な添字である。-1ではなくNoneを指定しておくことで、何も指定されていないということがはっきりする。

3

a)の解答はこちらが解答に近いと思います(4.7.3、4.7.4の項目)。

b)の解答

def test(var, *pargs, **kwargs):
    print var
    print pargs
    print kwargs

test(1, 2, 3, x=4, y=5, z=6)

上のコードを実行すると次のようになる。

1
(2, 3)
{'y': 5, 'x': 4, 'z': 6}

varには値が1つ収まり、pargsには名前のついていない可変長引数、kwargsには名前つきの可変長引数が当てはめられる。テキストにあるように、受け取った関数では、varは変数、pargsはタプル、kwargsは辞書になる。従って、上の例ではvar=1(1番左にある値を代入)、pargs=(2, 3)(名前がついておらず、かつまだ利用されていない実引数の集まり)、kwargs={'x':4, 'y':5, 'z':6}(名前つきの実引数の集まり)という結果になり、その値が表示される。引数に与える順序としては通常の引数、キーワード引数、名前なし可変長引数、名前つき可変長引数の順序で左から並べなければならない。引数は次の順序でマッチングを行う。

  • 通常の引数の位置によるマッチング
  • キーワード引数の名前によるマッチング
  • *を使った引数が定義されていれば、上の2つでマッチングできなかったキーワード引数でない引数をタプルにまとめる
  • **を使った引数が定義されていれば、上の3つでマッチングできなかったキーワード引数を辞書にまとめる
  • その他指定されていない引数がデフォルト値が設定されていれば、その値を代入する

c)の解答

HTMLのタグを扱うときなどにキーワード引数を受け取れるようにしておくと便利である。例えばHTMLのimgタグには大量のオプション(altやwidthなど)が付けられるが、これを逐一引数に与えるのは面倒である。そこで指定したものだけをつけたいというときに利用すればよい。

4

ここで言う線が線分なのか直線なのかで解答が変わるので、問題文が曖昧になっています。問題文より、エラー処理は考えないということなので、入力に数値が必ず入るものとして、文字列が入ってきたときは考えないものとします。また、本問と次の問題において、問題文に登場する「線」は直線や半直線ではなく、線分と仮定します。

  • [[1.0, 1.0], [1.5, 1.5]]と[[2.0, 2.0], [3.0, 3.0]]のように、線は重ならないものの、延ばせば一致するという場合のテスト。線分は重ならないのでNoneが返される。
  • [[2.0, 2.0], [3.0, 3.0]]と[[2.0, 3.0], [3.0, 2.0]]のように、線が他方の線の真ん中あたりで重なる場合、交点の座標[2.5, 2.5]が返される。一般的に想定される重なり方をテスト。
  • [[1.0, 1.0], [2.0, 2.0]]と[[1.5, 1.5], [3.0, 3.0]]のように、線が一部重なる場合、第一引数[[1.0, 1.0], [2.0, 2.0]]が返される。
  • [[-1.0, 0.0], [4.0, 0.0]]と[[0.0, 0.0], [0.0, 2.0]]のように、一方が他方を包含する場合のテスト。第一引数[[-1.0, 0.0], [4.0, 0.0]]が返される。
  • [[0.0, 0.0], [0.0, 2.0]]と[[0.0, 1.0], [2.0, 1.0]]のように、線が他方の線の端で重なる場合、交点の座標[0.0, 1.0]が返される。ぎりぎり重なるという状況のテスト。
  • [[1.0, 1.0], [2.0, 2.0]]と[[2.0, 2.0], [3.0, 3.0]]のように、線の端と端で重なる場合のテスト。交点の座標[2.0, 2.0]が返される。

整数を引数に取った場合、実数として処理されるかということもテストで考えていましたが、次の問題文を読む限り、エラー扱いする入力のようなので、効果的な6種類のテストに含めることはできない模様です。

5

エラー処理のコードは全体の8割ほど占めると言われているので、まずはエラーが正しく処理されているかを確認する必要がある。エラーが起きない基本的なロジックではバグはあまり発生しないということもエラーからチェックすべきということを後押しする。以下、エラーが正しく処理されていることを確認するために考える6種類のテストを列挙した。

  • [["a", 1.0], [2.0, 3.0]]のような、引数に文字列が含まれる場合にValueErrorが返されるか
  • [[1, 2.0], [3.0, 4.0]]のような、引数が浮動小数点数になっていない場合にValueErrorが返されるか
  • [[1.0, 2.0], [3.0, 4.0, 5.0]]のように、浮動小数点数の対になっていない場合にValueErrorが返されるか
  • [[1.0, 2.0], [3.0, 4.0], [5.0, 6.0]]のように、浮動小数点数の対になっていない場合にValueErrorが返されるか
  • [[1.0, 1.0], [1.0, 1.0]]のような線を特定する2点が同じ点であった場合にGeometryError例外が返されるか
  • [[1, 1], [1, 1]]のような浮動小数点数でない値(整数でなく文字列でもOK)の対が一致した場合、ValueErrorの方が返されるか(例外の実装の順序を確認)

6

106通り。前提は元素記号が国際コードに関係のないということである。元素記号と国際コードを1回以上引数に与えるようにテストケースを作成するので、106の元素と26の言語という数の大きい方を選べばよい。

7

==とするのがよくない。丸め誤差が発生してしまうため、必ずしも==で値が同じであることを正確に判定できるわけではない。実数が等しいかそうでないかを判定する際には差の絶対値が十分小さいということで評価するべき。このコードではabs(actual-expected)<10**-15などにする。10**-15とするのは、浮動小数点の丸め誤差の最小単位が10**-16程度なので、それよりも若干大きめにとる必要があるためである。もしくはDecimalモジュールを利用した方法を取ることを考える必要がある。

8

  • Acids、Basesというものの存在を意識せずテストするべき。つまり、インタフェースである引数と返り値のみ既知として、内部仕様に依存したテストはやめるべき。関数の書き換えなどにより、動作しなくなる恐れがある(例えばAcidsという名前を書き換えられたら途端に動作しなくなる)。
  • リリースしようとしているコードをテストのためだけに書き換えることはよくない。書き換え前の本番用データに問題があった場合に発生しうるバグを考慮するべき。

9

上はex12_9.py、下はtestprefixes.pyという名前がついています。関数のテストは4種類書けということなのですが、これにあいまいな仕様を含むのか含まないのかが問題文からではわかりません。ひとまず、あいまいな仕様の箇所も固定してテストするということにしています。あいまいな仕様というのは、空文字が含まれた場合の対処と、文字列の途中にある空白の取り扱いになります。

# -*- encoding: sjis -*-

def all_prefixes(string):
    ''' 空文字が入ってきた場合の返り値に対する仕様がないこと、
        複数の語からなり、途中に空白がある場合の仕様がない点は問題である。
        今回は、空白も語の途中と扱うものと考えることにする。
    '''
    ret = set()
    for i in range(1,len(string)+1):
        tmp = string[:i]
        ret.add(tmp)
    return ret

if __name__ == '__main__':
    print all_prefixes('lead')
    print all_prefixes('')
    print all_prefixes('a pen')

テスト用コード

# -*- encoding: sjis -*-

import nose
from ex12_9 import all_prefixes

def test_null():
    ''' 対象が空文字からなるテスト '''
    assert all_prefixes('') == set([])

def test_one_char():
    ''' 対象が1文字からなるテスト '''
    assert all_prefixes('a') == set(['a'])

def test_one_word():
    ''' 対象が複数文字、1語からなるテスト '''
    assert all_prefixes('lead') == \
           set(['l', 'le', 'lea', 'lead'])

def test_two_words():
    ''' 対象が2語(途中に空白を含む)からなるテスト '''
    assert all_prefixes('a pen') == \
           set(['a', 'a ', 'a p', 'a pe', 'a pen'])

if __name__ == '__main__':
    nose.runmodule()

10

10個テストケースを思いつけと言われても、難しいですよね。最後に作成したテストケースである、リストの中のリストは捻りだした感じになってしまいました。

# -*- encoding: sjis -*-

import nose

def is_sorted(data):
    if not type(data) == list:
        raise ValueError
    for elem in data:
        # 要素が整数でないものがあった場合
        if not isinstance(elem, int):
            raise ValueError

    copy = data[:]
    return data == sorted(copy)

def test_zero_elem():
    ''' 空リストはリストであり、整数でない値を含まないので
        Trueが返されるべき '''
    assert is_sorted([]) == True

def test_tuple():
    ''' タプルはリストでないのでValueError '''
    try:
        is_sorted((1, 2, 3))
        assert False
    except ValueError:
        pass
    except:
        assert False

def test_list_in_list():
    ''' リストの中にリスト '''
    try:
        is_sorted([1, 4, [5, 7], 8])
        assert False
    except ValueError:
        pass
    except:
        assert False

def test_char_included():
    ''' 要素に文字列を含む場合はValueError '''
    try:
        is_sorted([1, 3 ,'ab2c'])
        assert False
    except ValueError:
        pass
    except:
        assert False

def test_float_included():
    ''' 実数が含まれた場合はValueError '''
    try:
        is_sorted([1, 2, 3.14, 5, 7])
        assert False
    except ValueError:
        pass
    except:
        assert False

def test_one_elem():
    ''' 1要素のみのリスト '''
    assert is_sorted([3]) == True

def test_all_the_same():
    ''' 全部の要素が同じ値の場合 '''
    assert is_sorted([4, 4, 4, 4, 4]) == True

def test_dsc():
    ''' 降順の場合 '''
    assert is_sorted([4, 3, 2 ,1]) == False

def test_asc():
    ''' 昇順の場合 '''
    assert is_sorted([1, 2, 5, 9]) == True

def test_normal():
    ''' 増加・減少がともにある、割と一般的なデータ '''
    assert is_sorted([1, 2, 7, 9, 1]) == False

if __name__ == '__main__':
    nose.runmodule()

2012年6月5日火曜日

Pythonにおける仮引数の取り方

Pythonにおける仮引数のテクニックは主に以下の3種類がある。サンプルコードを通じて、これらの機能について確認していくことにする。

名称 役割
デフォルト引数関数の引数で基本的に与える値が決まっている場合はデフォルト引数を利用するとよい。呼び出しの時に与える引数を減らすことができるので、記述量を減らすことができる。
可変長引数外からいくつ引数を与えても処理してくれる仕組み。
名前付き引数順番を変えても、呼び出す側で明示的に「引数名=値」の形式で指定しておけば引数の順番を関数定義で設定した順序から変えても構わないという仕組み。これにより、大量の引数があるときでも、順序を気にせず指定してもよいことになる。
# -*- encoding: sjis -*-

def all_add(lst, num=1): # num=1がデフォルト引数、デフォルト引数は引数群の後半に書く
    ''' リストの全要素にnumを加える '''
    for i in range(len(lst)):
        lst[i] += num
    return lst

def search_arg_max(dat, *new): # 可変長引数は*newである
    ''' 引数の順序が大事、複数引数を渡す場合、*newの前に引数をすべて定義する必要がある。
        複数の可変長引数は与えられない。可変長引数リストの区切りが分からないからである。
    '''
    if not dat or not new: # どちらかを欠いている場合
        return -1

    # 可変長引数はタプルであることに注意
    return max(max(dat),max(new))

if __name__ == '__main__':
    data = [1, 3, 5, 8, 11]
    print all_add(data) # [2, 4, 6, 9, 12]
    data = [1, 3, 5, 8, 11]
    print all_add(data, 0) # [1, 3, 5, 8, 11] (変化なし)
    data2 = [2, 9, 10]
    # 順序が関数定義とは異なっていても引数に名前をつけて渡せばOK
    print all_add(num=2, lst=data) # [3, 5, 7, 10, 13]
    print search_arg_max(data, 3, 9, 12) # 12

その他、可変長引数で該当する引数が存在しない場合は空のタプルが入力されることにも注意。

2012年6月1日金曜日

初めてのコンピュータサイエンス第11章解答

第11章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。

1

k回探索するものとすると、ソート+探索と、毎回探索するという計算の量について次の式が成り立つ(定数項がないため、すごく大まかですが)。k*log_2(N) + N*log_2(N) <= k*N*log_2(N)(_2は対数の底が2であることを意味する)。これを満たすkはk >= N/(N-1)である。右辺はN=1のとき最大値2をとり、かつ1より大きい。従ってk>=2であればよく、2回探索した時点で毎回未ソートのリストから探索するよりも、ソートしてから探索を繰り返すほうが高速になる。

2

利用したコードは以下の通り。既存のソートアルゴリズムに毎回print文を挟めばよい。

a)の場合

  • [1, 5, 4, 3, 7, 6, 2]
  • [1, 2, 4, 3, 7, 6, 5]
  • [1, 2, 3, 4, 7, 6, 5]
  • [1, 2, 3, 4, 7, 6, 5]
  • [1, 2, 3, 4, 5, 6, 7]
  • [1, 2, 3, 4, 5, 6, 7]
  • [1, 2, 3, 4, 5, 6, 7]
  • [1, 2, 3, 4, 5, 6, 7]

b)の場合

  • [5, 6, 4, 3, 7, 1, 2]
  • [4, 5, 6, 3, 7, 1, 2]
  • [3, 4, 5, 6, 7, 1, 2]
  • [3, 4, 5, 6, 7, 1, 2]
  • [1, 3, 4, 5, 6, 7, 2]
  • [1, 2, 3, 4, 5, 6, 7]
  • [1, 2, 3, 4, 5, 6, 7]
# -*- encoding: sjis -*-

def selection_sort(L):
    ''' L[:i]までソート済みとして、
        L[i]とL[i:]の最小値の交換を繰り返す
    '''
    for i in range(len(L)):
        smallest = L.index(min(L[i:]))
        L[i], L[smallest] = L[smallest], L[i]
        print L
    return L

def insertion_sort(L):
    ''' L[:b]までソート済みとして、
        L[b]をソート済みのリストに混ぜる
    '''
    for i in range(1, len(L)):
        pos = 0
        for j in range(i-1, -1, -1):
            # print L[i], " ", L[j]
            if L[i] >= L[j]:
                pos = j + 1
                # print "pos = ", pos, L[i], L[j]
                break
        L.insert(pos, L[i])
        del L[i+1]
        print L
    return L

3

テストと実装のファイルは分けずに書いていますが、本当なら分けるべきでしょう。

# -*- encoding: sjis -*-

import nose

def swap(L, pos1, pos2):
    tmp = L[pos1]
    L[pos1] = L[pos2]
    L[pos2] = tmp

def bubble_sort(L):
    ''' 1)先頭から隣り合う要素を比較し、添え字の小さいほうが
          大きいようなら値の交換を行う
        2)1)をi回繰り返すと後ろからi個の要素が整列済みになっている
          要素数-1回繰り返す
    '''
    for i in range(len(L)-1, 0, -1):
        for j in range(i):
            if L[j] > L[j+1]:
                swap(L, j, j+1)
        print L
    return L

# run_test とするとテストケースと勘違いされるのでrun_checkとする
def run_check(original, expected):
    bubble_sort(original)
    assert original == expected

def test_empty():
    run_check([], [])

def test_one():
    run_check([3], [3])

def test_reverse():
    run_check([5, 4, 3, 2, 1], [1, 2, 3, 4, 5])

def test_same():
    run_check([2, 2, 2, 2], [2, 2, 2, 2])

def test_random():
    run_check([6, 5, 4, 3, 7, 1, 2], [1, 2, 3, 4 ,5 , 6, 7])

if __name__ == '__main__':
    nose.runmodule()

4

テストコードは上のテストの使いまわしでよいと思います。

def bubble_sort_2(L):
    ''' 1)最後尾から先頭へ向けて隣り合う要素を比較し、添え字の
          小さいほうが大きいようなら値の交換を行う
        2)1)をi回繰り返すと先頭からi個の要素が整列済みになっている。
          要素数-1回繰り返す
    '''
    for i in range(len(L)-1):
        for j in range(len(L)-1, i, -1):
            if L[j] < L[j-1]:
                swap(L, j, j-1)
        print L

5

用意したデータは降順データなので、全部のデータを反転させることになる。結果としては、バブルソートは全体的に遅いということが分かる。また、ソートにかかる時間はO(n^2)に従っていることが確認できる。バブルソートが特に遅いのは、比較の回数が多いためと思われる。一方挿入ソート、選択ソートで実行速度に大きな差は見られなかった。大量データをずらすというコストは、交換するコストとほとんど差がないのではないかと推測される。なお、ch11_sort_algo.pyに上に挙げたbubble_sortなどのソートアルゴリズムを実装している。

import time
from ch11_sort_algo import *

def print_times(L):
    print len(L),
    for func in (bubble_sort, bubble_sort_2, insertion_sort, selection_sort):
        L_copy = L[:]
        t_from = time.time()
        func(L_copy)
        t_to = time.time()
        print "\t%.1f" % ((t_to - t_from) * 1000.),
    print

for list_size in [10, 1000, 2000, 5000, 10000]:
    L = range(list_size)
    L.reverse()
    print_times(L)

6

ソート済みの長さNのリストの場合

手法比較回数コピー回数
挿入ソートN-1回(毎回ソート済みの最終要素に1度アクセスして終了)0回(後ろにつけるだけでコピーは発生しない)
選択ソートN(N-1)/2回(未ソートの部分で最小値探索の必要あり)0回(未ソート部分の先頭が最小値と分かるのでコピー不要)

リストが逆順

手法比較回数コピー回数
挿入ソートN(N-1)/2回(毎回ソート済みのリスト全体の探索の必要あり)0回(コピーではなく値の交換がN-1回発生する)
選択ソートN(N-1)/2回N-1回(コピーするリストの長さは可変)

入力のリストがすべて同じ値の場合

手法比較回数コピー回数
挿入ソートN-1回(毎回ソート済みの最終要素にアクセスして終了)0回
選択ソートN(N-1)/2回0回

7

挿入に伴い発生するリストのコピーにかかるコストを考慮していない。これを考慮するのであれば、オーダーはN^2になる。全体の結論にも影響する。

8

ランダムに並び替えたものが偶然ソート済みになるのは、要素数がNであれば、平均してN!回に1回発生することなのでO(N!)になる。要素が一意であるかが問題になっているのは、一意かそうでないかでオーダーが変化するからである。例えば、N個のうちN-1個は同じ値で1つだけ違う値であれば、O(N)になるし、すべて同じ値であれば、O(1)になるからである。

9

extend呼び出しをなくすにはループ内で結合まで行うしかない。そこで、i1かi2が終端まで着たら他方をすべて結合してループを抜け出すという書き換えを行った。

# -*- encoding: sjis -*-

def merge(L1, L2):
    newL = []
    i1 = i2 = 0

    while i1 != len(L1) or i2 != len(L2): # and から orに変更
        if i1 >= len(L1): # 終端に着いたので他方の残りの要素を結合
            newL += L2[i2:]
            break
        elif i2 >= len(L2):
            newL += L1[i1:]
            break

        if L1[i1] <= L2[i2]:
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2])
            i2 += 1

    return newL

def mergesort(L):
    workspace = []
    for i in range(len(L)): # 1要素に分解
        workspace.append([L[i]])

    i = 0

    while i < len(workspace) - 1: # マージ開始
        L1 = workspace[i]
        L2 = workspace[i + 1]
        newL = merge(L1, L2)
        workspace.append(newL)
        i += 2

    if len(workspace) != 0:
        L[:] = workspace[-1][:]

    return L

if __name__ == '__main__':
    data = [3, 0, 2, 3, -1]
    print mergesort(data)
    data = [6, 5, 4, 3, 7, 1, 2]
    print mergesort(data)
    data = []
    print mergesort(data)

2012年5月30日水曜日

初めてのコンピュータサイエンス第10章解答

第10章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。その前にこの章の個人的なメモ。

  • pythonにおけるリストのコピーはList[:]のように、全体をスライシングする書き方にすればよい。

1

a)b)の解答

空の文字列を用意して、AであればT、TであればA、GであればC、CであればGを結合することを文字列の末尾まで続ける。

c)の解答

def complement(sequence):
    ret = ''
    for c in sequence:
        if c == 'A':
            ret += 'T'
        elif c == 'T':
            ret += 'A'
        elif c == 'G':
            ret += 'C'
        elif c == 'C':
            ret += 'G'

    return ret

if __name__ == '__main__':
    print complement('AATTGCCGT')

2

a)~c)までまとめて解答。a)の解答はmin_index関数の内部そのものになります。また、引数にboolというものを取れいう指示があるのですが、boolは予約語なので、booleanに変更。

def min_index(sequence):
    idx = 1
    val = sequence[0]
    for i in range(2, len(sequence)):
        if sequence[i] < val:
            val = sequence[i]
            idx = i
    return tuple((val, idx))

def max_index(sequence):
    idx = 1
    val = sequence[0]
    for i in range(2, len(sequence)):
        if sequence[i] > val:
            val = sequence[i]
            idx = i
    return tuple((val, idx))

def min_or_max_index(sequence, boolean):
    if boolean == True:
        return max_index(sequence)
    else:
        return min_index(sequence)

if __name__ == '__main__':
    data = [3, 7, 2, 0, 23.1, 1.4, 9]
    print min_index(data)
    print min_or_max_index(data, False)
    print min_or_max_index(data, True)

3

どこまでを仕様とするかにも依るが、面白いリストには、例えば長さ0や長さ1のリスト、最小値が先頭にあるリスト、文字列を含むリストというのも考えられる。最小値が先頭にある場合は、初期設定で最小値を先頭の値としている場合に対応するためのテストである。以下のコードでは、前提として、長さが1以上、文字列は一切含まないものとしてテストを行うものである。ex10_2は2番のコードである。

import nose
from ex10_2 import min_index

def test_min_index():
    data = [1, 100]
    assert min_index(data) == tuple((1, 0))
    data = [3]
    assert min_index(data) == tuple((3, 0))

if __name__ == '__main__':
    test_min_index()

4

最小の2つの要素を探すのに、0または1つの要素からなるリストを与えられた場合は、そのようなものは「ない」ということで、Noneを返す。もしくは添字アクセスに失敗することから、例外を返すというのが考えられる。はじめの先頭2要素の比較で、アクセスしようとしている添字が存在していないことが問題になることに注意。

2012年5月29日火曜日

初めてのコンピュータサイエンス第9章解答

第9章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。その前にこの章の個人的なメモ。

  • setオブジェクトで保持される順序にルールはない。
  • 集合はハッシュテーブルというデータ構造に格納される。
  • 集合の要素に対し、ハッシュコードが計算される。ハッシュコードはイミュータブル(書き換え不可能なデータ)のみ持つことが許される。
  • 辞書の初期化は{}で行う。追加はappendなどではなく、辞書名[キー] = 値 という形式で指定すればOK。
  • 185ページのdict_of_dicts.pyのサンプルコードに登場する辞書でJグドールに関する項目に'霊長類研究者'(英語では'primate researcher')とあるが、この後ろに「,」がないため、編集の必要がある。おそらくバグ。

1

# -*- encoding: sjis -*-

def find_dups(data):
    h_table = {}
    for d in data:
        if d in h_table.keys(): # getメソッドを利用する方法もある
            h_table[d] += 1
        else:
            h_table[d] = 1
    ret = []
    # iteritemsはオブジェクトのコピーを作らないので高速に動かすことができる
    for (key, value) in h_table.iteritems():
        if value >= 2:
            ret.append(key)
    return ret

if __name__ == '__main__':
    data = range(10) + range(10, 5, -1) + range(3, 7)
    ret = find_dups(data)
    print ret

2

def mating_pairs(males, females):
    ''' the size of males and that of females are the same. '''
    ret = []
    # while males: is OK. this answer is a bit copmlex.
    while len(males) > 0:
        ret.append((males.pop(), females.pop()))
    return set(ret)

if __name__ == '__main__':
    males = set(['A', 'B', 'C', 'D', 'E'])
    females = set(['1', '2', '3', '4', '5'])
    print mating_pairs(males, females)

3

PDB形式のAUTHORの行に関する情報はこちらのpdfを参考にするとよいでしょう。人物名はコンマ区切り、AUTHORと人名は空白で区切られているという条件を使います。また、最後にコンマがあり人名が続かないこともありますので、そのようなことも考慮しています。

# -*- encoding: sjis -*-

import sys

def read_author(r):
    ret = set()
    for line in r:
        if not line:
            continue
        if line[:6].upper() != 'AUTHOR': # AuthorなどもOKにするため、upper()を挟んでいる
            continue
        # 仕様の都合上8文字目から作者名が始まる可能性がある。
        # strip()でいったん両端の空白を削除してから","で区切る
        line = line[7:].strip().split(",")
        print line
        for i in range(len(line)):
            if not line[i]: # AUTHORとあるが、何も続かない場合
                continue
            ret.add(line[i])
    return ret # setを返しておく

if __name__ == '__main__':
    names = set()
    for filename in sys.argv[1:]: # 外部からファイルを読み込みたい
        infile = open(filename, 'r')
        name = read_author(infile)
        names = names.union(name) # 和集合はunionである
        infile.close()
    print names

4(自信薄)

setの中に中身が変更可能なsetが入れられないのでfrozensetにして入れている。vowelは要素にfrozensetのデータを持つが、すでに通常のsetとして扱って問題ない。中身が書き換え可能なメモリアドレスにvowelsが配置されるということになる。

5

def count_values(dic):
    values = {}
    for (key, value) in dic.iteritems():
        if not value in values:
            values[value] = 1
    return len(values)

if __name__ == '__main__':
    print count_values({'red':1, 'green':2, 'blue':3})
    print count_values({'red':1, 'green':2, 'blue':1})
    print count_values({'red':2, 'green':2, 'blue':2})

6

def min_elementary_particle(dic):
    minimum = 1.1 # probability is always smaller than 1
    elem = ''
    for (key, value) in dic.iteritems():
        if value < minimum:
            minimum = value
            elem = key
    return elem

if __name__ == '__main__':
    component = {'neutrino':0.14 , 'neutron':0.55,
                 'proton':0.21, 'meson':0.03, 'muon':0.07}
    print min_elementary_particle(component)

7

def count_duplicates(dic):
    dup = {}
    for (key, value) in dic.iteritems():
        if not value in dup:
            dup[value] = 1
        else:
            dup[value] += 1

    dup_list = []
    for (key, value) in dup.iteritems():
        if value >= 2:
            dup_list.append(key)
    return len(dup_list)

if __name__ == '__main__':
    color = {'red':1, 'green':4, 'blue':2, 'orange':3, 'green':2, 'orange':6}
    print count_duplicates(color) # 2 is duplicated number.

8

例外という先の内容を無理やり利用しろということなので、試しに使ってみた。

def fetch_and_set(dic, key, new_value):
    if key in dic:
        old_value = dic[key]
        dic[key] = new_value
        return old_value
    else:
        raise KeyError("Unable to replace value for nonexistent key")

if __name__ == '__main__':
    color = {'red':1, 'green':4, 'blue':2, 'orange':3}
    print fetch_and_set(color, 'green', 100) # 4
    try:
        fetch_and_set(color, 'black', 3) # KeyError exception
    except KeyError:
        print "KeyError occurred!"

9

問題の仕様にはないのですが、辞書には必ずしもキーがR、G、Bだけではないものと仮定します。RGB以外は無視するものとします。

def is_balanced(dic):
    total = 0
    for (key, value) in dic.iteritems():
        if key == 'R' or key == 'G' or key == 'B':
            total += value

    if abs(total - 1.0) < 10 ** -15: # almost equal to 1
        return True
    else:
        return False

if __name__ == '__main__':
    color = {'R':0.1, 'G':0.4, 'B':0.5}
    print is_balanced(color) # True
    color = {'R':0.1, 'G':0.4, 'X':0.2, 'B':0.5}
    print is_balanced(color) # True
    color = {'R':0.1, 'G':0.4, 'B':0.2}
    print is_balanced(color) # False

10

両方の辞書に同じキーと同じ値が含まれている対のみ返します。同じキーだが値が違うという場合はdict_intersectの返り値の辞書には含まないものとします。

def dict_intersect(dic1, dic2):
    k2 = dic2.keys()
    ret = {}
    for (k1, v1) in dic1.iteritems():
        if k1 in k2 and v1 == dic2[k1]:
            ret[k1] = v1
    return ret

if __name__ == '__main__':
    c1 = {'red':1, 'green':4, 'blue':2, 'orange':3, 'green':2, 'orange':6}
    c2 = {'red':1, 'green':5, 'blue':2, 'yellow ':3}
    print dict_intersect(c1, c2) # blue and red are extracted

11

scientists = {
  'jgoodall'  : {'surname'  : 'Goodall',
                 'forename' : 'Jane',
                 'born'     : 1934,
                 'died'     : None,
                 'notes'    : 'primate researcher', # distributed sample code lacks comma.
                 'author'   : ['In the Shadow of Man', 'The Chimpanzees of Gombe']},
  'rfranklin' : {'surname'  : 'Franklin',
                 'forename' : 'Rosalind',
                 'born'     : 1920,
                 'died'     : 1957,
                 'notes'    : 'contributed to discovery of DNA'},
  'rcarson'  : {'surname'  : 'Carson',
                 'forename' : 'Rachel',
                 'born'     : 1907,
                 'died'     : 1964,
                 'notes'    : 'raised awareness of effects of DDT',
                 'author'   : ['Silent Spring']}
}

def db_headings(dic):
    ret = []
    for values in dic.values():
        ret += values.keys()
    return set(ret)

if __name__ == '__main__':
    print db_headings(scientists)

12

scientistsは上のデータを利用することにします。rfranklinは他の二つとキーが異なるため内部の辞書は常に一定にはなりません。そのため、db_consistent関数にscientistsを渡すと、Falseになります。if elem.symmetric_difference(set(values)):は要素数が0でなければという意味になります。

def db_consistent(dic):
    first = dic.keys()[0]
    elem = set(dic[first].keys())
    for values in dic.values():
        if elem.symmetric_difference(set(values)):
            return False
    return True

if __name__ == '__main__':
    print db_consistent(scientists)

13

空行で機能が大まかに区切られているので、それを1つのまとまりとしてモジュールにするというだけですね。

import sys

def create_dic(files):
    count = {}
    for filename in sys.argv[1:]:
        infile = open(filename, 'r')
        for line in infile:
            name = line.strip()
            count[name] = count.get(name, 0) + 1
        infile.close()
    return count

def reverse_dict(dic):
    freq = {}
    for (name, times) in dic.iteritems():
        print name, times
        if times in freq:
            freq[times].append(name)
        else:
            freq[times] = [name]
    return freq

def print_dic(dic):
    for key in sorted(dic):
        print key
        for name in dic[key]:
            print ' ', name

if __name__ == '__main__':
    dic = create_dic(sys.argv[1:])
    r_dic = reverse_dict(dic)
    print_dic(r_dic)

14

a)、b)の解答は以下の通り。

def sparse_add(dic1, dic2):
    ret = dic1.copy()
    keys = set(dic1.keys() + dic2.keys())
    for key in keys:
        ret[key] = 0
        if key in dic1.keys():
            ret[key] += dic1[key]
        if key in dic2.keys():
            ret[key] += dic2[key]
    return ret

def sparse_dot(dic1, dic2):
    ret = 0
    for (key, value) in dic1.iteritems():
        if key in dic2:
            ret += value * dic2[key]
    return ret

if __name__ == '__main__':
    v1 = {0:1, 6:3, 7:-1}
    v2 = {1:1, 2:2, 6:1, 7:-1}
    print sparse_add(v1, v2) # {0: 1, 1: 1, 2: 2, 6: 4, 7: -2}
    print sparse_dot(v1, v2) # 4

c)に関しては、疎ベクトルの長さが、辞書の長さになるのか、それとも最後に現れた辞書のキーの値+1になるのかということが曖昧になっている。0を値に持つキーをどのように扱うかということが、「疎ベクトルの長さ」という言葉だけでははっきりしないということである。

2012年5月26日土曜日

初めてのコンピュータサイエンス第8章解答

第8章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。その前にこの章の個人的なメモ。

  • ファイルを読み込む際は関数の外でファイルのオープン・クローズを行うとよい。これは処理を1つの関数だけで済ませることができるためである。Webページやストリームなどを統一的に扱える。
  • ファイルの追加はopenする際の引数に'a'と与える
  • pp.161の注釈は「単一のタプルが返されている」ではなく、「単一のリストが返される」が正しい。おそらく誤植。

1

後ろから前に向かってファイル全体を読み出すという意味をどう捉えるかが問題になりそうですが、行だけ後ろから前へと見るか、行の中身まで反転させるか悩ましいところではあります。今回は前者で考えています。

def read_reverse(file):
    rev = []
    for line in file:
        rev.insert(0, line)
    for line in rev:
        print line,

if __name__ == '__main__':
    f = open('data.txt', 'r')
    read_reverse(f)

2

タプルのタプルの方が扱いやすいのは、意味的なまとまりで区切っているためである。今回のコードでは、日付、緯度、経度、天気情報という意味でまとまっているので、データへのアクセスが単純化できる(経度は何番目だっけ?などと悩むことは減るだろう)。実は問題の解答がオライリーから提供されているが、誤りのように思われる。fieldsがタプルのタプルでないとループが適切に動かないためである。コード中の中で呼び出しているテキストファイルは提供されていないので、関数のコメントにある仕様に沿って作成する必要がある。

def read_weather_data(r):
    '''Read weather data from reader r in fixed-width format.
    The field widths are:
        4,2,2   YYYYMMDD (date)
        2,2,2   DDMMSS   (latitude)
        2,2,2   DDMMSS   (longitude)
        6,6,6   FF.FFF   (temp, deg. C; humidity, %; pressure, kPa)
    The result is a tuples of tuples,
 where each tuple is of the form:
    ((YY, MM, DD), (DD, MM, SS), (DD, MM, SS), (Temp, Hum, Press))'''
    fields = (((4, int), (2, int), (2, int)),       # date
              ((2, int), (2, int), (2, int)),       # latitude
              ((2, int), (2, int), (2, int)),       # longitude
              ((6, float), (6, float), (6, float))) # data
    result = []
    for line in r:
        start = 0
        for grp in fields:
            record = []
            for (width, target_type) in grp:
                text = line[start:start+width]
                field = target_type(text)
                record.append(field)
                start += width
            result.append(tuple(record))
    return result

if __name__ == '__main__':
    f = open('ex08_2_data.txt', 'r')
    ret = read_weather_data(f)
    print ret

3

# -*- encoding: sjis -*-
''' fieldが固定幅の場合、先頭からの位置の場合のどちらにも対応'''

def read_weather_data(r, fields):
    result = []

    for line in r:
        start = 0
        a_line = []
        for (width, target_type) in fields:
            text = line[start:start+width]
            field = target_type(text)
            a_line.append(field)
            start += width
        result.append(tuple(a_line))
    return result

def transform_fields(fields, last_idx):
    res = []

    for i in range(len(fields)):
        if i != len(fields)-1:
            width = fields[i+1][0] - fields[i][0]
        else:
            width = last_idx - fields[i][0]
        res.append((width, fields[i][1]))
    return(tuple(res))

def wrapper_function(data, fields):
    ''' 先頭の幅に関する値で入力のfieldの種類がどちらか判別する。
        0ならば、いったんfieldsを変換してread_weather_dataに入れる。
        これによりread_weather_dataの引数は1つ増えることになる。
    '''
    if fields[0][0] == 0:
        # 38はハードコードだが、幅の値は仕様であり、既知とする。
        fields = transform_fields(fields, 38)
    ret = read_weather_data(data, fields)
    return ret

if __name__ == '__main__':
    f = open('ex08_2_data.txt', 'r')
    '''
    fields = ((4, int), (2, int), (2, int),       # date
              (2, int), (2, int), (2, int),       # latitude
              (2, int), (2, int), (2, int),       # longitude
              (6, float), (6, float), (6, float)) # data
    '''
    fields = ((0, int),    (4, int),    (6, int),    # date
              (8, int),    (10, int),   (12, int),   # latitude
              (14, int),   (16, int),   (18, int),   # longitude
              (20, float), (26, float), (32, float)) # data
    ret = wrapper_function(f, fields)
    print ret

4,5(2問同時解答)

continueを利用することにより、インデントの数が減るので目を動かす量が減り、読みやすさは向上するものと思われる。

# -*- encoding: sjis -*-
import sys
import tsdl

def smallest_value(r):
    line = tsdl.skip_reader(r).strip()
    if not line:
        return -1 # something error occurred.
    smallest = int(line)

    for line in r:
        line = line.strip()
        if line == '-':
            continue
        value = int(line)
        if value < smallest:
            smallest = value

    return smallest

if __name__ == '__main__':
    input_file = open(sys.argv[1], 'r')
    print smallest_value(input_file)
    input_file.close()

6

以下のコードに登場するmultimol3.pdbは、通常のpdbに対し、CMNTで始まるコメント行やタブやスペースのみからなる空白の行が含まれたファイルになります。訳者のコードでは動かし方が分かりにくいので、メソッド名は採用しておりますが、1から書き直しています。

# -*- encoding: sjis -*-

def read_all_molecules(r):
    result = []
    reading = True
    while reading:
        molecule = read_molecule(r) # COMPNDという行からENDという行まで読む
        if molecule:
            result.append(molecule)
        else:
            reading = False
    return result

def get_line(r):
    ''' 空白やコメントでない行を返す。rは返す行の次の行の先頭に向かう '''

    while True:
        line = r.readline() # とりあえず1行読んで
        if not line: # 最後に来たら終了
            break
        line = line.strip() # 前後の空白を取り除いて
        if not line: # 空白ならばタブやスペースのみからなる行なので処理を続行
            continue
        elif line.startswith('CMNT'): # コメントであっても続行
            continue
        else: # それ以外はPDBファイルに必要な行である
            return line
    return ''

def read_molecule(r):
    line = get_line(r)
    if not line:
        return None

    key, name = line.split()
    molecule = [name]
    reading = True

    while reading:
        line = get_line(r)
        if line.startswith('END'):
            reading = False
        else:
            key, num, typ, x, y, z = line.split()
            molecule.append((typ, x, y, z))
    return molecule

if __name__ == '__main__':
    f = open('multimol3.pdb', 'r')
    ret = read_all_molecules(f)
    f.close()
    print ret

7

本来であれば、原子のシリアルナンバーが1ずつ大きくなっていない場合、プログラムの実行者に対し、何も結果を返さず、エラーを明示的に出してやるのがよい。途中まで出してそれを表示するということも考えられるが、正常終了に見えてしまうため、問題があるということを隠してしまうことになるので、そのような処理にしないほうがよいものと思われる。ただし、以下のコードではエラーの出し方が本テキスト読書中時点でははっきりしない(例外を投げてしまうのが一番よさげなのだが、例外の利用方法を知らない)ため、print文でエラーメッセージを出しつつ、途中で処理を打ち切るようにしている。この場合、途中までの結果が返されることになる。改めて解答しなおすことになりそうですが、ひとまず載せることにします。

# -*- encoding: sjis -*-

def read_all_molecules(r):
    result = []
    reading = True
    while reading:
        molecule = read_molecule(r) # COMPNDという行からENDという行まで読む
        if molecule:
            result.append(molecule)
        else:
            reading = False
    return result

def get_line(r):
    while True:
        line = r.readline()
        if not line:
            break
        line = line.strip()
        if not line: # 空白ならば続行
            continue
        elif line.startswith('CMNT'):
            continue
        else:
            return line
    return ''

def read_molecule(r):
    line = get_line(r)
    if not line:
        return None

    print line
    key, name = line.split()
    molecule = [name]
    reading = True
    check_num = 1
    ret_mol = True

    print "line = ", line
    while reading:
        line = get_line(r)
        if line.startswith('END'):
            reading = False
        else:
            print "!", line
            key, num, typ, x, y, z = line.split()
            if int(num) != check_num:
                print "serial number error in %s!" % molecule[0]
                return None # Noneとすることで続きの処理が行われなくなる
            check_num += 1
            molecule.append((typ, x, y, z))
    return molecule

if __name__ == '__main__':
    f = open('multimol4.pdb', 'r') # ファイルは適当にいじっておくように。
    ret = read_all_molecules(f)
    f.close()
    print ret

2012年5月22日火曜日

初めてのコンピュータサイエンス第7章解答

第7章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。全部あわせるとかなり長い解答です。問題文は載せませんので悪しからず。本は必要なら買いましょう。間違い(コード、英語)は指摘していただければ。よほどひどい解答が見つかったなら対応いたします。その前にこの章の個人的なメモ。

  • enumerateというシーケンスを受け取ると添え字とセットにして返す関数がある
  • x, y = 1, 2のような多重代入という仕組みがある。右辺は[1, 2]のようなリスト、文字列などシーケンスでも動作する。
  • ネストされたリストの長さが一定でない場合、ラグリスト(不規則リスト)と呼ばれる

1

問題文中の「前の値の2倍」というのは引数にとったリストの各要素を2倍しろという意味にとりました。もしかすると、1だけ小さい添え字のことを指しているのかもしれません。曖昧な問題文なのですが、一応解答をあげておきます。英語ではpreceeding valueを2倍なので、1つ前の添え字というよりも、処理前の要素と思うのですが...

def double_preceeding_correct(values):
    if values == []:
        pass
    else:
        values[0] = 0
        for i in range(1, len(values)):
            values[i] *= 2
    return values

print double_preceeding_correct([1, 2, 3])

2

rat1 = [23, 24, 22, 21, 22, 25, 26, 26, 23, 22]
rat2 = [21, 23, 24, 25, 26, 24, 24, 22, 21, 24]
# a)の解答
msg = "Rat %d weighed more than Rat %d on Day %d."
if rat1[0] > rat2[0]:
    print msg % (1, 2, 1) # 後から数値のみを付け加えることもできる
elif rat1[0] < rat2[0]:
    print msg % (2, 1, 1)
# b)の解答
if rat1[0] > rat2[0] and rat1[len(rat1)-1] > rat2[len(rat2)-1]:
    print "Rat 1 remained heavier than Rat 2."
else:
    print "Rat 2 became heavier than Rat 1."
# c)の解答
if rat1[0] > rat2[0]:
    if rat1[len(rat1)-1] > rat2[len(rat2)-1]:
        print "Rat 1 remained heavier than Rat 2."
    else:
        print "Rat 2 became heavier than Rat 1."

3~5

いずれも簡単な処理なので、一度にまとめて解答する。

print range(33, 50) # 3の解答

print range(10, 0, -1) # 4の解答、リストを降順にするには第3引数のステップ幅に負数を指定する

# 5の解答
total = 0
for num in range(2, 23):
    total += num

print float(total) / len(range(2,23)) # 整数/整数なので、切捨を避けるためfloatに変換しておく

6

もう少しコードを変形しすぎずに解答したいところなのですが...

def remove_neg_correct(num_list):
    '''num_listから正しく負数を取り除く'''
    result = []
    for item in num_list:
        if item >= 0:
            result.append(item)
    return result

aList = [1, 2, 3, -3, 6, -1, -3, 1]
result = remove_neg_correct(aList)
print result

7~8

def print_triangle_right(num):
    ''' Tを右三角形にして表示する'''
    for i in range(1, num+1):
        print 'T' * i

print_triangle_right(7)

def print_triangle_left(num):
    ''' Tを左三角形にして表示する'''
    for i in range(1, num+1):
        print ' ' * (num-i) + 'T' * i

print_triangle_left(7)

9

def print_triangle_right_while(num):
    ''' Tを右三角形にして表示する'''
    i = 1
    while i < num + 1:
        print 'T' * i
        i += 1

print_triangle_right_while(7)

def print_triangle_left_while(num):
    ''' Tを左三角形にして表示する'''
    i = 1
    while i < num + 1:
        print ' ' * (num -i) + 'T' * i
        i += 1

print_triangle_left_while(7)

10

rat_1_weight = 10
rat_2_weight = 10
rat_1_rate = 0.04
rat_2_rate = 0.04

# a)の解答
nWeek = 0
current_weight =  rat_1_weight
while True:
    nWeek += 1
    current_weight *= (rat_1_rate + 1)
    if current_weight > rat_1_weight * 1.25:
        break

print nWeek

# b)の解答
rat_2_rate = rat_1_rate + 0.03
rat1_current_weight = rat_1_weight
rat2_current_weight = rat_2_weight
nWeek = 0
while True:
    rat1_current_weight *= (rat_1_rate + 1.0)
    rat2_current_weight *= (rat_2_rate + 1.0)
    nWeek += 1
    if rat2_current_weight / rat1_current_weight > 1.1:
        break

print nWeek

11

import media

# 同じフォルダにあるマドレーヌの画像を利用している
madeleine = media.load_picture('pic207.jpg')
width, height = \
    media.get_width(madeleine), media.get_height(madeleine)

rotate = media.create_picture(height, width)
for y in range(0, height):
    for x in range(0, width):
        p_from = media.get_pixel(madeleine, x, y)
        p_to = media.get_pixel(rotate, height-y-1, x)
        media.set_color(p_to, media.get_color(p_from))

media.show(rotate)

12

a)の解答

import media

def swap_pix(pic, x1, y1, x2, y2):
    ''' swap color between (x1, y1) and (x2, y2) '''
    p1 = media.get_pixel(pic, x1, y1)
    p2 = media.get_pixel(pic, x2, y2)
    c1 = media.get_color(p1)
    c2 = media.get_color(p2)
    media.set_color(p1, c2)
    media.set_color(p2, c1)

def return_pic_size(pic):
    return media.get_width(pic), media.get_height(pic)

madeleine = media.load_picture('pic207.jpg')
width , height = return_pic_size(madeleine)

for y in range(0, height):
    for x in range(0, width/2):
        swap_pix(madeleine, x, y, width-x-1, y)

media.show(madeleine)

b)の解答。a)から改良を加えています。関数作成にこだわってみました。

import media

def swap_pix(pic, x1, y1, x2, y2):
    ''' swap color between (x1, y1) and (x2, y2) '''
    p1 = media.get_pixel(pic, x1, y1)
    p2 = media.get_pixel(pic, x2, y2)
    c1 = media.get_color(p1)
    c2 = media.get_color(p2)
    media.set_color(p1, c2)
    media.set_color(p2, c1)

def return_pic_size(pic):
    return media.get_width(pic), media.get_height(pic)

def y_axial_symmetry(pic):
    width , height = return_pic_size(madeleine)
    for y in range(0, height):
        for x in range(0, width/2):
            swap_pix(madeleine, x, y, width-x-1, y)

def x_axial_symmetry(pic):
    width , height = return_pic_size(madeleine)
    for y in range(0, height/2):
        for x in range(0, width):
            swap_pix(madeleine, x, y, x, height-y-1)

if __name__ == '__main__':
    madeleine = media.load_picture('pic207.jpg')
    x_axial_symmetry(madeleine)
    # y_axial_symmetry(madeleine)
    media.show(madeleine)

13

picを左上を基準にユークリッド距離でnピクセル離れた位置にある画素のみをサンプリングします。縮小した画像のサイズ計算が面倒ですね。

import math
import media

def down_scaling(pic, n):
    width, height = media.get_width(pic), media.get_height(pic)
    new_pic = media.create_picture(int(math.ceil(float(width)/n)),
                                   int(math.ceil(float(height)/n)))
    print new_pic.get_height(), new_pic.get_width()
    for y in range(height):
        for x in range(width):
            if y % n != 0 or x % n != 0:
                continue
            # print x, y, x/n, y/n
            p_from = media.get_pixel(pic, x, y)
            p_to = media.get_pixel(new_pic, x / n , y / n )
            target_col = media.get_color(p_from)
            media.set_color(p_to, target_col)

    return new_pic

if __name__ == '__main__':
    f = media.load_picture('pic207.jpg')
    ret = down_scaling(f, 2)
    media.show(ret)

14

問題よりも親切に10*10以外の平均値フィルタも実装しておりますが、端の処理だけは完全ではありません。問題の前提として、画像サイズは平均値フィルタの1辺のサイズで割り切れることを仮定しているため、これで解答としては十分と考えております。

import media

def fill_color(pic, x, y, n = 10):
    ''' make (x, y) to (x + n, y + n) rectangle pixels
        to the same color '''
    # print x, y
    r = g = b = 0
    for height in range(n):
        for width in range(n):
            a_pic = media.get_pixel(pic, x + width, y + height)
            r += media.get_red(a_pic)
            g += media.get_green(a_pic)
            b += media.get_blue(a_pic)
    r /= n*n
    g /= n*n
    b /= n*n
    set_color = media.create_color(r, g, b)
    for height in range(n):
        for width in range(n):
            a_pic = media.get_pixel(pic, x + width, y + height)
            media.set_color(a_pic, set_color)
    return pic

def mosaic_filter(pic, n = 10):
    ''' warning : edge is not processed if width and height is
        not divisible by n.
    '''
    width, height = media.get_width(pic), media.get_height(pic)
    for y in range(int(height/n)):
        for x in range(int(width/n)):
            fill_color(pic, x*n, y*n, n)
    return pic

if __name__ == '__main__':
    f = media.load_picture('pic207.jpg')
    mosaic_filter(f, 10)
    media.show(f)

15

ループをネストさせてモノクロイメージを作成する関数を作れという指示に従わない書き方もあるのですが、ここでは省略。create_monochrome_image関数の第2引数は3要素が必要で、それぞれr, g, bの重み付けに対応しています。全部同じ値にすればa)の解答、緑の重みを上げたのはb)の解答になります。重みはrgbからモノクロに変換する際によく使われる値を利用しています。実際のところ2種類でどの程度違うのかといわれると、私の目ではよく分からないところではありますが...

import media

def create_monochrome_image(pic, weight):
    ''' pic is picture to be processed.
        weight is weight for r, g, b values when we
        create monochrome image from color image.
        Default value should be [a, a, a], but
        green has more effective than other colors for human eyes,
        so when we take this fact into considaration,
        please change weight. ex.[a, 2a, a] (weight of green is hevier than that of others)
    '''
    s = float(sum(weight))
    for i in range(len(weight)):
        weight[i] /= s

    width, height = media.get_width(pic), media.get_height(pic)
    for y in range(height):
        for x in range(width):
            a_pic = media.get_pixel(pic, x, y)
            r = media.get_red(a_pic)
            g = media.get_green(a_pic)
            b = media.get_blue(a_pic)
            val = round(r * weight[0] + g * weight[1] + b * weight[2])
            col = media.create_color(val, val, val)
            media.set_color(a_pic, col)
    return pic

if __name__ == '__main__':
    f = media.load_picture('pic207.jpg')
    # create_monochrome_image(f, [1, 1, 1])
    create_monochrome_image(f, [0.299, 0.587, 0.114])
    media.show(f)

2012年5月17日木曜日

初めてのコンピュータサイエンス第6章解答

第6章の解答。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。その前にこの章の個人的なメモ。

  • 0、0.0はFalseであるが、それ以外の値はTrue

1

>>> True and not False
True
>>> True or True and False
True
>>> not True or not False
True
>>> True and not 0
True
>>> 52 < 52.3
True
>>> 1 + 52 < 52.3
False
>>> 4 != 4.0
False

2

後半のルールはよくない。被演算子のうち、0やFalseになるものを返すべきである。例えばx = 3 and 0はFalseだが、3を返すのはTrueを意味することになるので矛盾する。

3

>>> z = x and y # a)の解答
>>> z = not x # b)の解答
>>> z = x or y # c)の解答

4

>>> result = full or empty

5

友人の発言は正しい。二つの論理値がTrueとFalseという異なった値になっているときにifの中がTrueになるようにできているからである。

6

>>> x = -1
>>> result = x == abs(x)
>>> result
False

7

def different(a, b):
    return a != b

8

population = 10000
land_area = 200
if population > 10000000:
    print population

if 10000000 >= population >= 35000000:
    print population

if population / land_area > 100:
    print "過密"

if population / land_area > 100:
    print "過密"
else:
    print "過疎"

9

wikipediaで温度変換の公式を参照せよということなのですが、多少変更が加えられたのか、Newtonなどの温度へ変換する公式が指定されたページ内に見つからないため、全部実装するのは断念しています。考え方のみ参考にしてください。b)の解答は新しい単位を追加すると、if文を2回追加することになります。これはsourceをセルシウス度に変換するときに1度、セルシウス度からtargetに変更するのに1度追加する必要があるためです。

def temperatures(t, source, target):
    ''' Kelvin, Celsius, Fahrenheit, Rankine, Delisle, Newton, Reaumur
        とあるのだが、wikipediaでは最初の4つしかないので、4つのみで実装する
    '''
    if source == 'Kelvin':
        temp = float(t) - 273.15
        pass
    elif source == 'Celsius':
        temp = float(t)
        pass
    elif source == 'Fahrenheit':
        temp = (t - 32) * 5.0 / 9
        pass
    elif source == 'Rankine':
        temp = (t - 491.67) * 5.0 / 9
        pass
    else:
        return 'Error in source'

    if target == 'Kelvin':
        return temp + 273.15
    elif target == 'Celsius':
        return temp
    elif target == 'Fahrenheit':
        return temp * 9.0 / 5 + 32
    elif target == 'Rankine':
        return (temp + 273.15) * 9.0 / 5
    else:
        return 'Error in target'

print temperatures(10, 'Celsius', 'Celsius')
print temperatures(10, 'Celsius', 'Kelvin')

10

先に3.0未満か評価した。もしくは最初のifで3.0以上7.0未満で「酸性」と表示するような変更をしてもよいでしょう。

ph = 2.5
if ph < 3.0:
    print "%sは強酸性です。注意してください。" % ph
elif ph < 7.0:
    print "%sは酸性です。" % ph

11

a)、b)はどちらも"酸性です!"と表示される。c)の解答は以下の通り。

ph = float(raw_input("ph値を入力してください"))
if ph < 7.0:
    print "酸性です!"
if ph < 4.0: # elifからifに書き換える
    print "強酸性です!"

12

以下のようにすれば同じように書き換えればよい。

age = 30
bmi = 19.2
table = [['高', '中'], # 中、高を入れ替えておく
         ['中', '低']] # 低、中も同様
young = age < 45
light = bmi < 22.0 # heavy = bmi >= 22.0からの書き換え 
risk = table[young][light]
print risk

2012年5月14日月曜日

初めてのコンピュータサイエンス第5章解答

第5章の解答を上げます。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。その前にこの章の個人的なメモ。

  • リストはミュータブル(書き換え可能)であるのに対し、数値や文字列はイミュータブル(書き換えできない)である。
  • リストではエイリアシングによるエラーに注意。エイリアシングとは違う変数名が同じオブジェクトを指すことである。数値や文字列オブジェクトではエイリアシングはない。
  • リストメソッドは新しいリストを生成しない。また、popメソッドを除き、リストに関連するメソッドの返り値はNoneになる。
  • 1個の要素を持つタプル(イミュータブルなシーケンス)は(data, )のように","をつける必要がある。

1~4

>>> alkaline_earth_metals = [4, 12, 20, 38, 56, 88] # 1の解答
>>> alkaline_earth_metals[5] # 2の解答
88
>>> alkaline_earth_metals[-1]
88
>>> len(alkaline_earth_metals) # 3の解答
6
>>> max(alkaline_earth_metals) # 4の解答
88

5

改行かスペースかという違いがある。すなわちprint aは改行せず、print a,はスペースを入れる。

6

問題文には「5.5 スライシング」のhalf_livesリストとあるが、正しくは「5.3 リストの組み込み関数」と思われる。

>>> half_lives = [87.74, 24110.0, 6537.0, 14.4, 376000.0]
>>> for val in half_lives:
...     print val
... 
87.74
24110.0
6537.0
14.4
376000.0

7

>>> for val in half_lives:
...     print val, # ,を入れることで空白区切りで、改行なく出力する
... 
87.74 24110.0 6537.0 14.4 376000.0

8

country_populations = [1295, 23, 7, 3, 47, 21]
total = 0
for cp in country_populations:
    total += cp

print total

9~13

temps = [25.2, 16.8, 31.4, 23.9, 28, 22.5, 19.6] # 9の解答
temps.sort() # 10の解答
# 11の解答
cool_temps = [t for t in temps if t < 20] # リスト内包表記を用いている
# cool_temps = temps[:2]とする方法もあるが、一般化した解答を採用した
print cool_temps # tempsはソート済みなので、昇順に表示される
warm_temps = [t for t in temps if t >= 20]
print warm_temps # 上と同じくソート済みで表示される
temps_in_celsius = cool_temps + warm_temps # 12の解答
temps_in_fahrenheit = [] # 以下13の解答
for cels in temps_in_celsius:
    fahr = cels * 1.8 + 32
    temps_in_fahrenheit.append(fahr)

14~16

# 14の解答
alkaline_earth_metals = [[4, 9.012], [12, 24.305], [20, 40.078], \
 [38, 87.62], [56, 137.327], [88, 226]]
print alkaline_earth_metals
# 15の解答
for elem in alkaline_earth_metals:
    print elem[0], elem[1]
# 16の解答
number_and_weight = []
for elem in alkaline_earth_metals:
    number_and_weight.append(elem[0])
    number_and_weight.append(elem[1])
print number_and_weight

17

f = open('alkaline_metals.txt', 'r')
number_and_weight = []
for line in f:
    elems = line.split()
    number_and_weight.append([elems[0], elems[1]])

print number_and_weight

18

valuesに[0, 1, 2]という値が設定された後、values[1] = valuesによって、1という要素が[0, 1, 2]に差し替えられる。リストはミュータブルなので、値が書き換えられ、結局[0, [0, 1,2], 2]というリストになる。

19

def mystery_function(values):
    ''' 各リストのn番目の要素をn番目のリストの要素にする
        リストの要素数が不変でn*mの長方形型であれば、
        転置に相当する操作が行われる
    '''
    result = []
    for i in range(len(values[0])):
        result.append([values[0][i]]) # 先頭は一列目の値
        for j in range(1, len(values)):
            # result[-1]は上でappendしたもの。
            # i列目のj番目の要素を順にリストに追加する
            result[-1].append(values[j][i])
    return result

20

ミュータブルな文字列あったとき、例えば途中の文字を大文字に変換するといった操作は、便利であろう。イミュータブルにしている理由としては、文字列の生成時にメモリの割り当てを固定できるという点である。これによりパフォーマンスの向上が期待できる(www.python.jpのオフィシャルサイトにそのような記述がある)。

21

ソートするとNoneが返される。文字列と数字を比較すること自体に意味はない(Javaなどのchar型と比較するのは意味があるといえなくも無いですが...)。例えば3章の文字列の規則と照らし合わせ、'123' - 4は何かと問われると、定義する方法がないことに気づかされる('123'+(-4)の'+'は文字列として結合するか、足し算とみなすかで曖昧さが発生してしまう。Python側で勝手な処理をするとエラーの捕捉が難しくなってしまう)。返り値がNoneであればエラー処理をせよという考え方もできるので、Pythonの動作としては、このままでもよいものと思われる。

>>> ret = [1, 'a', 2, 'b'].sort()
>>> print ret
None

2012年5月13日日曜日

初めてのコンピュータサイエンス第4章解答

第4章の解答を上げます。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。その前にこの章の個人的なメモ。

  • import文は実行も同時に行っている。つまり、importするライブラリにprint関数があると、それが実行され、何か表示されるということになる。
  • builtin変数の__main__は重要。これにより実行しているファイルがimportする側なのか、importされた側なのか判別できる
  • python2.7でmediaモジュールを動かすときはこちらを参考に各種モジュールをインストールする。
  • サンプルで紹介されている画像pic207.jpgはこちらにある。ただし、テキストで利用している実物とは若干違うように思われる。

1

import math

print abs(round(-4.3))
print math.ceil(math.sin(34.5))

2

# b)の解答
import calendar
year = 2013
while True:
    if calendar.isleap(year):
        print year # 2016が表示される
        break
    year += 1
# c)の解答
help(calendar.isleap)

# isleap関数を用いたd)へのアプローチ方法
def nLeap(rng):
    nleap = 0
    for i in rng:
        if calendar.isleap(i):
            nleap += 1
    return nleap

# 1行が長いコードになる場合は\で続けて入力できる
print 'The number of leap year between %d to %d = %d' % \
 (2000, 2050, nLeap(range(2000, 2051)))

# d)の解答
print calendar.leapdays(2000, 2051)

# e)の解答
# help(calendar.weekday)
# 1が返されるので火曜日になる。0が月曜日~6が日曜日という仕様である。
print calendar.weekday(2016, 7, 19)

3

>>> 'boolean'.upper() # a)の解答
'BOOLEAN'
>>> 'C20 H20'.find('2', 0) # b)の解答
1
>>> 'C20 H20'.find('2', 2) # c)の解答。添え字1に'2'があるので2から後ろを探索する
5
>>> 'Boolean'[0].isupper() # d)の解答
True
>>> 'MoNDaY'.lower().capitalize() # e)の解答、文字列処理のメソッドは次々とかませられる
'Monday'
>>> ' Monday'.strip() # f)の解答
'Monday'

4

実数ではなく、文字列として表記しようとしているから。

5

mediaモジュールは特定の用途に限られているから標準ライブラリに含んでいない。標準モジュールに組み込むか否かの基準としては、標準的なデータに関わる操作に限ったものと思われる。標準ライブラリに含まれていないものについてはググル、もしくはPyPIで探すとよいでしょう。

6

import media
f = media.choose_file()
pic = media.load_picture(f)
media.show(pic)
media.show(pic)

7

import media
f = media.choose_file()
pic = media.load_picture(f)
for p in media.get_pixels(pic):
    media.set_red(p, 0)
media.show(pic)

8

import media
f = media.choose_file()
pic = media.load_picture(f)
for p in media.get_pixels(pic):
    media.set_green(p, media.get_green(p)/2)
media.show(pic)

9

import media
f = media.choose_file()
pic = media.load_picture(f)
for p in media.get_pixels(pic):
    col = media.get_color(p)
    col.r = col.b = col.g = (col.r + col.g + col.b)/3
    # set_colorメソッドは3色をまとめたオブジェクトが必要であることに注意!
    media.set_color(p, col)

media.show(pic)

10

ValueError: Invalid red value specified.というメッセージが出てエラーになる

import media
pic = media.load_picture(media.choose_file())
for p in media.get_pixels(pic):
    new_r = media.get_red(p) * 2
    media.set_red(p, new_r)

media.show(pic)

11

メディアは変更を加えていないイメージだけ利用するという制約は必要ないものと思われる。より画像をきれいに見えるようにする処理など、事実を的確に伝えるのに必要な処置はあってしかるべきと思われる。

12

a)について。浮動小数点を含む計算において、その値がある値になっているか評価するのは、丸め誤差が含まれていることがほとんどなので、難しくなってしまう。

b)について。距離の計算結果と想定される値の差が10^-6以下であれば、テストに合格と判断している。問題点としては10^-6という値の設定理由が不明瞭であること、またx0とx1を入れ替えたケースを追加することが必要になるということである。2点間のユークリッド距離を計算するのに4つの値が現れるが、そのうち、変化する値が2種類しかないのは心もとない。

2012年5月11日金曜日

初めてのコンピュータサイエンス第3章解答

第3章の解答を上げます。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず。必要なら買いましょう。

1

>>> 'Comp' 'Sci' # +がなくても文字列は結合される
'CompSci'
>>> 'Computer' + 'Science' # +を明示した方が読みやすい...
'ComputerScience'
>>> 'H20' * 3
'H20H20H20'
>>> 'C02' * 0 # 0回の繰り返しは空文字
''

2

>>> "They'll hibernate during the winter"
"They'll hibernate during the winter"
>>> '"Absolutely not," he said.'
'"Absolutely not," he said.'
>>> '"He said, \'Absolutely, not\'" recalled Mel.'
'"He said, \'Absolutely, not\'" recalled Mel.'
>>> 'hydrogen sulfide'
'hydrogen sulfide'
>>> 'left\right'
'left\right'

3

'A\nB\nC'

4

>>> len('')
0

5

>>> x = 3
>>> y = 12.5
>>> print 'The rabbit is %d' % x
The rabbit is 3
>>> print 'The rabbit is %d years old' % x
The rabbit is 3 years old
>>> print '%.1f is average' % y # .1fで小数点1桁まで表示する
12.5 is average
>>> print '%.1f * %d' % (y, x) # 複数の引数をとる場合は括弧で囲む
12.5 * 3
>>> print '%.1f * %d = %.1f' % (y, x, y * x)
12.5 * 3 = 37.5

6

>>> print "%.2f" % 34.5
34.50
>>> print "%.2e" % 34.5 # eは指数表示、.2で小数点第2位まで表示
3.45e+01
>>> print "%04d" % 8 # 0が0埋めを意味する
0008
>>> print "%-2d" % 8 # -が左詰めを意味する
8 

7

>>> num = float(raw_input("Please input number")) # 入力を求める画面が出るので3.14と入力
>>> print num
3.14

8

たとえば「文字列 + 整数」のようなデータに対し足し算を認めていないので、変数を+で結べないようにしている。'123' + 4 は文字列('1234')としてみるか、数値(127)としてみるかという複数の解釈が発生してしまうので、そのような問題も避けている。

9

文字列に負数をかけるという操作は無意味なものであり、0回かけた空文字列とは区別するべきという立場であればエラーにするべき。 ただし、そこに気をつけていれば、負数をかけることでエラーにならないことは処理が簡単になるというメリットもあると思われる。

フォロワー

ページビューの合計