Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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