第１章
「世界で闘うプログラミング力を鍛える150問」と並行して、こちらも少し読み始めました。
まず１章読んだので、軽くまとめ。
ポイントは"TRAFFIC"
T rack : 問題をデータベースに記録する
R eproduction : 障害を再現する
A utomate : テストケースの自動化と単純化を行う
F ind : 感染源の疑いがある箇所を見つける
F ocus : 感染源の疑いが最も高い箇所に着手する
I solate : 感染の連鎖を分離する
C orrect : 欠陥を修正する
言葉で書かれてもピンと来ない人向けに、実際のプログラムの問題解析をベースに解説されています。
サンプルは sample.c にありますが、せっかくなんでPythonで書きました。
汚い(特にsort_list関数)ですが、それはわざとです。ロジックが分かりづらいソースコードの解析のためですね。
まぁこれよりひどいのをよく見かけますが。。。
#encoding: utf-8 import sys def sort_list(num_list, size): h = 1 while True: h = h * 3 if h > size: break while True: if h == 1: break h /= 3 i = h for i in range(1, size): j = i v = num_list[i] while True: if j < h or num_list[j - h] <= v: break else: num_list[j] = num_list[j - h] j -= h if i != j: num_list[j] = v if __name__ == '__main__': num_list = [] for i in range(0, len(sys.argv) - 1): num_list.append(sys.argv[i + 1]) sort_list(num_list, len(sys.argv))
先に書いておくと、Cとは挙動が違います。
テキストにあるcのコードだと、以下のような挙動になるようです。
> ./sample 9 7 8
Output: 7 8 9
> ./sample 11 14
Output: 0 11
Pythonのコードだと、どちらもエラーになります。
この問題はallocしたメモリ外をアクセスすることによって発生するってものなんですが、
Pythonだとそもそもメモり外をアクセスした時点でエラーってことですね。
Cだとそうならないのが辛いですよね。とりあえず動いちゃうから、ある日突然障害が起きたりするわけで。。。
さて、テキストではこの問題について、先ほどのTRAFFICに沿って問題調査をします。
が、まとめるの面倒なので省略。ただ、それぞれの詳細な説明については、以下の通り各章であるようです。
T rack : 問題をデータベースに記録する
➡2章
R eproduction : 障害を再現する
➡4章
A utomate : テストケースの自動化と単純化を行う
➡3章、5章
F ind : 感染源の疑いがある箇所を見つける
➡7章、9章
F ocus : 感染源の疑いが最も高い箇所に着手する
➡7章、8章、10章、11章、13章、14章、16章
I solate : 感染の連鎖を分離する
➡6章
C orrect : 欠陥を修正する
➡15章
実際にはFind、Focus、Isolateを繰り返す作業になります。
これが一番大変なのですが、そのための技術を「自動デバッグテクニック」として紹介。
入力の単純化
➡差分デバッグを使用。詳細は5章。
プログラムスライス
➡演繹法で、怪しいソースコードを絞る。詳細は7章。
状態の観察
➡デバッガで特定時点の状態を観察。詳細は8章。
状態の監視
➡デバッガで特定変数を監視。詳細は8章。
アサーション
➡Unit Testのアサーションのこと？詳細は10章。
異常
➡異常の検出法と書いてあるけど、全部そうなのじゃ？詳細は11章。
ミスから学ぶ
➡これは毛色が違って、過去のバグ報告から、不安定なモジュールを選んでactiveに調査。詳細は15章、16章。
最後に言葉の定義。
欠陥(defect) ：不正なプログラムコード (コードに含まれるバグ)
感染(infection)：不正なプログラム状態 (状態に含まれるバグ)
障害(failure)：外部から観察できる、不正なプログラムの動作 (動作に含まれるバグ)
今後やることについての概観って感じの章でした。
さて、ジム行ってくる！
問題3.2
3章入りました。
最初popのこと考えなかったので簡単かと思いきや、、、ってやつですね。
まぁ最初なんでウォーミングアップ。
問題
pushとpopに加えて、最小の要素を返す関数minを持つスタックをどのようにデザインしますか？ただしpush、pop、min関数はすべてO(1)の実行時間になるようにしてください。
pystack.py
#encoding: utf-8 class PyStack(): ''' pushとpopを行うクラス。 >>> stack_instance = PyStack() >>> stack_instance.push(10) >>> stack_instance.push(20) >>> stack_instance.push(0) >>> stack_instance.pop() 0 >>> stack_instance.pop() 20 >>> stack_instance.pop() 10 >>> stack_instance.pop() ''' def __init__(self): self.stack_data = [] def push(self, num): self.stack_data.append(num) def pop(self): if len(self.stack_data) > 0: return self.stack_data.pop() else: return None def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
これをインポートしたけど、ほとんど変えてるのでインポートしてる意味ないですね。笑。
まぁ普通のスタックだけクラスで分離しておいた方が、多分後の問題で使う気がするので。
3-2.py
#encoding: utf-8 from pystack import PyStack class PyStackWithMin(PyStack): ''' スタッククラスに新機能を追加。 スタックの中で最小値を返す。 push、pop、min関数の実行時間はすべてO(1)。 >>> stack_instance = PyStackWithMin() >>> stack_instance.min() >>> stack_instance.push(30) >>> stack_instance.min() 30 >>> stack_instance.push(20) >>> stack_instance.min() 20 >>> stack_instance.push(10) >>> stack_instance.min() 10 >>> stack_instance.push(10) >>> stack_instance.min() 10 >>> stack_instance.pop() 10 >>> stack_instance.min() 10 >>> stack_instance.pop() 10 >>> stack_instance.min() 20 >>> stack_instance.pop() 20 >>> stack_instance.min() 30 >>> stack_instance.pop() 30 >>> stack_instance.min() >>> stack_instance.pop() ''' def __init__(self): self.stack_data = [] self.min_stack = [] def push(self, num): # 最小値更新処理。最小値と同じ値をpushする時の処理に注意。 if len(self.min_stack) == 0 or num <= self.min_stack[-1]: self.min_stack.append(num) self.stack_data.append(num) def pop(self): if len(self.stack_data) > 0: # 最小値が取り出されたら、最小値更新。 if self.stack_data[-1] == self.min_stack[-1]: self.min_stack.pop() return self.stack_data.pop() else: return None def min(self): if len(self.min_stack) == 0: return None else: return self.min_stack[-1] def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題2.7
問題集だと、また再帰で解いてますね。
再帰ねー。数学脳じゃないんで、どうも苦手。
はやくこの問題集終わらせて、オライリーの「デバッグの理論と実装」読みたいので、再帰はやりませぬ。
って、まだ問題集130問以上あるけどね。。。
問題
連結リストが回文(先頭から巡回しても末尾から巡回しても、各ノードの要素がまったく同じになっている)かどうかを調べる関数を実装してください。
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def is_kaibun(linked_list): ''' 連結リストが示す文が回文かどうかをチェックする関数 >>> linked_list = LinkedList() >>> linked_list.insert(0, 'a') >>> linked_list.insert(1, 'b') >>> linked_list.insert(2, 'c') >>> linked_list.insert(3, 'b') >>> linked_list.insert(4, 'a') >>> is_kaibun(linked_list) True >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 'a') >>> linked_list2.insert(1, 'b') >>> linked_list2.insert(2, 'c') >>> linked_list2.insert(3, 'b') >>> linked_list2.insert(4, 'b') >>> is_kaibun(linked_list2) False ''' # 「ランナー」テクニック使用 fast = linked_list.get_top() slow = linked_list.get_top() # リストの前半を入れるスタック stack_list = [] # リストの真ん中を調べる while True: if not fast.get_next() or not fast.get_next().get_next(): list_target = slow.get_next() break else: # リストの前半はスタックに入れる stack_list.append(slow.get_data()) fast = fast.get_next().get_next() slow = slow.get_next() # リストの前半と後半を比較 while len(stack_list) > 0: if stack_list.pop() != list_target.get_data(): return False list_target = list_target.get_next() return True def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題2.6
今回は解答みないと解けませんでした。
リスト処理でランナーテクニックって定石らしいです。
多分大学で教えてたんだろうね。ほとんど行ってなかったからね。。。
問題
循環する連結リストが与えられたとき、循環する部分の最初のノードを返すアルゴリズムを実装してください。
定義
循環を含む連結リスト：連結リストAではループを作る為に、リスト内のノードの次へのポインタが以前に出現したノードを指している。
例
入力：A -> B -> C -> D -> E -> C [最初のCと同じもの]
出力：C
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
#encoding: utf-8 from pylist import Cell def find_loop_head(head_cell): ''' 循環する連結リストが与えられたとき、循環する部分の最初のノードを返す関数 >>> cell10 = Cell(10) >>> cell9 = Cell(9, cell10) >>> cell8 = Cell(8, cell9) >>> cell7 = Cell(7, cell8) >>> cell6 = Cell(6, cell7) >>> cell5 = Cell(5, cell6) >>> cell4 = Cell(4, cell5) >>> cell3 = Cell(3, cell4) >>> cell2 = Cell(2, cell3) >>> cell1 = Cell(1, cell2) >>> cell0 = Cell(0, cell1) >>> cell10.set_next(cell3) >>> find_loop_head(cell0) 3 >>> cell10 = Cell(10) >>> cell9 = Cell(9, cell10) >>> cell8 = Cell(8, cell9) >>> cell7 = Cell(7, cell8) >>> cell6 = Cell(6, cell7) >>> cell5 = Cell(5, cell6) >>> cell4 = Cell(4, cell5) >>> cell3 = Cell(3, cell4) >>> cell2 = Cell(2, cell3) >>> cell1 = Cell(1, cell2) >>> cell0 = Cell(0, cell1) >>> find_loop_head(cell0) ''' # ファストランナーとスローランナーによる「ランナー」テクニック使用 fast = head_cell slow = head_cell # ループの検出 while True: # ループ無し if fast is None or fast.get_next() is None: return None else: fast = fast.get_next().get_next() slow = slow.get_next() # ループ発見 if fast is slow: break # 先頭からループ開始点までをkとする。 # スローランナーがループ開始点に到着した時、ファストランナーはループ開始点からkノード目。 # ファストランナーはスローランナーより(ループサイズ - k)後方にいる。 # ファストランナーはスローランナーに1セルずづ近づくので、(ループサイズ - k)ステップ後に衝突。 # よってループ開始点より(ループサイズ - k)ステップ先で衝突する。つまりループ開始点までkステップの地点。 # 以上より、衝突地点からkステップ進めたところがループ開始点。 # 同じ速度のランナーが、リストの先頭からと、衝突点から、それぞれスタートすれば、ループ開始点で衝突する。 fast = head_cell while fast is not slow: fast = fast.get_next() slow = slow.get_next() return fast.get_data() def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題2.5
今回は同じ問題を２通りの方法で解いてみました。
１個目が、最初に何も考えずに解いた解法。
２個目が、解答みて再帰使ってたので、そちらを取り入れたもの。
どっちがいいんでしょうねぇ。
たしかに１個目はきれいじゃないからバグも出やすい感じ。再帰の方がコードも短くシンプル。
でもやっぱり再帰の脳が頭の中にないから、これはこれで間違いそう。
慣れの問題？
問題
各ノードの要素が1桁の数である連結リストで表された2つの数があります。一の位がリストの先頭になるように、各位の数は逆順に並んでいます。このとき2つの数の和を求め、それを連結リストで表したものを返す関数を書いてください。
例
入力：(7 -> 1 -> 6) + (5 -> 9 -> 2) -> 617 + 295
出力：2 -> 1 -> 9 -> 912
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
2-5.py (1個目の解法)
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def list_addition(linked_list1, linked_list2): ''' 各ノードの要素が1桁の数字で構成された2つのリストの足し算を行う関数。 リストは一の位が先頭になるよう、逆順に並んでいる。 結果も逆順のリストで返す。 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list1.insert(1, 2) >>> linked_list1.insert(2, 3) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 5) >>> linked_list2.insert(2, 9) >>> result_list = list_addition(linked_list1, linked_list2) >>> result_list.index(5) 0 >>> result_list.index(7) 1 >>> result_list.index(2) 2 >>> result_list.index(1) 3 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 6) >>> linked_list2.insert(2, 7) >>> result_list = list_addition(linked_list1, linked_list2) >>> result_list.index(5) 0 >>> result_list.index(6) 1 >>> result_list.index(7) 2 ''' # 結果のリスト格納用 result_list = LinkedList() # linked_list1とlinked_list2の先頭セルを取得 cell1 = linked_list1.get_top() cell2 = linked_list2.get_top() # 2つのリストの足し算処理 counter = 0 # 繰り上げ用 carry = 0 # 各桁の足し算用 tmp_value = carry while True: if not cell1 and not cell2 and carry == 0: break # 2つのリストの各桁と繰り上げ数の足し算 if cell1: tmp_value += cell1.get_data() cell1 = cell1.get_next() if cell2: tmp_value += cell2.get_data() cell2 = cell2.get_next() # 繰り上げ考慮 if tmp_value >= 10: carry = 1 result_list.insert(counter, tmp_value - 10) else: carry = 0 result_list.insert(counter, tmp_value) # 次の桁に繰り上げを渡す tmp_value = carry counter += 1 return result_list def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
2-5r.py (2個目の解法)
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def list_addition_recursion(cell1, cell2, carry): ''' 各ノードの要素が1桁の数字で構成された2つのリストの足し算を行う関数。 リストは一の位が先頭になるよう、逆順に並んでいる。 結果も逆順のリストで返す。 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list1.insert(1, 2) >>> linked_list1.insert(2, 3) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 5) >>> linked_list2.insert(2, 9) >>> result_list = list_addition_recursion(linked_list1.get_top(), linked_list2.get_top(), 0) >>> print result_list.get_data() 5 >>> print result_list.get_next().get_data() 7 >>> print result_list.get_next().get_next().get_data() 2 >>> print result_list.get_next().get_next().get_next().get_data() 1 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 6) >>> linked_list2.insert(2, 7) >>> result_list = list_addition_recursion(linked_list1.get_top(), linked_list2.get_top(), 0) >>> print result_list.get_data() 5 >>> print result_list.get_next().get_data() 6 >>> print result_list.get_next().get_next().get_data() 7 ''' # 各桁の足し算結果格納用セル result_cell = Cell(0) # 足し算用 tmp_value = carry # 再帰終了条件 if not cell1 and not cell2 and carry == 0: return None # 足し算処理 if cell1: tmp_value += cell1.get_data() if cell2: tmp_value += cell2.get_data() # データを格納して、次の桁を再帰処理 result_cell.set_data(tmp_value % 10) next_cell = list_addition_recursion(cell1.get_next() if cell1 else None, cell2.get_next() if cell2 else None, 1 if tmp_value >= 10 else 0) result_cell.set_next(next_cell) return result_cell def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題2.4
昨日呑みに行ったばかりに、せっかく毎日書いてたブログが早速途切れてしまった。
ってか今日も明日も明々後日も呑みなんだけど。師走。。。
問題
ある数xが与えられたとき、連結リストの要素を並べ替え、xより小さいものが前にくるようにするコードを書いてください。
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def dimidiate_list(linked_list, number): ''' numberより小さい値と、number以上の値とで、linked_listを二分する関数 >>> linked_list = LinkedList() >>> linked_list.insert(0, 100) >>> linked_list.insert(1, 200) >>> linked_list.insert(2, 300) >>> linked_list.insert(3, 250) >>> linked_list.insert(4, 150) >>> linked_list.insert(5, 500) >>> dimidiate_list(linked_list, 300) >>> linked_list.index(100) 0 >>> linked_list.index(200) 1 >>> linked_list.index(250) 2 >>> linked_list.index(150) 3 >>> linked_list.index(300) 4 >>> linked_list.index(500) 5 ''' # numberより小さい値リストの先頭と末尾セル smaller_linked_list_head = None smaller_linked_list_tail = None # number以上リストの先頭と末尾セル bigger_linked_list_head = None bigger_linked_list_tail = None # numberより小さい値とnumber以上の値とでリスト分割 cell = linked_list.get_top() while cell: if cell.get_data() < number: if not smaller_linked_list_head: smaller_linked_list_head = cell smaller_linked_list_tail = cell else: smaller_linked_list_tail.set_next(cell) smaller_linked_list_tail = cell else: if not bigger_linked_list_head: bigger_linked_list_head = cell bigger_linked_list_tail = cell else: bigger_linked_list_tail.set_next(cell) bigger_linked_list_tail = cell cell = cell.get_next() # 2つのリストを連結 smaller_linked_list_tail.set_next(bigger_linked_list_head) def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
備考
テキストだと別の解き方も紹介してます。説明するのは面倒なので省略するけど、リストの並びが変わっちゃ駄目とは書いてないから、その方法もたしかに・・・って感じ。
問題2.3
問題自体は簡単。
Pythonのオーバーライドや、doctestのELLIPSISの使い方は多少参考になるかも？
ってかこの本、邦訳が悪いのか、たまに質問の意味がわからないですね。
問題
単方向連結リストにおいて、中央の要素のみアクセス可能であるとします。その要素を削除するアルゴリズムを実装してください。
例
入力：a->b->c->d->eという連結リストのcが与えられます。
結果：何も返しませんが、リストはa->b->d->eのように見えます。
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
pylist2.py (単方向連結リスト)
#encoding: utf-8 from pylist import Cell from pylist import LinkedList class LinkedList2(LinkedList): ''' LinkedListとほぼ同じだが、insert関数だけ変更したクラス >>> linked_list = LinkedList2() >>> linked_list.get_top() >>> linked_list.insert(0, 100) # doctest:+ELLIPSIS <pylist.Cell instance at ...> >>> print linked_list.index(100) 0 ''' # オリジナルのinsertと同じだが、作成したCellのポインタを返す関数 def insert(self, offset, data): # offsetが0もしくはリストが空の時 if offset == 0 or not self.top: self.top = Cell(data, self.top) return self.top else: cell = self.top while cell.get_next(): offset -= 1 if offset == 0: break cell = cell.get_next() # 新たにセルを作成し、リストに挿入する added_cell = Cell(data, cell.get_next()) cell.set_next(added_cell) return added_cell def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
2-3.py (指定セルの削除)
#encoding: utf-8 from pylist2 import Cell from pylist2 import LinkedList2 def delete_cell(linked_list, cell): ''' linked_listよりcellを削除する関数。 linked_listの先頭セルはアクセス不可とする。 >>> linked_list = LinkedList2() >>> target_cell1 = linked_list.insert(0, 'a') >>> linked_list.insert(1, 'b') #doctest:+ELLIPSIS <pylist.Cell instance at ...> >>> linked_list.insert(2, 'c') #doctest:+ELLIPSIS <pylist.Cell instance at ...> >>> target_cell2 = linked_list.insert(3, 'd') >>> linked_list.insert(4, 'e') #doctest:+ELLIPSIS <pylist.Cell instance at ...> >>> target_cell3 = linked_list.insert(5, 'f') >>> linked_list.index('d') 3 >>> delete_cell(linked_list, target_cell2) True >>> linked_list.index('d') -1 >>> delete_cell(linked_list, target_cell1) True >>> linked_list.index('a') -1 >>> delete_cell(linked_list, target_cell3) False ''' if cell.get_next(): # 指定されたセルの次のセルを、指定されたセルに上書き。 next_cell = cell.get_next() cell.set_data(next_cell.get_data()) cell.set_next(next_cell.get_next()) return True # 末尾のセルは削除対象外 else: return False def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
