Sorting algorithms with Python project

Question

I wrote my first project in Python and I would like to know if this is correct. I prepared some guidelines I want to ask. (I know that I don't have any documentation yet). In the future I want to extend my project about new algorithms such as search, crypto, machine learning, hashes, graphs and so on. Also, I would like to add some data structures. For easier review I can share my files if needed.

1. Is my code compatible with PEP8?
2. Is my code compatible with ZenOfPython?
3. Is my code compatible with OOP?
4. Is my code easy to expand? (Extended with new algorithms and classes)
5. Is my code readable?
6. Are my subclasses easy to build for testcases?
7. Are my unit tests correct (don't really know what I should ask about)?
8. Should I use some design patterns in such a project?

initiate.py

from dsal.algorithm_list import algorithms


class Initiate:
    def __init__(self, algorithm_name, **kwargs):
        self.algorithm_name = algorithm_name
        self.result = {}
        self.args = kwargs

    @staticmethod
    def get_algorithm(name):
        algorithm = None
        for key, alg in algorithms.items():
            if name in key:
                algorithm = alg
                break
        if algorithm is None:
            raise TypeError('Algorithm not defined !')
        return algorithm

    def set_params(self, name):
        algorithm, params = Initiate.get_algorithm(name), dict()
        for k, v in algorithm.check_params(self).items():
            val = self.args.get(k, None)
            if val is not None and v(val):
                params[k] = val

        return algorithm(**params)

    def run(self):
        algorithm = self.set_params(self.algorithm_name)
        return algorithm.run()

    def run_time(self):
        algorithm = self.set_params(self.algorithm_name)
        return algorithm.time_task()

algorithm_list.py

from dsal.algorithms.sorting.simple_sort.bubble_sort import bubble_sort

algorithms = {"BubbleSortV1": bubble_sort.BubbleSortV1,
              "BubbleSortV2": bubble_sort.BubbleSortV2}

allgorithms\sorting\simple_sort\bubble_sort\bubble_sort.py

from dsal.core.algorithms.sorting.simple_sort import SimpleSort


class BubbleSortV1(SimpleSort):

    def run_task(self):

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


class BubbleSortV2(SimpleSort):

    def run_task(self):

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

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

core\algorithms\algorithm.py

import time


class Algorithm:
    def __init__(self, **kwargs):
        self.set_params(**kwargs)

    def set_params(self, **kwargs):
        pass

    def check_params(self, **kwargs):
        pass

    def run_task(self):
        return None

    def time_task(self):
        t1 = time.time()
        self.run_task()
        t2 = time.time()
        return (t2 - t1) * 1000

    def run(self):
        return self.run_task()

core\algorithms\simple_sort\simple_sort.py

from dsal.core.algorithms.algorithm import Algorithm


class SimpleSort(Algorithm):

    def set_params(self, **kwargs):
        self.container = kwargs["container"]

    def check_params(self):
        return {
            'container': lambda x: isinstance(x, list)
        }

    def run_task(self):
        return None

tests\run_tests.py

import unittest

    if __name__ == '__main__':
        testsuite = unittest.TestLoader().discover('./algorithms')
        for test in testsuite:
            unittest.TextTestRunner(verbosity=3).run(test)

tests\algorithms\test.py

from unittest import TestCase

from dsal.core.algorithms.algorithm import Algorithm


class AlgorithmBaseTestCase(TestCase):
    def setUp(self):
        self.algorithm = Algorithm()

    def test_run(self):
        self.assertEqual(self.algorithm.run(), None)

    def test_run_task(self):
        self.assertEqual(self.algorithm.run_task(), None)

    def test_time_task(self):
        self.assertEqual(self.algorithm.time_task(), 0.0)

    def test_set_params(self):
        self.assertEqual(self.algorithm.set_params(), None)
        self.assertEqual(self.algorithm.set_params(container=[1, 2, 3, 4]), None)

    def test_check_params(self):
        self.assertEqual(self.algorithm.set_params(), None)
        self.assertEqual(self.algorithm.set_params(container=[1, 2, 3, 4]), None)


class AlgorithmTestCase(TestCase):

    def algorithm_run_test(self, algorithm):
        return algorithm.run()

tests\algorithm\sorting\test.py

from tests.algorithms.test import AlgorithmTestCase


class SortTestCase(AlgorithmTestCase):

    def setUp(self):
        super(AlgorithmTestCase, self).setUp()

    def _test_sort_single_func(self, input_list, **kwargs):
        expected_list = sorted(input_list)
        result = AlgorithmTestCase.algorithm_run_test(self, self.function_name(**kwargs))
        self.assertEqual(result, expected_list)

tests\algorithms\sorting\simple_sort\tests.py

from dsal.algorithms.sorting.simple_sort.bubble_sort.bubble_sort import BubbleSortV1
from tests.algorithms.sorting.test import SortTestCase


class SimpleSortTestCase(SortTestCase):

    def setUp(self):
        self.function_name = BubbleSortV1
        super(SortTestCase, self).setUp()

    def test_sort_empty_list(self):
        input_list = []
        self._test_sort_single_func(input_list, container = sorted(input_list))

    def test_sort_one_element(self):
        input_list = [0]
        self.container = input_list
        self._test_sort_single_func(input_list, container = sorted(input_list))

    def test_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self.container = input_list
        self._test_sort_single_func(input_list, container = sorted(input_list))

    def test_sort_already_sorted(self):
        input_list = [1, 2, 3, 4]
        self.container = input_list
        self._test_sort_single_func(input_list, container = sorted(input_list))

    def test_sort_reversed(self):
        input_list = [4, 3, 2, 1]
        self.container = input_list
        self._test_sort_single_func(input_list, container = sorted(input_list))

    def test_sort_disorder_with_repetitions(self):
        input_list = [3, 5, 3, 2, 4, 2, 1, 1]
        self.container = input_list
        self._test_sort_single_func(input_list, container = sorted(input_list))

tests\algorithms\sorting\simple_sort\bubble_sort

from dsal.algorithms.sorting.simple_sort.bubble_sort.bubble_sort import BubbleSortV1, BubbleSortV2
from tests.algorithms.sorting.simple_sort.test import SimpleSortTestCase


class BubbleSortV1TestCase(SimpleSortTestCase):

    def test_bubble_sort_v1(self):
        self.function_name = BubbleSortV1
        super(SimpleSortTestCase, self).setUp()


class BubbleSortV2TestCase(SimpleSortTestCase):

    def test_bubble_sort_v2(self):
        self.function_name = BubbleSortV2
        super(SimpleSortTestCase, self).setUp()

Answer 1

1. Stop writing frameworks!

This code seems very "enterprisey" to me — by which I mean that there is a big framework of classes that don't do anything except add complexity. If you come from a Java background you might be used to writing this kind of framework, but the sheer volume of code is a maintenance burden that you should not take on unless you are sure that the returns will justify the costs.

In Python, we can nearly always avoid this kind of framework, or at least postpone writing it until it becomes worthwhile.

Let's take the elements of the framework in turn:

1. Initiate is a class which provides the features: (i) looking up an algorithm by name; (ii) running an algorithm; (iii) timing how long an algorithm takes. Instead of (i) you could use globals; instead of (ii) you could just call the function; and instead of (iii) you could use the timeit module. But the code doesn't use the Initiate class anywhere, so you could delete it.

2. Algorithm is a class which provides the features: (i) calling a function with some keyword arguments; (ii) timing how long the function takes. Instead of (i) you could just call the function, and instead of (ii) you could use the timeit module. So you could delete this class and use functions instead.

3. algorithm_list.py provides a table mapping algorithm name to algorithm class. But this is only needed by Initiate.get_algorithm, and that isn't used anywhere, so you could delete this file. In Python, if you really need to look up a function by name, you can use the globals built-in. But this is rarely necessary.

4. SimpleSort is a subclass of Algorithm providing specialized features for sorting algorithms. This class isn't needed (for the same reasons that Algorithm isn't needed) and you could delete this class.

5. BubbleSortV1 and BubbleSortV2 are subclasses of SimpleSort that implement the bubble sort algorithm. These classes aren't needed (for the same reasons that Algorithm isn't needed). All you need to keep is the sort function.

6. AlgorithmBaseTestCase is a class of unit tests for the Algorithm class. But if you deleted the Algorithm class, then you wouldn't need to test it, and so you could delete AlgorithmBaseTestCase too.

7. SortTestCase checks that an algorithm sorts a sequence correctly. This is fine!

8. SimpleSortTestCase provides tests of a sorting algorithm on various input lists. This is fine, except that the tests are very repetitive. It would be better to refactor the code so that it is table driven. See the test_cases method below for how to do this.

9. run_tests.py runs unittest test discovery. But you can do this using the unittest command-line interface without having to write any code: python -m unittest discover -s algorithms. So you could delete this file.

2. Other review comments

1. The argument to the sorting algorithms needs to be a sequence (so that you can index it), not any old container. So sequence would be a better name.

2. The sorting algorithms are destructive — they modify the input sequence, like the list.sort method. In Python it is conventional for destructive functions and methods to return None. This makes it harder to accidentally confuse them with non-destructive equivalents like sorted, which return a fresh result but leave the original data unchanged.

3. The tests are not very thorough. This is a case where you have a test oracle in the form of the built-in function sorted, making this suitable for random testing. See the test_random method below.

3. Revised code

def bubble_sort_v1(seq):
    length = len(seq)
    changed = True
    while changed:
        changed = False
        for i in range(length - 1):
            if seq[i] > seq[i + 1]:
                seq[i], seq[i + 1] = seq[i + 1], seq[i]
                changed = True
        length -= 1

def bubble_sort_v2(seq):
    length = len(seq)
    while length >= 1:
        changed_times = 0
        for i in range(1, length):
            if seq[i - 1] > seq[i]:
                seq[i - 1], seq[i] = seq[i], seq[i - 1]
                changed_times = i
        length = changed_times


import random
from unittest import TestCase

class TestSort:
    def check(self, seq):
        expected = sorted(seq)
        found = list(seq) # take a copy since self.function is destructive
        self.function(found)
        self.assertEqual(expected, found)

    CASES = [
        (), # empty
        (0,), # one element
        (1, 1, 1, 1), # same numbers
        (1, 2, 3, 4), # already sorted
        (4, 3, 2, 1), # reversed
        (3, 5, 3, 2, 4, 2, 1, 1), # disorder with repetitions
    ]

    def test_cases(self):
        for case in self.CASES:
            self.check(case)

    def test_random(self):
        for k in range(100):
            self.check(random.choices(range(k), k=k))

class TestBubbleSortV1(TestSort, TestCase):
    function = staticmethod(bubble_sort_v1)

class TestBubbleSortV2(TestSort, TestCase):
    function = staticmethod(bubble_sort_v2)

Notes

1. The reason that TestSort does not inherit from unittest.TestCase is so that it is not run by unittest test discovery: it won't work because it doesn't have a function attribute.

2. The reason for using staticmethod is that we need self.function to be a plain function, not an instance method.

3. I made the test cases tuples so that they can't be modified by accident. TestSort.check makes a copy in the form of a list so that it can be modified by the function under test.

Answer 2

    algorithm = None
    for key, alg in algorithms.items():
        if name in key:
            algorithm = alg
            break
    if algorithm is None:
        raise TypeError('Algorithm not defined !')
    return algorithm

A few things, here. First of all, are you sure you want to be doing substring searching through the keys of a dictionary? Shouldn't you just do regular key lookup on algorithm name?

Don't name your key "key". If it's an algorithm name, call it "alg_name" or something.

Also, you can simplify your return logic. Something like:

try:
   return algorithms[name]
except KeyError:
   raise TypeError('Algorithm not defined !')

For this line:

val = self.args.get(k, None)

None is the default anyway, so you can simply write val = self.args.get(k).

For this:

for k, v in algorithm.check_params(self).items():

Apparently v is callable, but you wouldn't know by looking at it. Give it a meaningful name. validate?

if val is not None and v(val):

My best guess is that this runs validation on the parameter, and if the validation fails, the parameter is silently dropped. This is bad. You want to know if your validation fails, and probably abort execution of the algorithm.

This path:

allgorithms\sorting\simple_sort\bubble_sort\bubble_sort.py

has a typo in it. It's "algorithms", not "allgorithms" (unless you intended a portmanteau of "all algorithms").

def time_task(self):
    t1 = time.time()
    self.run_task()
    t2 = time.time()
    return (t2 - t1) * 1000

This is fragile. Consider calling timeit instead.