Skip to content

Instantly share code, notes, and snippets.

@nvbn nvbn/
Created May 29, 2017

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]
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,
class Complexity:
def __init__(self, title: str, log: List[ComplexityLogEntry]) -> None:
self.title = title
self.log = log
def show_plot(self) -> 'Complexity':'ggplot')
plt.plot([size for size, _ in self.log],
[hits for _, hits in self.log])
plt.title('{}: {}'.format(
self.title, self._asymptotic_complexity()))
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 = ''
def get_data_set(self, size: int) -> T:
def run(self, data_set: T) -> None:
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
def calculate(cls, sizes: Iterable[int]) -> Complexity:
log = []
inst = cls()
for size in sizes:
hits = cls._get_hits(, inst.get_data_set(size))
entry = ComplexityLogEntry(size, hits)
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)) \
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.