初めてのコンピュータサイエンス第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()