merge_sort和单元测试

Question

我做了一个合并排序，并想要求检查代码。它通过了所有单元测试。经典Mergesort算法的思想是将数组分成两部分，每一半进行排序，然后将这两部分合并成一个排序列表。

示例：

merge_sort([2,7,5,9,8,9]) -> [2,5,7,8,9,9]

merge_sort()([7,1,8,2]) -> [1,2,7,8]

merge_sort()([2]) -> [2]

[] -> [Empty] list 

合并排序

def merge(xs, ys):
    xs, ys = iter(xs), iter(ys)
    x,  y  = next(xs,None), next(ys,None)
    while x and y:
        yield min(x,y)
        if x <= y: x = next(xs, None)
        else:      y = next(ys, None)

    # Yield remaining items from whichever list isn't empty
    yield [x,y][x is None]
    for item in [xs,ys][x is None]: yield item

def merge_sort(xs):
    # from heapq import merge
    if len(xs) < 2:
        return xs

    mid = len(xs)/2
    return list(merge(merge_sort(xs[:mid]), merge_sort(xs[mid:])))



# unit testing

#!python

from merge_sort import quicksort

from sorting import merge_sort
import unittest

# Change this variable to the sort function you want to test
is_sort = quick_sort2


class IsSortedTest(unittest.TestCase):
    def test_merge_sort_on_sorted_integers(self):
        # Positive test cases (examples) with lists of sorted integers
        assert merge_sort([])  # Empty lists are vacuously sorted
        assert merge_sort([3])  # Single item is trivially sorted
        assert merge_sort([3, 3])  # Duplicate items are in order
        assert merge_sort([3, 5])
        assert merge_sort([3, 5, 7])
        # : Write more positive test cases with assert  statements
        assert merge_sort([-4, -3, -2, -1])
        assert merge_sort([-4, -4, -4, -4])
        assert merge_sort([-4, 0, 4])
        assert merge_sort([-4, 0, -0, 4])

    def test_merge_sort_on_unsorted_integers(self):
        # Negative test cases (counterexamples) with lists of unsorted integers
        assert not merge_sort([5, 3])  # is False
        assert not merge_sort([3, 5, 3])  # is False
        assert not merge_sort([7, 5, 3])  # is False
        # : Write more negative test cases with assert # is False statements
        assert not merge_sort([-11, 3, 2])  # is False
        assert not merge_sort([2, -1, 1, 1])  # is False
        assert not merge_sort([4, -3, 2, -1])  # is False

    def test_merge_sort_on_sorted_strings(self):
        # Positive test cases (examples) with lists of sorted strings
        assert merge_sort(['A'])  # Single item is trivially sorted
        assert merge_sort(['A', 'A'])  # Duplicate items are in order
        assert merge_sort(['A', 'B'])
        assert merge_sort(['A', 'B', 'C'])
        # : Write more positive test cases with assert  statements
        # You'll need a lot more than this to test sorting algorithm robustness
        # lowercase
        assert merge_sort(['a', 'b', 'c'])
        assert merge_sort(['a', 'a', 'c'])
        # Mixed
        assert merge_sort(['A', 'a', 'b'])
        assert merge_sort(['C', 'a', 'b'])
        # Testing Multiple
        assert merge_sort(['AA', 'BB', 'CC'])
        assert merge_sort(['AA', 'BA', 'CA'])
        assert merge_sort(['AAAA', 'BB', 'CCC'])
        assert merge_sort(['AA', 'AAA', 'AAAA'])

    def test_merge_sort_on_unsorted_strings(self):
        # Negative test cases (counterexamples) with lists of unsorted strings
        assert not merge_sort(['B', 'A'])  # is False
        assert not merge_sort(['A', 'B', 'A'])  # is False
        assert not merge_sort(['C', 'B', 'A'])  # is False
        # : Write more negative test cases with assert # is False statements
        # You'll need a lot more than this to test sorting algorithm robustness
        # Multiple
        assert not merge_sort(['CCC', 'BBB', 'AAA'])  # is False
        assert not merge_sort(['CCCC', 'CCC', 'C'])  # is False
        # Lowercase
        assert not merge_sort(['c', 'b', 'a'])  # is False
        assert not merge_sort(['c', 'c', 'a'])  # is False

    def test_merge_sort_on_sorted_tuples(self):
        # Positive test cases (examples) with lists of sorted tuples
        assert merge_sort([(3, 5)])  # Single item
        assert merge_sort([(3, 'A')])  # Single item
        assert merge_sort([('A', 3)])  # Single item
        assert merge_sort([('A', 'B')])  # Single item
        assert merge_sort([(3, 5), (3, 5)])  # Duplicate items
        assert merge_sort([(3, 'A'), (3, 'A')])  # Duplicate items
        assert merge_sort([('A', 3), ('A', 3)])  # Duplicate items
        assert merge_sort([('A', 'B'), ('A', 'B')])  # Duplicate items
        assert merge_sort([('A', 3), ('B', 5)])  # Both items sorted
        assert merge_sort([('A', 3), ('B', 3)])  # First item sorted
        assert merge_sort([('A', 3), ('A', 5)])  # Second item sorted
        assert merge_sort([(3, 'A'), (5, 'B')])  # Both items sorted
        assert merge_sort([(3, 'A'), (5, 'A')])  # First item sorted
        assert merge_sort([(3, 'A'), (3, 'B')])  # Second item sorted
        # : Write more positive test cases with assert  statements
        # ...

    def test_merge_sort_on_unsorted_tuples(self):
        # Negative test cases (counterexamples) with lists of unsorted tuples
        assert not merge_sort([(5, 'B'), (3, 'A')])  # is False  # Both items unsorted
        assert not merge_sort([(5, 'A'), (3, 'B')])  # is False  # First item unsorted
        assert not merge_sort([(3, 'B'), (3, 'A')])  # is False  # Second item unsorted
        assert not merge_sort([('B', 5), ('A', 3)])  # is False  # Both items unsorted
        assert not merge_sort([('B', 3), ('A', 5)])  # is False  # First item unsorted
        assert not merge_sort([('A', 5), ('A', 3)])  # is False  # Second item unsorted
        # : Write more negative test cases with assert # is False statements
        # ...



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

Answer 1

while x and y:
    yield min(x,y)
    if x <= y: x = next(xs, None)
    else:      y = next(ys, None)

这是正确的。但是，请注意，它依赖于min的稳定性保证，以确保如果两个对象相等，则生成的对象与被更新的对象相同。这是一个相当微妙的假设。

为了清楚起见，我个人更愿意将yield放在if块中。它还将避免对比较进行两次测试，这对于对某些数据类型进行排序可能是一种比较昂贵的操作。

while x and y:
    if x <= y:
         yield x
         x = next(xs, None)
    else:
         yield y
         y = next(ys, None)

两者都有

from merge_sort import quicksort

和

is_sort = quick_sort2

看上去很困惑。快艇在这里做什么？我怀疑这是需要清理的剩余代码。

您的测试用例显示了通用和特殊用例在一系列数据类型之间的良好扩展。我建议对对象类型进行一些测试，特别是根据它们的比较函数相等的对象，但如果不是这样，则可以区分这些对象。例如

class TestObject(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.x < other.x
    def __str__(self):
        return "LTO (%d, %d)" % (self.x, self.y)

如前所述，这些帮助检查排序的稳定性(相等的对象相对于未排序的列表保持相同的顺序)和正确性(特别是排序列表确实包含与输入相同的元素)。

我不熟悉这种编写Python测试的方法。这意味着我不能说的更多，这看起来很奇怪。我希望测试用例能够指定所需的函数输出。也许就像

assertEqual(merge_sort([3, 7, 5]), [3, 5, 7])