冒泡排序算法与Python中的单元测试

Question

我是Python方面的新手，我从排序算法、PEP8和Python的禅宗开始了我的旅程。到目前为止，我写了一篇BubbleSort文章，我得出了结论并遵循了建议。我用维基百科的优化实现了两种方法。我想询问有关当前代码、测试和目录的信息。

1. 是否有可能更简洁地编写测试？
2. 我应该使用测试进行文档化吗？(或者函数的特定名称就足够了)
3. 代码与Python的PEP8和Zen兼容吗？
4. 代码与Python风格的编码兼容吗？
5. 我应该更改什么以避免代码将来出现问题？
6. 我是否应该向函数中添加更多选项，例如:反向选项、默认选项、异常？(或者在算法中没有必要)
7. 我应该添加比较器吗？那应该是一堂课吗？你能给点建议吗？
8. 我的目录布局正确吗？
9. 如果你在课文中发现了其他的东西，试着给我这个信息。

我的目录看起来是：

Python:.
│
├───algorithms
│   └───sorting
│           bubble_sort.py
│           __init__.py
│
└───tests
    └───algorithms
        └───sorting
                bubble_sort_test.py
                __init__.py

bubble_sort.py

import copy


def bubble_sort_v_one(container: object) -> object:
    """
        Bubble sort with first optimization.

        Description
        ----------
        From wikipedia: inner loop can avoid looking
        at the last (length − 1) items when running for the n-th time.
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.

        Returns
        -------
        container : Sorted container

        Examples
        ----------
        >>> bubble_sort_v_one([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_one(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    container = copy.copy(container)
    length = len(container)
    changed = True

    while changed:
        changed = False
        for i in range(length - 1):
            if container[i] > container[i + 1]:
                container[i], container[i + 1] = container[i + 1], container[i]
                changed = True
        length -= 1
    return container


def bubble_sort_v_two(container: object) -> object:
    """
        Bubble sort with second optimization.

        Description
        ----------
        From wikipedia: This allows us to skip over a lot of the elements,
        resulting in about a worst case 50% improvement in comparison count.
        Performance cases:
        Worst      : O(n^2) - 50%
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.

        Returns
        -------
        container : Sorted container

        Examples
        ----------
        >>> bubble_sort_v_two([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_two(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    container = copy.copy(container)
    length = len(container)

    while length >= 1:
        changed_times = 0
        for i in range(1, length):
            if container[i - 1] > container[i]:
                container[i - 1], container[i] = container[i], container[i - 1]
                changed_times = i
        length = changed_times
    return container

bubble_sort_test.py

import unittest

from Algorithms.Sorting.bubble_sort import bubble_sort_v_one as bubble_one
from Algorithms.Sorting.bubble_sort import bubble_sort_v_two as bubble_two


class TestBubbleSortVOneAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_one([5, 5, 7, 8, 2, 4, 1]),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_one([-1, -3, -5, -7, -9, -5]),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_one([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_one([1, 1, 1, 1]), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_one([]), [])

class TestBubbleSortVTwoAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_two([5, 5, 7, 8, 2, 4, 1]),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_two([-1, -3, -5, -7, -9, -5]),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_two([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_two([1, 1, 1, 1]), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_two([]), [])


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

我是否应该添加bubble_sort函数，这样用户就可以选择更容易运行的版本？

def bubble_sort(container: object, version : int = 1) -> object:
    if version == 1:
        bubble_sort_v_one(container)
    elif version == 2:
        bubble_sort_v_two(container)
    else:
        raise ValueError

您如何看待比较器和编辑函数的头部：

def comparator(a: object, b: object) -> object:
    return a - b


def bubble_sort_v_one(container: object, comparator=comparator) -> object:

当然，比较这两个变量的线应该是这样的：

if comparator(container[i] , container[i + 1]) > 0:

当然，问题不仅仅是关于这段代码的。我想知道这种方法将来是否将帮助我编写正确和干净的代码，并增加它的功能。

所以我的bubble_sort.py看起来是：

import copy


def comparator(a, b):
    return a - b


def bubble_sort(container, version: int = 1, cmp=comparator):
    if version == 1:
        return bubble_sort_v_one(container, cmp)
    elif version == 2:
        return bubble_sort_v_two(container, cmp)
    else:
        raise ValueError


def bubble_sort_v_one(container, cmp):
    """
        Bubble sort with first optimization.

        Description
        ----------
        From wikipedia : inner loop can avoid looking
        at the last (length − 1) items when running for the n-th time.
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best       : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.
        cmp : Comparator default a - b > 0

        Returns
        -------
        container : New sorted container,

        Examples
        ----------
        >>> bubble_sort_v_one([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_one(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    container = copy.copy(container)
    length = len(container)
    changed = True
    while changed:
        changed = False
        for i in range(length - 1):
            if cmp(container[i], container[i + 1]) > 0:
                container[i], container[i + 1] = container[i + 1], container[i]
                changed = True
        length -= 1
    return container


def bubble_sort_v_two(container, cmp):
    """
        Bubble sort with second optimization.

        Description
        ----------
        From wikipedia: This allows us to skip over a lot of the elements,
        resulting in about a worst case 50% improvement in comparison count.
        Performance cases:
        Worst      : O(n^2) - 50%
        Average    : O(n^2)
        Best       : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.
        cmp : Comparator default a - b > 0

        Returns
        -------
        container : New sorted container,

        Examples
        ----------
        >>> bubble_sort_v_two([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_two(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    container = copy.copy(container)
    length = len(container)

    while length >= 1:
        changed_times = 0
        for i in range(1, length):
            if cmp(container[i - 1], container[i]) > 0:
                container[i - 1], container[i] = container[i], container[i - 1]
                changed_times = i
        length = changed_times
    return container

和bubble_sort_test.py

import unittest

from Algorithms.Sorting.bubble_sort import bubble_sort


class TestBubbleSortVOneAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1]),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5]),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_with_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1],
                                     cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1])

    def test_bubble_sort_negative_numbers_only_reverse(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5],
                                     cmp=lambda x, y: y - x),
                         [-1, -3, -5, -5, -7, -9])

    def test_bubble_sort_with_negative_and_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1],
                                     cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1, 0, -4, -5, -6])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_sort([1, 1, 1, 1]), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_sort([]), [])


class TestBubbleSortVTwoAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1], version=2),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5], version=2),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1], version=2),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_with_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1], version=2,
                                     cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1])

    def test_bubble_sort_negative_numbers_only_reverse(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5], version=2,
                                     cmp=lambda x, y: y - x),
                         [-1, -3, -5, -5, -7, -9])

    def test_bubble_sort_with_negative_and_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1],
                                     version=2, cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1, 0, -4, -5, -6])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_sort([1, 1, 1, 1], version=2), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_sort([], version=2), [])


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

哪个更好，为什么？当然，我会接受胸口上所有的不完美。

Answer 1

没有精确顺序的各种事物：

函数名

数字在标识符中被接受，例如函数名。与my_func_v_one不同，您可以选择my_func_v1。

较少冗长的测试

这些评论都是小菜一碟:有些人希望他们的单元测试尽可能简单，有些人则倾向于把它们当作代码，并应用通常的原则，比如不要重复自己。

为了使测试更加简洁和易于编写，您可以考虑添加一个助手方法。

另外，您可以有一个这样的类：

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort(self, sorting_func, input_list, expected_list):
        self.assertEqual(sorting_func(input_list), expected_list)

    def test_bubble_sort_v1_with_positive_numbers(self):
        self._test_sort(bubble_sort_v1, [5, 5, 7, 8, 2, 4, 1], [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v1_negative_numbers_only(self):
        self._test_sort(bubble_sort_v1, [-1, -3, -5, -7, -9, -5], [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_v1_with_negative_and_positive_numbers(self):
        self._test_sort(bubble_sort_v1, [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1], [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v1_same_numbers(self):
        self._test_sort(bubble_sort_v1, [1, 1, 1, 1], [1, 1, 1, 1])

    def test_bubble_sort_v1_empty_list(self):
        self._test_sort(bubble_sort_v1, [], [])

    def test_bubble_sort_v2_with_positive_numbers(self):
        self._test_sort(bubble_sort_v2, [5, 5, 7, 8, 2, 4, 1], [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v2_negative_numbers_only(self):
        self._test_sort(bubble_sort_v2, [-1, -3, -5, -7, -9, -5], [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_v2_with_negative_and_positive_numbers(self):
        self._test_sort(bubble_sort_v2, [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1], [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v2_same_numbers(self):
        self._test_sort(bubble_sort_v2, [1, 1, 1, 1], [1, 1, 1, 1])

    def test_bubble_sort_v2_empty_list(self):
        self._test_sort(bubble_sort_v2, [], [])

然后，您可以使用这样的事实:我们有一个排序函数，我们可以信任它作为一个测试甲骨文使用。

然后你可以写这样的东西：

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort(self, sorting_func, input_list):
        expected_list = sorted(input_list)
        self.assertEqual(sorting_func(input_list), expected_list)

    def test_bubble_sort_with_positive_numbers(self):
        input_list = [5, 5, 7, 8, 2, 4, 1]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_negative_numbers_only(self):
        input_list = [-1, -3, -5, -7, -9, -5]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        input_list = [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_empty_list(self):
        input_list = []
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

甚至：

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort_single_func(self, sorting_func, input_list):
        expected_list = sorted(input_list)
        self.assertEqual(sorting_func(input_list), expected_list)

    def _test_sort_all_funcs(self, input_list):
        self._test_sort_single_func(bubble_sort_v1, input_list)
        self._test_sort_single_func(bubble_sort_v2, input_list)

    def test_bubble_sort_with_positive_numbers(self):
        input_list = [5, 5, 7, 8, 2, 4, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_negative_numbers_only(self):
        input_list = [-1, -3, -5, -7, -9, -5]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        input_list = [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_empty_list(self):
        input_list = []
        self._test_sort_all_funcs(input_list)

另外，至于测试本身，我不会将我的测试建立在你有其他标准(阳性、阴性等)的数字类型上。例如，我编写了以下测试：

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort_single_func(self, sorting_func, input_list):
        expected_list = sorted(input_list)
        self.assertEqual(sorting_func(input_list), expected_list)

    def _test_sort_all_funcs(self, input_list):
        self._test_sort_single_func(bubble_sort_v1, input_list)
        self._test_sort_single_func(bubble_sort_v2, input_list)

    def test_bubble_sort_empty_list(self):
        input_list = []
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_one_element(self):
        input_list = [0]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_already_sorted(self):
        input_list = [1, 2, 3, 4]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_reversed(self):
        input_list = [4, 3, 2, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_disorder_with_repetitions(self):
        input_list = [3, 5, 3, 2, 4, 2, 1, 1]
        self._test_sort_all_funcs(input_list)