noseとpudbを使ったテスト駆動開発

ソートされた配列の中に与えられた値があるかを調べるためのアルゴリズムに二分探索があります。二分探索の歴史は古くKnuth先生によれば、最初に二分探索の考え方が公開されたのは1946年だったのに、バグなしのプログラムが出版されたのは1962年になってからだったそうです。
というわけで、今回は二分探索のコードを実装しながらPythonのテストユーティリティであるnoseモジュールと、CUIベースのデバッグ環境であるpudbモジュール、そしてnoseからpudbを呼び出すnose-pudbモジュールを使ってPythonにおける簡単なテスト駆動開発を行ってみようと思います。

準備

nose, pudb, nose-pudbをいつものようにeasy_installを使ってインストールします。

テストを書いてみる

二分探索アルゴリズムの詳細はさておき、テスト駆動開発なのでとりあえずテストをこんな感じに書いてみました(test_binary_search.py)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
from binary_search import MyTuple # これから実装する
from nose.tools import assert_equal, assert_raises

class TestMyTuple:
    def test_binary_search(self):
        t = MyTuple([0, 10, 20, 30, 40]) # 配列の中身は0, 10, 20, 30, 40
        for i in range(5):
            assert_raises(ValueError, t.binary_search, 10 * i - 5) # 無い場合はValueErrorを投げる
            assert_equal(t.binary_search(10 * i), i) # あった場合はインデックスが返ってくる

ではテストを実行してみます。

$ nosetests -v test_binary_search.py --pudb
python.binary_search.TestMyTuple.test_binary_search ... FAIL

======================================================================
FAIL: python.binary_search.TestMyTuple.test_binary_search
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/local/lib/python2.6/dist-packages/nose-0.11.3-py2.6.egg/nose/case.py", line 186, in runTest
    self.test(*self.arg)
  File "/home/yuku_t/python/test_binary_search.py", line 11, in test_binary_search
    assert_raises(ValueError, t.binary_search, 10 * i - 5)
AssertionError: ValueError not raised

----------------------------------------------------------------------
Ran 1 test in 0.001s

FAILED (failures=1)

nosetestsコマンドを呼ぶことでテストを実行できます。ここではtest_binary_search.pyに書いてあるテストを実行し、もしErrorが発生した場合はnose-pudbを使ってpudbを呼び出すようにしています。今回はFailureが発生しただけなのでpudbは呼ばれません。nosetestsのその他のオプションについてはnosetests -hを実行すれば確認することができます。
さて、当然ですがここではテストは失敗しています。次はこのテストを通過するようなMyTupleクラスを実装します。

二分探索を実装

二分探索の詳しいアルゴリズムはこちら→二分探索
そして、以下のように実装してみました(binary_search.py)

#!/usr/bin/env python
# -*- coding:utf-8 -*-

class MyTuple(tuple):
    def binary_search(self, t):
        l = 0 # 探索範囲の下限
        u = len(self) - 1 # 探索範囲の上限
        while l <= u:
            m = (l + u) / 2
            if self[m] < t:
                l = m
            elif self[m] > t:
                u = m
            else: # self[m] == t
                return m
        raise ValueError

さっそくテストを実行してみると...

$ nosetests -v test_binary_search.py --pudb
python.test_binary_search.TestMyTuple.test_binary_search ...

こんなところで止まって結果が返ってきません。どうやら無限ループに入ってしまっているようです。それではpudbを使ってデバッグしてみましょう。

pudbを使ってデバッグしてみる

binary_search.pyに以下を追加します。

if __name__ == "__main__":
    t = MyTuple([0, 10, 20, 30,40])
    t.binary_search(0)
    t.binary_search(10)
    t.binary_search(20)
    t.binary_search(30)
    t.binary_search(40)

そして、pudbを使ってbinary_search.pyを実行します

$ python -m pudb.run binary_search.py

するとこんな画面が表示されるはずです

pudbのコマンドの詳しい使い方は別のサイトに譲るとして、ここでは's'ボタンをとりあえず押しながら、右上のVariablesボックスの中を見てみましょう。ここには、現在インタプリタがいる環境に束縛されている変数の値が表示されるので、変数lとuの値の変遷を見ながら二分探索の探索範囲がどのように変化していくのかを見てみます。
さて、's'ボタンを押しつづけていくとt.binary_search(40)の中で永遠とループし始めます。このとき、Variablesの欄からl=3, u=4, m=3となっているのが分かります。

'q'ボタンを2回押すと抜けられます。
どうやらlやuの更新の仕方に問題があるようだと分かりました。そこで、色々考えた挙句、以下のようにコードを変更しました。

class MyTuple(tuple):
    def binary_search(self, t):
        l = 0 # 探索範囲の下限
        u = len(self) - 1 # 探索範囲の上限
        while l <= u:
            m = (l + u) / 2
            if self[m] < t:
                l = m + 1 # 変更
            elif self[m] > t:
                u = m - 1 # 変更
            else: # self[m] == t
                return m
        raise ValueError

テストを実行してみると

$ nosetests -v test_binary_search.py --pudb
python.test_binary_search.TestMyTuple.test_binary_search ... ok

----------------------------------------------------------------------
Ran 1 test in 0.001s

OK

めでたくテストを通過するようになりました!!

最後に

今回は二分探索アルゴリズムの実装をしながらnoseやpudbの使い方を簡単に説明しました。題材の選び方が悪くて*1nose-pudbの威力を紹介することはできなかったのですが、pudbの使い方が分かれば問題無く使いこなせるようになるはずです。
テスト駆動とか言いながら、テストがしょぼ過ぎる！などの指摘は勘弁してください。。。