コルーチン化によって関数のテスト可能性を高める
マージソートみたいな関数は、テストが書きにくいと思います。マージソートを書くときはだいたい下のように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)