Create a gist now

Instantly share code, notes, and snippets.

Embed
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment