テスト駆動開発を利用したfibonacciのPythonコード作成
1.概要
本記事は2023年の記事です。TDD（テスト駆動開発）の開発手法を利用して私はプログラムを作成するようになりました。そのきっかけはKent Beckの書籍です。Kent BeckはアジャイルのXP手法の提唱者であり、UnitTestの最初の開発者です。プログラム作成方法を変えた原点なので、備忘録に残すべきと考えました。
開発手法としてKent BeckのTDD(Test-Driven Development)を活用しています。参考書籍ではJavaを利用してfibonacci関数をTDDで開発する手法が紹介されています。ここでは、Pythonを利用してJava版と同じことを最初に実施します。
次に再帰呼出しの問題点を指摘して、再帰呼出しを利用しない方式へTDDで改良します。改良した結果、大きなfibonacciの計算ができるようになります。
TDDはテストコードを作成し、そのテストコードがパスするコードを作成するという作業を続けて、目的とするコードを作成する手法です。アジャイル(XP手法)の１つであり、スクラムなどの開発でも幅広く利用されている方法です。テストコードはUnitテスト方式で作成します。UnitテストはKent Beckが最初にjunitを開発し、様々な言語に波及しました。
2.再帰呼出による詳細説明
fibonacci数列は、0,1,1,2,3,5,8,13,.....と継続する数列で、先行する２つの数値を足した値が、次の数値になる無限に続く数列です。初期値と次の値は、0と1になっています。
2.1 【Red】環境のセットアップとテスト失敗（ステップ1〜2）
(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'
2.2 【Green】最小限のクラス作成（ステップ3〜4）
(3) code(fibonacci.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
2.3 【Red】初期値（0, 1）のテスト追加（ステップ5〜6）
(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)
2.4 【Green】初期値処理の補正（ステップ7〜8）
(7) code(fibonacci.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
2.5 【Red/Green】3番目以降の再帰処理の実装（ステップ9〜12）
(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(fibonacci.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(fibonacci.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(fibonacci.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
２万桁を超える結果です。
考察と改善
fibonacci(100000)が実行できたので、fibonacci(1000000)も実行しました。しかし、PCがハングしたようになりました。利用しているPCのMemory容量では実行できないサイズになっていると考えました。改善策を考察します。
すべての数値をリスト（
しかし、フィボナッチ数列の計算に必要なのは「直前の2つの値」だけなので、変数2つだけを使い回せば、メモリ（空間計算量）をほぼゼロに抑えることができます。
fibolist）に保存すると、100万番目の時には「100万個の巨大な整数」がメモリを埋め尽くしてしまい、PCがフリーズ（ハング）してしまいます。しかし、フィボナッチ数列の計算に必要なのは「直前の2つの値」だけなので、変数2つだけを使い回せば、メモリ（空間計算量）をほぼゼロに抑えることができます。
是非、TDDを利用して、チャレンジして欲しいと思います。
5.所見
TDDはお気に入りの開発手法です。いつもテストコードが先とは限りませんが、必ずセットになるように作成しています。TDDの完全な利用でなくてもテストコードを必ず作成する方式を採用すると、後のプログラムメンテナンスがとても楽になります。
汎用機時代から様々なプログラム言語を利用してプログラム作成をしてきました。仕様書とテスト仕様書を作成することが長かったのですが、紙ベースのテストでは再実行をするためには、人手が必要となり、効率が上がらず、十分なテストになりません。結果の確認も人手に頼ることになり、正確性にかけています。
TDDを初めて勉強した時に、この方式が最善策だと感じて、それ以降、TDDを利用するようになりました。TDDは様々な言語で利用できるようになっています。Unitテストと言われる手法の応用です。参考書籍ではUnitテスト自体を開発する説明も記載され、理解を深めることが可能です。
記事の更新
2026/08/27
参考
[本ブログ内参照]
参考書籍
テスト駆動開発入門 ケント・ベック著
コメント
コメントを投稿