テスト駆動開発を利用したfibonacciのPythonコード作成

1.概要

開発手法としてKent BeckのTDD(Test-Driven Development)を活用しています。参考書籍ではJavaを利用してfibonacci関数をTDDで開発する手法が紹介されています。ここでは、Pythonを利用してJava版と同じことを最初に実施します。

次に再帰呼出しの問題点を指摘して、再帰呼出しを利用しない方式へTDDで改良します。改良した結果、大きなfibonaccの計算ができるようになるので、試します。

TDDはテストコードを作成し、そのテストコードがパスするコードを作成するという作業を続けて、目的とするコードを作成する手法です。アジャイル(XP手法)の１つであり、スクラムなどの開発でも幅広く利用されている方法です。テストコードはUnitテスト方式で作成します。UnitテストはKent Beckが開発したものです。

2.再帰呼出による詳細説明

fibonacci数列は、0,1,1,2,3,5,8,13,.....と継続する数列で、先行する２つの数値を足した値が、次の数値になる無限に続く数列です。初期値と次の値は、0と1になっています。

(1) testcode(TestFibonacci.py)を作成

import unittest
from fibonacci import Fibonacci

class TestFibonacci(unittest.TestCase):
    None

if __name__ == '__main__':
    unittest.main()

(2) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py

fibonacciが存在しないとのエラー発生

Traceback (most recent call last):
  File "TestFibonacci.py", line 4, in <module>
    from fibonacci import Fibonacci
ModuleNotFoundError: No module named 'fibonacci'

(3) code(finonacci.py)を作成

class Fibonacci:
    None

if __name__ == '__main__':
    obj = Fibonacci()

(4) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py

実行エラーがなくなりました。これで、testcodeとcodeのベースができました

Ran 0 tests in 0.000s
OK

(5) testcode(TestFibonacci.py)を修正

初期値の0,1を記述します。

import unittest
from fibonacci import Fibonacci

class TestFibonacci(unittest.TestCase):

    def setUp(self):
        self.obj = Fibonacci()
    def tearDown(self):
        del self.obj
    def testFibonacci01(self):
        assert(self.obj.fibonacci(0) == 0)
        assert(self.obj.fibonacci(1) == 1)
        
if __name__ == '__main__':
    unittest.main()

(6) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py

testFibonacci01でエラー発生。fibonacci(0)が計算できていない

ERROR: testFibonacci01 (__main__.TestFibonacci)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "TestFibonacci.py", line 13, in testFibonacci01
    assert(self.obj.fibonacci(0) == 0)
AttributeError: 'Fibonacci' object has no attribute 'fibonacci'

----------------------------------------------------------------------
Ran 1 test in 0.000s

FAILED (errors=1)

(7) code(finonacci.py)を修正

初期値処理を追加します

class Fibonacci:
    def fibonacci(self, number):
        if number == 0:
            return 0
        if number == 1:
            return 1

if __name__ == '__main__':
    obj = Fibonacci()

(8) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py
エラーがなくなります

Ran 1 test in 0.000s
OK

(9) testcode(TestFibonacci.py)を修正

３番目の項目の試験を記述します。
１番目と２番目の項目を加えると、３番目の項目になります。

import unittest
from fibonacci import Fibonacci

class TestFibonacci(unittest.TestCase):
    def setUp(self):
        self.obj = Fibonacci()
    def tearDown(self):
        del self.obj
    def testFibonacci01(self):
        assert(self.obj.fibonacci(0) == 0)
        assert(self.obj.fibonacci(1) == 1)
        assert(self.obj.fibonacci(2) == \
                self.obj.fibonacci(0) + self.obj.fibonacci(1))

if __name__ == '__main__':
    unittest.main()

(10) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py
testFibonacci01でエラー発生。fibonacci(2)が計算できていない

FAIL: testFibonacci01 (__main__.TestFibonacci)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "TestFibonacci.py", line 15, in testFibonacci01
    assert(self.obj.fibonacci(2) == \
AssertionError

----------------------------------------------------------------------
Ran 1 test in 0.000s
FAILED (failures=1)

(11) code(finonacci.py)を修正

３番目以降の処理を追加します

class Fibonacci:
    def fibonacci(self, number):
        if number == 0:
            return 0
        if number == 1:
            return 1
        return (self.fibonacci(number-2) + self.fibonacci(number-1))

if __name__ == '__main__':
    obj = Fibonacci()

(12) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py
エラーがなくなります
Ran 1 test in 0.000s
OK

(13) testcode(TestFibonacci.py)を修正

１０番目の項目の試験を記述します。
８番目と９番目の項目を加えると、１０番目の項目になります。

import unittest
from fibonacci import Fibonacci

class TestFibonacci(unittest.TestCase):
    def setUp(self):
        self.obj = Fibonacci()
    def tearDown(self):
        del self.obj
    def testFibonacci01(self):
        assert(self.obj.fibonacci(0) == 0)
        assert(self.obj.fibonacci(1) == 1)
        assert(self.obj.fibonacci(2) == \
                self.obj.fibonacci(0) + self.obj.fibonacci(1))
        assert(self.obj.fibonacci(10) == \
                self.obj.fibonacci(8) + self.obj.fibonacci(9))

if __name__ == '__main__':
    unittest.main()

(14) testcode(TestFibonacci.py)を実行
python3 TestFibonacci.py

Ran 1 test in 0.000s
OK

これで、fibonacci関数プログラムfibonacci.pyが完成しました。

3.再帰呼出を止めた性能向上詳細

fibonacci数列は、0,1,1,2,3,5,8,13,.....と継続する数列で、先行する２つの数値を足した値が、次の数値になる無限に続く数列です。初期値と次の値は、0と1になっています。前回作成したtestcode(Testfibonacci.py)とcode(fibonacci.py)を利用して修正します。

(1) testcode(TestFibonacci.py)を修正

５０番目の項目の試験を記述します。
４８番目と４９番目の項目を加えると、５０番目の項目になります。
この試験項目を追加します。

import unittest
from fibonacci import Fibonacci

class TestFibonacci(unittest.TestCase):

    def setUp(self):
        self.obj = Fibonacci()
    def tearDown(self):
        del self.obj
    def testFibonacci01(self):
        assert(self.obj.fibonacci(0) == 0)
        assert(self.obj.fibonacci(1) == 1)
        assert(self.obj.fibonacci(2) == \
                self.obj.fibonacci(0) + self.obj.fibonacci(1))
        assert(self.obj.fibonacci(10) == \
                self.obj.fibonacci(8) + self.obj.fibonacci(9))
        assert(self.obj.fibonacci(50) == \
                self.obj.fibonacci(48) + self.obj.fibonacci(49))

if __name__ == '__main__':
    unittest.main()

(2) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py

実行すると処理が終わりません。しばらく経過しても何も変わりません。
そこで、Ctrl-Cで終了します。
理由は以下の通りです。

fibonacci(50) = fibonacci(48) + fibonacci(49)

この式は以下の計算が必要です
fibonacci(48) = fibonacci(46) + fibonacci(47)
fibonacci(49) = fibonacci(47) + fibonacci(48)

更にこの式は以下の計算が必要です
fibonacci(46) = fibonacci(44) + fibonacci(45)
fibonacci(47) = fibonacci(45) + fibonacci(46)
fibonacci(47) = fibonacci(45) + fibonacci(46)
fibonacci(48) = fibonacci(46) + fibonacci(47)

この計算をfibonacci(0), fibonacci(1)になるまで実施する必要があり、計算量が非常に多くなります。つまり、再帰呼出しがボトルネックです。

そこで、fibonacci(N)に対して、fibolist = [0,1,1,2,3,......]とN個のlistを作成するように変えます

(3) code(finonacci.py)を修正

初期値と次の項目を処理するコードに変更します。

class Fibonacci:
    def fibonacci(self, number):
        fibolist = [0,1]
        return fibolist[number]

if __name__ == '__main__':
    obj = Fibonacci()

(4) testcode(TestFibonacci.py)を実行

python3 TestFibonacci.py

fibonacci(2)でエラーになります。

RROR: testFibonacci01 (__main__.TestFibonacci)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "TestFibonacci.py", line 15, in testFibonacci01
    assert(self.obj.fibonacci(2) == \
  File "/home/nakasima/mycode/fibotest/fibonacci.py", line 11, in fibonacci
    return fibolist[number]
IndexError: list index out of range

----------------------------------------------------------------------
Ran 1 test in 0.000s

FAILED (errors=1)

(5) code(finonacci.py)を修正

３番目以降をfibolistに追加するロジックを追加します。

class Fibonacci:
    def fibonacci(self, number):
        fibolist = [0,1]
        for i in range(2, number+1):
            fibolist.append(fibolist[i-2] + fibolist[i-1])
        return fibolist[number]

if __name__ == '__main__':
    obj = Fibonacci()

(6) testcode(TestFibonacci.py)を実行
python3 TestFibonacci.py
エラーがなくなります

Ran 1 test in 0.000s
OK

これで、fibonacci関数プログラムを再帰呼出しを利用せずにfibonacci.pyが完成しました。

4.性能向上版の実行詳細

fibonacci数列は、0,1,1,2,3,5,8,13,.....と継続する数列で、先行する２つの数値を足した値が、次の数値になる無限に続く数列です。初期値と次の値は、0と1になっています。前回作成したcode(fibonacci.py)を利用して修正します。

(1) code(fibonacci.py)を修正

まず、手始めにfibonacci(50)を計算するように修正します。

class Fibonacci:
    def fibonacci(self, number):
        fibolist = [0,1]
        for i in range(2, number+1):
            fibolist.append(fibolist[i-2] + fibolist[i-1])
        return fibolist[number]

if __name__ == '__main__':
    obj = Fibonacci()
    print(obj.fibonacci(50))
    print()

(2) coce(fibonacci.py)の実行

$ python3 fibonacci.py
12586269025

(3) code(fibonacci.py)を修正

次に、fibonacci(100000)を計算します。
非常に大きな整数になるので桁数も表示します。

class Fibonacci:
    def fibonacci(self, number):
        fibolist = [0,1]
        for i in range(2, number+1):
            fibolist.append(fibolist[i-2] + fibolist[i-1])
        return fibolist[number]

if __name__ == '__main__':
    obj = Fibonacci()
    print(obj.fibonacci(100000))
    print()
    print(len(str(obj.fibonacci(100000))))

(4) coce(fibonacci.py)の実行

$ python3 fibonacci.py

添付実行結果
$ python3 fibonacci.py

259740693472217241661550340212759154148804853865176965847247707039525345435112736862656837743
............
4355609970015699780289236362349895374653428746875

20899
２万桁を超える結果です。

5.所見

TDDはお気に入りの開発手法です。いつもテストコードが先とは限りませんが、必ずセットになるように作成しています。TDDの完全な利用でなくてもテストコードを必ず作成する方式を採用すると、後のプログラムメンテナンスがとても楽になります。

汎用機時代から様々なプログラム言語を利用してプログラム作成をしてきました。仕様書とテスト仕様書を作成することが長かったのですが、紙ベースのテストでは再実行をするためには、人手が必要となり、効率が上がらず、十分なテストになりません。結果の確認も人手に頼ることになり、正確性にかけています。

TDDを初めて勉強した時に、この方式が最善策だと感じて、それ以降、TDDを利用するようになりました。TDDは様々な言語で利用できるようになっています。Unitテストと言われる手法です。参考書籍ではUnitテスト自体を開発する説明も記載され、理解を深めることが可能です。

fibonacci(100000)が実行できたので、fibonacci(1000000)も実行しました。しかし、PCがハングしたようになりました。利用しているPCのMemory容量では実行できないサイズになっていると考えました。

参考

[本ブログ内参照]
参考書籍
テスト駆動開発入門　ケント・ベック著 

コメント

コメントを投稿

過去30日間に良く読まれた記事

miniPCのBMAXでWindows11のsecure boot設定漏れでトラブル発生

0.推奨 Windows11をプリインストールモデルの状態で利用されている場合は問題になることはありません。Windows11のUSB bootメディアを作成して自分で新規導入したり、Windows10からWindows11へupgradeをした場合。Windows11への移行条件確認が十分でない状態があったのではないかと思います。Windows11で必須要件を満たさずに移行されたWindows11環境がありました。 今回のトラブルでBitLockerの48桁の回復キーがないことが痛手でした。Windows11を利用する上でBitLockerの回復キーは大切に保管が必要です。secure bootを設定するとディスクは暗号化されてしまいます。障害復旧に回復キーは必須です。６月の証明書期限切れで問題が発生して、思わぬ事態にならぬように早めにチェックすること、回復キーを保管することを推奨します。 1.概要 始まりは、参考資料の「6月からパソコンが動かなくなる？」です。miniPCのsecure boot設定をmsinfo32で確認すると「無効」でした。そこで、BIOSの設定でsecure bootをenableに設定して、msinfo32は「有効」になりました。これが暗号化設定と認識不足でした。Windows Updateを実行して証明書の更新を実行すると、Windows Updateのボタンが赤色に変わりました。ここからトラブルです。理解不足で複数のミスが重なり、データを消失。復旧も時間を必要としました。その内容を記述します。 2.詳細 (1) トラブルの始まり ネット記事で、secure boot設定が必要で、６月にPCが動かなくなると思って、BIOS設定を変更したことが始まりです。この変更は、BIOSでSecurityのsecure bootをdisableからenableに変更だけです。Windows11を起動してmsinfo32で有効をチェックして完了。追加としてWindows Updateで証明書の導入をしてからハマりました。 障害の状況は、Windows11自体は普通に使えるのですが、Windows Updateのボタンが赤色。文字も赤字に変わりました。今後、発生するupdate適用ができなくなると認識しました。 (2) GoogleAI(Gemini)に...
続きを読む

Windows95/98のPCゲームをUbuntu/LinuxMintの最新PCで楽しむ方法 ( KVM / Wine / dosbox-x / midi )

1.概要 Ubuntults 24.04のリポジトリを利用するLinuxMint 22.3で、32bitのアプリケーションを楽しむことができるのか整理をしました。今回、仮想環境のKVMでの試験を実施して、KVM,Wine,Dosbox-xの３種類を実施した範囲で、遜色なく利用できるのはDosbox-xだけでした。KVMやWineではサウンド処理関連の互換性がなくなったような気がします。この内容に関して記述します。 注意事項 Windowsの利用にあたっては、Microsoftが定める使用許諾契約（EULA）を遵守する必要があります。ライセンス違反（不正なプロダクトキーの利用、規約外の商用利用など）は違法行為となるため、必ず正規のライセンスを取得・確認した上で操作を行ってください。 2.詳細 (1)KVM環境 KVM環境はRegacyBIOS互換のCSMで試しました。KVM上でWindows98SEは起動します。デバイスマネージャを参照した範囲ではエラーはありませんが、サウンドが想定通りに再生されない点、ディスプレイ表示設定が思うようにならない点がありました。どちらもドライバの問題と思います。構築した環境はUbuntu 22.04まで試験をしていた環境です。仮想ソフト（KVM, VMware, Virtualboxなど）は新しい環境への対応を進める中で古い環境の互換性は保たれなくなっていると感じています。 (a) KVMにWindows98seを導入 Windows98の仮想マシンを作成（サポート期間が切れたOSを選択） Memory=128MB、CPU=1、Disk=0.5GBを選択 インストールの前に設定をカスタマイズするを選択 ブートオプション：IDE CD-ROMにチェック CD-ROM bootのため、IDE ディスクとIDE CR-ROMの順番を入替える サウンド ich6：sb16を上書設定 ビデオ QXL：cirrusを上書設定 CD-ROM boot後、CD-ROMサポート付きmsdosを利用して、fdiskでCドライブを作成 再度、上記構成で再起動をして、d:\win98にてformat c:を実行してfat16で初期化 d:\win98のsetupを実行して導入 (2)Wine環境 Wine 11.8で試験をしました。 ディスプレイ表示は普通に使...
続きを読む

LinuxMint/ubuntuにWine 11導入を試しました ( LinuxMint 21.3 / 22.3 ubuntu 22.04 / 26.04 Wine 11.0 / 11.6 / 11.8 / 11.13 )

1.概要 Wine 11.0がリリースされました。メジャーアップデートで「Wine 11.0 6300以上の変更と600件以上の不具合修正を反映」と記載されています。早速、試してみることにしました。少し前にWinBoatを導入したことと比較すると、とても簡単でミスをすることはありません。しかし、Windowsのアプリを動かす意味を考え直すことになりました。 ubuntu desktop 26.04をKVM環境で評価しているので、Wine 11.13(最新版)導入を試しました。手順はWikiに記載されている手順で問題なく実施できます。詳細手順は、4.追加に記載します。 2.詳細 環境は、intel i3, Memory 16GBのPCにLinuxMint-21.3を新規導入しました。 Wine 11.0の導入手順を見つけるのに少し手間取りましたが、Wiki/Debian-Ubuntuに詳しく記載されています。 その手順に沿って作業を実施しました。 $ cat /etc/os-release $ sudo mkdir -pm755 /etc/apt/keyrings $ wget -O - https://dl.winehq.org/wine-builds/winehq.key | sudo gpg --dearmor -o /etc/apt/keyrings/winehq-archive.key - $ sudo dpkg --add-architecture i386 $ sudo wget -NP /etc/apt/sources.list.d/ https://dl.winehq.org/wine-builds/ubuntu/dists/jammy/winehq-jammy.sources $ sudo apt update $ sudo apt install --install-recommends winehq-stable $ wine --version $ sudo apt install winetricks $ winetricks cjkfonts $ winetricks --version 上記手順でWine 11.0の導入が終わります。３分間程度なので負担はありません。日本語環境も導入しました。 何をしようかと考えて、動かしたいWindo...
続きを読む