## bigO
`bigO` automatically measures empirical computational complexity (in both time and space) of functions.
To use `bigO`, you just need to add a `@bigO.track` decorator to your function together with a "length" function (the "n").
You can then run your function as usual, ideally along a wide range of inputs, and `bigO` will report the computational
complexity of that function.
A novel feature of `bigO` is that, as long as your function calls another function, `bigO` will automatically generate diversity.
This feature ensures that you can get computational complexity information even when there are not a wide range of inputs to the function (even one input is enough!).
`bigO` accumulates its results in a file named `bigO_data.json` in the local directory;
you can then generate a graph of time and space complexity for each tracked function by running `python3 -m bigO.graph`.
### Demonstration
The file `test/facts.py` is a small program that demonstrates `bigO`.
```python
import bigO
def fact(x: int) -> int:
v = 1
for i in range(x):
v *= i
return v
@bigO.track(lambda xs: len(xs))
def factorialize(xs: list[int]) -> list[int]:
new_list = [fact(x) for x in xs]
return new_list
# Exercise the function - more inputs are better!
for i in range(30):
factorialize([i for i in range(i * 100)])
```
Now run the program as usual:
```bash
python3 test/facts.py
```
Now you can easily generate a graph of all tracked functions. Just run the following command in the same directory.
```bash
python3 -m bigO.graph
```
This command creates the file `bigO.pdf` that contains graphs like this:
### Technical Details
#### Curve-fitting
`bigO`'s curve-fitting based approach is directly inspired by
["Measuring Empirical Computational
Complexity"](https://theory.stanford.edu/~aiken/publications/papers/fse07.pdf)
by Goldsmith et al., FSE 2007, using log-log plots to fit a power-law distribution.
Unlike that work, `bigO` uses the
[AIC](https://en.wikipedia.org/wiki/Akaike_information_criterion) to
select the best model. `bigO` also measures space complexity by
tracking memory allocations during function execution.
#### Diversity via random time and space dilation
While previous work depends on functions being executed over a wide
range of inputs, `bigO` uses a novel approach that lets it generate
diversity even for fixed inputs. This approach works by randomly
dilating the execution time of functions called by the function being
tested, as well as the size of memory allocations. This approach lets
`bigO` collect more data points and better measure computational
complexity.
Raw data
{
"_id": null,
"home_page": "https://github.com/plasma-umass/bigO",
"name": "bigO",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": null,
"keywords": "performance, profiler",
"author": "Emery Berger",
"author_email": "Emery Berger <emery.berger@gmail.com>",
"download_url": null,
"platform": null,
"description": "## bigO\n\n`bigO` automatically measures empirical computational complexity (in both time and space) of functions.\nTo use `bigO`, you just need to add a `@bigO.track` decorator to your function together with a \"length\" function (the \"n\").\nYou can then run your function as usual, ideally along a wide range of inputs, and `bigO` will report the computational\ncomplexity of that function.\n\nA novel feature of `bigO` is that, as long as your function calls another function, `bigO` will automatically generate diversity.\nThis feature ensures that you can get computational complexity information even when there are not a wide range of inputs to the function (even one input is enough!).\n\n`bigO` accumulates its results in a file named `bigO_data.json` in the local directory;\nyou can then generate a graph of time and space complexity for each tracked function by running `python3 -m bigO.graph`.\n\n### Demonstration\n\nThe file `test/facts.py` is a small program that demonstrates `bigO`.\n\n```python\nimport bigO\n\ndef fact(x: int) -> int:\n v = 1\n for i in range(x):\n v *= i\n return v\n\n@bigO.track(lambda xs: len(xs))\ndef factorialize(xs: list[int]) -> list[int]:\n new_list = [fact(x) for x in xs]\n return new_list\n\n# Exercise the function - more inputs are better!\nfor i in range(30):\n factorialize([i for i in range(i * 100)])\n```\n\nNow run the program as usual:\n\n```bash\npython3 test/facts.py\n```\n\nNow you can easily generate a graph of all tracked functions. Just run the following command in the same directory.\n\n```bash\npython3 -m bigO.graph\n```\n\nThis command creates the file `bigO.pdf` that contains graphs like this:\n\n\n\n### Technical Details\n\n#### Curve-fitting\n\n`bigO`'s curve-fitting based approach is directly inspired by\n[\"Measuring Empirical Computational\nComplexity\"](https://theory.stanford.edu/~aiken/publications/papers/fse07.pdf)\nby Goldsmith et al., FSE 2007, using log-log plots to fit a power-law distribution.\n\nUnlike that work, `bigO` uses the\n[AIC](https://en.wikipedia.org/wiki/Akaike_information_criterion) to\nselect the best model. `bigO` also measures space complexity by\ntracking memory allocations during function execution.\n\n#### Diversity via random time and space dilation\n\nWhile previous work depends on functions being executed over a wide\nrange of inputs, `bigO` uses a novel approach that lets it generate\ndiversity even for fixed inputs. This approach works by randomly\ndilating the execution time of functions called by the function being\ntested, as well as the size of memory allocations. This approach lets\n`bigO` collect more data points and better measure computational\ncomplexity.\n",
"bugtrack_url": null,
"license": null,
"summary": "Track asymptotic complexity in time and space.",
"version": "0.0.1",
"project_urls": {
"Homepage": "https://github.com/plasma-umass/bigO",
"Repository": "https://github.com/plasma-umass/bigO"
},
"split_keywords": [
"performance",
" profiler"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "ac859ad6e80e44a6c19ebc281655c33e4d729e479b16f0988287e4b18fa063f9",
"md5": "0706f7fdb2d4a90082e3f77655bac2d4",
"sha256": "2d14734e4528b7ddc2dcf38bcbfa5f1b1758b22571cd58286a7142c22e35bb58"
},
"downloads": -1,
"filename": "bigO-0.0.1-cp311-cp311-macosx_10_9_universal2.whl",
"has_sig": false,
"md5_digest": "0706f7fdb2d4a90082e3f77655bac2d4",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.8",
"size": 14429,
"upload_time": "2024-12-11T22:12:31",
"upload_time_iso_8601": "2024-12-11T22:12:31.734659Z",
"url": "https://files.pythonhosted.org/packages/ac/85/9ad6e80e44a6c19ebc281655c33e4d729e479b16f0988287e4b18fa063f9/bigO-0.0.1-cp311-cp311-macosx_10_9_universal2.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "cfdc0341b2b15d34c899a0543521e15871972a308914face56dc59f7a6d909a1",
"md5": "9367dfc9c8c87f97bc5f1caa2320875f",
"sha256": "9823a06caaea22dc773ee8e7262702534a900a10b7f725c1c68132332c64a42a"
},
"downloads": -1,
"filename": "bigO-0.0.1-cp313-cp313-macosx_10_13_universal2.whl",
"has_sig": false,
"md5_digest": "9367dfc9c8c87f97bc5f1caa2320875f",
"packagetype": "bdist_wheel",
"python_version": "cp313",
"requires_python": ">=3.8",
"size": 14318,
"upload_time": "2024-12-11T22:25:37",
"upload_time_iso_8601": "2024-12-11T22:25:37.536267Z",
"url": "https://files.pythonhosted.org/packages/cf/dc/0341b2b15d34c899a0543521e15871972a308914face56dc59f7a6d909a1/bigO-0.0.1-cp313-cp313-macosx_10_13_universal2.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-11 22:12:31",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "plasma-umass",
"github_project": "bigO",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "bigo"
}
JSON
