utility tool that analyzes symbolic runtime of python functions
Project description
Chronos
About this Project
Python utility tool that takes in a function and outputs symbolic $O$ runtime.
How it works
We basically take a couple known trajectories (specifically $O(1), O(n), O(n^2), O(n^3), O(\log{n}), O(n\log{n}), O(2^n)$ and we compute a least squares regression for each trajectory. We use a loss function to aggregate the differences and then return the trajectory with the smallest loss.
Getting Started
Prerequisites
You will need numpy
in order to use py-chronos. These should install as dependencies by default.
pip install py-chronos numpy
Usage
Features to Add
Right now, the model is only able to support offline aysmptotic analysis. The goals is to perform online analysis so that we can utilize an EARLY_STOP
if the last k
predictions have been the same.
Prior Attempts
In order to approximate asymptotic behavior, we use the second degree Taylor Expansion in order to estimate the trajectory of the runtime given the point. We retain a lookup table for the different asymptoics runtimes that we can expect (This included precomputing first and second derivatives). Following trajectories and their derivative functions are known:
$$ O(1), O(n), O(n^2), O(n^3), O(\log{n}), O(n\log{n}), O(2^n)$$
We can compare the second degree Taylor expansion for every known tracjectory. The formula for the second degree expansion is shown below.
$$T_2^f(x) = \sum_{n=0}^{2} \frac{f^{(n)}(x_0)}{n!} = g(x_0) + \frac{d}{dx}f(x_0)(x-x_0) + \frac{\frac{d^2}{dx^2}f(x_0)}{2}(x-x_0)^2$$
Where $g(x)$ is defined to be the measured runtime at timestep $x$.
We linearly scale the input to the test function and record its runtime. This new update is incorporated at the next time step to get a better approximation of the trajectory. Our optimization problem is defined to be as follows.
$$ \underset{f \in F}{\arg\min} \sum_1^{i=n}|T_n^f(i-i)(i)-g(i)|$$
Where $F$ is defined to be the set of all known trajectories to us, and $n$ is the number of data points we have.
HOWEVER, the problem with this attempt is that if there are large or small coefficients present in our terms, they can artiically inflate or deflate the loss function. This leads to incorrect predictions with the asympotic analysis
Helpful Links
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for py-quantize-chronos-0.1.0.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | cc710379fa0d1db35de195ee92eef037a2da0b1d7893c587c071b7ab683b296b |
|
MD5 | 5d3fe29f2543ee193b4e994125926fda |
|
BLAKE2b-256 | d3e6af903e797ce76a91c5f36748bd13606090718c3773dac09f62a2393a6822 |
Hashes for py_quantize_chronos-0.1.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0faffcbe9fc3bdda5d55d940dcc054fbe727879ddf9975f0e1745fd2aad41f5e |
|
MD5 | f5ecef733beda3d68b288de4ddf563ee |
|
BLAKE2b-256 | c3f0368cb436390842d2e2ab5b85cc9f1ea9ef50fee425b07ac8fb160546a0eb |