# Chronos
[](https://badge.fury.io/py/py-quantize-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` and `tqdm` in order to use `chronos`. These should install as dependencies by default.
```sh
pip install py-quantize-chronos
```
## Usage
You need to pass in the name of the function you want timed into `timer`. The `timer` func will return the name of the function that models the runtime trajectory as a string. It also returns the coefficient that was outputted the least squares regression.
```py
import chronos
def fib_exp(n):
if n <= 1:
return n
return fib_exp(n-1) + fib_exp(n-2)
print("running expoential runtime function")
func, coeff = chronos.timer(fib_exp, silent=True, num=100)
print(func, coeff, "\n")
```
In order for the analyis to work, the function's runtime must scale with respect to the input (ie. fibonacci sequence). Hence, the function must take an integer value. If the function doesn't support this, you must wrap the function in such a manner that the input's length can me modified with an integer.
```py
# original function
def counter(string: str):
counter = 0
for i in len(string):
if i == "0":
counter += 1
return counter
# modified function to time
def wrapper(n: int):
# generate random string with variable size
letters = string.ascii_lowercase + string.digits
inp = "".join(random.choices(letters, k=n))
return counter(inp)
```
## 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.
We would also like to support function that doesn't necesarily have integer inputs.
Furthermore, we need some more robust unit testing...
## 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
- https://danielmuellerkomorowska.com/2020/06/02/smoothing-data-by-rolling-average-with-numpy/
- https://pythonnumericalmethods.berkeley.edu/notebooks/chapter16.05-Least-Square-Regression-for-Nonlinear-Functions.html
Raw data
{
"_id": null,
"home_page": "https://github.com/h3x4g0ns/py-chronos/tree/main",
"name": "py-quantize-chronos",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "python,runtime,cli",
"author": "Ekansh Agrawal",
"author_email": "agrawalekansh@berkeley.edu",
"download_url": "https://files.pythonhosted.org/packages/0b/36/b1d3a364f908a15194f0608d5aaf7321d7b7250aa951fad09a0b0d2fd09e/py-quantize-chronos-0.1.8.tar.gz",
"platform": null,
"description": "# Chronos\n\n\n\n[](https://badge.fury.io/py/py-quantize-chronos)\n\n## About this Project\n\nPython utility tool that takes in a function and outputs symbolic $O$ runtime.\n\n## How it works\n\nWe 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.\n\n## Getting Started\n\n### Prerequisites\n\nYou will need `numpy` and `tqdm` in order to use `chronos`. These should install as dependencies by default.\n\n```sh\npip install py-quantize-chronos\n```\n\n## Usage\n\nYou need to pass in the name of the function you want timed into `timer`. The `timer` func will return the name of the function that models the runtime trajectory as a string. It also returns the coefficient that was outputted the least squares regression.\n\n```py\nimport chronos\n\ndef fib_exp(n):\n if n <= 1:\n return n\n return fib_exp(n-1) + fib_exp(n-2)\n\nprint(\"running expoential runtime function\")\nfunc, coeff = chronos.timer(fib_exp, silent=True, num=100)\nprint(func, coeff, \"\\n\")\n```\n\nIn order for the analyis to work, the function's runtime must scale with respect to the input (ie. fibonacci sequence). Hence, the function must take an integer value. If the function doesn't support this, you must wrap the function in such a manner that the input's length can me modified with an integer.\n\n```py\n# original function\ndef counter(string: str):\n counter = 0\n for i in len(string):\n if i == \"0\":\n counter += 1\n return counter\n\n# modified function to time\ndef wrapper(n: int):\n # generate random string with variable size\n letters = string.ascii_lowercase + string.digits\n inp = \"\".join(random.choices(letters, k=n))\n return counter(inp)\n```\n\n## Features to Add\n\nRight 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.\n\nWe would also like to support function that doesn't necesarily have integer inputs.\n\nFurthermore, we need some more robust unit testing...\n\n## Prior Attempts\n\nIn 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:\n\n$$ O(1), O(n), O(n^2), O(n^3), O(\\log{n}), O(n\\log{n}), O(2^n)$$\n\nWe can compare the second degree Taylor expansion for every known tracjectory. The formula for the second degree expansion is shown below.\n\n$$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$$\n\nWhere $g(x)$ is defined to be the measured runtime at timestep $x$.\n\nWe 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.\n\n$$ \\underset{f \\in F}{\\arg\\min} \\sum_1^{i=n}|T_n^f(i-i)(i)-g(i)|$$\n\nWhere $F$ is defined to be the set of all known trajectories to us, and $n$ is the number of data points we have.\n\n> 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\n\n## Helpful Links\n\n- https://danielmuellerkomorowska.com/2020/06/02/smoothing-data-by-rolling-average-with-numpy/\n- https://pythonnumericalmethods.berkeley.edu/notebooks/chapter16.05-Least-Square-Regression-for-Nonlinear-Functions.html\n",
"bugtrack_url": null,
"license": "",
"summary": "utility tool that analyzes symbolic runtime of python functions",
"version": "0.1.8",
"project_urls": {
"Homepage": "https://github.com/h3x4g0ns/py-chronos/tree/main"
},
"split_keywords": [
"python",
"runtime",
"cli"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "b68eda5bc52bac2a00fd8f83431bbbc56adbbf4cc4ddf8b7c6f154c46de2ab5d",
"md5": "4fc118da71cf56a2ce44cdecc693f5c2",
"sha256": "8d2dea6288611e2926399eea8e458e51aa66bb6bae45518956a352a68e73c22d"
},
"downloads": -1,
"filename": "py_quantize_chronos-0.1.8-py3-none-any.whl",
"has_sig": false,
"md5_digest": "4fc118da71cf56a2ce44cdecc693f5c2",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 5119,
"upload_time": "2024-01-29T21:46:36",
"upload_time_iso_8601": "2024-01-29T21:46:36.533672Z",
"url": "https://files.pythonhosted.org/packages/b6/8e/da5bc52bac2a00fd8f83431bbbc56adbbf4cc4ddf8b7c6f154c46de2ab5d/py_quantize_chronos-0.1.8-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "0b36b1d3a364f908a15194f0608d5aaf7321d7b7250aa951fad09a0b0d2fd09e",
"md5": "5a58963b0b7ea66c1fdf7a7606e67ae7",
"sha256": "d132e895b7847c0e8fb9f22a8f36bc4e786e1349254da242f0854390b0e49f31"
},
"downloads": -1,
"filename": "py-quantize-chronos-0.1.8.tar.gz",
"has_sig": false,
"md5_digest": "5a58963b0b7ea66c1fdf7a7606e67ae7",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 5043,
"upload_time": "2024-01-29T21:46:38",
"upload_time_iso_8601": "2024-01-29T21:46:38.115766Z",
"url": "https://files.pythonhosted.org/packages/0b/36/b1d3a364f908a15194f0608d5aaf7321d7b7250aa951fad09a0b0d2fd09e/py-quantize-chronos-0.1.8.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-29 21:46:38",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "h3x4g0ns",
"github_project": "py-chronos",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "py-quantize-chronos"
}
JSON
