読者です 読者をやめる 読者になる 読者になる

コルーチン化によって関数のテスト可能性を高める

マージソートみたいな関数は、テストが書きにくいと思います。マージソートを書くときはだいたい下のようにprintで書きだして、動いているか見ながらプログラムを書くような感じになると思います。

def MergeSort0(data, l=0, r=None):
    if r is None:
        r = len(data)
    if l >= r-1:
        return
    m = (l + r)/2
    MergeSort0(data, l, m)
    MergeSort0(data, m, r)
    Merge(data, l, m, r)
    #print "l=%d, m=%d, r=%d" % (l, m, r)
def Merge(data, lb, le, re):
    left = data[lb: le]
    right = data[le: re]    
    i = 0
    j = 0
    n1 = len(left)
    n2 = len(right)
    n = len(data)
    for k in range(lb, re):
        if i == n1:
            for idx, elem in enumerate(right[j:]):
                data[idx+k] = elem
            return
        elif j == n2:
            for idx, elem in enumerate(left[i:]):
                data[idx+k] = elem
            return
        if left[i] <= right[j]:
            data[k] = left[i]
            i += 1
        else:
            data[k] = right[j]
            j += 1
import unittest
from test import test_support
class MergeSortTest(unittest.TestCase):
    def test_merge_sort0(self): 
        data = [5, 2, 7, 4, 3, 1, 6, 2]
        MergeSort0(data)
        self.assertEqual([1, 2, 2, 3, 4, 5, 6, 7], data)

どうにか分割してテスト可能にできないかなぁと思ったら、なんとなくコルーチン化したら良いかなと思いました。コルーチンに書きなおせば、「ソート」という一つの操作を「マージする範囲を生成する」、「指定された範囲をマージする」の二つの操作に分けられます。また、この分け目こそprintデバッグしていたポイントでもあります。

#!/usr/bin/env python2.6
def MergeSortGenerator(data, l=0, r=None):
    if r is None:
        r = len(data)
    if l >= r-1:
        return
    m = (l + r)/2
    for i in MergeSortGenerator(data, l, m):
        yield i
    for i in MergeSortGenerator(data, m, r):
        yield i
    yield data, l, m, r
def MergeSort(data, l=0, r=None):
    for i in MergeSortGenerator(data, l, r):
        Merge(*i)
import unittest
from test import test_support
class MergeSortTest(unittest.TestCase):
    def test_merge_sort_gen(self):
        data = [1, 3, 4, 7, 2, 4, 6, 8]
        g = MergeSortGenerator(data)
        expections = [
            (0, 1, 2),
            (2, 3, 4),
            (0, 2, 4),
            (4, 5, 6),
            (6, 7, 8),
            (4, 6, 8),
            (0, 4, 8),
            ]
        for expection in expections:
            self.assertEqual(expection, next(g)[1:])
    def test_merge_sort(self): 
        data = [5, 2, 7, 4, 3, 1, 6, 2]
        MergeSort(data)
        self.assertEqual([1, 2, 2, 3, 4, 5, 6, 7], data)