# nanolsap
A Python module to solve the linear sum assignment problem (LSAP) efficiently.
Extracted from SciPy, and modified to minimal memory cost.
## Description
```
from nanolsap import linear_sum_assignment
```
```
Solve the linear sum assignment problem.
Parameters
----------
cost_matrix : array
The cost matrix of the bipartite graph.
It should be 2-D ArrayLike object, with nr rows and nc cols.
maximize : bool (default: False)
Calculates a maximum weight matching if true.
subrows : array (default: None)
Use sub rows from cost matrix if not None.
subcols : array (default: None)
Use sub cols from cost matrix if not None.
Returns
-------
row_ind, col_ind : array
An array of row indices and one of corresponding column indices giving
the optimal assignment. The cost of the assignment can be computed
as ``cost_matrix[row_ind, col_ind].sum()``. The row indices will be
sorted if subrows and subcols are both None; in the case of a square cost
matrix they will be equal to ``numpy.arange(cost_matrix.shape[0])``.
```
This module is useful in cases when you need an efficient LSAP solver on
very large cost_matrix and limited memory.
For a cost_matrix with dtype float64 has shape of 30000\*30000, it needs 30000\*30000\*8 / 1024\*\*3 = 6.7GB memory to store it.
In scipy.optimite.linear_sum_assignment, it will first convert it to float64 contiguous numpy 2-D array, then do a copy, and finally starts the solver.
So, the actual memory cost is at least 6.7\*2 = 13.4GB.
if the origin cost_matrix does not match, for example a float32 2-D array,
the first step here will cause one extra copy, increases the actual memory cost to 6.7/2+6.7\*2 = 16.75GB.
In this module, When input cost_matrix is a contiguous numpy 2-D array, the solver can run on it directly without any copy.
Also, cost_matrix can use small dtype like float32 to half reduce memory, so 3.35GB memory is enough.
Notice: when nr > nc, scipy.optimize.linear_sum_assignment will copy then transpose and rearrange cost matrix so keeps memory access locality,
but this module do not do this, so it is about 2x slower in this situation.
For nr <= nc, this module has almost no performance drop,
so you can manually construct a transposed cost matrix for this module,
and manually swap row_ind and col_ind result if nr > nc to get better performance.
The subrows and subcols arguments allow solver run on only a subgroup of row and cols on cost_matrix.
The result should be same as scipy.optimize.linear_sum_assignment(cost_matrix[np.ix_(subrows, subcols)]), but it avoids the expensive construct of sub cost_matrix.
## License
The code in this repository is licensed under the 3-clause BSD license, except
for files including a different license header.
The LSAP solver copied from [SciPy](https://github.com/scipy/scipy ) is also licensed under the 3-clause BSD
license.
Some files copied from [minilsap](https://github.com/ntamas/lsap ) are also licensed under the 3-clause BSD license.
Raw data
{
"_id": null,
"home_page": "",
"name": "nanolsap",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "lsap,munkres,kuhn-munkres,linear sum assignment problem",
"author": "",
"author_email": "hzqmwne <huangzhengqmwne@sina.cn>",
"download_url": "https://files.pythonhosted.org/packages/33/87/dfadc5c57a1eea9104398aa48275d765bfbb5b4482644d53979c241a97e7/nanolsap-0.1.3.tar.gz",
"platform": null,
"description": "# nanolsap\n\nA Python module to solve the linear sum assignment problem (LSAP) efficiently.\nExtracted from SciPy, and modified to minimal memory cost.\n\n## Description\n\n```\nfrom nanolsap import linear_sum_assignment\n```\n```\nSolve the linear sum assignment problem.\n\nParameters\n----------\ncost_matrix : array\n The cost matrix of the bipartite graph.\n It should be 2-D ArrayLike object, with nr rows and nc cols.\n\nmaximize : bool (default: False)\n Calculates a maximum weight matching if true.\n\nsubrows : array (default: None)\n Use sub rows from cost matrix if not None.\n\nsubcols : array (default: None)\n Use sub cols from cost matrix if not None.\n\nReturns\n-------\nrow_ind, col_ind : array\n An array of row indices and one of corresponding column indices giving\n the optimal assignment. The cost of the assignment can be computed\n as ``cost_matrix[row_ind, col_ind].sum()``. The row indices will be\n sorted if subrows and subcols are both None; in the case of a square cost\n matrix they will be equal to ``numpy.arange(cost_matrix.shape[0])``.\n```\n\nThis module is useful in cases when you need an efficient LSAP solver on \nvery large cost_matrix and limited memory. \n\nFor a cost_matrix with dtype float64 has shape of 30000\\*30000, it needs 30000\\*30000\\*8 / 1024\\*\\*3 = 6.7GB memory to store it. \nIn scipy.optimite.linear_sum_assignment, it will first convert it to float64 contiguous numpy 2-D array, then do a copy, and finally starts the solver. \nSo, the actual memory cost is at least 6.7\\*2 = 13.4GB. \nif the origin cost_matrix does not match, for example a float32 2-D array, \nthe first step here will cause one extra copy, increases the actual memory cost to 6.7/2+6.7\\*2 = 16.75GB. \n\nIn this module, When input cost_matrix is a contiguous numpy 2-D array, the solver can run on it directly without any copy. \nAlso, cost_matrix can use small dtype like float32 to half reduce memory, so 3.35GB memory is enough. \n\nNotice: when nr > nc, scipy.optimize.linear_sum_assignment will copy then transpose and rearrange cost matrix so keeps memory access locality,\nbut this module do not do this, so it is about 2x slower in this situation. \nFor nr <= nc, this module has almost no performance drop, \nso you can manually construct a transposed cost matrix for this module, \nand manually swap row_ind and col_ind result if nr > nc to get better performance. \n\nThe subrows and subcols arguments allow solver run on only a subgroup of row and cols on cost_matrix. \nThe result should be same as scipy.optimize.linear_sum_assignment(cost_matrix[np.ix_(subrows, subcols)]), but it avoids the expensive construct of sub cost_matrix.\n\n## License\n\nThe code in this repository is licensed under the 3-clause BSD license, except\nfor files including a different license header.\n\nThe LSAP solver copied from [SciPy](https://github.com/scipy/scipy ) is also licensed under the 3-clause BSD\nlicense.\n\nSome files copied from [minilsap](https://github.com/ntamas/lsap ) are also licensed under the 3-clause BSD license.\n",
"bugtrack_url": null,
"license": "BSD-3-Clause",
"summary": "Python module to solve the linear sum assignment problem (LSAP) low memory friendly",
"version": "0.1.3",
"project_urls": {
"Homepage": "https://github.com/hzqmwne/nanolsap"
},
"split_keywords": [
"lsap",
"munkres",
"kuhn-munkres",
"linear sum assignment problem"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "5a54b066890861c48dc953ca42ca4060426b93dae236e84b66c792336fe2c8ac",
"md5": "4681583a2238f038a1996584eae485fc",
"sha256": "b90f47d1bff7a3737ea28849aef858b46e8e96a3c8d7d5edf4f3d0f6d3c44fd4"
},
"downloads": -1,
"filename": "nanolsap-0.1.3-cp37-abi3-macosx_10_9_universal2.whl",
"has_sig": false,
"md5_digest": "4681583a2238f038a1996584eae485fc",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 55237,
"upload_time": "2023-08-09T17:13:40",
"upload_time_iso_8601": "2023-08-09T17:13:40.969024Z",
"url": "https://files.pythonhosted.org/packages/5a/54/b066890861c48dc953ca42ca4060426b93dae236e84b66c792336fe2c8ac/nanolsap-0.1.3-cp37-abi3-macosx_10_9_universal2.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "67b93322de85e769819bccbcf8884bc8f50aece933f86b832008460eb3dc0f57",
"md5": "1a96578a8234ab4bccada63261c431fe",
"sha256": "62d3f7f1b41a815caedeadf97e564507f1b611d2e53464e770f2d736c4471a8e"
},
"downloads": -1,
"filename": "nanolsap-0.1.3-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl",
"has_sig": false,
"md5_digest": "1a96578a8234ab4bccada63261c431fe",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 33263,
"upload_time": "2023-08-09T17:13:42",
"upload_time_iso_8601": "2023-08-09T17:13:42.548689Z",
"url": "https://files.pythonhosted.org/packages/67/b9/3322de85e769819bccbcf8884bc8f50aece933f86b832008460eb3dc0f57/nanolsap-0.1.3-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "fba5786d12fa1acc7cd9392166163fd901899f3b6005c62ef168b20b8ae77b61",
"md5": "ebe949ed1104678c354b3773df882527",
"sha256": "1f0ff2a51a6d29af1a922a44c191259e4d45ce82357c6dede91d6a852c2484fb"
},
"downloads": -1,
"filename": "nanolsap-0.1.3-cp37-abi3-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "ebe949ed1104678c354b3773df882527",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 35938,
"upload_time": "2023-08-09T17:13:43",
"upload_time_iso_8601": "2023-08-09T17:13:43.991974Z",
"url": "https://files.pythonhosted.org/packages/fb/a5/786d12fa1acc7cd9392166163fd901899f3b6005c62ef168b20b8ae77b61/nanolsap-0.1.3-cp37-abi3-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a83468ce25685549ce5892f1782019843987374d1fd7fc6bb2b0755e829da1a0",
"md5": "760f308c172502553fee9377113a63ad",
"sha256": "9d5d05a04ca9086783b5297dc5b09268cf2ffcb86c28f38ce24e3dfeccaba50f"
},
"downloads": -1,
"filename": "nanolsap-0.1.3-cp37-abi3-win32.whl",
"has_sig": false,
"md5_digest": "760f308c172502553fee9377113a63ad",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 21166,
"upload_time": "2023-08-09T17:13:45",
"upload_time_iso_8601": "2023-08-09T17:13:45.327862Z",
"url": "https://files.pythonhosted.org/packages/a8/34/68ce25685549ce5892f1782019843987374d1fd7fc6bb2b0755e829da1a0/nanolsap-0.1.3-cp37-abi3-win32.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "dc09bcefb12db9f7486c585b7cf64411a63d1d551387ae7510d0bce7b765d294",
"md5": "d9b5f0849f1388958f74300dee9b09c2",
"sha256": "346dd3ca520de7117848e9f7f1a510cb379c14071ef21873eed4b3f899db454a"
},
"downloads": -1,
"filename": "nanolsap-0.1.3-cp37-abi3-win_amd64.whl",
"has_sig": false,
"md5_digest": "d9b5f0849f1388958f74300dee9b09c2",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 24883,
"upload_time": "2023-08-09T17:13:46",
"upload_time_iso_8601": "2023-08-09T17:13:46.217219Z",
"url": "https://files.pythonhosted.org/packages/dc/09/bcefb12db9f7486c585b7cf64411a63d1d551387ae7510d0bce7b765d294/nanolsap-0.1.3-cp37-abi3-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "3387dfadc5c57a1eea9104398aa48275d765bfbb5b4482644d53979c241a97e7",
"md5": "f12df0017966e1c482dc5e4e7566784d",
"sha256": "2374963138d1985d86ded94229251a6d5d6fb5771de7e91208c4a2b8a445ee11"
},
"downloads": -1,
"filename": "nanolsap-0.1.3.tar.gz",
"has_sig": false,
"md5_digest": "f12df0017966e1c482dc5e4e7566784d",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 15914,
"upload_time": "2023-08-09T17:13:47",
"upload_time_iso_8601": "2023-08-09T17:13:47.663464Z",
"url": "https://files.pythonhosted.org/packages/33/87/dfadc5c57a1eea9104398aa48275d765bfbb5b4482644d53979c241a97e7/nanolsap-0.1.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-08-09 17:13:47",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "hzqmwne",
"github_project": "nanolsap",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "nanolsap"
}
JSON
