Primitive complexity analyzer

complexity.py

from collections import namedtuple
import timeit
import matplotlib.pyplot as plt

ComplexityLogEntry = namedtuple('ComplexityLogEntry', ('size', 'time'))


class BaseComplexityAssumption(object):
    title = ''

    def __init__(self, log):
        self.time = [entry.time for entry in log]

    def _get_growth(self, xs, ):
        return [abs(xs[n - 1] - x) or 0.0001 if n > 0 else 0.0001
                for n, x in enumerate(xs)]

    def _get_average(self, xs):
        return sum(x for x in xs) / len(xs)

    def _get_diff(self, xs):
        average = self._get_average(xs)
        return [abs(average - x) for x in xs]

    def get_score(self):
        raise NotImplementedError


class ConstantComplexityAssumption(BaseComplexityAssumption):
    title = 'O(1)'

    def get_score(self):
        return sum(self._get_diff(self.time))


class LinearComplexityAssumption(BaseComplexityAssumption):
    title = 'O(n)'

    def get_score(self):
        growth = self._get_growth(self.time)
        return sum(self._get_diff(growth))


class QuadraticComplexityAssumption(BaseComplexityAssumption):
    title = 'O(n ^ 2)'

    def get_score(self):
        growth = self._get_growth(self.time)
        second_growth = self._get_growth(growth)
        return sum(self._get_diff(second_growth))


assumptions = [ConstantComplexityAssumption,
               LinearComplexityAssumption,
               QuadraticComplexityAssumption]


class Complexity(object):
    def __init__(self, title, log):
        self.title = title
        self.log = log

    def show_plot(self):
        plt.plot([size for size, _ in self.log],
                 [time for _, time in self.log])
        plt.title('{}: {}'.format(
            self.title, self._asymptotic_complexity()))
        plt.show()
        return self

    def _asymptotic_complexity(self):
        assumptions_ = [assumption(self.log) for assumption in assumptions]
        most_possible = min(assumptions_,
                            key=lambda assumption: assumption.get_score())
        return most_possible.title


class BaseComplexityAnalyzer(object):
    title = ''

    def get_data_set(self, size):
        raise NotImplementedError

    def run(self, data_set):
        raise NotImplementedError

    @classmethod
    def calculate(cls, sizes, repeat_each):
        log = []
        for size in sizes:
            setup = ('from {module} import {cls}\n'
                     'analyzer = {cls}()\n'
                     'data_set = analyzer.get_data_set({size})\n').format(
                module=__name__, cls=cls.__name__, size=size)

            time = timeit.timeit('analyzer.run(data_set)', setup,
                                 number=repeat_each)
            entry = ComplexityLogEntry(size, time * 1000 * 1000)
            print(entry)
            log.append(entry)

        return Complexity(cls.title, log)


class SomethingQuadratic(BaseComplexityAnalyzer):
    title = 'Something quadratic'

    def get_data_set(self, size):
        from numpy.random import randint
        return list(randint(1000, size=size))

    def run(self, data_set):
        result = []
        for x in data_set:
            for y in data_set:
                result.append((x, y))


SomethingQuadratic \
    .calculate(range(100, 1000, 100), 10) \
    .show_plot()