complexity.py

from abc import ABC, abstractmethod
from typing import List, NamedTuple, Iterable, Any, TypeVar, Generic, Callable
import matplotlib.pyplot as plt
from line_profiler import LineProfiler

ComplexityLogEntry = NamedTuple('ComplexityLogEntry', [('size', int),
                                                       ('hits', int)])


class BaseComplexityAssumption(ABC):
    title = ''

    def __init__(self, log: List[ComplexityLogEntry]) -> None:
        self.log = log
        self.hits = [hit for _, hit in self.log]

    @abstractmethod
    def get_score(self) -> int:
        ...


def get_growth(hits: List[int]) -> Iterable[int]:
    for hit_a, hit_b in zip(hits[:-1], hits[1:]):
        yield abs(hit_a - hit_b)


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

    def get_score(self) -> int:
        return sum(abs(self.hits[0] - hit) for hit in self.hits[1:])


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

    def get_score(self) -> int:
        growth = list(get_growth(self.hits))
        return sum(abs(growth[0] - grow) for grow in growth[1:])


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

    def get_score(self) -> int:
        growth = list(get_growth(self.hits))
        growth_of_growth = list(get_growth(growth))
        return sum(abs(growth_of_growth[0] - grow)
                   for grow in growth_of_growth[1:])


assumptions = [ConstantComplexityAssumption,
               LinearComplexityAssumption,
               QuadraticComplexityAssumption]


class Complexity:
    def __init__(self, title: str, log: List[ComplexityLogEntry]) -> None:
        self.title = title
        self.log = log

    def show_plot(self) -> 'Complexity':
        plt.style.use('ggplot')
        plt.plot([size for size, _ in self.log],
                 [hits for _, hits in self.log])
        plt.title('{}: {}'.format(
            self.title, self._asymptotic_complexity()))
        plt.show()
        return self

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


T = TypeVar('T')


class BaseComplexityAnalyzer(Generic[T], ABC):
    title = ''

    @abstractmethod
    def get_data_set(self, size: int) -> T:
        ...

    @abstractmethod
    def run(self, data_set: T) -> None:
        ...

    @staticmethod
    def _get_hits(fn: Callable[[T], None], *args: Any, **kwargs: Any) -> int:
        profiler = LineProfiler(fn)
        profiler.runcall(fn, *args, **kwargs)
        hits = 0
        for timing in profiler.get_stats().timings.values():
            for _, line_hits, _ in timing:
                hits += line_hits
        return hits

    @classmethod
    def calculate(cls, sizes: Iterable[int]) -> Complexity:
        log = []
        inst = cls()
        for size in sizes:
            hits = cls._get_hits(inst.run, inst.get_data_set(size))
            entry = ComplexityLogEntry(size, hits)
            log.append(entry)

        return Complexity(cls.title, log)


# Example:
class SomethingQuadratic(BaseComplexityAnalyzer[int]):
    title = 'Something quadratic'

    def get_data_set(self, size) -> List[int]:
        from numpy.random import randint
        return list(randint(1000, size=size))

    def run(self, data_set: Iterable[int]) -> None:
        result = []
        for x in data_set:
            for y in data_set:
                result.append((x, y))


if __name__ == '__main__':
    SomethingQuadratic \
        .calculate(range(100, 1000, 100)) \
        .show_plot()