<div align="center">
<h1>BFPRT </h1>
<p>
<strong>Median of Medians Quickselect Algorithm</strong>
</p>
<hr />
</div>
## About
This package implements fast median finding with the median of medians selection algorithm, also known as BFPRT (named after the authors of [Blum et al. (1973)](http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf)). It can be used to find the kth smallest value in a list, also known as the "kth order statistic".
When k is halfway through a list, then quickselect finds the median of the list in O(n) time. While this asymptotically linear algorithm is provably optimal, the constant factor overhead is known to be large, making this approach less useful in practice. In theory, however, the median of medians trick can be a very powerful proof step.
This package is intended primarily as a learning tool rather than a practical implementation. For faster runtime on most reasonably sized problems, prefer standard implementations of the median.
## Installation
```bash
pip install bfprt
```
## Usage
```py
from bfprt import select_fast
# Items can have any type that implements less-than comparison
items = [4, 2, 1, 9, 5, 8]
# We want to get the kth smallest element from the list
k = 3
# This is the index of the kth smallest element
selected_index = select_fast(items, k)
# If k is len(items) // 2, then this is the median
kth_order_statistic = items[selected_index]
```
## Installing from source
Install using [Poetry](https://python-poetry.org/)
```bash
poetry install
```
Raw data
{
"_id": null,
"home_page": "https://github.com/gregorybchris/bfprt",
"name": "bfprt",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.12",
"maintainer_email": null,
"keywords": "median, finding, quick, select",
"author": "Chris Gregory",
"author_email": "christopher.b.gregory@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/4b/cc/06fbf36353ff7f3f51fbd1712eab99b022850a39964aab1c29406c2279fa/bfprt-0.3.0.tar.gz",
"platform": null,
"description": "<div align=\"center\">\n <h1>BFPRT </h1>\n\n <p>\n <strong>Median of Medians Quickselect Algorithm</strong>\n </p>\n\n <hr />\n</div>\n\n## About\n\nThis package implements fast median finding with the median of medians selection algorithm, also known as BFPRT (named after the authors of [Blum et al. (1973)](http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf)). It can be used to find the kth smallest value in a list, also known as the \"kth order statistic\".\n\nWhen k is halfway through a list, then quickselect finds the median of the list in O(n) time. While this asymptotically linear algorithm is provably optimal, the constant factor overhead is known to be large, making this approach less useful in practice. In theory, however, the median of medians trick can be a very powerful proof step.\n\nThis package is intended primarily as a learning tool rather than a practical implementation. For faster runtime on most reasonably sized problems, prefer standard implementations of the median.\n\n## Installation\n\n```bash\npip install bfprt\n```\n\n## Usage\n\n```py\nfrom bfprt import select_fast\n\n# Items can have any type that implements less-than comparison\nitems = [4, 2, 1, 9, 5, 8]\n\n# We want to get the kth smallest element from the list\nk = 3\n\n# This is the index of the kth smallest element\nselected_index = select_fast(items, k)\n\n# If k is len(items) // 2, then this is the median\nkth_order_statistic = items[selected_index]\n```\n\n## Installing from source\n\nInstall using [Poetry](https://python-poetry.org/)\n\n```bash\npoetry install\n```\n",
"bugtrack_url": null,
"license": "Apache Software License",
"summary": "Fast median finding",
"version": "0.3.0",
"project_urls": {
"Homepage": "https://github.com/gregorybchris/bfprt",
"Repository": "https://github.com/gregorybchris/bfprt"
},
"split_keywords": [
"median",
" finding",
" quick",
" select"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "a85656b5bb7fd0504747ebca259848c20d691cbd488784e473cec88256888f0c",
"md5": "86247ca521954361673a5a9f8df56843",
"sha256": "da765a47c398d0507f21b9fd05bb280cf15bc1b7cca2f78eaa94b65030849832"
},
"downloads": -1,
"filename": "bfprt-0.3.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "86247ca521954361673a5a9f8df56843",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.12",
"size": 4178,
"upload_time": "2024-09-16T04:48:26",
"upload_time_iso_8601": "2024-09-16T04:48:26.813505Z",
"url": "https://files.pythonhosted.org/packages/a8/56/56b5bb7fd0504747ebca259848c20d691cbd488784e473cec88256888f0c/bfprt-0.3.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4bcc06fbf36353ff7f3f51fbd1712eab99b022850a39964aab1c29406c2279fa",
"md5": "c05b15e077f2131cead1e1b7563d66d1",
"sha256": "464088d623517b1c41c9a275081e87390c4f52fa228e7d250787cb4c8490c80c"
},
"downloads": -1,
"filename": "bfprt-0.3.0.tar.gz",
"has_sig": false,
"md5_digest": "c05b15e077f2131cead1e1b7563d66d1",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.12",
"size": 3964,
"upload_time": "2024-09-16T04:48:28",
"upload_time_iso_8601": "2024-09-16T04:48:28.141787Z",
"url": "https://files.pythonhosted.org/packages/4b/cc/06fbf36353ff7f3f51fbd1712eab99b022850a39964aab1c29406c2279fa/bfprt-0.3.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-09-16 04:48:28",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "gregorybchris",
"github_project": "bfprt",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "bfprt"
}
JSON
